FAQ - Modern Algebra I
Dr. Monks
This isn't really a FAQ, but rather is just an AQ... it is just a compilation
of questions I have answered about modern algebra by email. I have not
edited these email messages much and they are usually replies to questions
asked by students, so keep that in mind when reading through them. Each
message is separated from the next by it's subject line. They are in roughly
chronological order. I hope they help.
--------------------------------------------------------------------
Messages from the Fall 1997 course
--------------------------------------------------------------------
--------------------------------------------------------------------
Subject: another example
--------------------------------------------------------------------
Here is another example of using Gentzen's Natural deduction for you
current homework.
Let's prove the Contrapositive Law:
Thm: (P=>Q)<=>(~Q=>~P)
Pf.
1. Assume P=>Q
2. Assume ~Q
3. Assume P
4. Q =>- ; 1,3
5. Q&~Q &+ ; 4,2
6. ~P ~+ ; 3,5
7. ~Q=>~P =>+ ; 2,6
8. (P=>Q)=>(~Q=>~P) =>+ ; 1,8
9. Assume ~Q=>~P
10. Assume P
11. Assume ~Q
12. ~P =>- ; 9,11
13. P&~P &+ ; 10,12
14. Q ~- ; 11,13
15. P=>Q =>+ ; 10,14
16. (~Q=>~P)=>(P=>Q) =>+ ; 9,15
17. (P=>Q)<=>(~Q=>~P) <=>+; 8,16
QED
--Great Gentzen Guru
---------------------------------------------------------------------
Subject: example you posted (fwd)
---------------------------------------------------------------------
Carole informs me that the "new" example I sent you is the same one I
sent you before! Aye yi yi! I am an idiot. OK, here is a new one. (I
hope).
Thm: (P&Q=>R)<=>(P=>(Q=>R))
Pf:
1. Assume P&Q=>R
2. Assume P
3. Assume Q
4. P&Q &+ ; 2,3
5. R =>- ; 1,4
6. Q=>R =>+ ; 3,5
7. P=>(Q=>R) =>+ ; 2,6
8. (P&Q=>R)=>(P=>(Q=>R)) =>+ ; 1,7
9. Assume P=>(Q=>R)
10. Assume P&Q
11. P &- ; 10
12. Q=>R =>- ; 9,11
13. Q &- ; 10
14. R =>- ; 12,13
15. P&Q=>R =>+ ; 10,14
16. (P=>(Q=>R))=>(P&Q=>R) =>+ ; 9,15
17. P&Q=>R <=> P=>(Q=>R) <=>+; 8,16
QED
I don't think I gave you this one before?
--Absent Minded 1
---------------------------------------------------------------------
Subject: request
---------------------------------------------------------------------
Hi, it's the math DJ here. This request goes out to Carole who wanted to
see another example of a double quantifier proof.
Before we get to that however, I want to mention that unlike the other
rules, the rules involving quantifiers must have the "input" statements in
the order shown in the rule. For example, in the @+ rule you must FIRST
have the Let x and THEN the P(x) in that same order. If the Let x came
after the P(x) then the x wouldn't be a new variable (in general).
Similarly, in #- rule the Let t must come after the #x,P(x) in your proof
because you need to guarantee that t is not one of the free variables in
P(x). So that is just something I forgot to mention.
Now on with our show...
Thm: (#x,#y,P(x,y))=>#y,#x,P(x,y)
Pf:
1. Assume #x,#y,P(x,y)
2. Let t be a constant such that
3 #y,P(t,y) #- ; 1
4. Let s be a constant such that
5. P(t,s) #- ; 3
6. #x,P(x,s) #+ ; 5
7. #y,#x,P(x,y) #+ ; 6
8. (#x,#y,P(x,y))=>#y,#x,P(x,y) =>+; 1,7
QED
So there you go...
--Dr. 100% Proof
--------------------------------------------------------------------
Subject: more goodies
--------------------------------------------------------------------
Fellow Math-o-nauts:
As we move into phase two of proving things... we need to make the transition
from these extremely formal proofs to the more common English language
mathematical proofs commonly found in text books, etc.
To help you make this transition, let us consider the same proof done two
ways, both formally and informally.
New Email Notation
------------------
U means the UNION operator on sets
c means the SUBSET symbol
in means "is an element of"
For example, "A U B" means the union of sets A and B
and "A c B" means A is a subset of B
and "x in A" means "x is an element of set A"
(Hey its the best I could come up with on the keyboard!)
In the formal proof below, if a reason is like "Subset axiom" or "Ordered
Pairs axiom " it refers to the axiom of that same name on your definition
handout that I gave you in class.
Thm: A c B <=> A U B = B
Formal Proof:
1. Assume A c B
2. A c B <=> @x, x in A => x in B Subset axiom
3. A c B => @x, x in A => x in B <=>- ; 2
4. @x, x in A => x in B =>- ; 3,1
5. Let x
6. Assume x in A U B
7. x in A U B <=> x in A or x in B Union axiom
8. x in A U B => x in A or x in B <=>- ; 7
9. x in A or x in B =>- ; 8,6
10. Assume x in A
11. x in A => x in B @- ; 4
12. x in B =>- ; 11,10
13. x in A => x in B =>+ ; 10,12
14. Assume x in B
15. x in B => x in B =>+ ; 14,14
16. x in B or- ; 9,13,15
17. x in A U B => x in B =>+ ; 6,16
18. @x, x in A U B => x in B @+ ; 5,17
19. A U B c B <=> @x, x in A U B => x in B Subset axiom
20. (@x, x in A U B => x in B) => A U B c B <=>- ; 19
21. A U B c B =>- ; 20,18
22. Assume x in B
23. x in A or x in B or+ ; 22
24. x in A U B <=> x in A or x in B Union axiom
25. x in A or x in B => x in A U B <=>- ; 24
26. x in A U B =>- ; 25,23
27. x in B => x in A U B =>+ ; 22,26
28. @x, x in B => x in A U B @+ ; 5,27
29. B c A U B <=> @x, x in B => x in A U B Subset axiom
30. (@x, x in B => x in A U B) => B c A U B <=>- ; 29
31. B c A U B =>- ; 30,28
32. A U B c B & B c A U B &+ ; 21,31
33. A U B = B <=> A U B c B & B c A U B Set Equality Axiom
34. A U B c B & B c A U B => A U B = B <=>- ; 33
35. A U B = B =>- ; 34,32
36. A c B => A U B = B =>+ ; 1,35
37. Assume A U B = B
38. Let x
39. Assume x in A
40. A U B = B <=> A U B c B & B c A U B Set Equality Axiom
41. A U B = B => A U B c B & B c A U B <=>- ; 40
42. A U B c B & B c A U B =>- ; 41,37
43. A U B c B &- ; 42
44. A U B c B <=> @x, x in A U B => x in B Subset axiom
45. A U B c B => @x, x in A U B => x in B <=>- ; 44
46. @x, x in A U B => x in B =>- ; 45,43
47. x in A U B => x in B @- ; 46
48. x in A or x in B or+ ; 39
49. x in A U B <=> x in A or x in B Union axiom
50. x in A or x in B => x in A U B <=>- ; 49
51. x in A U B =>- ; 50,48
52. x in B =>- ; 47,51
53. x in A => x in B =>+ ; 39,52
54. @x, x in A => x in B @+ ; 38,53
55. A c B <=> @x, x in A => x in B Subset axiom
56. (@x, x in A => x in B) => A c B <=>- ; 55
57. A c B =>- ; 56,54
58. A U B = B => A c B =>+ ; 37,57
59. A c B <=> A U B = B <=>+ ; 36,58
QED!
So there it is in only 59 short steps. Now let's do the same proof in a
normal English language proof.
Thm: A is a subset of B if and only if A U B = B.
Proof: (=>) Assume A c B. Let x in A U B. Then either x in A or x in B by def
of union. Case 1: If x in A then x in B anyway because A c B. Case 2: x in B.
So in both cases, x in B. Since x was arbitrary, every x in A U B is also in
B. Thus by definition of subset, A U B c B.
Now let x in B. Then x in A or x in B, so x in A U B by definition of
union. Since x was arbitrary, every x in B is also in A U B. So B c A U B by
definition of subset.
Hence A U B = B by definition of set equality. So A c B implies A U B = B.
(<=) Now assume A U B = B and let x in A. Then x in A or x in B, so
x in A U B by def of union. Since x in A U B, x must also be in B because
A U B = B. Since x was arbitrary, every element of A is also in B. Thus A c B
by def of subset. So A U B = B => A c B.
Thus we have proved both implications, so A c B if and only if A U B = B.
QED
Now what I want you to do is compare these two proofs line by line, step by
step, and see what English statements in the second proof correspond to what
parts of the formal proof and vice verse. If you do that carefully you will
see how the formal proof is the rigid "skeleton" that is implicitly hiding
beneath every wordy English proof that you find in your textbooks.
Often, a beginning theorem-prover writes a proof that seems to him or her to
be imitating what they have seen in other proofs, but yet it gets marked
wrong. This is because they usually are do not yet see the underlying formal
logical structure that is supporting their argument. The formal proofs make
this structure explicit, but are far too lengthy and time consuming to be of
much practical use. So the art of proof writing is partly the art of learning
to communicate efficiently the logic of the formal proof that your don't want
to write out in detail.
Compare these two proofs. The first is extremely precise, and no single
step is difficult to follow, but the whole thing looks a bit strange and
unnatural. It is also very LONG even though this is a relatively simple
theorem. A typical theorem taken from your modern algebra book could easily
require a formal proof that is several hundred or even thousands of lines
long. The second proof is much shorter but quite wordy and descriptive. It
is also less precise in the sense that it is obvious that many steps are
being skipped over as just being intuitively obvious. But all of the proofs
we will do from now on will be in this format.
So there is a bit of an ART involved with writing these English language
proofs. You have to decide which steps are so bloody obvious that you can just
skip them, and what things are important and need to be said. On one extreme
this whole theorem might be said to be "bloody obvious" so that no proof is
required at all, and on the other extreme is the formal proof above which
doesn't skip any details at all.
So how do you decide what is obvious and what is not obvious. My suggestion is
this: I am a fairly tough grader, which means I am much more likely to mark
you wrong for something you think is obvious but which I don't think is
obvious. Thus, when in doubt... don't skip the extra step. Be detailed,
explain everything. Make me yell at you for being TOO detailed and
careful.
--Math-o-naut Leader
--------------------------------------------------------------------
Subject: indexed unions and intersections
--------------------------------------------------------------------
Carole asked about the homework problem on indexed unions and
intersections. She wanted to know what form the answer should take. The
rule of thumb is as it always is... the answer should take the simplest
form possible. For example, if you can write an indexed union as a
single interval or a simple set in set-builder notation, then that would
be simpler than an infinite union.
For a concrete example, consider the indexed union:
INT (-n^2,n^2]
n in P
(more email notation, INT means the upside down U symbol that we use for
intersection and ^ means exponentiation. P is as in the text.)
So this is the same as:
(-1,1] INT (-4,4] INT (-9,9] INT (-16,16] INT ... etc
So if we plot these on a number line it is easy to see that the real
numbers which are common to all these sets is just the interval
(-1,1], so that would be the answer.
On the other hand, if we changed this same problem to UNION,
U (-n^2,n^2]
n in P
we have
(-1,1] U (-4,4] U (-9,9] U (-16,16] U ... etc
which again if you plot on a number line you will easily see that
eventually every real number is in one of these intervals... so this union
is just R.
Note that this question in the homework does not ask you to prove that
your answer is correct, only that you state what the answer is.
So my advice is to plot the first five or six intervals that you are
trying to intersect or unionize on a number line and then it should be
clear what the answer is. Write the answer using the least number of
intervals you can.
--A Union Man
--------------------------------------------------------------------
Subject: N vs P
--------------------------------------------------------------------
I was e-asked what the difference between N and P is. For the record
N={0,1,2,3,4,...}={x: x is an integer and x is not negative}
=the set of nonnegative integers
whereas
P={1,2,3,4,...}={x:x is an integer and x is positive}
= the set of positive integers.
--your positively nonnegative instructor
--------------------------------------------------------------------
Subject: comments on the homework
--------------------------------------------------------------------
In order to assist you with Wed's homework so that you don't repeat the
same mistakes, let me tell you what the most common and egregious errors
on Moday's homework. Like a David Letterman top ten list...
Top Ten Bad Things Commonly Found in Monday's proofs
----------------------------------------------------
10. To choose an arbitrary element of BxC you must say: "Let (a,b) in BxC.
Then a in B and b in C by def of Cartesian product." or else you can say
"Let x in BxC. Then x=(a,b) for some a in B and some b in c." But you should
NOT say "Let a in B and let b in C. Then (a,b) in BxC." While this is not
totally wrong, it implies that you are quantifying over B and C individually
instead of over BxC. In order to justify this you would need to prove that
picking and arbitrary a in B and b in C is equivalent to picking an arbitrary
x in BxC (which it is) but if you don't justify it it just makes the logic
very obscure. So this is something you shouldn't do anymore, it's not
totally wrong, just bad.
9. To show f is injective you should assume f(x)=f(y) and then prove
x=y (for arbitrary x,y in the domain of f). It is ALWAYS true that x=y =>
f(x)=f(y) just by substitution, whether or not the function is injective.
So DON'T try to assume x=y and show f(x)=f(y). Also some people use the
contrapositive... ~(x=y) => ~(f(x)=f(y)). This is OK but usually is much
harder to prove, so do it the other way unless you like abusing yourself.
Thus anytime you want to show f:B->C is injective you should do your proof
like this:
HOW TO PROVE f:B->C IS INJECTIVE:
Let x in B, let y in B.
Assume f(x)=f(y).
:
:
Show x=y.
8. Surjective... YOU CANNOT SHOW SURJECTIVE BY PICKING AN ELEMENT IN THE
DOMAIN FIRST AND SEEING WHERE IT MAPS. This is a really common mistake.
To show a function f:B->C is surjective you must start by saying "Let x in
C"... notice... "Let x in C" NOT "Let x in B". You are trying to show
everything in the codomain is in the image of the function, so pick an
arbitrary element of the CODOMAIN and show there is an element of the
domain that maps to it.
HOW TO PROVE f:B->C IS SURJECTIVE:
Let x in C.
:
:
Show there exists y in B such that x=f(y).
7. Get the arguments right. If f:BxC->D and x in B and y in C then you
can talk about f(x,y) but you can't talk about f(x) and f(y). In general
you can't have f(something) if the something is not in the domain of f!
6. A set is not a statement. You can't say "Therefore Ax(B U C)." in a
proof because Ax(B U C) is not a statement... it is a set. It is like
trying to say "Therefore 12." This is not a statement. You need a verb
somewhere. On the other hand "Therefore A=B." is a statement because the
verb is =, see?
5. There is a difference between "or" and "union". If A and B are sets
then A U B is a set, but A or B is not a set. They are related to each
other in that "x in A U B iff a in A or x in B". "or" is a logical
operator, not a set operator. For the same reason you should not write "x
in A or B". While it makes sense in English it doesn't in math. Either
write "x in A U B" or else write "x in A or x in B".
4. Put parenthesis around ordered pairs. Don't write x,y instead of (x,y).
The only exception is in a function where we usually write f(x,y) as an
abbreviation for f((x,y)).
3. You MUST use parenthesis whenever you are mixing "and" and "or" in the
same statement. You can't say "x in B and y in C or y in D" because it
can have two different meanings. Either write
"x in B and (y in C or y in D)"
or else write
"(x in B and y in C) or y in D"
they are two completely different meanings. English is VERY bad in this
regard because we never distinguish between these cases in our normal
writing.
2. Don't use what you are trying to prove... if you are trying to prove f
is bijective don't say: "Since f is bijective, it must be injective, hence
if f(x)=f(y)... etc". You can't use what you are trying to show because
that is begging the question.
1. No answer... no credit!
--KM
--------------------------------------------------------------------
Subject: pregrading the homework
--------------------------------------------------------------------
Future Mathematicians:
I was asked if you could use the Euclidean algorithm (thm 1.6) to prove
gcd(n,n+1)=1 for every integer n. The short answer is YES. The long
answer is that you are always allowed to use any theorem that is given in
the book prior to a homework problem, EXCEPT for the cases where the
homework problem asks you to prove the theorem itself or some theorem
whose proof depends on what you are showing, of course. Just be
sure to state which theorem you are using when you write up your proof.
So in this example, using the Euclidean algorithm theorem is fine.
Now for some pre-grading. Even though this looks trivial it isn't. It
isn't hard either, but I can warn you about something that a lot of you
will miss. It says that you must prove it FOR ALL INTEGERS n. So you
can't just willy nilly apply the Euclidean algorithm for every value of n
all at once because you have various cases to worry about like, n>1, n=1,
n=0, n=-1, n<-1 etc. The hypotheses of the Euclidean algorithm IS NOT
satisfied for all of these various cases, so you have to figure out which
ones it applies to and which it doesn't and prove the result for each case
what ever way you have to. So be careful.
--Coach
--------------------------------------------------------------------
Subject: gcd(a,b)
--------------------------------------------------------------------
By the way, I would appreciate it if you write gcd(a,b) on your homework
instead of the book's notation (a,b). Otherwise I might get confused and
think you mean an ordered pair and then I will mark wrong a perfectly good
proof by accident.
--gcd(Dr. Monks,0)
--------------------------------------------------------------------
Subject: homework help
--------------------------------------------------------------------
Since I didn't cover as much as I would have liked in class, let me give
you another example of how to attack these gcd type problems. Let us
consider number 16, pg 13. It says
If gcd(a,b)=d, prove that gcd(a/d,b/d)=1.
This is strange wording but typical in mathematics. SO what they really
want us to prove is:
Thm: gcd(a,b)=d => gcd(a/d,b/d)=1.
Now it is much clearer from our study of natural deduction how this proof
ought to go... it is of the form P=>Q, so our RECIPE from natural
deduction tells us that the proof should be done like this:
Pf: Assume gcd(a,b)=d.
Show gcd(a/d,b/d)=1.
OK. Now we have two parts to consider. The first part is our
assumption that gcd(a,b)=d. Now what can we conclude from that? Well, by
definition of gcd we can conclude that:
d|a
d|b
(c|a and c|b) => c<=d.
[new email notation... <= means less than or equal to, >= means greater
than or equal to... neither to be confused with => which means implies or
<=> which is iff]
and from d|a we can conclude by definition of | that
a=ds for some integer s
we can conclude a similar thing from d|b. We can also substitute anything
we like for c if that will help us in the proof.
So armed with this information, we now want to turn our attention to the
task at hand, namely we need to show gcd(a/d,b/d)=1. But I gave you a
RECIPE for doing this in class, thus THOU SHALT follow it. So now the
proof should be like this:
Pf: Assume gcd(a,b)=d.
Show 1|(a/d)
Show 1|(b/d)
Let c be an integer.
Assume c|(a/d) and c|(b/d)
Show c<=1.
Notice that in this case we lucked out because it is fairly easy to show 1
divides something.
So now your task is to fill in lines where necessary and use whatever
information you have to show that c<=1. Now you can try to do this in many
different ways. For example, you can try proof by contradiction, or you
can try using corollary 1.4. There is no unique solution to proofs in
general. However, if you stick to your recipes it can take a lot of the
chaos out of the attempt.
Speaking of recipes. Here is another one you might find useful for the
course.
To show a|b
Show b=as for some integer s.
(or more formally, show #s,s in Z & b=as)
--The Divisor Advisor
--------------------------------------------------------------------
Subject: Re: another homework ?
--------------------------------------------------------------------
I was just asked this question about the homework:
> When I prove t|a, do I have to go thru the whole big long thing again to show
> t|b or can I say "by similar argument" or something? It seems redundant but so
> do a lot of the parts of these proofs so I don't know. THat's why I'm asking
> Dr. Proof.
My response...
In your current role as modern algebra student, should not ever say:
"by a similar argument" in your homework proofs until such time as I am
convinced that you all are so good at proofs that I am sure you know the
difference between what a "similar argument" is and what it is not.
Currently I am not that confident. I'll let you know when I am, then you
can start using it.
Now an honest-to-goodness trained mathematician, like the author of your
book, or your humble teacher, can say "by a similar argument" in certain
cases in a proof, but certainly not in all cases. In the example of
showing t|a and t|b in the recipe for gcd, sometimes you can prove it for
a and then say it is true for b by a similar argument and sometimes you
can't.
You can say it if the proof for showing t|b is exactly the same as the
proof that t|b except that you substitute b everywhere you said a in the
previous proof, and need to make only minor analogous changes to convert
one proof to the other. In other words if each proof requires exactly the
same logical recipe but you are just using different variable names, then
you can say "by a similar argument". But if there is even a small logical
difference between the two cases, then you can't say by a similar
argument.
In many cases in the GCD setting, the two cases will be quite different.
For example if you want to prove
Thm: For all positive integers n, gcd(n+1,n^2+2n+1)=n+1
Pf: n+1=(n+1)*1 (def of *)
So (n+1)|(n+1) (def of |)
n^2+2n+1=(n+1)(n+1) (distributive law)
So (n+1)|(n^2+2n+1) (def of |)
Let c>0 be an integer.
Assume c|(n+1) and c|(n^2+2n+1)
Then c|(n+1). (&-)
So n+1=gcd(n+1,n^2+2n+1) (Corollary 1.4)
QED.
Notice that this follows the gcd "recipe" exactly but there is no way you
could say that (n+1)|(n^2+2n+1) "by a similar argument" in line four,
because the argument isn't similar to showing (n+1)|(n+1) at all.
--Dr. 100% Proof
--------------------------------------------------------------------
Subject: now that's odd
--------------------------------------------------------------------
There seems to be a bit of a confusion about what you can and cannot say
about odd and even on the homework you just handed in. Many people just
used the fact that every odd integer can be written in the form 2n+1 for
some integer n. But you CAN'T use this fact unless you prove it and you
need the division algorithm to prove it! I know you have been using this
fact since ninth grade, but we are seeing WHY all this stuff is true. So
here is the way it should be done:
Def: An integer n is even iff 2|n.
Def: An integer n is odd iff n is not even.
Thm: n is odd <=> n=2q+1 for some integer q.
Pf: (=>)
Assume n is odd.
n is not even. (def of odd)
#q,#r, n=2q+r and 0<=r<2 (div alg)
r=0 or r=1 (since 0<=r<2)
Case 1: Assume r=0.
n=2q (substitution)
2|n (def of |)
n is even (def of even)
n is not odd. (def of odd)
-><-
n=2q+1 (anything follows from -><-)
Case 2: Assume r=1.
n=2q+1 (substitution)
n=2q+1. (or-)
(<=)
[uh ohh.. now I have a problem in email notation because <= can mean "less
than or equal to" and it can also indicate the if part of an iff proof. I
guess you will just have to figure it out by context.]
Assume n=2q+1.
Assume n is not odd.
n is even (def of odd)
2|n (def of even)
#p, n=2p (def of |)
2p=2q+1 (subs)
1=2p-2q=2(p-q) (algebra.. add = to = and distr. law)
2|1 (def of |)
But ~2|1 (arith)
-><-
n is odd
QED
[More new notation... often mathematicians use the symbol -><- to denote a
contradiction instead of writing Q&~Q. It is suppose to be two arrows
pointing at each other --> <-- like that, only close together. -><- is
the best I can do by email.]
Notice I did the above in a semi-formal way, hopefully this will help you
bridge the gap between the formal logic that your proofs must be based on
and the carefree English proofs we actually write. The proof above is
somewhere in between. I don't give line numbers in my reasons. I skip a
lot of obvious steps and so on. But this should give you an idea of what
sorts of things you can skip and what sorts of things you can't.
In any event, NOW that we have a proof that every odd integer is of the
form 2q+1, we can now feel free to use it in the future. So be my guest
from now on.
This brings up another good point though. If a problem says to prove:
THM 1: For all odd integers n, P(n).
where P(n) is some statement about n, then you should not begin your proof
like this:
"Let 2n+1 be an odd integer."
This is quite sloppy but even worse is saying...
"Let n be an integer, then 2n+1 is odd."
This is not the right way to choose an arbitrary odd integer. It is very
sloppy.
The right way to handle such a theorem is this way:
"Let n be an odd integer.
Then n=2q+1 for some q (by the theorem above)."
To see why this is the right way, consider the formalization of the
THM 1:
THM 1: @n,n is odd => P(n)
To prove this formally we see it is of the form "@n,something". So we pick
an arbitrary n.
"Let n be arbitrary."
next we look at the "something", namely "n is odd=>P(n)".
This is of the form A=>B so we use =>+ rule
"Assume n is odd
Show P(n)"
Thus the "recipe" for this proof should be
THM 1: @n,n is odd => P(n)
Pf: Let n be arbitrary.
Assume n is odd.
#q, n=2q+1 (by prev thm)
Show P(n)
See? So that is how you can "choose an arbitrary odd integer" or other
such thing in the future.
--Your Odd Instructor
--------------------------------------------------------------------
Subject: Re: Quick question concerning divisors
--------------------------------------------------------------------
Here is another question someone asked.
> dr. monks:
>
> If I have an integer, can i list its divisors as a given (without any
> further proof) or do i have show that its divisors are its divisors.
> Example:
>
> I have the number 2. Can I say "Since the divsors of 2 are -1,1,-2, and
> 2, blah, blah blah"
>
> This may seem trivial, but i was one of those who said: "2n+1
> represents all odds. Its obvious!"
>
> I'm not taking any chances
We are allowed to assume basic arithmetic skill in this chapter, so if I
really wanted to PROVE that the only divisors of 2 are -2,2,-1,1 I would
probably say:
2=-2(-1)
2=-1(-2) <-- all these are by basic arithmetic
2=2(1)
2=1(2)
so -2,-2,2,1 are divisors of 2. Let d be a divisor of 2. Then -2<=d<=2
by the remark on page 7. So the only other possibility is d=0. But 0 is
not a divisor of anything by definition of divisor. Thus, the only
divisors of 2 are 2,1,-2,-1.
However, we know that in doing normal math proofs we often skip over steps
that are obvious or trivial. I would say that in the case of listing the
divisors of a PARTICULAR number (not something like n) that the argument
above is trivial enough that you could skip most of it and just say that
the divisors of 2 are 2,-2,1,-1.
However, if you, as a blossoming mathematician, could not have come up
with the proof above by yourself, then it is hardly obvious at all to you,
so you shouldn't skip the proof of it because it is not obvious enough to
skip. See?
In any event, if what you are asking is whether or not I would take off
points if you just said that the divisors of 2 are 2,-2,1,-2 in your
proof, then I would have to say that I probably would not take off points
for this particular "obvious" statement". However, that is the number 2 is
a small finite number that anyone can check your claim just by simple hand
calculation.
The case of just skipping the proof that n is odd iff n=2q+1 is quite
different however, especially since in one of the problems you were asked
to prove that n is odd iff n=4q+1 or n=4q+3! This theorem is part of a
whole family of theorems:
Thm 1: n is odd iff n=2q+1
Thm 2: n is odd iff n=4q+1 or n=4q+3
Thm 3: n is odd iff n=6q+1 or n=6q+3 or n=6q+5
Thm 4: n is odd iff n=8q+1 or n=8q+3 or n=8q+5 or n=8q+7
etc
so it hardly makes sense to assume that Thm 1 is true and use it without
proof to prove Thm 2, does it? Especially since the proofs of all these
theorems are essentially the same. That is why I couldn't give credit for
such a thing. It is not a "trivial" fact in the context of the proof of
Thm 2.
As a side comment, I have to say that I am quite pleased with the
student's statement above to the effect that "even though this is
blatantly obvious to a 4 year old, I am not taking any chances anymore"!
This is great, because it is the first stage in the mental growth of the
wannabe mathematician... total absolute skepticism about ANY statement in
mathematics that you don't have a proof for! This is essential to the
mathematical way of thought.
You will skip many steps in your proofs, and so will I, and so will the
book. But the important thing is that you need to be sure that if you
REALLY HAD TO you could fill in all the missing steps. As long as the
reader and the writer of the proof agree that the missing steps could be
filled in, then the proof is ok. But if one of them is skeptical, then
the details should be shown.
--King of the Skeptics
--------------------------------------------------------------------
Subject: Re: question on lcm and on integers
--------------------------------------------------------------------
Here is another email question which I will answer for everyone so you can
all benefit if you have similar concerns.
> dr. m,
>
> a problem i had with last nights homework was proving that the quotient
> of two integers was an integer. this prevented me from successfully
> solving the lcm problem. (it just occurred to me now to try to fiddle
> with the division algorithm involving this case, or that the framework
> of the lcm problem made it possible in some way to show that the
> quotient is an integer.)
Rule of thumb number one... try to stay away from quotients at all cost
when dealing with integers. To use quotients you need to check, as you
found out, that the quotient is indeed an integer... but there is a simple
fact that shows that you never need to resort to quotients when doing
these proofs...
Thm: Let a,b be integers with ~(b=0). Then a/b is an integer iff b|a.
Pf: Let a,b be integers with ~(b=0).
(=>) Assume a/b is an integer. Then a/b=n for some integer n.
Multiplying both sides by b gives a=bn, so b|a.
(<=) Now assume b|a. Then a=bs for some integer s. Since ~b=0
we can divide both sides by b to obtain a/b=s. Thus a/b is an integer.
QED
So saying that a/b is an integer is equivalent to saying that b|a. So you
might as well just stay away from the whole quotient deal and work just
with | because then you never have to check if your expressions are
integers or not, because you only deal with products and sums and the
integers are closed under products and sums.
> Then I got thinking about the products and sums of integers. Can it be
> proven that if a and b are integers, then a+b and a*b are integers. It is
> extremely obvious that it is true, but then again we are trying not to
> assume things here. Is this just assumed with the rest of basic
> arithmetic? I tried to prove this in my class after mod alg. but i
> didn't get very far:
> Thm: @a,@b in Z => (a+b) in Z
> let a
> let b
> Assume a,b in Z
> Assume (a+b) ~in Z (was going for contradiction)
>
> Surely something so obvious should be provable.
It is good that you are questioning such things. As I said before, this
is a necessary component to mathematical thought.
Of course, you can prove such things, but not quite in the way you are
trying to do it above. The problem you are running into is caused by one
sloppy thing that we have to work with in chapter one of the book, that is
that they are assuming we know certain facts about Z, but are making us
prove other facts without telling us exactly which facts we CAN assume we
know. For example, on page 2 the author says:
"We assume that you are familiar with the arithmetic of the integers with
the usual order relation (<) on the set Z."
But this is very vague because it doesn't tell us exactly what we can
assume we know and what we cannot. Certainly he expects that you know how
to add and subtract and multiply any two integers, and even divide them
into the quotient and remainder you need for the Division Algorithm. He
also assumes that we know basic properties of absolute values as you can
see by looking at his proofs. But why not give us all the axioms that
these properties are based on?
Well the reason is this: Whether you believe it or not, this is a really
really simple modern algebra book. Most other books are MUCH harder than
this book (which is why I chose it). So instead of dumping you right into
the weird alien number systems on day one, it first works through some
examples, like the integers, that you should feel familiar with and
comfortable with. Then slowly he moves you into total abstraction land.
So he wants you to feel somewhat familiar with the surroundings and thus
that is why he starts by illustrating some main concepts in the context of
the integers. But to do it the "right" way, we should have built up the
integers from scratch without assuming ANYTHING, even arithmetic. But
this would take us too long to do and we would never get anything done in
the course. (In fact, we offer a course called number theory whose job is
to teach you exactly that.) So it is a trade off.
Now on to your question.
If we define Z to be the set of integers, then we can define
addition and multiplication as functions:
+:ZxZ->Z
*:ZxZ->Z
For example, +(3,2)=5, *(3,2)=6 etc. Usually we don't write them this way
because we use infix notation instead which says we should write 3+2
instead of +(3,2). But this is only a cosmetic change and the fact
remains that + and * are functions from ZxZ to Z. So when you ask if you
can prove that the sum of two integers is and integer or if the product of
two integers is an integer, then from this perspective the answer is
obviously a resounding YES. The sum and product of two integers is and
integer by definition of + and *, since they are functions whose codomain,
and hence range, is a set of integers.
Of course, this is not the whole story because we need to formally define
what we mean by the set Z and we have to formally define the functions +
and * for this set so they correspond to our elementary school arithmetic.
That would take quite a while and get us far off track. But suffice it to
say that it CAN be done and that we could have built the whole tower from
the ground up. In the meanwhile we will have to keep on guessing what we
are allowed to assume about the integers. Just keep checking with me when
you have a question. Regarding the sum and product of two integers being
an integer... you can go ahead and use that fact all you like.
--The Divisor Advisor
--------------------------------------------------------------------
Subject: example
--------------------------------------------------------------------
Here is an example similar to the ones you are currently working one since
there seems to be some question about how to attack these.
[Rule of thumb, use the recipe for showing R is an equivalence relation given
on your recipe sheet.]
Email notation: We have a bit of a problem because R usually means the set of
real numbers and I have been using it for an arbitrary relation in this
section because we use ~ for "not". So from now on I will use R for the real
numbers and E for a general relation. Of course, ^ means exponentiation, i.e.
x^2 is "x squared". * will mean multiplication when needed.
This is problem #12, pg 531.
#12. Is the following relation an equivalence relation on R: aEb iff #k in Z,
a=10^k*b ?
Answer: Yes.
Pf:
Assume @a,@b, aEb iff #k in Z, a=10^k*b.
Let x in R
Let k=0.
x=10^0*x by arith.
x=10^k*x for some integer k (by substitution)
xEx by def of E
So E is reflexive.
Let x,y in R
Assume xEy
x=10^k*y for some integer k
y=10^(-k)*x for some integer k by arith.
Let K=-k, then K is an integer because -k is (def of Z).
y=10^K*x for some integer K
yEx by def of E
So E is symmetric
Let x,y,z in R
Assume xEy and yEz
x=10^k*y and y=10^j*z for some integers k,j.
x=10^k*10^j*z by substitution
x=10^(k+j)*z by arith.
Let K=k+j, then K is an integer because k and j are (def of + on Z).
x=10^K*z for some integer K
xEz
So E is transitive.
Thus E is an equivalence relation.
QED
Now this is even a bit more detailed than you need to do, but I wanted to
be fairly detailed since this is an example. Most of the problems in
today's homework are of this general form so this might help.
--In an Equivalence Class by Himself
--------------------------------------------------------------------
Subject: Re: another one
--------------------------------------------------------------------
I was just asked this question.
> In #13 it says "In the set R[x] of all polynomials with real coefficients.
> Do I have to beware of something because this is an equivalence class or
> can I still do it "ala your recipe"?
The symbol R[x] does not consist of a R followed by an equivalence class
[x]. It is a single symbol in the same sense that f(x) is a single symbol
if f is a function. R[x] is a set. It is the set of all polynomials with
real coefficients whose variable is x. So x^2+5x+1 would be an element of
R[x] but x+3y would not because it is a polynomial with more than one
variable. sin(x) has only one variable, but it is not in R[x] because it
is not a polynomial. In the problem, when they use symbols like f(x),
they mean that f(x) is an polynomial with variable x having real
coefficients i.e.
f(x)=a0 + a1*x + a2*x^2 + a3*x^3 + ... + an*x^n
where ai is in R for all 0<=i<=n.
In terms of using the recipe, R[x] corresponds to the set X that the
relation is defined on in the recipe.
--KM
--------------------------------------------------------------------
Subject: Re: quick question on #5
--------------------------------------------------------------------
> i can start 5a off by saying:
>
> Assume @(x,y), @(u,v), (x,y)E(u,v) iff x=u
>
> right?
This is not quite right from a strictly formal standpoint because in
formal logic you can only quantify variables, not ordered pairs. But to
do that would be a pain in the butt:
Assume @x,@y,@u,@v, (x,y)E(u,v) iff x=u
or even
Assume @p,@q, pEq iff #x,#y,#v, p=(x,y) & q=(x,v)
would be formally better, but the meaning of what you are doing above is
clear, so I would not mark it wrong if you wrote it the way you said it
above.
KM
--------------------------------------------------------------------
Subject: Zen wisdom
--------------------------------------------------------------------
I just read this an thought it was relevant to our discussions about being
skeptical in mathematics when writing proofs, so I am passing it along to
you for your enjoyment. --KM
"Where there is great doubt, there will be great awakening;
small doubt, small awakening;
no doubt, no awakening."
-Zen saying
--------------------------------------------------------------------
Subject: Re: homework
--------------------------------------------------------------------
Another question from the audience...
> Just a quick question. One of the homework problems talks about odd
> primes. You mentioned before we couldn't just use 2n+1 for odds without
> proving it. So do we put a lemma in there somewhere to prove what an odd
> is before we start the proof and then refer to it?
I did prove in email that an integer n is odd iff n=2q+1 for some integer
q, so you can use this fact without proof from now on since we did prove
it. Regarding odd primes, we never stated this and I don't recall it
being in the book, but:
Thm: If p is a positive prime number other than 2, then p is odd.
Pf: Assume p be a positive prime number and ~(p=2).
Assume p is even.
p=2m for some integer m (def of even)
2|p (def of |)
2=p (the only positive divisors of p are 1,p)
-><- (since p=2 and ~(p=2))
p is not even (~-)
p is odd (def of odd).
QED
Notice I am skipping a lot of trivial steps in going from 2|p to 2=p.
Technically I should say that since p is prime, c|p => c in {+1,-2,p,-p}
Since 2|p, 2 in {1,-1,p,-p}. Since 2 is not equal to 1 or -1 and p>0 we
know 2=p by several applications of the or- rule. To write this proof out
formally would require about 50 lines. That is why we skip some steps.
The art is not to skip improtant steps that are essential to the proof or
ones that you couldn't prove if someone held a gun to your head.
In any event, we see that the only even positive prime is 2 and all the
rest are odd. I don't know that you need this fact for your homework, but
it is a very common fact.
KM
--------------------------------------------------------------------
Subject: Re: homework question
--------------------------------------------------------------------
Another question for group enjoyment:
> To prove or disprove something, if it's not true can I use or counterexample?
I assume you mean 'a' counterexample... not 'or' counterexample.
Roughly speaking, yes, you can use a counterexample to disprove something.
So I think the answer you are looking for is "yes".
However, if we look deeper into this whole thing we might wonder WHY we
can use a counterexample to disprove something when we are so rigid about
proving everything otherwise. Well in order to see why we CAN use a
counterexample to disprove something we should PROVE that doing so is
valid.
So first we need to ask what we mean by a COUNTEREXAMPLE and also what we
mean by DISPROVE.
Def: Let P be a statement. To DISPROVE P means to prove ~P.
So disproving just means proving its negation. What about a
counterexample.
Def: Let P(x) be any predicate involving the variable x. Then we can find
a COUNTEREXAMPLE for the statement @x,P(x) iff #y,~P(y).
[The variable y should not occur as a free variable in P(x)... it should
be a fresh variable]
Now, let's prove:
Thm: We can disprove @x,P(x) <=> we can find a counterexample.
Pf. This is trivial.
We can disprove @x,P(x) <=> we can prove ~@x,P(x) (def of DISPROVE)
<=> we can prove #x,~P(x) (by Demorgan's Law)
<=> we can prove #y,~P(y) (change of dummy variable)
<=> we can find a counterexample (def of CounterEx)
QED
So there is a proof that we can disprove things by counterexample.
--Counterexample to @x,Normal(x)
--------------------------------------------------------------------
Subject: The end of math as we know it
--------------------------------------------------------------------
Awesome!
I am grading the homework you gave me on Monday and I found that one of
you proved that any two integers are equal!! Holy Equality, Batman!
Here is the proof. I slightly modified it for readability. I will give
one extra homework bonus point to anyone who can tell me what is wrong
with this proof before I hand the homework back in class tomorrow. (I
know what is wrong, but it will be a good exercise for you guys to figure
out what is wrong.) You must tell me your answer by email, not in
person. Only one answer per person is allowed so you can't keep guessing
and guessing until you hit on it.
So here it is:
Thm: Any two integers are equal.
Pf.
1. Let a,b be integers.
2. Let p=1 (the definition form of Let)
3. (a-b)=1(a-b) (arith)
4. (a-b)=p(a-b) (substitution ; 2,3)
5. p|(a-b) (def of | ; 4)
6. (a-b)=pn for some integer n (def of | ; 5)
7. p=(a-b)/n (arith ; 6)
8. (a-b)/n | (a-b) (substitution ; 7,5)
9. (a-b) = (a-b)/n * t for some integer t (def of | ; 8)
10. n(a-b)=(a-b)t (arith ; 9)
11. na-nb=ta-tb (arith ; 10)
12. na-ta=nb-tb (arith ; 11)
13. a(n-t)=b(n-t) (arith ; 12)
14. a=b (arith ; 13)
QED
--All things being equal...
--------------------------------------------------------------------
Subject: Re: iff vs. =
--------------------------------------------------------------------
Another question:
> Dr. Monks,
>
> Is proving a = the same as proving an iff? More specifically, for #4,
> does showing a+b <=> b+a prove that a+b = b+a?
No. They are two completely different things. In the expression P<=>Q, P
and Q must be statements, but in the expression P=Q, P and Q can be
anything at all. In particular, since in problem #4 they are talking about
elements of Zn, you can't even say "a+b <=> b+a" because it doesn't make
any sense at all because "a+b" and "b+a" are elements of Zn, not
statements. It is like saying "Blue iff Pig". It's not even grammatically
a statement. So you want to show a+b=b+a in Zn the problem you are asking
about.
--Dr. NightOwl
--------------------------------------------------------------------
Subject: Re: Confused...
--------------------------------------------------------------------
And another:
> Dr. Monks,
>
> I am a little confused on what #10 is asking. Is it asking for all
> possible combinations of ax that equal 1? Or is it just asking what
> number a can be so that there exists an x so that ax=1? Or what a is
> there such that for all x, ax=1?
Of your three questions above, it is asking the second one.
--KM
--------------------------------------------------------------------
Subject: homework
--------------------------------------------------------------------
Comments on the homework I just graded from section 2.2.
#11 is not actually stated precisely. They never defined the word
"ordering" (as far as I can see by looking around the book). So that means
if we allow < to be ANY RELATION which satisfies i and ii then the thing it
is asking you to prove is false! Consider this, let < be the relation
"equals" then it certainly satisfies i and ii. What they really needed
was to tell you that
iii For all a in Zn, ~(a<a).
without assuming this condition you can't do the proof. I was, of course,
exceedingly liberal in grading this misstated problem for that reason.
Also, almost nobody got Problem 8c. Since it isn't that hard I think I
will provide it for you as an e-xample.
Thm: If p is prime, the only solutions of x^2+x=0 in Zp are 0 and p-1.
Ok... let's analyze the English... it says
Thm: p is prime and x^2+x=0 in Zp => x=0 or x=p-1.
Pf: Assume p is prime and x^2+x=0 in Zp.
x in Zp so x=[n] for some integer 0<=n<p (by Cor 2.5)
n^2+n=0 mod p (by Thm 2.3)
p | n^2+n - 0 (def of = mod p)
p | n(n+1) (arith)
p|n or p|n+1 (Thm 1.8)
Case 1:
Assume p|n
Assume n~=0
p<=n (remark on page 7)
p<=n and n<p (&+)
p<p (transitive of <)
-><- (antireflexivity of <)
n=0 (~-)
Case 2:
Assume p|n+1
n+1~=0 (because 0<=n (skipping a ~- here))
p<=n+1 (remark on page 7)
p-1<=n and n<p (&+)
n=p-1 (arith)
Thus in either case n=0 or n=p-1.
So x=[0] or x=[p-1].
QED
Now that is a bit formal (even though I still skipped some steps), so
let's make it a little sloppier and do the English version.
Thm: If p is prime, the only solutions of x^2+x=0 in Zp are 0 and p-1.
Pf: Assume p is prime and x is a solution of x^2+x=0 in Zp. Then x=[n]
for some 0<=n<p by Cor 2.5. Then p|n^2+n and so p|n(n+1). But p is
prime, so p|n or p|n+1 by Thm 1.8. Case 1: If p|n and n~=0 then p<=n and
n<p so p<p which is a contradiction. So n=0. Case 2: if p|n+1 then since
0<=n, n+1~=0 and so p<=n+1. So p-1<=n<p. Thus n=p-1. So in either case n=0
or n=p-1. Hence x=[0] or x=[p-1].
QED
Notice that I am taking pains to distinguish between the number n and the
class x, but often we will blur the distinction. There is a way to
eliminate all this mess of worrying about the difference between a class
and a number, but I will save it for another day.
--Dr. E-xample
--------------------------------------------------------------------
Subject: Re: #6
--------------------------------------------------------------------
One more from the Modern Algebra Hotline:
> I have a question about #6, Is it asking us to prove Corollary 2.10 or can
> we use that in the proof?
You can use Corollary 2.10 in your proof.
--Late Night with Dr. Monks
--------------------------------------------------------------------
Subject: Re: homework
--------------------------------------------------------------------
Hmm, another one about the same problem:
> dr. m:
>
> looking over homework and realized i may have made a faux pas. Can i use
> thm 2.11 in the book for a homework problem before i solve question #8?
Here is the "Rule of Allowability"... you are allowed to use a theorem on
a given homework problem if:
a. the theorem appears in the book before the homework problem does.
b. the homework problem does not ask you to prove the theorem itself, or
any other theorem on which the proof of the theorem in question depends.
So in this case you can't use Theorem 2.11 in the solution to problem 8
because the proof of Theorem 2.11 refers to problems 8-10 for the proof.
However, you CAN use Theorem 2.11 in problem #6 because it's use does not
defy the Rule of Allowability.
> I'm thinking not because technically the theorem isn't proven until #8 is
> done, even though its listed in the book as a proved thm. Also. it makes
> problem #6 too easy :)
Yah, I guess I should assign harder problems in the future... I keep
getting all these complaints about problems being too easy. :)
On the other hand, if you feel mathematically "unclean" by using a theorem
you really haven't proven (nor will prove unless you do problems 9 and 10
also) then feel free to prove #6 from first principles using only stone
knives and bearskins. I'll be so proud!
--David LetterMonk
--------------------------------------------------------------------
Subject: READ THIS!
--------------------------------------------------------------------
On to other matters, my proof that a field is automatically an integral
domain that I did to answer Dinis' question is correct and in fact it is
theorem 3.9 in the book.
The proof I gave depended on this lemma:
Lemma: Let (R,+,*) be a ring and let a in R. Then a*0=0 and 0*a=0.
This is Thm 3.5.1 and you can see the proof in the book. So we are cool
with this. Remember that we are in Oz now, so that all these "trivial"
facts like 0*a=0 are no longer obvious by any means. You have to prove
everything like this to see if it works in every ring or only in rings
with identity or only in integral domains, or only in commutative rings,
or whatever.
Next topic. I didn't have time to show you an example a ring which is not
a field which contains a field as a subring. Here is a good example.
First, be sure to read all the examples in the book. There is not enough
time in class for me to cover them all, but they are all used many times
in the homework problems.
One important way to construct new rings from old ones is to make a ring
out of the Cartesian product as done in Thm 3.1.
In particular if R and T are rings then we can define addition and
multiplication on RxT by (r,t)+(a,b)=(r+a,t+b) and (r,t)*(a,b)=(r*a,t*b).
Thm 3.1 says that this definition turns RxT into a ring.
Now for the example. Consider the ring Z2 x Z2. This ring has four
elements in it, namely (0,0),(1,0),(0,1),(1,1). The zero element is (0,0)
and the identity is (1,1). Now this ring is not a field because (1,0) is
not zero, but it doesn't have a multiplicative inverse... i.e. there is
nothing I can multiply (1,0) by to get (1,1) in this ring. So Z2 x Z2 is
not a field. BUT if we consider the subset { (0,0),(1,1) } we can see
that this contains the zero element, (0,0), every element has an additive
inverse, and it is closed under multiplication and addition, so by theorem
3.2 it is a subring of Z2xZ2. But notice that this two element ring is a
field because it is easy to check that it is a commutative ring and the
multiplicative inverse for (1,1) is itself. So that is an example
(probably the smallest example) of a ring which contains a field but is
not itself a field. Thus it does not follow that just because the real
numbers are a field, that the complex numbers have to be.
In fact, consider this. Suppose instead of the usual multiplication of
complex numbers, instead we define a new multiplication, namely
(a+bi)(c+di)=ac+bdi
I claim that we can easily prove the C with this strange multiplication is
indeed a ring and that it contains R with the usual multiplication as a
subring. In this case, R is still a field, but C is no longer a field!
For example, i no longer has a multiplicative inverse because (a+bi)i=bi
which is not equal to 1 no matter what values of a and b we choose. So
there is a way to put R inside of C and have R be a field but C not be a
field.
[Notice that with the above wierd multiplication on C, i^2=i instead of
i^2=-1, which sort of eliminates the reason we made C in the first place,
which is another reason that it isn't defined this way.]
Happy proving.
--The Proof Meister
--------------------------------------------------------------------
Subject: Re: homework recipes
--------------------------------------------------------------------
More from the homework hotline:
> I was just looking over the recipes you mailed us. I have a question. When
> we want to show something is a commutative ring (or identity or division),
> you said we first have to show that (R,+,*) is a ring. So do we have to go
> back and prove all ten things for the ring proof and then in addition,
> prove the other property that we need for it to be commutative, etc.?
Yes.
Now it sounds really bad, but in a lot of cases it isn't. In many cases
you might already be given in the problem that it is a ring, or you might
know that it is a ring from previous theorems, or you might get 8 or 9 of
the properties for free because you already know they are satisfied from
previous work, and only have to verify two or three of the ten properties.
What things do we already know are rings? Well we know Z,Q,R,C with the
normal multiplication and division are rings. We know Zn with its usual
addition and multiplication is a ring because of Theorem 2.7. We know
that all the things given in the examples in section 3.1 are rings (e.g.
rings of matrices, rings of continuous functions etc) as long as they
show it is a ring in the example or tell us it is.
But the bottom line is yes, in some legal manner you must prove that the
thing is a ring before you can show it is a commutative ring or whatever.
Example: Here is Problem #20 on page 52.
Thm: Define a new addition and multiplication on Z by
a(+)b=a+b-1 and a(x)b=ab-(a+b)+2
Prove that (Z,(+),(x)) is an integral domain.
[Comments: I can't type those funky symbols that are in the book in email
so (+) means the plus sign in the circle and (x) means the multiplication
symbol in the circle. Since these are different addition and
multiplication than the usual ones we don't know that (Z,(+),(x)) is a
ring! All we know is that (Z,+,*) is a ring. So in this case we must
prove EVERYTHING.]
Pf: Assume (+) and (x) are defined as in the theorem.
(+):ZxZ->Z because it is defined for any integers a,b and if a,b are
integers then so is a+b-1.
(x):ZxZ->Z because it is defined for any integers a,b and if a,b are
integers then so is ab-(a+b)+2.
Let a,b,c in Z.
(a(+)b)(+)c=(a+b-1)(+)c
=(a+b+-1+c-1)
=(a+b+c-1-1)
=a(+)(b+c-1)
=a(+)(b(+)c)
So (+) is associative.
(a(+)b)=a+b-1
=b+a-1
=b(+)a
So (+) is commutative.
a(+)1=a+1-1=a and 1(+)a=1+a-1=a
So there exists 0R, namely 1, such that a(+)1=1(+)a=a.
[Comment from the Doc: Notice that the zero element in this ring, which we
usually call 0R (the zero with the subscript R) is the integer 1, not the
integer 0. So 0R=1 in this ring. In all the recipes any mention of the
symbol 0 or 1 ALWAYS refers to 0R and 1R, not the actual numbers 0 or 1.]
a(+)(2-a) = a+2-a-1 = 1
So every element has an additive inverse.
(a(x)b)(x)c=(ab-(a+b)+2)(x)c
=(ab-(a+b)+2)c-(ab-(a+b)+2+c)+2
=abc-ac-bc+2c-ab+a+b-2-c+2
=a(bc-(b+c)+2)-(a+bc-(b+c)+2)+2
=a(x)(b(x)c)
So (x) is associative.
a(x)(b(+)c)=a(x)(b+c-1)
=a(b+c-1)-(a+b+c-1)+2
=ab+ac-a-a-b-c+1+2
=ab-(a+b)+2+ac-(a+c)+2-1
=(ab-(a+b)+2)(+)(ac-(a+c)+2)
=(a(x)b)(+)(a(x)c)
So one of the distributive laws holds.
[Note: I can save work here by showing the ring is commutative before
trying to show the second distributive law. Watch...]
a(x)b=ab-(a+b)+2
=ba-(b+a)+2
=b(x)a
So (x) is commutative
[Now the other distributive law is free:]
(b(+)c)(x)a=a(x)(b(+)c) (by commutativity of (x))
=(a(x)b)(+)(a(x)c) (the other dist law proven above)
=(b(x)a)(+)(c(x)a) (by commutativity of (x))
[So in general you can ignore the second distributive law if you can show
the multiplication is commutative]
So everything above shows that this is a commutative ring.
Now we find the multiplicative identity.
a(x)2=a*2-(a+2)+2=a
2(x)a=2a-(2+a)+2=a
So taking 1R=2 we see that 2 is the multiplicative identity.
[Again don't confuse the NUMBER 1 in this ring with the
multiplicative identity of the ring which is 2.]
So we have a commutative ring with identity and 1R=2~=1=0R.
Finally,
Assume a(x)b=0R.
a(x)b=ab-(a+b)+2
0R=1
So ab-(a+b)+2=1 by substitution
ab-(a+b)+1=0
ab-a-b+1=0
a(b-1)-(b-1)=0
(a-1)(b-1)=0
a-1=0 or b-1=0 because the original ring, (Z,+,*) is an integral domain
a=1 or b=1
a=0R or b=0R
So (Z,(+),(x)) is an integral domain.
QED
Oh, one more email notational problem. Sometimes we use R for a ring and
sometimes for the real numbers. I will leave it to context to tell which
is which until we get forced to use both in the same discussion or proof.
> And
> what about a subring. Are we sure that (R,+,*) is a ring in the first
> place and then prove that S is a subset or do you have to prove that the
> ring exists first?
Good point. I modified the recipe and attached it below. Nobody will ever
ask you if something is a subring of (R,+,*) if (R,*,+) is not already
known to be a ring, it is always given. It is like asking if A is a subset
of B. If B isn't a set, there isn't much point in asking. So what I did
is change the recipe to say:
To show (S,+.*) is a subring of a ring (R,+.*)
since this will always be given to you. On the other hand, if it isn't,
then I guess you would have to show it.
--Math Doc
--------------------------------------------------------------------
Subject: divides
--------------------------------------------------------------------
Quick comments on the use of the | symbol. There were two common abuses
of this poor symbol on the homework.
1. a|b is a statement not a number. It is either true or false, not some
numerical value. Thus you cannot say 3|6=2 ! You can say, 3|6 because
this is a TRUE statement. But 3|6 does not mean 6/3.
2. We ONLY defined a|b when a,b are INTEGERS. We did not define it for
any other ring. Especially Zn. We never defined it in Zn. If we DID want
to define it the same way in Zn we would have to do it like this:
Def: Let a,b in Zn. a|b iff am=b in Zn for some m in Zn.
But notice that this is going to be QUITE weird compared to what you are
used to in Z. For example, 2|3 is false in Z but [2]|[3] would be true in
Z5 because [2][4]=[3] in Zn.
3. Just because [a][x]=[b] in Zn, it does NOT imply that a|b in Z. See #2
above.
So let us be careful in the future only to use | in Z.
Also you should be very clear in your proofs whether you are assuming that
a in Zn means a=[m] for some integer m or if you are using the
abbreviation which is to say a in Zn means a is an integer and 0<=a<n. If
you want to use the abbreviation then you have to make this very clear and
use that restriction all the time.
--He Who Giveth the +0's and +1's
--------------------------------------------------------------------
Subject: STOP!!!
--------------------------------------------------------------------
A lot of you on today's homework (the one I am grading) are repeatedly
assuming what it is you are trying to prove. Here is a trivial example to
illustrate the point:
Thm: Let R be a ring. For any n in R, (n+n)n=n(n+n).
Pf (WRONG):
Let R be a ring.
Let n in R.
(n+n)n = n(n+n)
n^2+n^2 = n^2+n^2
0 = 0
QED
Now this is just plain WRONG. You CAN'T assume what you want to prove on
line 3 and then deduce a tautology from that and claim you have a proof!
There is no rule of inference in logic that says:
Assume- Rule:
Assume P
0=0
----------
P
This is nonsense. Watch:
Thm: 0=1 in Z.
Pf (Using the same technique):
0=1
0=0 (reflexive, or substitution, take your pick)
QED
There! I proved 0=0 by assuming 0=1 so 0=1 must be true, right? Gimme a
break!
Do it like this:
Thm: Let R be a ring. For any n in R, (n+n)n=n(n+n).
Pf: Let R be a ring and n in R.
(n+n)n=n^2+n^2 (distributive law)
=n(n+n) (distributive law)
QED
So in your proofs like the one where you define a*b=0 for all a,b, in Z
and you want to show associativity of *, you don't do it like this:
(a*b)*c=a*(b*c)
0*c=a*0
0=0
This is assuming what you want to show! The same is true for the other
dozen things you have to check to show that something is a ring.
So don't do this anymore!
Cease and Desist!
Arrrrrghhhhh!!!
:-)
--Dr. Mean-o
--------------------------------------------------------------------
Subject: Re: Question...
--------------------------------------------------------------------
From the in bin:
> Dr. Monks,
>
> In one of the problems, it mentions a ring M(R). I am not sure what
> this is. I think that it is from either the first or second
> problem... Thanks...
M(R) is the ring of 2x2 matrices with entries in R where R is any ring. So
for example if R is the real numbers (as in problem #2) then M(R) is the
set of all 2x2 matrices with real number entries. The addition is matrix
addition and the multiplication is matrix multiplication just like you did
in linear algebra course. This is explained fully on page 44-45.
--Ghost of Linear Algebra Past
--------------------------------------------------------------------
Subject: Re: help
--------------------------------------------------------------------
Another cry from the abyss of Modern:
> Dear Prof Monks,
> I was wondering if maybe you could give some more examples of
> proving subrings.
> I am also becoming quite confused trying to sort out all
> of the many different notations the book is using in asking a question.
> For example, #8a: When R=M(R), find at least one element of M(R) that
> is not in C and at least three elements that are in C where C= (blah
> blah blah) etc.
> It's possible that I am just not seeing something very obvious.
> I tend to need to see numbers or even blue/red or heart/triangle to make
> sense of everything. Could you just give me some hints as to how to
> read these problems in my mind so they seem clearer.
> About #8, is the element the matrix or the entries in the
> matrix? I don't see it.
> Thanks.
What you describe is the natural reaction we all have when we encounter
something unfamiliar. This happens several times in our mathematical
lives (actually it never stops happening).
Adding seems hard compared to counting, that is why little kids use their
fingers to add, because it is easier to count than add.
Then the other arithmetic operations like subtraction and multiplication
and division come along and suddenly we are longing for the comfort of
good old addition.
Then negative numbers come along and suddenly those operations on plain
old positive integers are not looking so bad anymore.
Then fractions... god forbid.
And then we hit Algebra I and we realize that all that arithmetic stuff
with actual numbers was actually really nice and easy... what is this x
business?
Then on to precalc and now we have sin and cos and ln and e and suddenly
8x^2=4 doesn't seem all that bad anymore.
Then on to calc and now that 8sin(x^2) is some kind of function to be
integrated and differentiated.
Then onwards to linear algebra and now we have whole big matrices of
numbers and variables to deal with, and structures called vector spaces
and systems for linear equations in several variables and subspaces and
all of a sudden those differentiation questions are looking pretty good.
And then we go on to Modern Algebra where all of a sudden we are making
abstract number systems and linear algebra and number theory and calculus
are all providing us with examples of these abstract object which
generalize the concept of a number system.
Where are the nice numbers and the nice triangles and hearts!
And I am here to tell you that the abstraction ladder doesn't stop here
either. This is just the first level baby weenie sissy undergraduate
kindergarten teething course in Modern algebra. I can't begin to tell you
what the second course is like and what the graduate course is like after
that.. or how you can then take algebraic topology which uses modern
algebra the same way that you use algebra I in calculus... like a simple
everyday tool. Then there are higher more abstract forms of algebraic
topology which generalize the "simple concrete" examples of the first year
graduate course in algebraic topology to abstract theories... homotopy
theory... stable homotopy theory... category theory... This last one is
the theory of mathematical theories. Talk about abstract!
The point is that every time we move from one level of mathematics to the
next it seems abstract and weird, but after you study it for a while it
becomes natural and like an old friend. Also each time we struggle to
learn a new topic it gives us new insights and new enjoyment... new
mathematical beauty unfolds before us. I don't think any of us would be
doing mathematics right now if there was nothing to learn beyond addition
of whole numbers. It would be a dead art.
OK. So there is my pep talk.. now on to #8. In this problem they are
telling us that R is a ring and they are defining a set called C by
C={a in R : ra=ar for every r in R}
So let's break this down. It says that C is a set of a in R... what does
that mean? It means that every element of C is in R. So the mental
picture you should get is that C is a subset of R. Maybe the whole thing,
maybe the empty set, but definitely a subset.
OK now we read a bit further... which things are in C?
Well an element of the ring R gets to be in C if it commutes with every
element of R... i.e. a is in C iff ra=ar for all r in R.
Now at this point I say to myself:
"Hmmm, let's see... what element of an arbitrary ring would commute with
every element under multiplication? Hmmm... wait a second... if the ring
is commutative, then EVERY element a will satisfy ra=ar for any r in R!
That is the definition of commutativity of *! So if R is commutative then
C=R and of course in that case C is a subring because every ring is
trivially a subring of itself.
So the interesting case must be in non-commutative rings. Hmm, so suppose
R is not commutative? Is there anything I know that will be in C? Oh,
yes... I know one thing for sure that will be in C.... 0R will be because
r*0=0=0*r for any r in R. But since the ring is non-commutative, there
must be elements x,y such that xy~=yx. So neither x nor y could be in C in
that case. So what I proved in my head so far is that C is equal to R iff
R is commutative, and that 0 is always in C whether or not R is
commutative. Cool. Ok, now it is time to read some more..."
So now having digested that much I would read the next part...
Let R=M(Reals)...
"Ahah,", I think at this point, "I know why they are picking M(Reals) as
an example... because that is a noncommutative ring and I know this
problem is trivial for commutative rings..."
...find at least one element of M(Reals)...
"What is an element of M(Reals)... oh, yah I remember... it is just a 2x2
matrix with real numbers for entries like it says on page 44-45."
...which is NOT in C and at least three elements which ARE in C.
"Oh, ok.. So this is asking us to find a 2x2 matrix which does not commute
with EVERY 2x2 matrix (where the matrices have real entries). Now I have
a better idea... I will find a 2x2 matrix that doesn't commute with one
particular matrix... because if it doesn't commute with one matrix it
certainly doesn't commute with them all (that almost sounds illogical,
doesn't it? Boy English stinks.)."
So then I would proceed to try the simplest matrices I could think of
because I am very lazy... matrices like
|1 0| |1 1|
|0 0|,|0 0|,
You know... things with numbers in them like 0 and 1 that I still know how
to do arithmetic with... not hard numbers like 6 or -3. :-)
Now the second part says to find three matrices that commute with EVERY
matrix... well let's see... now it is not so simple because I can't just
find two matrices that don't commute, I need to find a matrix that when
I multiply it by a generic matrix:
|a b|
|c d|
first on the left and then on the right, I always get the same answer.
Well certainly the zero matrix has to work because it is the OR in the
ring of matrices and we showed above that 0 always is in C. So now it is
just a matter of fussing around and trying to find some other matrices
that commute with everything... hmmm what other FAMOUS matrices are
there... they must be famous for a reason? Maybe they will work out...
So that is how I would read and dissect this problem.
In part b of #8, to show C is a subring of R, all you have to do is follow
the recipe for proving something is a subring, namely show that if two
elements of a ring (note they are no longer matrices, now they are just
any old elements in any old ring) commute with everything, then their sum
and product does too. Then show that the zero element commutes with
everything (already did it above)... finally show that if an element
commutes with everything then so does the negative of the element. This
is all very easy to do so you should all get two +1's on this problem.
G'night..
--Dr. Sleepy
--------------------------------------------------------------------
Subject: Re: homework ? (fwd)
--------------------------------------------------------------------
From the Thursday night in bin:
> Question 10 asks to find which are homomorphisms. f:Z->Z ,f(x)=-x and/or
> f:Z2->Z2, f(x)=-x. If we know that Z is a ring, even if it's not stated as
> such, we can't just use the definition to figure this out, can we? Don't
> we have to check that it meets Thm. 3.12's requirements too?
Thm 3.12 says IF f is a homo THEN it satisfies all those properties. So
by contrapositive if any of the properties are NOT satisfied then clearly
f is NOT a homomorphism. However, the theorem is not IFF. Thus you can't
show that f IS a homo by checking that those properties hold.
So to check that f IS a homo just follow the time-honored recipe...
To show f:R->S is a ring homomorphism
1. Let a,b in R
2. Show f(a+b)=f(a)+f(b)
3. Show f(ab)=f(a)f(b)
I guess I should add this to the recipe sheet. Better go do that now...
KM
--------------------------------------------------------------------
Subject: homework policy
--------------------------------------------------------------------
Elite Modern Students:
I am grading the homework and I would like to announce the following
policy... you should prove all of your answers to homework problems,
whether or not the problem specifically asks you to prove or justify your
answer. So if a problem says,
1. Let f be ...blah blah blah... . Is f a homomorphism?
You shouldn't just answer YES or NO, even though I will be the first to
admit that logically speaking that is all that it is asking for in the
question. Hence, I can't in good conscience mark it wrong if you did that
up until now, because after all, you are answering the question. But from
now on I am declaring that all questions in the book have an implied
"Prove your answer." appended to them, whether or not it says so
directly.
Even in the "find an example" kind of problem, you should not just give
the example, but show that it is an example of what you are trying to find
an example of.
For example, if the problem says:
1. Find a zero divisor in M(Z2).
Don't just say:
|1 0|
|1 0|
and leave it at that.
Instead say:
|1 0| |0 0| |0 0|
| |*| |=| |=0R where R=M(Z2)
|1 0| |1 1| |0 0|
|1 0|
and |1 0| ~= 0R
|1 0|
so |1 0| is a zero divisor.
Okay?
--The Caffinated Dr. Monks
--------------------------------------------------------------------
Subject: Re: clarifying O
--------------------------------------------------------------------
From the inbox:
> (what a weird subject header...)
>
> anyway, question #1: the only way that O can be in R[x] is if
> a0 + a1x + ... + anx^n = 0 for some a0, a1,... right?
Yes, for example, a0=a1=a2=...=an=0R.
0R is always in R[x] because R is a ring, so it has a 0R element and this
element is a polynomial. In fact, 0R[x]=0R... see?
We are using your familiar understanding of what a polynomial is in this
section. If you want a really accurate technical description you can read
Appendix G. But as a rule of thumb, you will find that the only
difference between polynomials in R[x] and polynomials that you studied in
high school is that the coefficients can now be in an arbitrary ring
instead of just the ring of real numbers. Thus, since 0 was a polynomial
in high school, it still is a polynomial now, except that the 0 is now 0R
in whatever ring we have.
> question 2: if i have a set of polynoms whose degree must be less than k
> (pos int), can 0 be in this set? (i know 0 doesn't have a degree)
No. 0R is not in the set of polynomials of degree less than k in R[x]
because it has no degree.
--0Monks
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
From the "Ask Dr. Monks" advice column:
> Could you give me an example of the type of problem in #10? The more I
> play with this, the more confused I get so I'm sure I'm missing something.
> I can't find any examples to help me.
I assume you are asking about 10b and not 10a since 10b is the one I
assigned.
Let us consider a similar problem. Is x^2+x-2 irreducible in Z5[x]?
Let p(x)=x^2+x-2. Well if it is not irreducible then it is the product of
two polynomials with lower degree by Thm 4.10. But deg(x^2+x-2)=2, so if
it is irreducible then x^2+x-2=g(x)h(x) for some polynomials g(x),h(x)
having degree less than 2. But by Thm 4.2,
2=deg(x^2+x-2)=deg(g(x)h(x))=deg(g(x))+deg(h(x)), so
deg(g(x))=deg(h(x))=1. Thus g(x) and h(x)are linear polynomials in Z5[x].
Thus g(x)=ax+b and h(x)=cx+d for some a,b,c,d in Z5 with a~=0 and c~=0.
But notice that I can find MONIC linear polynomials whose product is p(x)
because:
x^2+x-2=g(x)h(x)=(ax+b)(cx+d)=acx^2+(ad+bc)x+bd
equating coefficients we see that ac=1. Since a,c are nonzero and Z5
is a field, both a and c are units. Thus a^(-1) and c^(-1) exist. Thus
p(x)=(ax+b)(cx+d)=ac(x+a^(-1)b)(x+c^(-1)d)
=1(x+a^(-1)b)(x+c^(-1)d)
=(x+a^(-1)b)(x+c^(-1)d)
Let G(x)=(x+A) and H(x)=(x+B) where A=a^(-1)b and B=c^(-1)d we see that
G(x) and H(x) are monic and linear and that p(x)=G(x)H(x).
OK, so we have shown that p(x) is irreducible in this problem iff p(x) is
not the product of any two monic linear polynomials in Z5[x]. SO now it
is a simple matter of computing all the products of such polynomials and
seeing if p(x) is on the list.
So what are the monic linear polynomials in Z5[x]? Well they are
x
x+1
x+2
x+3
x+4
So I compute:
x*x =x^2
x(x+1) =x^2+x
x(x+2) =x^2+2x
x(x+3) =x^2+3x
x(x+4) =x^2+4x
(x+1)(x+1)=x^2+2x+1
(x+1)(x+2)=x^2+3x+2
(x+1)(x+3)=x^2+4x+3
(x+1)(x+4)=x^2+4
(x+2)(x+2)=x^2+4x+4
(x+2)(x+3)=x^2+1
(x+2)(x+4)=x^2+x+3
(x+3)(x+3)=x^2+x+4
(x+3)(x+4)=x^2+2x+2
So the polys on the RHS above are the reducible degree two monic polys in
Z5[x]. Now p(x) is not written in terms of the equivalence class
representatives 0,1,2,3,4 as coefficients because of the -2.
But -2=3 mod 5 so that p(x)=x^2+x+3 in Z5[x]. Looking at the list above we
can see that p(x)=(x+2)(x+4) in Z5[x] so it is not irreducible in Z5[x].
QED
[Note: If it had not appeared anywhere on the RHS of the above list we
would know it is irreducible.]
Another way to go about it would be to write the product table
for Z5:
* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
and the addition table:
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
Then, noting that x^2+x-2=x^2+(A+B)x+(AB)
We must have (in Z5)
i. A+B=1
ii. AB=-2 (=3)
Now the pairs (A,B) that satisfy i. can be seen to be
(0,1),(1,0),(2,4),(4,2), and (3,3) while the pairs that satisfy ii. can be
seen to be (3,1),(1,3),(4,2),and (2,4) in the tables above. SO what do
they have in common? Well (4,2) and (2,4) of course. So
x^2+x-2=(x+2)(x+4) in Z5[x], so it is reducible.
--Dr. QED
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
From the homework hotline...
> For what value of k is x+1 a factor of x^4+2x^3-3x^2+kx+1 in Z5[x]?
> Can you have more than one answer for this? Like any value of k that would
> give you a solution to the equation that would be either zero or a
> multiple of 5 that would be 0 mod 5? In which case, there would be a lot.
> I hope you understand what I'm asking. This looks convoluted to me.
If you are considering k to be an integer, then if there are ANY values of
k that work then there must be infinitely many values of k that work
because we can add any multiple of 5 to k without changing anything since
we are working mod 5. However, if we are considering k to be an
equivalence class mod 5 (which is really what it MUST be by definition of
Z5[x]) then there are only 5 possible values of k corresponding to the
five elements of Z5.
I hope you understand my convoluted answer to your convoluted question.
--Dr. Convolution
--------------------------------------------------------------------
Subject: Re: another ?
--------------------------------------------------------------------
Homework hotline #137:
> In #16, I want to make sure I understand the question
> because of the notation in the book. When it says "prove f(x)=g(x) in
> F[x]", do they mean the functions or the polynomials? I'm guessing
> polynomials because it talks about f(c)=g(c) which are the functions but
> I just want to make sure before I start to mess with this one.
In problem #16 they want you to show that f(x)=g(x) as polynomials, not as
functions. That is why it says show f(x)=g(x) in F[x]. F[x] contains
polynomials, not functions. In our email notation (using .f for the
function associated with f(x)) the problem would read:
16. Let f(x),g(x) in F[x] have degree <= n and let c0,c1,...,cn be
distinct elements of F. If .f(ci)=.g(ci) for i=0,1,...,n, prove that
f(x)=g(x) in F[x].
So that is the right way to state that question.
--Dr. Hotline
--------------------------------------------------------------------
Subject: Re: #4, page 128
--------------------------------------------------------------------
From the In-Box:
> For problem #4, the question asks us to write out the multiplication
> and addition tables for F[x]/p(x) when F=Zmod5 and p(x)=x^2 +1
> I don't mean to complain, but that is
> 1 2 3 4 x x+1 x+2 x+3 x+4 2x 2x+1 2x+2 2x+3 2x+4 3x 3x+1 3x+2 3x+3 3x+4 4x
> 4x+1 4x+2 4x+3 4x+4 is is not?
No, you are missing 0.
> That involves 2* (24^2)=1152 calculations, half
> for addition and half for multiplication. (I also omitted the zero cases.)
Ah, I see... no 0 on purpose. OK.
I also agree with the number of calculations you state as long as we agree
that a "calculation" is defined to be one product or sum of two elements
of Z5[x]/(x^2+1) and we agree that mult and addition by 0 does not count
as a calculation.
Now, when you compute, say (2x+4)*(x+3) you have to actually do a lot of
little calculations like 2x*x and 4*x and 2x*3 and 4*3 and combine like
terms and reduce all the coefficients mod 5 and reduce the polynomial
modulo (x^2+1) when you are finished. This reduction either involves long
division of polynomials or it involves substituting -1 everywhere you see
an x^2 and simplifying mod 5 again... lots of tiny computations. So if
we call all of these things a "calculation" then it probably involves much
more than 1152 calculations, maybe five to ten times as many depending how
detailed you want to be when you count.
So you might do as many as 10,000 tiny calculations just to do this
one problem... isn't then human mind amazing...!
> I admit, actually, it involves 600 because multiplication and addition are
> commutative.
Ahhh, I see, so we are not counting a+b and b+a as being separate
calculations anymore... so we make an equivalence relation on the entries
in our tables so that a+b is equiv to b+a and ab is equiv to ba. Then we
define a calculation to be an equivalence class (and still ignore the
ones involving zero) to get a smaller number of computations.
Ohh, this is fun! We can reduce our workload by redefining the word
"calculation"! Cool!
OK, I have a few more reductions for you. How about if instead of writing
the coefficients as 0,1,2,3,4 we use -2,-1,0,1,2 as the equivalence class
representatives in Z5. Then we get a lot of "free" addition problems like
(3x+2)+(2x+3) because this becomes (-2x+2)+(2x-2) where it is obvious that
they are just additive inverses of each other. So that reduces our work
even further! Now we also know that Z5 is a field so that every nonzero
element has a multiplicative inverse. For example, 2=3^(-1) so that
2x*3=3^(-1)x*3=x shouldn't really count as a computation, now should it?
Hmm, wait, I have a really good idea... suppose we write ax+b as an
ordered pair (a,b) for short? Then we only need to compute the formula
for (a,b)*(c,d) in this ring and we have done all the products at once ...
similarly for addition. Addition is easy:
(a,b)+(c,d)=(a+c MOD 5, b+d MOD 5)
So there is the answer for ALL the additions, so none of them count as a
calculation anymore. For the products we have:
(a,b)*(c,d)=(ad+bc MOD 5, bd-ac MOD 5) (prove it!)
where in both cases MOD 5 is the modular *function* (not the relation)
that gives the remainder on division by 5.
Hmm, so those two formulas tell us the answer for all the products and
all the sums, so I think we really can't count anything as being a
calculation if we have the answer given to us, right? So we have
successfully reduced this problem to requiring NO calculations!
> If I am incorrect in the elements of F[x]/p(x) please inform me,
> and if the real number is more reasonable I will do the problem. If I am
> correct, then I hope you'll see one proof point isn't worth several hours'
> worth of calculations.
Well, seeing that this problem really doesn't require any calculations
anymore I guess it really IS too trivial of a problem to do now. So I
will agree with you and cancel this problem. No sense giving everyone a
free +1 point on their homework for something so easy.
Oh, but wait... what about the poor people who already did this problem
before I had a chance to cancel it? They will want to kill me! Well, ok,
let's do this. Everyone can EITHER do problem #4 in the homework or else
they can do problem #15 instead.
--Dr. Trivial
--------------------------------------------------------------------
Subject: Re: Dear Abby...
--------------------------------------------------------------------
The latest cry from the battlefield of mathematics in which our heros
continue their efforts to overcome the immense challenges placed before
them, thus guaranteeing their place in history...
> Dr. Monks,
>
> #3b states:
>
> Show that the set T = {(k,k) | k in Z} is not an ideal in Z x Z.
>
> I have looked at this over and over again and every time I look at it, it
> seems that T should be an ideal because if there is an integer n
> multiplied with (k,k), then it results in (nk,nk). And nk is an integer
> and commutative because of being in Z. Am I doing the multiplication
> wrong? I am lost on this problem. Please Help.
>
> Flustered
Well, here is where I get to make a pitch for the great recipes of Chef
Monks. Let's look at the recipe and see what could be wrong with your
argument:
To show I is an ideal in ring R
1. Show I is a subring of R
2. Let r in R
3. Let a in I
4. Show ra in I and ar in I
Now in your problem you have I=T and R=ZxZ. Thus if we substitute we get:
To show T is an ideal in ring ZxZ
1. Show T is a subring of ZxZ
2. Let r in ZxZ
3. Let a in T
4. Show ra in T and ar in T
So now let's see what could be going wrong. Well, maybe line 1 can't be
shown if T is not a subring of ZxZ. So that is one thing you have to
check. Then you also need to show line 4. In your argument above you
seem to be claiming that you did show line 4. But you did not because you
didn't follow the recipe. In line 2 you have to pick an arbitrary element
of ZxZ, but you picked n, which is an arbitrary element of Z, not ZxZ. In
fact, we don't even have a definition for how to multiply an element of Z
by and element of T (although the one you made up above is somewhat
natural?). So that is another problem you should resolve.
--Battlefield Commander
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
From the Sunday night in-box:
> Got a question for you. #6 says list all principal ideals in Z12.
> So if I understand this correctly, we are to list sets of numbers that are
> multiples of a number within Z12. For instance, {0,2,4,6,8,10} would be
> the principal ideal generated by 2. But, assuming what I just said is
> correct, would we have to list {0,4,8} as another principal ideal
> generated by 4 because this is just a subset of (2). If I'm figuring this
> out wrong, please correct me.
You are correct. (2)={0,2,4,6,8,10} while (4)={0,4,8}. But (4) is a
principal ideal not because it is a subset of (2) but because it is a
principal ideal of Z12. For example, {0,2} is also a subset of (2) but it
is not an ideal.
--Principal Monks
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
The thread continues:
> > > Got a question for you. #6 says list all principal ideals in Z12.
> > > So if I understand this correctly, we are to list sets of numbers that are
> > > multiples of a number within Z12. For instance, {0,2,4,6,8,10} would be
> > > the principal ideal generated by 2. But, assuming what I just said is
> > > correct, would we have to list {0,4,8} as another principal ideal
> > > generated by 4 because this is just a subset of (2). If I'm figuring this
> > > out wrong, please correct me.
> >
> > You are correct. (2)={0,2,4,6,8,10} while (4)={0,4,8}. But (4) is a
> > principal ideal not because it is a subset of (2) but because it is a
> > principal ideal of Z12. For example, {0,2} is also a subset of (2) but it
> > is not an ideal.
> >
> > --Principal Monks
> What about {0,7} or {0,11}? Would they be considered ideals because they
> are the only multiples of 7 and 11 respectively in Z12 or am I going
> overboard here?
They are not principal ideals because they are NOT the only multiples of 7
and 11 respectively in Z12. For example, 7*2=2 mod 12 and 7*3=9 mod 12
and 7*4=4 mod 12 and 7*5=11 mod 12 and 7*6=6 mod 12 and 7*7=1 mod 12 and
7*8=8 mod 12 and 7*9=3 mod 12 and 7*10=10 mod 12 and 7*11=5 mod 12 and
7*1=7 mod 12 and 7*0=0 mod 12. Therefore the principal ideal generated by
7 is the whole ring, i.e. (7)=Z12.
Remember that "multiple" means multiple in the ring Z12, not in Z.
--Idealistic Leader
--------------------------------------------------------------------
Subject: Re: another ?
--------------------------------------------------------------------
The saga continues:
> After we figure out all the principal ideals for 6a, then we're supposed
> to work up mult. and add. table for them. Just so I don't waste my time
> doing all this wrong, does that mean for (7) for instance we are putting
> 0+I, 1+I, 2+I,...11+I into a table and multiplying everything out?
In the case of Z12/(7) you only have one equivalence class because
(7)=Z12. So the multiplication and addition tables for a set containing
only one element is not very tough.
In a more interesting case, consider Z12/(2). In this case
(2)={0,2,4,6,8,10}. So there are two equivalence classes in Z12/(2),
namely 0+(2) and 1+(2) (boy this notation stinks, I would rather write it
[0] and [1] like we did before, but who am I to change mathematical
history, in any event remember that the + in 0+(2) is "not a plus"). Now
what are the addition and multiplication tables?
Well 0+(2) is the zero in the quotient ring, so it is clear what every sum
and product involving this class must be, namely 0+x=x=x+0 and 0*x=0=x*0
in ANY ring, so it it true in this ring in particular. SO the only thin we
have to check is 1+(2) + 1+(2) and 1+(2) * 1+(2). In the first case we
clearly have 1+(2) + 1+(2) = 2+(2) = 0+(2) in this ring and
1+(2)*1+(2)=1*1+(2)=1+(2). So the multiplication and addition tables for
this quotient ring show that it is isomorphic to Z2. So Z12/(2) is
isomorphic to Z2.
Now you just have to do this for the other principle ideals. Note that you
don't have to do it for 12 different principle ideals, because sometimes
(n)=(m) even though n~=m. For example, you might find that (2)=(10), so you
only have to compute the quotient ring for one of them.
KM
--------------------------------------------------------------------
Subject: Re: #10
--------------------------------------------------------------------
The first homework of the Double Jeopardy round draws a question:
> Dr. Monks,
>
> In number 10, when the book says that A(T) is all of the permutations
> of T, is it implied that they are bijective? Is being bijective a trait
> of all permutations?
page 161, line 10: "we define a permutation of a set T to be a bijective
function from T to T"
--Dr.QED
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
Yet another query:
> #16 gives a list of six functions from K to K and asks if this is a
> group under composition of functions. So does that mean that every
> composition, say f o g(x) has to be one of those six functions.
Yes.
> And that
> for every one of those functions, there has to be another in the set that
> the composition of the two functions will give you the first function and
> then the second one is the identity?
Yes, except that composition is not commutative in general so you can't
just check that for all functions s, sot=s and then declare t is the
identity as you are suggesting above. You must show that for all
functions s, sot=s AND tos=s. Then you can declare that t is an identity.
(here o denote the composition symbol, of course).
> If I work on one of the above and
> can't find a function to satisfy them, then it's not a group?
Well, I wouldn't put it this way. I would say this: If you can PROVE that
none of the six functions is an identity, or if you can PROVE that the
composition of two of the six functions is not one of the six, then you
will have proven that the set of six functions is not a group under
composition.
Now here is a tip: You can't say two functions are not equal just because
they don't LOOK equal. For example, the functions f:Z2->Z2 by f(x)=x^2
and g:Z2->Z2 by g(x)=x are equal, but they don't "look" the same.
Another example, the functions f:R->R and g:R->R by
{ x^2/x if x~=0
f(x)={
{ 0 if x=0
and
g(x)=x
are equal, and yet they don't look anything alike. So if you think that
the composition of two of the six functions is not equal to any of the
other ones, then you had better prove it. Just a warning.
--Group Leader
--------------------------------------------------------------------
Subject: Re: #16
--------------------------------------------------------------------
From the late night in bin:
> Dr. Monks,
> I was just wondering about #16. When we are showing that this is
> associative, do we have to case by case for all a,b,c in the group or is
> there a way to generalize using the operation table?
Composition of functions is ALWAYS associative as stated on page 509 at
the bottom (aren't you glad we covered the appendices in the beginning of
the course? :) ) Thus it is automatically associative no matter what
particular set of functions you are considering. So you get this for
free.
KM
--------------------------------------------------------------------
Subject: Re: group stuff
--------------------------------------------------------------------
A Sat night modern question:
> Why aren't the nonzero elements of Z6 a group under multiplication? What
> part fails the definition and please give me an example of Z-something
> that is a group under multiplication. This isn't a homework question but I
> was reading over the theorems and decided I didn't understand groups
> enough yet. Thanks in advance.
2*3=0 in Z6 so the set of nonzero elts is not closed under multiplication.
KM
--------------------------------------------------------------------
Subject: Re: group stuff
--------------------------------------------------------------------
The previous question, continued:
> And could you please give me an example of
> Z-something that is a group under multiplication?
Since 0 doesn't have an inverse, no Z-something is a group under
multiplication. But the non-zero elements in Zn are a group under
multiplication iff n is prime, since in that case Zn is a field and we
showed that the set of units in Zn is always a group under multiplication.
Every nonzero element of a filed is a unit, of course.
KM
--------------------------------------------------------------------
Subject: Re: help
--------------------------------------------------------------------
The email hotline continues:
> for my general knowledge does the order of the element a = 5 mean that
> a^5=e for e is the identity element.
It depends what you mean by "mean" in your question. If your "mean" means
"implies" then it is true, but if your "mean" means "iff" then it is
false.
The order of a is n iff n is the smallest positive number such that a^n=e.
In your case, the order of a is 5 iff a^5 = e AND (if a^k=e and k>0 then
k>=5).
So it is true that |a|=5 implies that a^5=e.
But it is not true that if a^5=e then |a|=5. For a counterexample, take
a=e. Then a^5=e but |a|=1, not 5.
For nonprime exponents there are worse counterexamples, for example,
suppose |a|=6. Then a^6=e. But if a^6=e that doesn't mean that |a|=6
because, for example, a might have order 3 and then a^6 would still be e
because it is (a^3)^2.
So it depends on what you mean by "mean".
--Your "Mean" Instructor
--------------------------------------------------------------------
Subject: Re: help
--------------------------------------------------------------------
The order question continues:
> Well I am still confused I get what you say there is a difference. Okay
> so take for example #34 on pg180. does |a|=5 imply a^5 = e.
Yes. |a|=5 always implies a^5 = e.
But in the last email you asked if |a|=5 MEANS a^5=e.
So I didn't know which logical operator you meant when you said MEANS.
If you meant IMPLIES then it is true. But it is not true to say |a|=5 IFF
a^5=e, because when a=e, the reverse implication is false. See?
> Next question: if you have |a*b*a| does |a*b*a^-1|=|a|*|b|*|a^-1| for *
> is multiplication or am I way off base?
|a| has NOTHING to do with absolute value, so NONE of the properties of
absolute value can be used in the group context. It is a shame that they
use the same symbol for two different things. Maybe we should say Ord(a)
for the order of a instead of |a|. So in that case what you are
essentially asking above is if
Ord(a*b)=Ord(a)*Ord(b) for all a,b, in a group. The answer is a big NO
WAY.
Consider any a and let b=a^(-1) for example. Then Ord(a*a^(-1))=Ord(e)=1
and yet we might have Ord(a)=Ord(a^(-1))=1307. If you want a particular
counterexample, consider a=2 and b=3 in Z7. Then Ord(2)=Ord(3)=7 but
Ord(2*3)=Ord(6)=7 so that Ord(2)*Ord(3)=49 while Ord(2*3)=7. So Ord does
not preserve products.
In problem 34 you do not want to work with properties of Ord (or ||). All
it is saying is this:
Given:
1. aaaaa=e
2. aba^(-1)=bb
for what n is the string bbbb...bb (with n b's) equal to e.
Now I love this kind of question because it is like a puzzle kind of
problem. When I work with these I don't like to work with the ^-1
exponents, so if I can eliminate them I do. In this problem I would
multiply the given #2 above by a on both sides and rewrite it as:
1. aaaaa=e
2. ab=bba
Then there are no messy ^-1's to deal with. So this is really a nice
question. It's actually a lot of fun.
KM
--------------------------------------------------------------------
Subject: Re: help
--------------------------------------------------------------------
One question begets another:
> > In problem 34 you do not want to work with properties of Ord (or ||). All
> > it is saying is this:
> >
> > Given:
> >
> > 1. aaaaa=e
> > 2. aba^(-1)=bb
> >
> > for what n is the string bbbb...bb (with n b's) equal to e.
> >
> > Now I love this kind of question because it is like a puzzle kind of
> > problem. When I work with these I don't like to work with the ^-1
> > exponents, so if I can eliminate them I do. In this problem I would
> > multiply the given #2 above by a on both sides and rewrite it as:
> >
> > 1. aaaaa=e
> > 2. ab=bba
> >
> > Then there are no messy ^-1's to deal with. So this is really a nice
> > question. It's actually a lot of fun.
> >
> > KM
>
> So in this problem, if you have "a=something" can you assume that the
> order of the something is the same as the order of a?
By definition of "=" if two things are equal then anything that is true
about one of them is true about the other. It's what EQUALS means. It is
probably the single most commonly used fact in all of mathematics. It
is the fact that you use every time you use "substitution" in a proof:
Thm: If a has order n and a=SomeThing then SomeThing has order n.
Pf:
1. Assume a has order n and a=SomeThing
2. a has order n &-;1
3. a=SomeThing &-;1
4. SomeThing has order n substitution;2,3
5. a has order n and a=SomeThing => SomeThing has order n =>+;1,4
QED
Notice we don't even need to know what order means or even that a is an
element of a group in order to do this proof. It follows directly from
logic and the definition of equals.
--Substitute Teacher
--------------------------------------------------------------------
Subject: Re: another stupid question
--------------------------------------------------------------------
Our happy math family has another discussion round the e-fireplace:
> Can you cancel like this:
> abc=cab cancel the c's
> ab=ab
The answer to what you are asking is technically yes, but the answer to
what you really WANT to be asking is a definite NO.
See, ab=ab is ALWAYS true for any a,b because = has this little known
property called the REFLEXIVE property which say that anything equals
itself. Now since P=>Q is true if Q is true, that means that I certainly
CAN conclude that ab=ab no matter what statement you want to give me as a
hypothesis, including abc=cab. Now if you want to think of that as
canceling the c's, well that is your business.
But what you really wanted to ask me (I know what you wanted to ask me
because I can read minds, did I ever tell you that?) was the following
question:
Q: If a,b,c are all elts of a group G and ac=cb, does that imply
that a=b?
The answer to this questions is NO. For example, in the dihedral group D4,
if r and m are as I showed you in class, then rm=mr^3 but you can't cancel
the m's because r is not equal to r^3 in D4.
> or do the factors that you cancel have to be in the same position in
> the statement, as in:
> abc=abc
> ab=ab
Yes! First of all it is true for the silly reason that ab=ab is always
true and thus can be concluded from anything. What you really meant to
ask is:
Q: If a,b,c are all elts of a group G and ac=bc, does that imply
that a=b?
The answer to this is also YES because it says so on Thm 7.5.2 on page
174. The proof is trivial. You just do this:
Assume ac=bc
c^-1 exists because G is a group.
acc^(-1)=abc^(-1)
ae=be
a=b
QED
(You fill in the reasons)
Now you might be wondering why I can multiply both sides by c^(-1) on the
right but not multiply one side on the right and the other on the left.
Well here is a proof that in any group I can multiply both sides of an
equation by an element on the right:
Lemma: If a,b,c in G and a=b then ac=bc.
Pf: Assume a=b
ac=ac (reflexive of =)
ac=bc (substitution)
QED
But if you try to imitate this proof to show a=b => ac=cb you will fail.
Try it!
So that old equals sign keeps popping up. But we all understand
everything about equals, right? :)
--Head Cancellor
--------------------------------------------------------------------
Subject: Re: HELP
--------------------------------------------------------------------
Cancellation laws continue to plague our heroic troop:
> Dr Monks,
> Is it ever possible to use the cancellation law to do something like:
> axb=bxa
> ab=ba
> Or is this just ridiculous?
I will have to go with the "just ridiculous" option.
In D4 (one of my favorite non-abelian groups), we have rrm=mrr (so this is
a=r,b=m,x=r in your example) but we don't have rm=mr in D4.
--The Doc formerly known as mr
--------------------------------------------------------------------
Subject: Typo in recent email
--------------------------------------------------------------------
From a recent email I sent:
> > Assume ac=bc
> > c^-1 exists because G is a group.
> > acc^(-1)=abc^(-1)
> > ae=be
> > a=b
> > QED
Nathan pointed out to me that I have a typo in the above... it should say
Assume ac=bc
c^-1 exists because G is a group.
acc^(-1)=bcc^(-1)
ae=be
a=b
QED
Sorry about that...
--Typo-negative
--------------------------------------------------------------------
Subject: Re: Since...
--------------------------------------------------------------------
Tonight's math-side chit chat:
> the homework has already been handed in, can you tell me the proof of #16?
> It is still baffling me.
Ask and ye shall receive...
#16. Let G={a1,...,an} be a finite Abelian group of order n. Let
x=a1*a2*...*an. Prove that x^2=e.
Proof: First the "gist" then the proof.
Gist: x^2=a1*a2*...*an*a1*a2*...*an
but for each ai there is a unique aj such that aj=ai^(-1).
Since the product is abelian I can rearrange the factors so that
every element is next to it's inverse. The all kill each other in a
big ball of flames and you get e. Voila!
Actual proof:
Let G={a1,...,an} be a finite Abelian group of order n.
Let x=a1*a2*...*an.
For notational convenience let bi=ai^(-1).
Let G'={b1,...,bn} (i.e. G' os the set of all inverses of
elts of G)
Let y in G
Then y=ai for some i.
ai^(-1) in G
y=(ai^(-1))^(-1)
y is the inverse of an elt of G
y in G'
G is a subset of G'
Let z in G'
Then z=bi for some i
z=ai^(-1)
z in G
G' is a subset of G.
G=G'
a1*a2*...*an=b1*b2*...*bn ; both are the product of the elts of G
; in some order order, but the group
; is abelian so the order doesn't
; matter*
x^2=a1*a2*...*an*b1*b2*...*bn
=a1*b1*a2*b2*...*an*bn
=e*e*...*e
=e
QED
* to prove this we should technically use induction, but this is good
enough at this point in the term since you have all earned the right to be
a bit more "loose" with your proofs.
--Deductomatic
--------------------------------------------------------------------
Subject: comments
--------------------------------------------------------------------
Fellow Modernists:
I am grading your homework and I see some common mistakes that I want to
correct now so you don't repeat them in the future.
1. When you multiply two permutations ab since the product is composition
you must apply b to the set before you apply a to the set. Thus
(1 2 3)(1 2 3) = (1 2 3)
(2 1 3)(3 1 2) (3 2 1)
not (1 2 3) like several of you did. You must work from right to left
(1 3 2)
when computing these products, not left to right.
2. To show that |a|=n it is NOT ENOUGH to show that a^n=e !!!!! You must
show that n is the SMALLEST positive integer such that a^n=e. For
example, if a^12=e that does NOT imply that |a|=12. For example, |a|
might be only 2, but we would still have that a^12=(a^2)^6=e^6=e.
Check my recipe sheet for the right way to prove |a|=n.
3. BTW, everyone missed the fact in 13b that p might be a NEGATIVE prime
in which case the order of b would be -p, not p.
--Back to grading I go...
--------------------------------------------------------------------
Subject: Abelian
--------------------------------------------------------------------
People are having a terrible time with showing a group is Abelian.
It is not true that if a group is not Abelian then no two elements of the
group commute! The identity commutes with every element whether or not
the group is Abelian, for example.
--Willing and Abel-ian
--------------------------------------------------------------------
Subject: Re: comments
--------------------------------------------------------------------
A question on my comment:
> On Tue, 11 Nov 1997, Ken Monks wrote:
> >
> > 3. BTW, everyone missed the fact in 13b that p might be a NEGATIVE prime
> > in which case the order of b would be -p, not p.
>
> How can you have a negative order of something?
You can't, but the problem does NOT say that b has order p, it says that
b^p=e.
For example, suppose p=-7. Then we are given that b~=e and b^(-7)=e. So
in this case we the order of b is 7 which is -p, not p. Those of you who
said the order of b is p were assuming that p is positive.
--Positive Influence
--------------------------------------------------------------------
Subject: examples
--------------------------------------------------------------------
Proof Warriors:
I am noticing some big weaknesses in your understanding of the material on
this homework. The group theory stuff is harder in general than the ring
theory material and it is new to you so I do expect some of this "growth
pains" in the beginning until you get used to the idea of a group. In the
meanwhile let me clear up a few things that everyone got wrong on the
homework.
Problem #7: Show that the set T of elements of finite order in an Abelian
group G is a subgroup of G.
Pf: To show it is a subgroup it suffices to follow the recipe:
To show T is a subgroup of G
1. Show T is a subset of G
2. Let a,b in T
3. Show a*b in T
4. Show a^(-1) in T
So let's follow it! The numbers indicate which part of the recipe I am using:
Let G be an Abelian group
Let T the subset of finite order elements in G.
1. T is a subset of G ; given
2. Let a,b in T
3. |a| and |b| are finite ; def of T
|a|=n and |b|=m for some pos integers n,m ; def of finite
a^n=e and b^m=e ; def of order
(ab)^(nm)=(a^(nm))(b^(nm)) ; G is abelian
=((a^n)^m)((b^m)^n)
=(e^m)(e^n)
=e
ab has finite order ; some positive power of it is e so
; there exists a least such power by
; the WOP
ab in T ; def of T
4. (a^(-1))^n=(a^n)^(-1)
=e^(-1)
=e
a^(-1) has finite order
a^(-1) is in T ; def of T
QED
Problem #20: Show that (3,1),(-2,-1),(4,3) generate ZxZ.
Pf: Let's follow the recipe:
To show a set S generates a group G
1. Let g in G
2. Show g is a product of elements of S.
In this case we are using additive notation because the group is abelian, so
the recipe becomes:
To show S={(3,1),(-2,-1),(4,3)} generates ZxZ
1. Let g in ZxZ
2. Show g is a sum of elements of S.
Here we go:
1. Let g in ZxZ.
2. g=(a,b) for some integers a,b ; def of ZxZ
Let w=(1,0)
x=(0,1)
Now w,-w,x, and -x are sums of elements of S because:
w=(3,1)+(-2,-1)
x=(-2,-1)+(-2,-1)+(4,3)=2(-2,-1)+(4,3)
-w=(3,1)+4(-2,-1)+(4,3)
-x=2(3,1)+3(-2,-1)
Now g=aw+bx.
But aw+bx is a sum of elements of S because w and x and -w and -x are.
So g is a sum of elements of S.
QED
There is a fine point above.... why did I have to show -w and -x were a sum of
elements of S? Why not just show w and x are?
--Recreation Director Monks
--------------------------------------------------------------------
Subject: Re: inner automorphisms...
--------------------------------------------------------------------
From the in bin:
> Dr. Monks,
>
> While trying to do problem 13, it mentions inner automorphisms. I
> studied over the definition on page 193, but was confused about what it
> exactly was. I thought that it meant that f(f(x)=x, but then I
> went back on that. What does it actually mean?
An inner automorphism is an isomorphism from G to itself (an
automorphism). There is one inner automorphism for each element of G *but
they are not all necessarily distinct). If a is an element of G then the
inner automorphism of G associated with a s the function
f:G->G by f(x)=a^(-1)xa
For example, the inner automorphism associated with e is the identity ma
from G to G. If G is Abelian, then f(x)=a^(-1)xa=a^(-1)ax=ex=x, so that
there is only one inner automorphism in that case, the identity map.
> Also, are we supposed to assume in 13a that it is an inner automorphism
> or just an automorphism.
It depends on what you mean by "it" in your question. If you are referring
to the f in the Hint, then yes, you are supposed to assume tha the inner
automorphism induced by a is an inner automorphism (which sounds pretty
obvious when you say it that way). Since f is the only function mentioned
in the question, I assume that is what you are referring to.
--Cousin "It"
--------------------------------------------------------------------
Subject: Re: homework?
--------------------------------------------------------------------
From the late night hotline:
> #9 says for each a in G, there exists b in G such that Na=bN. Prove that N
> is a normal subgroup. If I prove that an is in bN and bn is in Na, does
> that prove that it's normal?
No.
--KM
--------------------------------------------------------------------
Subject: Re: homework?
--------------------------------------------------------------------
> #9 says for each a in G, there exists b in G such that Na=bN. Prove that N
> is a normal subgroup. If I prove that an is in bN and bn is in Na, does
> that prove that it's normal?
OK. Maybe I should say a little more. :)
To show N is normal you can show one of two things... either
A. @a in G, aN=Na
or else
B. @a in G, @n in N, ana^(-1) in N (Thm 7.34.3)
If you chose to do it by A. then you should:
Let a in G
Let x in aN
Show x in Na
Let x in Na
Show x in aN
If you choose to do it by B you should:
Let a in G
Let n in N
Show ana^(-1) in N
--Recipiemeister
--------------------------------------------------------------------
Subject: #9
--------------------------------------------------------------------
On the homework you just handed in, nobody got #9 correct. I will not
grade it though because after working it out I realized that it is an
example of a situation in which you DON'T need to use the recipe for
showing a subgroup is normal, and in fact the recipe makes it harder. But
I kind of gave you the impression that you should use the recipe in a
previous email message, so I sort of led you astray in that regard. In
any event here is the proof:
#9. Let N be a subgroup of G. Suppose @a in G, #b in G, Na=bN. Prove N is
normal.
Pf:
Let N be a subgroup of G.
Assume @a,#b,Na=bN
Let a in G
e in N ; def of subgroup
ea in Na ; def of Na
a in Na ; ea=a
Na=bN for some b ; @- on assumption
a in bN ; substitution
bN and aN are either disjoint or equal ; they are equivalence classes!
ae in aN ; def of aN
a in aN ; ae=a
a in aN and a in bN ; &+
aN and bN are not disjoint ; a is in both of them
aN=bN ; if they ain't disjoint they be equal!
Na=aN ; substitution
@a,Na=aN ; @+
N is normal! ; def of normal
QED
So it is easy, but instead of using the recipe we just use the definition
of normal directly.
--Abby Normal
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
Saturday night with the algebraist's:
> I need help on something. What would the set Z8/N, where N={0,1,2} look
> like and what would the cosets be?
What it would "look like" is exactly the same as any other undefined
object, I guess. N is not a subgroup of Z8 because it is not closed
under addition, so Z8/N is not defined. What do the non-existant cosets
in the undefined set look like? I think they look like the the number
5/0.
--<undefined signature goes here>
ps. Since I can read minds AND predict the future I can tell you that your
next question will probably be something like:
> I need help on something. What would the set Z8/N, where N={0,4} look
> like and what would the cosets be?
Now that N is a honest goodness subgroup (and normal too since Z8 is
abelian!), the set Z8/N is defined and in fact is:
Z8/N={{0,4},{1,5},{2,6},{3,7}}
The cosets are the elements of Z8/N. In gory detail we have four cosets
that can be named several different ways each
N=N+0=N+4
N+1=N+5
N+2=N+6
N+3=N+7
Notice that here I am using the additive notation for the cosets because
the group operation on Z8 is +, not *. So instead of writing N3, I write
N+3. Also I am writing right cosets but I could just as easily have
written left cosets like 3+N, etc. What is the group structure on Z8/N?
Well the "product" table looks like:
+ N N+1 N+2 N+3
N N N+1 N+2 N+3
N+1 N+1 N+2 N+3 N
N+2 N+2 N+3 N N+1
N+3 N+3 N N+1 N+2
Since N+1 has order 4, this group is isomorphic to Z4. This can easily be
seen by just erasing all the N's in the table.
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
Pre-Turkey week question:
> I don't understand the concept of a group that is "finitely generated"
> as in #22.
A group G is finitely generated iff there is a finite subset S of G such
that every element of the group can be written as a product of elements of
S and their inverses.
[Note: we always allow for the possibility that a product has only one
factor.]
Ex: Any finite group is trivially finitely generated because we can take
S=G in that case.
Ex: Z is finitely generated by S={1} because every element of Z can be
written as a sum of 1's and -1's.
Let's look at problem #22. It is asking you to show G is finitely
generated. Let me check the recipe:
To show a set S generates a group G
1. Let g in G
2. Show g is a product of elements of S.
Yuk. OK, I admit. This is a poor tasting recipe. I must have been
having a bad chef day. Let's spice it up a bit:
To show a subset S generates a group G
1. Let g in G
2. Show g=b1*b2*...*bn for some b1,...,bn in S U S^(-1)
where S^(-1)={x in G : #s in S, x=s^(-1) }
That's better. In the finitely generated case we have an even more tasty
morsel:
To show a group G is finitely generated
1. Let g in G
2. Show #s1,s2,...,sk in G, g=b1*b2*...*bn
for some b1,...,bn in {s1,s2,...,sk,s1^(-1),...,sk^(-1)}
That ought to be enough to fix all your woes on problem #22.
--Twice Baked
--------------------------------------------------------------------
Subject: Re: #14, #15 (fwd)
--------------------------------------------------------------------
Another happy customer:
> Dr Monks,
> I have two questions, and I'm afraid they aren't particularly
> specific. For #14, it asks us to use the first isomorphism theorem to
> prove that MxN is a normal subgroup of GxH (given M is a normal subgroup
> of G, N is a normal subgroup of H). The first Isomorphism Theorem states
> (as I'm sure you know):
> Let f:G->H be a surjective homomorphism of groups with Kernel K.
> Then the quotient group G/K is isomorphic to H.
> I don't see the connection between what it asks for and the
> theorem at all. I know this question is basically asking you to give me
> the answer. Could you offer any hints for it, though?
> ... and in the process of trying to phrase my question for #15, I
> think I figured out the answer.
The reason you don't see the connection is because you don't need the
First Iso Thm to prove that MxN is normal sub of GxH, you only need to use
it to prove the second part of problem #14: that GxH/MxN is ISO to
G/MxH/N. To show MxN is normal in GxH you can use Thm 7.39 if you can
find a homomorphism from GxH to some other group such that MxN is the
kernal. In fact, if you could construct a homomorphism from GxH onto
G/MxH/N whose kernal is MxN then you would be done, right? Of course you
have to prove that the map you construct (there is only one obvious way to
make such a map) is a homo and that it is onto and that MxN is the kernal.
But once you do then Thm 7.39 and the 1st iso thm gives you the result
immediately.
--Group Leader
--------------------------------------------------------------------
Subject: Re: ;homework ?
--------------------------------------------------------------------
As the in bin empties for the term:
> This isn't one of the homework problems assigned, but I'm using it for an
> example.
> 2(b) Compute the product: (246)(147)(135)
> Is this right? (1234567)
> (3457621)
Yes. But it is more "customary" to write the product of an element which
is written in cycle notation in cycle notation rather than mixing cycle
notation and this matrix-like permutation notation. So you probably
should write the product this way:
(246)(147)(135)=(1356247)
> And if it asked to write this as a product of transpositions, I'm getting
> screwed up doing that, so could you do this one for me? It is not an
> assigned one.
Once you write it in cycle notation you can use the "transposition
formula" that always works that I used in the proof in class. So in this
case it would be just
(246)(147)(135)=(1356247)=(17)(14)(12)(16)(15)(13)
Since this is a product of six transpositions it is an even element and
hence a member of A7.
So there you go!
--Cyclic Sensei of Humor
--------------------------------------------------------------------
Subject: Re: ;homework ?
--------------------------------------------------------------------
The unending cycle continues:
> > (246)(147)(135)=(1356247)=(17)(14)(12)(16)(15)(13)
>
> So do you always work your way from right to left with just putting a 1
> with each number in the cycle notion?
This is one of those questions where you can easily figure out the example
by trying an example:
Ex: Write (1452) as a product of transpositions:
Solution #1:
(1452)=(12)(15)(14)
Does it work? 1->4, 4->1->5, 5->1->2, and 2->1 So this works.
Proposed Solution #2:
?
(1452)=(14)(15)(12)
It doesn't work because 1->2 on the RHS but 1->4 on the LHS.
Note: There are lot's (infinitely many) ways of writing a cycle as a
product of transpositions. For example:
(1452)=(25)(41)(24)
also works. So there are LOTS of different ways to write a cycle as a
product of transpositions. The only thing you know for certain is that
either every possible way or writing it will have an even number of
transpositions, or else every possible way will have an odd number of
transpositions.
--(SM)(MK)(NM)(OM)
--------------------------------------------------------------------
Subject: Re: homework ?
--------------------------------------------------------------------
Cycling along:
> I'm still stuck on something. How about this one. This is one of the
> examples but it's like something I ran into on one of the problems.
> (1234567)
> (5172463) = (1542)(37) What would the product of transpositions be for
> this one?
You can say "the" product of transpositions. You have to say "a" product
of transpositions because there are lots of ways to do it. In any event
in order to convert a product of cycles into a product of transpositions,
all you have to do it convert each one into transpositions and paste them
all together in the same order. So for example:
(1542)(37)=(12)(14)(15)(37)
--(KM)
--------------------------------------------------------------------
Subject: Re: ;homework ?
--------------------------------------------------------------------
Even the signature yields a question:
> >
> > (1452)=(25)(41)(24)
> >
> > also works
> > So there are LOTS of different ways to write a cycle as a
> > product of transpositions. The only thing you know for certain is that
> > either every possible way or writing it will have an even number of
> > transpositions, or else every possible way will have an odd number of
> > transpositions.
> >
> > --(SM)(MK)(NM)(OM)
> >
> I think I'm approaching this the wrong way. When I work backwards to see
> if what I wrote works, I'm assuming the transposition on the right will be
> the first two numbers, but that would mean that your name starts with ON.
> So all I have to do is check the cycle notation and just see if the
> sequence works and it doesn't matter where I start. Like in the above
> example, your alternative solution started with 2->4->1 instead of
> starting with the left side where 1->4. You're pretty good at reading my
> mind so if I didn't word this right, I'll trust you to figure out what I'm
> trying to say.
>
> --Running in cycles
Yes. You start from the right and "see if the sequence works" in the sense
I think you mean above. The point that is confusing you is that there the
way we write a cycle is not unique. For example:
(1452)=(4521)=(5214)=(2145)
These are all equal to the same permutation: (12345)
(41352)
Similarly, in my signature-via-transpositions above you could write it as
(ONKSM) or (NKSMO) or (KSMON) or (SMONK) or (MONKS)
because these are all equal to what is shown.
When I first showed you the cycle notation for permutations in class,
someone asked me why I didn't show that in the first place instead of
the messy (1234567) kind of notation. I said it was because the book does
(2317564)
that way and you needed to be able to understand the homework problems and
also because the messy notation is easier to understand, just messier to
write. I think the problems you are having with the cycle notation above
indicates that the author is correct, the cycle notation is shorter and
more convenient, but is definitely trickier to understand than the messy
table notation. Food for thought when some of you are teaching modern
algebra some day.
--Future Fellow Modern Teacher
--------------------------------------------------------------------
Subject: Read this before trying the Cube!
--------------------------------------------------------------------
I told you in class that the four happy moves are:
C
[C,sigma]
[C,B]
[CC,B]
In the article I gave you that is the notation they use, but they are
using the letter B to mean 90 deg clockwise rotation of the Bottom face,
whereas I defined B in class to be 90 deg clockwise rotation of the Back
face and I defined D to be the 90 deg clockwise rotation of the bottom
face.
Thus in terms of the notation I gave you in class, the correct four moves
should be:
C
[C,sigma]
[C,D]
[CC,D]
Sorry for the mixup. That would be mighty frustrating if you tried to
solve the cube with the wrong four moves.
In any event, bring your cubes with you again on Monday and we will do a
little bit more cubistry before launching into Maple (which probably means
we will never get to Maple because I always think that I am going to be
able to cover more material than I actually do with the cubes).
--Doesn't know his Back from his Bottom
--------------------------------------------------------------------
Subject: Re: cube stuff
--------------------------------------------------------------------
The cube brings a question:
> I'm doing something wrong with this damn cube. Tell me what sigma is
> again. The paper that you gave us refers to a clockwise rotation of the
> puzzle 1/3 of a turn about the diameter thru vertex a. What is "1/3" of a
> turn and do I keep one row stationary and turn the other 2 rows? Is that
> what you mean by turning the entire cube?
Sigma is not an element of R, but rather just a notational convenience to
allow us to write the four move in a simple way. If you want to translate
the second happy move, [C,sigma] in terms of the six basic moves, it would
be this:
Let X'=X^(-1) for any X (because it's easier to type in email).
Then [C,sigma]=LF'L'FT'FTF'
in terms of the basic moves. So sigma just means you turn the whole cube
so that what used to be the top face now becomes the front face and what
used to be the front face now becomes the left face. So to do move
number 2, first you do C, then you change positions so the top becomes
the front and the front becomes then left and then you do C'. It is
actually the easiest of the four moves to work with in practice. See?
In fact you could write all the four happy moves in terms of basic moves:
C = LF'L'F
[C,sigma] = LF'L'FT'FTF'
[C,D] = LF'L'FDF'LFL'D'
[CC,D] = LF'L'FLF'L'FDF'LFL'F'LFL'D'
but obviously it's much easier to think of and memorize the four symbols
on the left rather than the strings on the right.
--KMK'M'
--------------------------------------------------------------------
Subject: Re: cube
--------------------------------------------------------------------
> How do I interchange the top left and top front edges? Those are the only
> edges left to put in place and I don't know how to do it without screwing
> up the rest of the cube.
Ahah. This is the one tricky situation that is not accounted for by the
list of four happy moves. The problem you run into in this situation is
that you have an ODD permutation of edge positions because you only have
two edges out of place (e.g. if the edges out of place are e and f, then
the position permutation can be written as (ef) in cycle notation which is
the product of just one transposition and hence odd). But the move that we
use to swap edge positions, C, is and EVEN permutation of edge positions
because it is a 3-cycle (e.g. if move C swaps edges e,f,h then in cycle
notation C is (efh) which equals (eh)(ef) and is thus even.) Hence when
you find yourself in the position of having only two edges out of place it
is IMPOSSIBLE to fix the edge positions by using move C alone, because no
matter how many times you compose an even permutation with an odd one you
still get an odd one, but you need to reach the identity which is even.
So how to you fix it? Well fortunately the fix is trivially easy. Let's
assume you have placed all of the edges on the bottom slice correctly and
you have also placed the edges on the middle horizontal slice correctly
and all you have left is the top edges. If you look at it and find that
you have only two out of place, so that you are in an odd state with
regard to edge positions relative to the original state of the cube. Well
we need some way to change the odd permutation to an even one. That means
we need to apply an odd permutation. But all of the basic moves are odd
permutations on edge locations (e.g. the basic move R is (abcd) in cycle
notation and this equals (ad)(ac)(ab) which is obviously odd.). So all
you have to do is do one U operation (i.e. 90deg twist of the top) and you
will change from having an odd permutation to an even one. After the twist
you will either have
1. three edges on the top out of place... then use conjugacy and move C to
interchange the three of them
2. two pairs of edges swapped with each other like (gb)(fe)... again use
conjugacy and C to swap any three and put one of them in place. This will
leave you with three out of place which you the fix by conjugacy and C.
So the short answer is, if you end up with only two top edges out of
positions, give the top a quarter twist and proceed as usual. :)
--Let's Do the Twist