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 1998 course
--------------------------------------------------------------------
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, September 05, 1998 3:18 PM
Subject: updates and examples
Math-o-nauts:
I posted some due dates on the homework page at the website.
There are two examples of formal proofs in propositional logic in the
FAQmodern.txt web page (which can be obtained from the Math 448 page for those
of you in geometry only). They may be of help in doing your homework.
Also, I didn't mention to the geometry class one other rule of inference...
the Rule of Stupidity (which we will abbreviate S in our proofs):
;S (stupidity rule)
P
------
P
This rule is not really needed in your proofs, but it is useful when you have
a line in a proof that you want to copy to another line for legibility. All
it says is if I know P then I can conclude P. I use it in an example below to
sow how it can be used to make a proof more readable.
Also, here is one other example which I was not able to get to in class. It
illustrates a common use of one of the theorems you are proving for homework
in assignment #2.
Thm: (P=>Q)<=>(~P or Q)
Pf:
1. Assume (P=>Q) -
2. P or ~P Homework problem #5, assignment #2
3. Assume ~P -
4. ~P or Q or+;3
5. ~P=>(~P or Q) =>+;3,4
6. Assume P -
7. Q =>-;6,1
8. ~P or Q or+;7
9. P=>(~P or Q) =>+;6,8
10. ~P or Q or-;2,5,9
11. (P=>Q)=>(~P or Q) =>+;1,10
12. Assume ~P or Q -
13. Assume ~P -
14. Assume P -
15. Assume ~Q -
16. P and ~P and+;13,14
17. Q ~-;15,16
18. P=>Q =>+;14,17
19. ~P=>(P=>Q) =>+;13,18
20. Assume Q -
21. Assume P -
22. Q S;20
23. P=>Q =>+;21,22
24. Q=>(P=>Q) =>+;20,23
25. P=>Q or-;12,19,24
26. (~P or Q) => (P=>Q) =>+;12,25
27. (P=>Q)<=>(~P or Q) <=>+;11,26
QED
Comments: If you have a hard time deciding what to do when you are doing your
proofs, try the recipe approach. In the above example, I see that the thm is
an <=> statement so I could begin by applying the <=>+ recipe:
Thm: (P=>Q)<=>(~P or Q)
Pf:
1. Show (P=>Q)=>(~P or Q) (on our "Things to do" list)
2. Show (~P or Q) => (P=>Q) (on our "Things to do" list)
3. (P=>Q)<=>(~P or Q) <=>+;1,2
QED (well, it will be when we are finished)
So now take each of the statements on your Things to Do list and apply some
recipe to them, etc. So, for example, line 1 is an => so I might want to use
=>+:
Thm: (P=>Q)<=>(~P or Q)
Pf:
1.1 Assume P=>Q -
1.2 Show ~P or Q (on our "Things to do" list)
1.3 (P=>Q)=>(~P or Q)
2. Show (~P or Q) => (P=>Q) (on our "Things to do" list)
3. (P=>Q)<=>(~P or Q) <=>+;1.3,2
QED (well, still not yet)
And so on. In this manner you can build your proof "from the bottom up".
Starting with what we want, we determine what we need to get it, and then
determine what we need to get THAT and so on and so forth. The disadvantage
of doing it this way is that it is almost impossible to do on paper, since it
is not easy to insert lines in the middle of your proof if you are doing it on
paper. So it might be easier to do this kind of proof in a word processor or
text editor if you want to use this method of expanding "shows".
--on with the show
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, September 05, 1998 3:24 PM
Subject: missing reason
I forgot to type the reason on one line in one of my demo pre-proofs in the
last email. It should read:
Thm: (P=>Q)<=>(~P or Q)
Pf:
1.1 Assume P=>Q -
1.2 Show ~P or Q (on our "Things to do" list)
1.3 (P=>Q)=>(~P or Q) =>+;1.1,1.2
2. Show (~P or Q) => (P=>Q) (on our "Things to do" list)
3. (P=>Q)<=>(~P or Q) <=>+;1.3,2
QED (well, still not yet)
--absent minded prof
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, September 06, 1998 2:42 PM
Subject: The Maria challenge
Just for kicks I assigned your homework (assignments #1 and #2) to my 5th
grade daughter Maria (who is now our class mascot :) ). She did the toy
proofs with no difficulty and breezed through number 1 and number 3 on
assignment #2. She was stuck on number two for a while and tried a couple of
dead ends. Then she finally got it, but when she brought the proof to me I
realized that she had done it an entirely different way than I had thought
of, and her proof was shorter than mine!! She did it in eleven lines. Once I
saw her proof I realized that it can actually be done in three lines if you
prove a lemma first whose proof is five lines long and then use the lemma.
So that is a total of 8 lines altogether!
That's my girl! (insert proud fatherly grin here with swelling chest). :-)
While a proof of any length if perfectly alright as long as it is correct, it
is always nice to try to find the shortest slickest proof you can find. So
the Maria Challenge is to see who gets the shortest proofs for each of the
other homework problems. Let the games begin!
I also wanted to mention the following regarding what theorems you can use as
reasons in your proofs. Basically you can use any of the five homework
problems, anything I proved in class, or any example that is in the FAQ
(complete with proof), or any Lemmas you yourself decide to prove, to help you
prove a theorem as long as you don't create a circular argument! In other
words, if in the proof of Theorem 1 you use Theorem 2 as a reason for a line
and then in the proof of Thm 2 you use Thm 1, that is a circular argument.
So you can't use a theorem that has not been proven as a reason in your
proofs. For example, you could not use the example theorem I sent you by
email as a reason for a line in the proof of problem number 5 because it uses
the theorem of problem number 5 as a reason for one of it's line. However you
CAN'T use a tautology just because you know it is a tautology by it's truth
table! You must have a proof of everything you use. You are NOT allowed to
use the meta-theorem that says that a statement of propositional logic is
provable iff it is a tautology.
You gotta love these proofs, right? Fun fun fun!
--Proof Prof
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Monday, September 07, 1998 9:23 PM
Subject: Re: assume vs show
The first email question of the season has arrived!!!
"Since before your sun burned in the sky... since before your race was born...
I have awaited... A QUESTION!"
(trivia -- where is that quote from?)
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Monday, September 07, 1998 7:01 PM
Subject: assume vs show
>I don't understand how in some problems, you assume statements that
>the recipes say should be shown and in other cases you follow the
>recipes by the book. When a recipe calls for something to be shown or
>assumed, can you do whichever is more convenient?
Remember that whatever you Assume is "shown" at in that level in the proof,
i.e. in the pretend land you are working in. So you can use the thing you are
assuming to satisfy a Show requirement in a recipe if you need to, but when
you "show" it it will be at the same level of indentation (or further to the
right) as the line where you Assumed it.
>Also, sometimes I
>have a line shown but the recipe calls for it to be assumed, do I still
>need to assume it?
Yep.
>Finally, can you assume something instead of showing
>it?
You can assume whatever the heck you want to assume. Showing something means
you prove it to be true. Assuming it means you are pretending it is true.
They are not the same thing. But when you assume a statement it IS Shown or
Proven in the pretend world you are working in (i.e. at that indentation
level).
In some cases the thing you need to Show might already be assumed to be true.
Then in your pretend world, you have already shown it, and if that is all you
need for the recipe, then you are all set. For example consider the following
correct proof:
Thm: P=>P
Pf:
1. Assume P -
2. P=>P =>+;1,1
QED
Here we see that I am using line 1 as both the Assume and the Show steps in
the =>+ recipe. We might make this a little bit easier to read if we used the
Stupidity Rule:
Thm: P=>P
Pf:
1. Assume P -
2. P S;1
3. P=>P =>+;1,2
QED
because now it looks more like the recipe does. But in either proof, P is
"shown" at indentation level one, but certainly P is not a theorem of
propositional logic, so there is
no way to say to show it unindented at level zero. But we don't require it to
be unindented in the recipe... we require only that it be Shown on the same
indentation level as the Assume... then the CONCLUSION is unindented.
I would recommend highly that you go through the examples I sent you by email,
did in class, and put on the FAQ sheet on the web site. That might help to
clear things up.
--Labor Day Laborer
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Monday, September 07, 1998 9:30 PM
Subject: Re: Confusion already!!
Two questions in one day!! Let the virtual office hours continue!! :)
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Monday, September 07, 1998 9:19 PM
Subject: Confusion already!!
>Dr Monks
>
>I started doing Math 345 Assignment #2 and have fun into a bit of confusion.
Glad you are having fun. :) (though I assume you meant to type "run")
>I am trying to do problem 2 and trying to prove that Q=>P, this is the way
>that I tried it:
>
> 1. Assume P -------
> 2. Assume Q --------
> 3. P :S;1
> 4. Q=>P :=>+;2,3
Your indentations on the Assumes are wrong. Whenever you put an Assume into
the proof, you must increase the indentation by one level, so your proof would
look like:
1. Assume P -------
2. Assume Q -------
3. P :S;1
4. Q=>P :=>+;2,3
up to this point what you have is correct. I am not saying that you are going
to be able to complete the proof by starting out this way (and I am not saying
you can't), I am just saying that there is nothing wrong with what you have
written so far. But it could also be a dead end...
>I got this from part of the proof that you emailed us on Saturday, but don't
>understand how you can get P if you are only assuming it. I got this from
>steps 20 through 23 in the emailed proof. Thanks for your help!!
Because you didn't have the indents right. In the version that I corrected
above, you see that P is only stated at the second indentation level, which is
ok, because we assumed it was true at an even higher level, level one.
--Level Headed
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, September 08, 1998 9:39 AM
Subject: Re: Confusion already!!
More trouble brewing...
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Tuesday, September 08, 1998 9:11 AM
Subject: Re: Confusion already!!
>Dr. Monks I am having a little trouble with Thm E in Assn 1. It seems to
>me that it can not be proven.
It can.
>If it could, I can't figure out where to
>start.
There is no formula for where to start a proof.
>I also am a little confused on question #2. I don't understand
>what you mean.
I mean that it is either the case that:
I. All toy proof formulas are provable.
II. Some toy proof formulas are not provable.
I am asking if I. is true or if II. is true, and if II. is true can you tell
me exactly which formulas are provable and which are not.
--Truth Seeker
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, September 08, 1998 3:06 PM
Subject: minor stuff
I should mention a simple Rule that you might be confused about. EVERY
TIME you insert an ASSUME statement into your proof you must increase the
indentation level by one. The ONLY way to decrease the indentation level is
by using one of the three recipes that have an Assume in them, namely: =>+ ,
~+, and ~-.
So when you check the indentations in your proof, the indentation moves to the
right on all the ASSUME lines, and it moves to the left on any line whose
reason is either =>+, ~+, or ~-. There are no exceptions to this rule, so you
can easily determine if your indentations are correct or not.
Also, you should note that the indentations are NOT shown in the recipes
themselves. They are only shown in the rule of inference format. But you can
determine exactly what indentations to use at any time by the above Rule.
-Mystic Ruler
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, September 09, 1998 7:35 PM
Subject: Re: I can't get out of DREAM LAND!?!?!
Hi gang! Here is the latest from the e-mail in-bin...
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Wednesday, September 09, 1998 7:06 PM
Subject: I can't get out of DREAM LAND!?!?!
>Hey Dr. Monks,
>I have a slight
>problem. In doing a lemma (or simple proof) such as P=>Q I can't get
>out of the first indented Assume?
>
>Lemma A: P=>Q
>
>PF:
>1. Assume Q ---
>2. Assume P ---
>3. Q ;S;1
>4. P=>Q ;=>+;2,3
>QED (but it's not done??? The 1st Assume is directly above the 4th
>line of the proof???)
>
>I guess I'm stuck, because this is causing problems in my other proofs?
>Thanks for your time,
Your proof of the Lemma is correct except for the QED part, because as you
rightly point out, the "proof" proves nothing because you are still on level
one Fantasy Island. And for a very good reason... the reason that you are not
having success proving this is because THE THING YOU ARE TRYING TO PROVE CAN'T
BE PROVEN!! Why? Because it's not a tautology!!! The truth table for P=>Q
is:
P Q P=>Q
T T T
T F F
F T T
F F T
so it is not a tautology and therefore no matter how hard you try you will
NEVER be able to prove Lemma A that you have stated above using propositional
logic!
However, let's not waste your good proof! For example we can take your proof
and add one more line to prove something for real:
Lemma B: Q=>(P=>Q)
PF:
1. Assume Q ---
2. Assume P ---
3. Q ;S;1
4. P=>Q ;=>+;2,3
5. Q=>(P=>Q) ;=>+;1,4
QED
Also notice that Q=>(P=>Q) IS a tautology, because if it were not, we could
not have proven it!
So that is why you are stuck in fantasy land... because you CAN'T prove
something that isn't a tautology in predicate logic. You are trying to do the
impossible but the indentations won't let you!
--Mr. Phelps
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, September 10, 1998 9:18 PM
Subject: Re: Prof Traffic cop: how about some directions?
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Thursday, September 10, 1998 6:08 PM
Subject: Prof Traffic cop: how about some directions?
>Ok, here's a question for you:
>I'm not sure if I need to prove this, or if I can assume the
>following. I thought I could assume it by the definition of
>"or"
You can't "assume" anything that hasn't been officially stated as a Rule of
Inference, if that is what you are driving at. But "assume" is a dangerous
word here because it has two meanings, the English one that you are using here
and the formal one that we use IN the proofs on an Assume line. To
distinguish in email between the two I will always capitalize Assume when I am
talking about and Assume line in a proof and leave it lower case if I am using
it in a sentence as an English word.
>If I know (P or Q) and I know ~Q can I assume P?
No. Not the way I think you mean. Not yet, anyway. Later in the course, when
we let our proofs get sloppier, then it will be ok.
>Or, do I need to prove the following and use it as a lemma:
>Thm: (~Q) & (P or Q) => P
Yes. This is what you have to do. Notice that once you have this then you can
get the first thing that you wanted because for example if in the middle of
the proof you have ~Q and you also have (P or Q) then you CAN get P in only
three lines:
:
34. ~Q for some reason...
35. P or Q for some other reason...
36. ~Q and (P or Q) and+;34,35
37. ~Q and (P or Q) => P Thm above (assuming you have a proof for it of
course)
38. P =>-;36,37
:
So you can't just say that if you have ~Q and also (P or Q) then you
automatically have P by definition of "OR", but if you have ~Q and also (P or
Q) then you can PROVE P in a few short lines if you have a proof of the above
Thm, which is effectively the same thing.
>If I need to prove this, am I starting off in the right
>direction?:
>Thm: (~Q) & (P or Q) => P
>Pf:
>1) Assume ((~Q) & (P or Q))
>2) (P or Q) &-; 1
>3) ~Q &-; 1
>4) ***(I think I need to do something with or- but I am
>having trouble with that one. So,
>
>A) Am I on the right track?
Yes.
>B) Can you give us an example of or- in action?
Yes.
Thm: P or Q => Q or P
Pf.
1. Assume P or Q -
2. Assume P -
3. Q or P or+;2
4. P => Q or P =>+;2,3
5. Assume Q -
6. Q or P or+;2
7. Q => Q or P =>+;5,6
8. Q or P or-;1,4,7 (there you go!)
9. P or Q => Q or P =>+;1,8
QED
The reason or- is harder to use than the other rules is quite simple... it is
the only rule that has three lines for inputs. All the rest have 2 or less.
--Conductor of the Train of Thought
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, September 12, 1998 3:11 PM
Subject: #- rule
After thinking about it some more I would like to suggest the following
formatting change for the #- rule. In class I wrote it this way:
;#-
#x,P(x)
----------
Let t be a constant such that P(t)
But now I want to change it to this way:
;#-
#x,P(x)
----------
Let t be a constant such that
P(t)
The restrictions on using this rule are the same as what I gave you in class
and in the recipe sheet. The only difference is I am putting P(t) on a
separate line from the declaration. So this rule will have ONE input line and
TWO output lines, the first being just a declaring the variable and the second
line being the actual statement we are inferring from the rule.
This is different from what I originally had in the FAQ sheet example, which
had the constant declaration as an input to the rule. I have now updated that
example to reflect this change. The example should look like this in this
notation:
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 this is not a substantial change, I am just word wrapping the single long
output line onto two lines for readability.
--Word Wrapped Up in his Work
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Monday, September 14, 1998 8:17 AM
Subject: Re: @-
-----Original Message-----
To: MONKS@EPIX.NET <MONKS@EPIX.NET>
Date: Sunday, September 13, 1998 9:42 PM
Subject: @-
>Dr. Monks
> I have a short question. I've forgotten what conclusion(s?) can be
>drawn from the 'for all minus' rule. I can't quite follow what's written
with
>the proof recipes.
The recipe says:
; @-
To show P with x replaced by t
1. Show @x,P
**Restrictions on @- rule:
* No free variable in t may become bound when t is substituted for x in P
What part of this don't you follow?
Note t can be any expression, not just a variable. So if you know P is true
for every x, then you know it is true for any particular value of x you decide
to substitute, namely t.
For example, if we know that @x,x^2>-1 then we can conclude that 3^2>-1,
t^2>-1, (2x+3)^2>-1, and x^2>-1. So I am not really sure what you are asking
because I don't know what part of the recipe you are confused about.
--unsure chef
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Monday, September 14, 1998 8:27 AM
Subject: another question
-----Original Message-----
To: monks@TIGER.UOFS.EDU <monks@TIGER.UOFS.EDU>
Date: Sunday, September 13, 1998 9:20 PM
>If you are using the rule #+ and you assume P(t) to get #yP(y) and then
>later on in the proof you need to prove #xP(x), do you assume P(z) instead
>or can you assume P(t) again?
If I understand your question correctly the answer is you can use the P(t)
again. For example:
:
245. P(t) (for some valid reason)
246. #x,P(x) #+;245
247. #y,P(y) #+;245
248. #z,P(z) #+;245
:
would be a valid proof snippet...
However I will WARN you that if you do this:
1. Assume P(t) -
2. #x,P(x) #+;1
Then you are still one level deep in fantasy land, so what you have shown "for
real" is, e.g.
1. Assume P(t) -
2. #x,P(x) #+;1
3. P(t)=>#x,P(x) =>+;1,2
which might not be what you want, right?
--Early Morning Warning
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Monday, September 14, 1998 8:31 AM
Subject: Re:
-----Original Message-----
To: monks@TIGER.UOFS.EDU <monks@TIGER.UOFS.EDU>
Date: Sunday, September 13, 1998 10:23 PM
>I'm having a problem figuring out what would be the contradiction for
>@xP(x). Any hints?
We never defined a "contradiction for" something. A contradiction is any
statement of the form Q and ~Q where Q is a statement. If you want to use
@x,P(x) as the statement Q, then the contradiction would be:
(@x,P(x)) and ~@x,P(x)
but we would not say this is the "contradiction for" anything.
--Monks and ~Monks
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 9:06 AM
Subject: Re: Mod Alg Assign #4
-----Original Message-----
To: Dr. Monks <monks@TIGER.UOFS.EDU>
Date: Wednesday, September 16, 1998 9:26 PM
Subject: Mod Alg Assign #4
>For problem 18 (a)-(d) in assignment #4, do we have to prove the unions and
>intersections using numbered, reasoned, formal proofs like we have up to this
>point or can we do them like the example you showed in class for indexed sets
>and unions? For example, for 18a, can I simply list the sets Ai, like A0 = {r
>E R : 0 <= r < 1}, etc.., and draw the answer from that like the in-class
>example or is there some recipe or other trick I am missing? Help! I am
>getting bogged down just on figuring out to what extent these problems need to
>be done.
-----------------------------------------------------------------
You can do them like the example I did in class. You don't need to prove your
answers. Not all problems in the course are proofs, just most of them. :) If
you are unsure if a certain problem requires a proof or not, just ask.
--Proof Prof
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 9:25 AM
Subject: email specs
If your email client allows you to send email as either html or plain text,
please use plain text only when sending me questions via email. Otherwise
when I reply my client doesn't quote the email correctly and some of the
formatting in your question will be lost when I forward it to the entire
class. If you have no clue what I am talking about here, you probably don't
have to worry about it.
--Ascii and ye shall receive
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 9:38 AM
Subject: Re:
-----Original Message-----
To: monks@TIGER.UOFS.EDU <monks@TIGER.UOFS.EDU>
Date: Wednesday, September 16, 1998 9:46 PM
>I have a question about assignment four. You said this assignment covered
>things we covered in class on monday. We only went over the definitions
>of set theory but we didn't do any examples of how to prove them. Should
>I know how to do assignment four because I don't even know where to start.
I did do at least one proof on showing a function is injective in class
yesterday and there is a very long and detailed example in the FAQ in which I
compare the English versions and Formal version of the same proof. I highly
encourage you all to look at that example in the FAQ! There are other tips in
the FAQ that refer to problems you are currently working on, so it is a VERY
good idea to read it.
In addition, you should know that I will NOT be doing an example proof that is
just like each and every homework problem you are assigned in the course. In
Calculus and below, that is how math is taught... I give you an example and
then assign three homework problems that look just like the example I did
except the 2's are changed to 3's or something. In Modern and Geometry, you
are encouraged to THINK and figure out on your own how all this stuff works
(with my guidance and help of course) so that you should not expect to have an
example that is almost identical to every homework problem.
I did cover all the relevant terms of set theory and discussed each one, and
you have recipes for doing proofs with each of them (check the recipe sheet),
and there are examples and further discussion in the FAQ sheet. So you are
well-armed to tackle these problems! I have great pride in my students and I
respect your abilities, so I don't fear giving you a little challenge on the
homework. You wouldn't be in these courses if you weren't bright, creative,
resourceful people. So keep your chin up and struggle on! You are the best
of the best! Don't sell yourselves short!
--Head Struggler
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 10:58 AM
Subject: Re: email specs
-----Original Message-----
To: Ken Monks <monks@LION.UOFS.EDU>
Date: Thursday, September 17, 1998 9:38 AM
Subject: Re: email specs
>Dr. monks, here is what i started to do for #15. I know you have to prove
>it is injective and surjective.
Correct. You are already part way there. :)
>I tried injective but i don;t think i am
>right. I need help. I am also lost with the surjective part. I know how
>to prove it using the recipe, but i don't know how to it relating to this
>problem.
>
>1. Let (x,y), (z,s) be in B X C.
>2. (x,y) in B Cartesian prod
>3. (z,s) in C " "
OK. Here is your first error. (x,y) is not in B unless B is itself a
Cartesian product, which we have no information on. What you mean is that x
in B and y in C. Similarly for z,s.
To show f is injective we want to pick two arbitrary elements of the domain of
f. Now skipping over a lot of the logic that we will take for granted from
now on, the right way to do this is:
1. Let u,v be in BxC
2. u=(x,y) for some x in B and y in C def of Cart prod;1
3. v=(z,s) for some z in B and s in C def of Cart prod;1
Here I am using a shorthand abbreviations like:
2. u=(x,y) for some x in B and y in C def of Cart prod;1
which is a shorthand for:
2. #x in B, #y in C, u=(x,y) def of Cart prod
3. Let x be a constant such that
4. x in B and #y in C, u=(x,y) #-;2
5. #y in C, u=(x,y) and-;4
6. Let y be a constant such that
7. y in C and u=(x,y) #-;5
(and even this uses the "#x in B" abbreviation I gave in class). So you see
why these shorthands are going to become necessary in order to shorten the
lengths of our proofs by skipping obvious parts that follow from logic.
Let's see where you go next:
>4. Assume f(x,y)=f(z,s)
This assumption is ok.
>5. @(x,y) f(x,y)=(y,x) given
This is bad notation since you can get in trouble by saying @(x,y). A better
way to say it might be:
5. @x in B,@y in C,f(x,y)=f(y,x)
>6. f(x,y)=(y,x) @-; 5
>7. f(z,s)=(s,z) @-; 5
>8. (y,x)=(z,s) subst; 4,6,7
Yes, this is the general idea.
Let me do an example of surjective that is in a very relaxed English style but
still correct.
Thm: Let g:BxC->C with B~={} by g(x,y)=y. Then g is onto.
Pf:
Let g:BxC->C with B~={} by g(x,y)=y.
Let x in C (1st step in the recipe for onto)
Let s be such that s in B (since B~={})
(s,x) in BxC (def of Cart Prod)
g(s,x)=x (def of g)
#z in BxC, g(z)=x (#+, namely z=(s,x). 2nd step in recipe
for onto)
g is onto (def of onto)
QED
This is a perfectly correct proof but skips a LOT of steps... no line numbers,
lots of formal logic is skipped right over because it is obvious. Yet the
proof is clear and correct and if someone FORCED us to defend it with a formal
argument we could easily do so by filling in the missing steps.
Now the danger as far as you guys are concerned is that that omitting line
numbers and formal reasons which refer to line numbers and skipping steps
opens the door for trying making statements that you CAN'T defend.. i.e. it
provides more room to be sloppy in your proofs.
So MY job in grading these is to determine if you skipped a step because you
could have filled it in but it is obvious vs if you skipped it because you
don't really know how to get from one line to the next.
YOUR job is to convince me that you definitely understand how to get from one
line to the next.
I am pretty good at my job, and now the goal is to make you good at yours! :)
Note that while I don't mind removing the need for line numbers or formal
indentations, I would prefer that you continue to write your proofs with one
statement per line rather than word-wrapped. They are easier to read and the
logic is easier to follow. So I will still insist on one statement per line.
Other than that you can start to be a little less formal in the proofs as long
as you still convince me your proof is right. (But I am tough to convince! :))
--Informal Informer
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 3:10 PM
Subject: Re: Question
-----Original Message-----
To: MONKS@EPIX.NET <MONKS@EPIX.NET>
Date: Thursday, September 17, 1998 1:57 PM
Subject: Question
>Grand Master Monks:
>
>let's say I "let" the following line in a proof:
>
>let (x,y) such that A x (B u C)
You can't say this. Ax(BuC) is a set, not a statement and you can only say
"such that P" if P is a statement. I think what you want to say is:
"Let (x,y) in Ax(BuC)"
This is a typical math statement, although I recommend you say:
"Let z in Ax(BuC).
z=(x,y) for some x in A and y in BuC"
Because it is easier to reason with it in this form. But you could say the
former, as long as you don't screw up later on in the proof because of it. So
lets assume you said one of these last two things and answer your next
questions:
>Do I automatically know that:
> x is an element of A and
> y is an element of (B u C)
>(where u in this case means union)?
Sure, but not "automatically". You know it by the definition of Cartesian
Product.
>Also, are there rules, I may have missed them in the recipe sheet that tell us
>how to perform a u+ (union plus) and a u- (union minus)?
There are no such rules in Gentzen's system because UNION is not a logical
operation, it is a set operation. However you can make rules that have the
right "flavor". For example, this rule:
To show x in A U B
1. Show x in A or x in B
could be called a U+ rule if you like because there is no U in the input but
you have one in the output. So in that sense, you can make such rules from the
definition sheet I have posted on the web if they are not already in the recipe
sheet. If there are rules you would like to add to the recipe sheet let me
know and I will add them. As I said in class, there are many many recipes you
can make, so you have to choose which are most useful, and those are the ones
that go in the recipe sheet.
>e.g.
>0. let A,B,C be sets
>1. let (x,y) such that A x (B u C)
>2. x is an element of A
>3. y is an element of (B u C)
>4. ( I would like to apply a u- here to get more info
Well, if you want a recipe that "approximates" U- rule, you can do it this way:
To show x in B or x in C
1. Show x in B U C.
This has U in the input but not in the output so you could call it U- if you
like. Normally I would call both the U- and U+ recipes given above the
"definition of Union" and that would be my reason. But the more I think about
it the more I am starting to like this idea, so if you want to call these rules
U- and U+ that is ok with me.
>Also, can I apply ~ to a set?
>e.g. if I want to prove A x (B u C)
>can I assume ~ (A x (B u C)
>and try to reach a contradiction???
NO! ~ is a logical operator, thus ~P is only defined if P is a statement. You
can't negate a set. You also can't ASSUME a set. You can only assume
statements. It is like me asking you:
True or False:
{4,3}
?
What will you answer? {4,3} is not a statement, it is a set. You can't say if
it is true or false. It just IS.
--A Union Man
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 7:36 PM
Subject: Re:
-----Original Message-----
To: monks@TIGER.UOFS.EDU <monks@TIGER.UOFS.EDU>
Date: Thursday, September 17, 1998 6:40 PM
>Can you explain to me in as much detail as possible what it means to be
>injective, surjective, and bijective. I used to know but now i am just
>confusing myself and it's giving me problems with the proofs.
I won't repeat the definitions since they are in your notes. Let me explain
them in "street English".
Once upon a time there were two cities (=sets) named Domain and Codomain. A
Matchmaker (=a function) is someone who assigns to each person (=element) in
the Domain, a partner (=element) who lives in Codomain.
A Matchmaker is injective if no two different people are assigned the same
partner. It is surjective if each person in Codomain is somebody's partner.
It is bijective if it is both surjective and injective, i.e. every person in
Domain is matched with a unique person in Codomain and vice-versa.
Examples from Calculus:
f:R->R by f(x)=x^2 is not injective because f(1)=f(-1) and it is not surjective
because there is no real number x such that f(x)=-1.
f:R->R by f(x)=e^x is injective because if f(x)=f(y) then e^x=e^y so taking ln
of both sides we see that x=y. On the other hand it is not surjective because
there is no real number such that f(x)=-3.
f:R->R by f(x)=x(x-1)(x+1) is not injective since f(1)=f(0) but it is onto
because it is an odd degree polynomial.
f:R->R by f(x)=x is clearly both injective and surjective and thus is bijective
also.
Hope this helps.
--Math Dude
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 7:44 PM
Subject: Re: When it rains it pours
-----Original Message-----
To: MONKS@EPIX.NET <MONKS@EPIX.NET>
Date: Thursday, September 17, 1998 6:02 PM
Subject: When it rains it pours
>I ~(promise) that this will be the last question for the day:
Somehow I doubt it. :)
> Please tell me if I can get the following by definition of subtraction:
>
> let x in (A u B) - (A int B)
> x in (A u B) and x not in (A int B) by def of subtraction (on sets)
> hannah or no?
I believe the correct spelling is "henna or no" :-) (BTW, if you are not from
NE Pa you probably won't get this joke.)
The answer is YES (i.e. henna).
--Da Prof frum Hazlt'n
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, September 17, 1998 7:52 PM
Subject: Fw: hwk confusion
-----Original Message-----
To: MONKS@EPIX.NET <MONKS@EPIX.NET>
Date: Thursday, September 17, 1998 6:47 PM
Subject: hwk confusion
Told you it wouldn't be the last question...
>For our Modern Hwk, I am confused about pblm 24. For example, 24a says:
>a * b = 2^ab in my world, that statement is false. If I take a= 1 and b =1
>a* b = 1 and 2^1*1 = 2
>1 dne 2. how can I show that that statement is commutative or associative if
>it is not true? Thanx
The problem is that you are interpreting * to mean "times" but it is not times,
it is a new operation that is not + or times or subtraction or division which
we are calling * and defining by a*b=2^ab. Thus if you take a=1 and b=1 you
get 1*1=2, not 1 as you claim above. If they meant * to be multiplication then
the equation would have to be written a*b=2^a*b right? But they are using
concatenation for multiplication on the RHS, as is usually done. So * is not
multiplication, it is just some new operation you can call "star" if you like.
--Star Teacher
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Friday, September 18, 1998 10:57 AM
Subject: Re: help
-----Original Message-----
To: Monks@epix.net <Monks@epix.net>
Date: Friday, September 18, 1998 12:20 AM
Subject: help
>chef monks, i realize it's late but I have been working the problems for the
>last several hours. i hit problem number 27B and I am stuck. I am having a lot
>of problems using the surjective rule. I know this problem requires an => +
>so i began by assuming the 1st part
> Assume f and g are surjective
> let x be in D
>
>here is where i am stuck. i know i have to show #y in B, f(x)=y but I don't
>know how to manipulate this.
>Help!
This is not what you want to show. You want to show that #y in B, gof(y)=x.
You should then use the fact that each of the functions f and g are onto and
the definition of composition of functions to try to come up with a proof since
that is what you have to work with.
--Onto Something
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Sunday, September 20, 1998 9:57 PM
Subject: Re: help
-----Original Message-----
To: Ken Monks <monks@LION.UOFS.EDU>
Date: Sunday, September 20, 1998 8:09 PM
Subject: Re: help
>dr. Monks, please help me with number 31 because i have no clue where to
>even begin. I don't remember you saying anything about proving images.
>
>thanks
I didn't define Im f in lecture, but it is defined on page 512, amazingly in
the same section that the problem is in. :) If you read the definition you
will see that Im f is exactly the same thing that I called Range(f) in class,
i.e. Im(f)=Range(f)=f(Domain(f))=f(B).
--Home, Home on the Im
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Tuesday, September 22, 1998 8:42 PM
Subject: Re: help
-----Original Message-----
To: Ken Monks <monks@LION.UOFS.EDU>
Date: Tuesday, September 22, 1998 5:40 PM
Subject: Re: help
>Dr. Monks, I'm having a problem with #4 on pg. 6. when it says to use the
>div algorithm, does that mean that we use that to show that it works for
>when c is positive (c > 0). So is it asking us to show it works for when c
>is negative because in the thm it just says c not equal to 0.
Roughly speaking, what you say is correct. You immediately know it is true for
c>0 by the division algorithm, so if you state that first then all you need to
do is show it for c<0.
>so would i
>use a set S- = {sES and s< o} to prove it.
Well, you could, but that is the hard way to do it. You can actually use the
division algorithm to handle c<0 too if you are careful about it and that saves
you tons of work.
--Work Saver
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Wednesday, September 23, 1998 10:34 AM
Subject: end of today's proof
Here is the other half of the proof I was doing in lecture today...
First two Lemmas:
Lemma: Let a,b be nonzero integers. a|b => |a|<=|b|.
Pf Assume a|b
am=b
|a||m|=|b| take abs value of both sides
|m|>=1 since m~=0
|a||m|>=|a| by subst
|b|>=|a| by subst
|a|<=|b| property of inequalities
QED
Lemma: Let a,b be nonzero integers. If a|b and b|a then a=b or a=-b.
Pf
Assume a,b are nonzero and a|b and b|a.
am=b and bn=a for some integers m,n by definition of |.
bnm=b by substitution
b(1-nm)=0 by algebra
1-nm=0 because the product is 0 and b isn't zero
nm=1 by alg
n|1 def of |
|n|<=1 Previous Lemma
n=-1 or n=0 or n=1 def of abs value
n=-1 or n=1 since 0 does not divide 1
a=b or a=-b subst
QED
...and now the other half of the proof...
(<=)
Assume @b@c,p|bc=>p|b or p|c
Let s be arbitrary.
Assume s|p
st=p for some integer t by def of |
p*1=st since p*p=p
p|st
p|s or p|t by @- and =>- on our first assumption
Case 1: Assume p|s
p|s and s|p by and+
s=p or s=-p by the previous lemma
s=p or s=-p or s=1 or s=-1 by or+
Case 2: Assume p|t
pk=t for some integer k by def of |
p=spk by subst
p(1-sp)=0 by alg
1-sp=0 the product is 0 and p isn't
sp=1 by alg
s|1 def of |
s=1 or s=-1 see proof of prev lemma
s=1 or s=-1 or s=p or s=-p by or +
s=1 or s=-1 or s=p or s=-p by or-
@s,s|p=>s=1 or s=-1 or s=p or s=-p @+ and =>+
p is prime
QED
--still in my prime
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Wednesday, September 23, 1998 1:47 PM
Subject: definition of divides
Apparently there is a slight difference between the definition for "divides"
that I gave in lecture and the one that is in the book and in the recipes. I
said that "a|b <=> #m,am=b" whereas the book says "a|b <=> a~=0 and #m,am=b".
Since by the definition I gave in lecture, the only number that is divisible by
0 is 0 itself, this is the only difference between the two definitions. So both
definitions are the same except that in the one I gave in lecture 0|0 is true,
but in the definition in the book and the recipes 0|0 is false.
But this is a difference, so in order to stay coordinated with the book and do
the homework problems, let us take the book's definition as the "official" one.
So from now on ~0|0 but everything else is the same.
--Zero Divides Nothing
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, September 24, 1998 9:53 AM
Subject: Fractions Banned
I hearby ban the use of the division sign / (ie all fractions having a
numerator and denominator) in the modern algebra course!!
It only gets you in trouble. Use | to discuss divisibility questions, not /.
For example, if you are talking about integers and you know that b|a then don't
talk about a/b in your proof but rather say that a=bm for some integer m and
then talk about m instead. This way it is clear that m is an integer, but when
you write a/b in your proof, you have to verify that a/b is an integer if that
is what you need because that is not clear at all from the expression. This is
the cause of countless mistakes on modern homework.
Thus, the division sign / and equivalent symbols are now banned in this course.
The only exceptions to this ban are:
1. If the problem itself explicitly refers to fractions, like in Problem #16 on
page 13.
2. If the problem is dealing with the set of rational numbers, Q, or it's
complement in R, the irrational numbers.
And even in these exceptions you should minimize the use of fractions. There
are very few problems that fit into these two categories, so the rule of thumb
is "NO FRACTIONS"!
--Rational Guy
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, September 24, 1998 11:05 PM
Subject: Re: question for problem #18 on page 13
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Thursday, September 24, 1998 8:07 PM
Subject: question for problem #18 on page 13
>Dr. Monks,
>I have a question about the wording of problem 18
>Does the question say
>If c>0, prove that gcd(ca,cb)=c(gcd(a,b)) ?????
Yes.
--Greatest Common Advisor
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, September 26, 1998 12:18 PM
Subject: preventing a mistake
I am grading your current homework and there is one error that a lot of you are
making over and over again in your problems, so I want to tell you about it in
case it comes up in any of your current homework problems so you don't keep
making the same mistake.
Namely, given a, b, you can't use Theorem 1.3 to say that a number d can be
written as d=au+bv for some u and v unless YOU ALREADY KNOW x is the gcd(a,b)!
In particular you can't use Thm 1.3 to prove that a certain number is the
gcd(a,b). Thm 1.3 says that IF d=gcd(a,b) THEN #u,#v,d=au+bv. It doesn't work
for ANY integer d.
To see that it doesn't work for any old integer d, consider a=2 and b=4 and
d=1. Can you find u,v such that d=au+bv? Well if you did then 1=2u+4v by
substitution so
1=2(u+2v) and so 2|1. But 2~|1. So -><-. So there are no u,v which work.
So don't use Thm 1.3 to prove something is a gcd. It doesn't work.
-Currently Grading In Hazleton
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, September 26, 1998 12:28 PM
Subject: more on Thm 1.3
One more thing, I was referring to the first part of Thm 1.3 in the previous
message. Namely, if d=gcd(a,b) then d=au+bv for some u,v. You CAN use the
second part of the theorem (that gcd(a,b) is the smallest positive integer of
the form au+bv) to prove that a given number is the gcd by showing it is the
smallest integer of this form. But you can't say it is in this au+bv form by
thm 1.3 unless you already know it is the gcd.
--Greatest Common Difficulties
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, September 26, 1998 11:25 PM
Subject: Re: ? on Proof by contradiction hwk 8 #2
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Saturday, September 26, 1998 10:44 PM
Subject: ? on Proof by contradiction hwk 8 #2
>Prof Not:
Hey, that could almost be construed as derogatory! :-)
>I'm attempting a proof by contradiction and I was wondering how much of the
>following is correct:
>(I'm trying to show p | bc)
>1 let p be an Integer such that p is prime
>2 let b,c be any Integers
>3 Assume p ~| bc (p does not divide bc)
>4 p ~| b and p ~| c (p does not divide b and p does not divide c)
> by Thm 1.8
>
>Thm 1.8 is: p is prime and p|bc <=> p| b or p|c
This is NOT what Thm 1.8 says. It says,
p is prime <=> (@b@c, p|bc => p|b or p|c) and ~(p in {0,1,-1})
But you can conclude from this that:
p is prime and p|bc => p| b or p|c
but you can't get <=> like you have above because the reverse implication is
certainly false. Just try some non-prime values for p to see.
>Can I say what Isay on line 4?
> Thanx the weekend warrior
You can say it, but you don't need Thm 1.8. That is overkill. The reason you
can say it is because:
Lemma 1: x|y => x|yz
Pf:
Let x,y,z in Z
Assume x|y
xm=y for some m in Z def of |
xmz=yz mult both sides by z
x(mz) = yz algebra
x|yz def of |
QED
Using this we can show:
Lemma 2: p|b or p|c => p|bc
Pf
Let p,b,c in Z
Assume p|b or p|c
Case 1: Assume p|b
p|bc by Lemma 1
Case 2: Assume p|c
p|bc by Lemma 1
p|bc by or-
QED
So your line 4 follows from the contrapositive of Lemma 2 which says:
p ~|bc => p~|b and p~|c
Notice that Lemma 1 and two are true for any integers at all regardless of
whether or not the are prime. So your line 4 is true regardless of whether p
is prime or not and thus doesn't require the power of Thm 1.8.
--Sat Night Prof
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, September 27, 1998 11:34 AM
Subject: Re: ? on hwk 8 #2 <=
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, September 27, 1998 10:34 AM
Subject: Re: ? on hwk 8 #2 <=
>Let me see ifI understand the <= direction of pblm #2 (Modern Algebra)
>
>If @a in Z and @p in z - {1,-1,0} if gcd(a,p) = 1 or p|a then p is prime.
>
>If this is indeed what I need to prove then does the following counter
>example make th <= false:
>let a = 9
>let p = 4
>4 ~| 9 but gcd(9,4) = 1
>But 4 is still not prime (as of 27 September 98)
>How can I prove <=if I know it is false? thanx
You are not interpreting the <= direction of the problem correctly. It doesn't
say:
@a in Z,@p in Z-{1,-1,0},gcd(a,p) = 1 or p|a => p is prime
which is what you are saying above. It says:
@p in Z-{1,-1,0},(@a in Z, gcd(a,p) = 1 or p|a) => p is prime
which is quite different! Notice with this correct interpretation, your
"counterexample" no longer holds, because p=4 is certainly not prime, but it is
also not the case that FOR EVERY a, either gcd(a,4)=1 or 4|a (because we can
take a=2 for example). So it is a problem with misplacing the scope of the
quantifier on a.
Thus in English, this roughly says that if gcd(a,p)=1 or p|a FOR ANY a YOU
MIGHT CHOOSE, then p is prime. So you can't just pick one particular a that
the hypothesis holds for... it must hold for them all!
--giver of all a's
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, September 27, 1998 11:36 AM
Subject: email protocols revisisted
Please refer to the Page # in the book and the problem number when asking a
question by email. Do not refer to Assignment #7 or HMK #7 or something like
that because I then have to look up to see what assignment is which to find
your problem.
--Swamped with Email
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, September 27, 1998 11:45 AM
Subject: Re: ? 10c hwk2
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, September 27, 1998 11:24 AM
Subject: Re: ? 10c hwk2
>Prof. Lemma:
>I need the following lemma I was wondering if my logic is correct, or if I
>even need to go into this much detail:
>
>lemma: let x,y be Integers. gcd(xy , x) = x
>Pf:
> let x,y,c,d be Integers
> x | xy since xy = x * y (x times y)
> x | x since x = x * 1 (x times 1)
> Assume c | xy and c | x
> x = cd by def of c|x
> Since c,d are Integers, the largest value c can be is x when d = 1
> so at most, c = x so c <= x
> Therefore, gcd(xy , x) = x
> thanx
Well this Lemma is false for example when x is negative, because gcd is always
positive. So to fix this Lemma you either have to assume the variables are
positive or else put absolute values in key spots where needed.
Also, even if we assume x,y are positive, then in this part of the proposed
proof:
> Assume c | xy and c | x
> x = cd by def of c|x
> Since c,d are Integers, the largest value c can be is x when d = 1
> so at most, c = x so c <= x
you are making life WAY to hard because you don't need to show c<=x, you only
need to show c|x by Corollary 1.4. But you are assuming that, so you are done
right after the first line.
--Works on Sunday too
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, September 27, 1998 5:35 PM
Subject: Re: ? Modern p18 #12a
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, September 27, 1998 3:18 PM
Subject: Re: ? Modern p18 #12a
>This problem gives the following hint:
>Hint: If 3 does not divide A, then A= 3k+1 or A = 3k+2
>Can we use this without proving it? i.e. is this a fact?
> thanx
You should prove it, but it should only take you about two lines to prove.
--Doesn't believe in facts
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, September 27, 1998 5:44 PM
Subject: Re: Modern p18 11a
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, September 27, 1998 2:24 PM
Subject: Modern p18 11a
>Prof Questions:
>Is the following reasoning valid?
>
>let P1..Pk be distinct positive primes
>let Ni , Ri >= 0, k in Z
>let k be in Z
>Assume (P1^N1)(P2^N2)...(Pk^Nk) | (P1^R1)(P2^R2)...(Pk^Rk)
>
>Then can I say from what I know about algebra that:
>
>(P1^N1) | (P1^R1) and (P2^N2) | (P2^R2) ... and (Pk^Nk) | (Pk^Rk)
No. You should prove it. In fact, the only things you don't have to prove
are:
1. elementary facts about arithmetic that don't have to do with primes, prime
factorization, the fundamentally theorem of arithmetic, gcd's, lcm's, the
division algorithm, or divisibility. Facts like a+b=b+a and 1*a=a are ok to
use.
2. Facts from logic that involve multiple steps that we agreed to skip in order
to shorten the lengths of our proofs.
Other than that, just assume you don't know anything and prove everything by
valid reasons.
--Doesn't know anything too
--------------------------------------------------------------------
From: Monks Kenneth G [monks@UofS.edu]
Sent: Tuesday, September 29, 1998 10:50 AM
Subject: Re: Modern p530 #2
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Tuesday, September 29, 1998 10:36 AM
Subject: Re: Modern p530 #2
>Conductor Monks:
>
>In problem 2, the author asks us to define an Equivalence relation
> "r is related to s" iff (r - s) is an Integer
>
>Now, do I need to come up with an equivalence relation or is r-s the E.R?
~ is the equivalence relation. It is given to you in the problem and you are to
prove that it is an equivalence relation. They are telling you that for every
r,s in Q, r~s iff r-s is an integer. You have to show ~ is an equiv reln.
>If I do need to come up with on, is it valid to use the following as an E.R.
>( I understand that I have to to prove it is an E.R by the recipe, but I
>would like to make sure I am on the right track:)
>
>let a,b,c,d,ef be Integers
>let r,s be rational numbers such that r = a/b and s= c/d
>
>then I will try and prove that
>cd | (ad - cb) is an E.R. by showing it is Reflexive, Symmetric, and
>Transative. thanx
You are not on the right track, you don't need to define the relation. It is
already given to you in the problem.
-The Conductor
--------------------------------------------------------------------
From: Monks Kenneth G [monks@UofS.edu]
Sent: Tuesday, September 29, 1998 11:08 AM
Subject: Re: Modern p530 4
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Tuesday, September 29, 1998 10:52 AM
Subject: Re: Modern p530 4
>Prof Modern:
>
>Which definition should we use for parallel in this problem.
>In geometry, we said parallel is defined as follows:
>for all Lines(l), all Points(P), ~(P is On(l)) => there exists a unique m
>such that P is On(m) and m||l
This is NOT how we defined parallel in geometry! This is the Euclidean
Parallel postulate, not the definition of parallel. The definition of parallel
in geometry is:
Def: Two lines (in the plane) are parallel if and only if they do not
intersect.
This is the definition you should use when doing problem number 4.
--GeoAlgebraist
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Wednesday, September 30, 1998 10:43 AM
Subject: Re: #13 page 531
-----Original Message-----
To: monks@LION.UOFS.EDU <monks@LION.UOFS.EDU>
Date: Tuesday, September 29, 1998 9:47 PM
Subject: #13 page 531
>Dr. Monks, I seem to always have problems with the function of x and x. If
you
>could please tell me if it is logically to start the proof for #13 page 531
>like:
>Assume @f(x)@g(x), f(x)Eg(x) iff f'(x)=g'(x)
Yes, this is given, but the book used bad notation here.
>let r in E
No. You want r in R[x].
>r=r by substitution
Not by substitution, it is because of the identity property of =.
>rEr by def of E
No. You have to show that r'=r' in order to say this.
>E is Reflexive
If you got this far, this would be right.
>Is that correct?
--Math Man
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Thursday, October 01, 1998 9:47 AM
Subject: Re: Modern p29 pblm 6
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Wednesday, September 30, 1998 6:26 PM
Subject: Modern p29 pblm 6
>Prof Monks:
>
>If I know a is congruent to b mod p then by def [a] = [b]
No, not by definition! By Thm 2.3 which I proved in lecture.
>so, by definition,
>[a] = [a + pk such that k is an Integer] and
>[b] = [b + pk such that k is an Integer]
>
>My question is this: Are the k's I mentioned above equal? If not, why not?
>thanx
This is a poorly worded question so I can't answer it yes or no (It's like if
someone asked you if you miss having three eyes, you can't really answer yes or
no because the question is wrong.)
What you mean to say is this:
1. @k in Z, [a] = [a + pk]
2. @k in Z, [b] = [b + pk]
In which case you still can't ask if the k's are equal or not because they are
BOUND variables, which means they are not defined outside the scope of the
individual statements, so by the time you get to line #2, the k in line number
1 is no longer defined. Compare this with a, b, p, which are free variables in
these two lines and thus e.g. the a in line 1 DOES equal the a in line 2.
Alternatively you might have meant:
3. [a]={a+pk : k is an integer}
4. [b]={b+pk : k is an integer}
But again, the k's in these two lines are not the same k, although it is less
obvious in this case. But to see they are actually bound variables notice that
the correct way to write this is:
5. [a]={x : #k in Z, x=a+pk}
6. [b]={x : #k in Z, x=b+pk}
and clearly in #5, and #6 k is bound, and so the same thing applies. Note that
mathematicians often write #3, and #4 when they mean #5 and #6, so this is
another indication of taking sloppy shortcuts and the confusion that can arise.
Technically speaking there is only one element in {a+pk : k is an integer}.
Notice also that another way to see that the k's aren't equal in the sense you
mean is that the lines:
5. [a]={x : #k in Z, x=a+pk}
6. [b]={x : #k in Z, x=b+pk}
could be replaced by
5'. [a]={x : #k in Z, x=a+pk}
6'. [b]={x : #j in Z, x=b+pj}
without changing the meaning at all. Since you would not say that k and j are
equal, you would not say that the k's are either in the sense of your question.
-K
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, October 01, 1998 9:55 AM
Subject: Re: Modern p29 no. 4
-----Original Message-----
To: Monks Kenneth G <monks@lion.UOFS.EDU>
Date: Wednesday, September 30, 1998 8:02 PM
Subject: Modern p29 no. 4
>Prof monks:
>
>In problem 4, the author is asking us to prove every odd prime is congruent
>to 1modulo4 or 3modulo4
>
>Now, my question is on how we should define every odd prime. Will the
>following definition suffice and/or help me in my quest to solve this
>problem:
>let m be an Integer
>let S be the set of all x such that x = 2m+1 and only 1|x, -1|x, x|x, -x|x
Well this isn't quite right. If you let m be an integer and then define
x=2m+1, then x is only one integer.
I would define an odd prime like this:
Def: p is an odd prime <=> p is odd and p is prime.
Since we never defined odd in class, we should say:
Def: p is odd iff p is not even.
of course that leads us to define:
Def: p is even iff 2|p.
[of course in all of these definitions, the domain of discourse of p is Z.]
Note that it is then a THEOREM that:
Thm: p is odd iff #m in z, p=2m+1
and you should prove this theorem or find it already proven somewhere in the
book if you want to use this fact.
>Will this help me? thanx
That has yet to be seen. :)
--Helper
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, October 01, 1998 12:06 PM
Subject: Re: Modern pblm 2 p 29
-----Original Message-----
To: Monks Kenneth G <monks@LION.UOFS.EDU>
Date: Wednesday, September 30, 1998 8:07 PM
Subject: Re: Modern pblm 4 p 29
>Prof Monks:
>I was wondering if the following proof by contradiction in fact provides a
>solution to this (pblm 4)
>(The reason I am concerned is that I never relied on the fact that my choice
>of x was prime)
Good observation. These are the kinds of things to be aware of when doing
proofs.
>let x be an odd prime
>Assume x is not congruent to 1 mod 4 and x is not congruent to 3 mod 4
>let m be an Integer
>x = 2m + 1 by def of x as an odd prime number
No, you mean x=2m+1 for some integer m, not Let m be an integer and then
x=2m+1. In other words you want to say that
#m in Z, x=2m+1.
(which you must justify with a proof or a lemma or a reference to somewhere in
the book where it is proven). But the way you have it:
Let m be an integer
x= 2m+1
I could conclude from your two statements that @m,x=2m+1 by @+, which is
clearly silly.
>x - 1
This is not a statement.
>2m+1 - 1 by substitution
This is also not a statement.
>let k be an integer
>let m = 2k
So now what, we are going to redefine m so it isn't the same m that we picked
above? I don't think that is what you mean. You mean "Assume m=2k for some
integer k".
>4k = 2 (2k)
>4 | 2 (2k) by def of |
>4 | 2m by substitution
>4 | (2m + 1 - 1) by algebra
>4 | x-1
>x is congruent to 1 mod 4 -><-
>Now, this contradicts my only assumption therefore
>x is conguent to 1 mod 4 or 3 mod 4
No, this contradicts your unstated assumption that m=2k.
-Q.E.D. Monks
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, October 01, 1998 2:56 PM
Subject: Re: An ODD question
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Thursday, October 01, 1998 2:38 PM
Subject: An ODD question
>Prof Monks:
>
>In the FAQ you have quite a discourse on how and why to prove
>m = 2k+1 is how to represent an odd number m for @k that are Integers.
>Can we then in our HWK from now on assume that this is the correct
>representation of odd without having to prove it?
> thanx
If I PROVE it in the FAQ, then you can refer to that proof rather than simply
copying it into your homework from the FAQ. However, if I DON'T prove it, then
you had better prove it yourself as a lemma if you want to use this fact in
your proofs. Dem is just da rules!
I will not tell you if I prove it or not in the FAQ, so you had better read the
FAQ yourself if you want to find out. There are a lot of good detailed
discussions of what we are doing in the FAQ and I encourage everyone to read
the parts of it that are relevant to the current homework as you go through the
course.
Anyway, I'm glad someone is still reading the FAQ!
--Just the FAQs
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, October 01, 1998 8:13 PM
Subject: Re: Modern pblm 4 p 29
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Thursday, October 01, 1998 5:06 PM
Subject: Re: Modern pblm 4 p 29
>Prof Monks:
>
>In pblm 4, we are asked to prove that every odd prime is congruent to 1mod4
>or 3 mod4.
>Now, isn't it the case that all prime numbers, except for 2 are odd?
No, -2 is prime but it isn't odd.
>I think I know your answer to this though: Prove every prime, other than 2
>is odd right?
Well, I would probably say "Prove every prime other than 2 or -2 is odd." but
you have the right idea. Well done, Grasshopper! :-)
--Master Po
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Monday, October 05, 1998 8:44 AM
Subject: Re: modern p36 pblm 4
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Sunday, October 04, 1998 10:59 PM
Subject: modern p36 pblm 4
>Prof Monks:
>
>In the showing the following, do we need to show => and <= or is =>
sufficient:
>
>[a] (+) [b] = [b] (+) [a]
>
>
> thanx
It is not an <=> statement, so you don't have to show either one. The
statement is an equality of two sets, so you must prove each is a subset of the
other.
--Show-man
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Monday, October 05, 1998 8:47 AM
Subject: Re: Modern p36 number 10
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Sunday, October 04, 1998 11:00 PM
Subject: Modern p36 number 10
>In 10a we are asked to find all a in Z5 for which ax = 1 has a solution. Can
we >assume then that x has values 0,1,2,3,4? and therefore must show the
cases:
>0*0 = 1
>0*1 = 1
>0*2 = 1
>.
>.
>.
>1*0 = 1
>1*1 = 1
>.
>.
>.
>4*4 = 1
Your don't have to show all the cases. You only need to find ONE solution for
each a that has one and check all the cases for the a's that don't.
-Casey Kasem
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, October 06, 1998 3:38 PM
Subject: Re: p39 pblm 4
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Tuesday, October 06, 1998 2:48 PM
Subject: p39 pblm 4
>Prof Monks:
>
>The problem tells us n is composite and wants us to prove that there exists
>a,b in Zn such that a !=0 and b !=0 but ab = 0
>
>My question to you is:
>since the subscript n in Zn is positive, i.e. n>0 ca nwe rephrase the
>question:
>
>If n is a positive composite integer, prove there exists a,b in Zn such that
>a != 0 and b!= 0 but ab = 0.
Yes. Zn is not defined for n<1.
--Zn Man
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, October 08, 1998 3:42 PM
Subject: Re: Modern PBLM 8 p 51
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Thursday, October 08, 1998 2:48 PM
Subject: Modern PBLM 8 p 51
>Prof Monks:
>
>Is it a property of 0s that 0s + 0s = 0s?
> thanx
Yep.
--0monks
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, October 08, 1998 3:51 PM
Subject: Re: Modern PBLM 8 pg 51
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Thursday, October 08, 1998 2:43 PM
Subject: Modern PBLM 8 pg 51
>Prof Pinky Ring:
>
>If we know that R is a ring and S is a ring, do we know that RxS ("R cross
>S") is a ring?
> thanx
That depends entirely on how you define the operations of addition and
multiplication in RxS. For some definitions it will be a ring and for others
it won't. There is a somewhat standard way to define it, namely the way they
define it in Theorem 3.1. In that case it is a ring (just like the Theorem
says). But there are many ways to define the addition and multiplication on
RxS and in any given problem you may or may not be considering the standard
definition.
--The Ringmaster
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, October 08, 1998 10:45 PM
Subject: Re: Modern pblm 24 p 53
-----Original Message-----
To: MONKS@EPIX.NET <MONKS@EPIX.NET>
Date: Thursday, October 08, 1998 9:56 PM
Subject: Modern pblm 24 p 53
>Prof Monks:
>
>In the multiplication table given for the problem, is it the case by the
nature
>of the tables that the entry into the table:
>t(column) . s(row) has the same value as
>t(row) . s(column)
>
>It appears as though this is the case. For example,
>s(row) . r(column) = r and s(column) . r(row) = s
>
>I hope this makes some sort of sense.
I'm not totally sure what you are trying to ask here since if you are asking
what I think you are trying to ask then this is not the way to ask it. :)
What I think you are trying to ask is if the multiplication in a ring has to be
commutative, ie in this case if x.y=y.x for every x,y in {r,s,t}. The answer
is NO, A ring doesn't a have to have a commutative multiplication. As I said
in class, matrix rings don't have a commutative product. So for example, you
can't use commutativity of the product to help fill in the table in problem 24
because you don't know that the product is commutative.
--Commuter from Hazleton
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, October 20, 1998 9:46 AM
Subject: Re: problem 9 page 76
-----Original Message-----
To: DR.KEN MONKS <"IN%monks@uofs.edu"@TIGER.UOFS.EDU>
Date: Monday, October 19, 1998 3:44 PM
Subject: problem 9 page 76
>Dr, Monks
>One part of my proof for problem #9 I'm not sure is correct. For example, I
>used the definition of surjective (because f as a function is given to be
>isomorphic) in my proof.
>Let a, b in Z
>@b, b in Z=>#a, b=f(a) by def of surjective
>a=f(a) since a in Z
>*****can I say this last step because I assumed a was in Z
No you can't.
>@a, a=f(a) @+
>f is an identity map
>thanks
The right way to prove this is by induction. First show that f(n)=n for all the
natural numbers. Then show f(-n)=-n for all the natural numbers.
--Just a Natural Kinda Guy
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, October 21, 1998 10:57 PM
Subject: Re: Problem 11 page 525
-----Original Message-----
To: DR.KEN MONKS <"IN%monks@uofs.edu"@TIGER.UOFS.EDU>
Date: Wednesday, October 21, 1998 4:08 PM
Subject: Problem 11 page 525
>Dr. monks I am having a hard time defining what my statement P(n) would be
>in this problem. Could I let P(n) be the statement of f(B)=n! where
>B={b1, b2, ...bn} and since f is injective, then f(b1)=n,
>f(b2)=n-1, f(b3)=n-3....
>Is there any way to find the right result by defining P(n) as f(B)=n! ???
>thanks
No. You are misunderstanding what it is asking. It wants to know how many
injective functions there are from B to B. So P(n) would be the statement "If
B has n elements then there are n! injective functions from B to B.".
--2B|~2B
P(n)
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Friday, October 23, 1998 8:01 PM
Subject: Re:
-----Original Message-----
To: monks@LION.UOFS.EDU <monks@LION.UOFS.EDU>
Date: Friday, October 23, 1998 6:53 PM
>Prof Monks:
>
>In problem 4a on page 88, what is meant by the maximum of deg f(x) and deg
>g(x)?
The maximum of two numbers is whichever number is bigger, i.e.
{ a if a>b
max{a,b} = {
{ b if a<=b
So "the maximum of deg(f(x)) and deg(g(x))" is whichever number is bigger (or
either number if they are equal).
>i thought that the deg f(x) is defined as being the largest exponent
>of x that appears with a nonzero coefficient,
Good think you thought that, cuz that is what it is! :-)
>so wouldn't
>the deg of f(x) + g(x) always be equal to the deg of f(x) and deg g(x)?
Uhhh, I am not sure what your "and" means in this sentence. If it means "+"
then no. If it means "deg(f(x)+g(x))=deg(f(x)) and deg(f(x)+g(x))=deg(g(x))"
then no again since deg(f(x)) and deg(g(x)) don't have to be equal.
Just try some various actual nonconstant polynomials f(x) and g(x) and you will
see what is going on.
--Math Degree
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Monday, October 26, 1998 8:03 PM
Subject: Re: Modern p93 number 3
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Monday, October 26, 1998 5:03 PM
Subject: Modern p93 number 3
>Dr Adhesive Remove:
>In trying to find the gcd(x+a, x+b) I applied the Euclidean Algorithm as
>follows:
>
> 1
> __________
>x+a ) x + b
> x + a
> ----------
> b - a
>
>Here, x+a does not divide into b-a yet b-a is not necessarily 0.
>So therefore my remainder is b-a
>But I cannot apply the Euclidean Algorithm again right?
> thanx Mr. Stuck
Well the Euclidean Algorithm is overkill for this problem. But you CAN apply
it here if you really want to. If a=b then the remainder is zero, so the gcd
is x+a. On the other hand, if a~=b then we would compute gcd(b-a,x+a). I will
leave it to you to figure out how to do this if this is the way you want to
attack the problem. The only hint I will give is to remember that the gcd must
be MONIC (aka "a Lewinski").
--MONIC MANIC MONKS
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, October 27, 1998 11:39 AM
Subject: Re: Modern p94 5d
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Monday, October 26, 1998 8:55 PM
Subject: Modern p94 5d
>Prof Negator:
>
>At one point in the problem I come to the following:
>(we are in the RING Z7)
> __________________
>-3x + 4 ) 5x^2 + 4x + 5
>
>Now, can I say that:
>
> -4x - 2
> _______________
>-3x + 4 ) 5x^2 + 4x + 5
> - 5x^2 + 2x
> ---------------
> 6x + 5
> - 6x + 1
> ---------
> 6
>
> Since -4x (-3x) = 12x^2 but 12x^2 mod 7 = 5x^2
> -4x(4) = -16x but -16x mod 7 = -2x
>
>
>Now I think I have done some of this wrong.
Well there is an easy way to check your work, just like in 4th grade...
multiply (-4x-2)*(-3x+4) and then add 6 and see if you get 5x^2+4x+5 in Z7[x].
--Work Checker
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Friday, October 30, 1998 11:08 AM
Subject: yet another reason to ban fractions...
Here is yet another reason to ban fractions...
If let r be an invertible element of an non-commutative ring with identity R
(like a matrix ring). Then r^-1 is an element of R. But if you write 1/r
instead of r^-1, then if you write the "fraction":
s
---
r
does this mean r^(-1)*s or s*r^(-1)? If the ring is not commutative, then
these can be two different things. Thus the fraction notation does not even
make sense, while the r^(-1) notation is well defined.
If you want a concrete example, consider the ring M2(R), the set of 2x2
matrices with real entries. Then the element:
r = [ 1 1 ]
[ 0 1 ]
is an invertible matrix so r^-1 exists and in fact is:
r^(-1) = [ 1 -1 ]
[ 0 1 ]
Now let s be the matrix:
s = [ 1 2 ]
[ 3 4 ]
Then you can check that
s*r^(-1) = [ 1 1 ]
[ 3 1 ]
while
r^(-1)*s = [ -2 -2 ]
[ 3 4 ]
So they are clearly not equal. Hence if s*r^(-1) is not equal to r^(-1)*s then
which one do you mean if you write
s
--- ?
r
See the problem? So when a homework problem is asking about a generic ring R,
you CANNOT write fractions because if you do then I have no way of knowing
unambiguously what you mean (because of the above example). See the problem?
So PLEASE STOP USING FRACTIONS IN GENERAL RINGS IN YOUR HOMEWORK!!!!!
--Fraction Annihilator
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, October 31, 1998 10:22 AM
Subject: Re: Modern 6 pg 98
-----Original Message-----
To: Monks@epix.net <Monks@epix.net>
Date: Saturday, October 31, 1998 12:49 AM
Subject: Modern 6 pg 98
>Prof Monks:
>If I assume x^2 + 1 is reducable in Q[x], then by THM 4.10 I can write x^2 +
>1 as (ax + b)(cx + d) for some a,b,c,d in Q.
>Now, can I also perform the following algebraic steps:
>
>(ax + b)(cx + d) = (ax)(cx) + dax + bcx +bd
> = acx^2 + (da+cb)x + bd
> = x^2 + 1
I would have written the x^2 + 1 first, but otherwise this is ok.
>Now, if all of that is true, can I then say that
> ac = 1
> (da +cb) = 0
> bd = 1
>and use that information to form a -><- ?
Can you say it? Yes.
Is it right? Yes.
Can you use it to prove a contradiction? That remains to be seen. :)
--Always the Skeptic
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, November 03, 1998 9:54 AM
Subject: Re: Modern Thm 4.15 p102
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Monday, November 02, 1998 11:13 PM
Subject: Modern Thm 4.15 p102
> Prof Theorem:
>
>Please let me know if the following example is a valid use of Thm 4.15
>correctly:
>Problem: show x^3 - 4x is irreducable or reducable in R[x]
>Pf
>
>let f(x) = x^3 - 4x in R[x] (real)
> _
>(x-2) is a factor of f(x) since f(2) = 2^3 - 4(2) = 0 by Thm 4.15
> Therefore f(x) has a factor that is not an associate nor a unit in R[x] so
>by definition of reducable, f(x) is reducible not irreducable.
> thanx
Yes, this is correct, except that there is no "a" in "irreducible" or
"reducible".
-Dr. Manks
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, November 07, 1998 11:07 AM
Subject: Re: Modern p128 2,4
****start of message *******************************************************
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Saturday, November 07, 1998 10:01 AM
Subject: Modern p128 2,4
Dr. Monks:
Do the entries for the table have to be monic? If they don't our tables will be
huge.
I.e. should our table for pblm 4 have the columns designated:
0 1 2 3 4 x 2x 3x 4x x+1 x+2 x+3 x+4 x^2 x^2+1 x^2+2 x^2+3 x^2+4
0
1
2
3
4
x
2x
3x
...
or should it have just:
0 1 2 3 4 x x+1 x+2 x+3 x+4 x^2 x^2+1 x^2+2 x^2+3 x^2+4
0
1
2
3
4
x
x+1
...
thanx
******end of message *************************************************
Since you are modding out by x^2+1 you only need linear polynomials, not
quadratic as you have listed above. So there are 25 such polynomials which
means the table has 25*25=625 entries. If you want to do this table on Maple,
I will allow it for this problem only. If you don't know how to use Maple, now
is a good time to learn. :)
I'll give you some help. I made a demo Maple worksheet that I posted at the
Modern Algebra web page. You can
modify that to do the problem if you like. Or you could make the entire 625
entry table by hand. It's your choice. :)
--Loves Maple Syrup too
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Monday, November 09, 1998 9:57 PM
Subject: Re: # 8 p.132
-----Original Message-----
To: MONKS@lion.UOFS.EDU <MONKS@lion.UOFS.EDU>
Date: Monday, November 09, 1998 9:41 PM
Subject: # 8 p.132
>Dr. Monks
>
>for # 9 on page 132 do we have to show that Z2 is a ring or we can
>assume it?
> Thanks.
Z2 is a ring by Theorem 2.7 on page 34.
--has a familiar ring to it
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, November 11, 1998 8:49 PM
Subject: Re: Modern 12b
-----Original Message-----
To: Monks Kenneth G <monks@lion.UOFS.EDU>
Date: Wednesday, November 11, 1998 4:00 PM
Subject: Modern 12b
>Prof "will receive many emails over the next two days":
>
>I'm a little confused on what (4,6) means.
>Is (4,6) the intersection of (4) and (6) in Z?
Ah, yes. Just what we need. Yet another use for the symbol (x,y). It is an
ordered pair... it stands for gcd(x,y) in our textbook... Now here is yet one
more use for this poor overworked and underpaid symbol!
The definition is in the paragraph under the "proof" (some proof!) of theorem
6.3 on page 138. Namely (x,y) is the ideal in a ring R generated by generators
x and y, i.e.. (x,y)={ax+by | a,b in R}. So in your case (4,6) is the ideal of
Z generated by the elements 4 and 6 (which is certainly not the intersection of
the two ideals).
>And correct me if I'm wrong but in Z:
That's my job! :)
>(4) = (...-8,-4,0,4,8,12,16,20....)
>(6) = (...-12,-6,0,6,12,18,....)
>so if my understanding is correct:
>(4,6) = (...-24,-12,0,12,24,....)
No, your understanding is not correct. (4,6)={4a+6b | a,b in Z} which contains
a lot more than what is in your set above.
--Idealistic
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, November 11, 1998 8:51 PM
Subject: Re: Modern 12b
-----Original Message-----
To: Monks Kenneth G <monks@lion.UOFS.EDU>
Date: Wednesday, November 11, 1998 6:25 PM
Subject: Modern 12b
>We are asked to show (4,6) = (2) in Z.
>But how did we define equality for ideals?
Ideals are sets, so equality of ideals is just equality as sets, i.e. two ideal
are equal iff they contain the same elements.
--Equality and Ideals for ALL!
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, November 11, 1998 8:54 PM
Subject: Re: Modern 14 pg 142
-----Original Message-----
To: Monks Kenneth G <monks@lion.UOFS.EDU>
Date: Wednesday, November 11, 1998 8:08 PM
Subject: Modern 14 pg 142
>Is it a fact that 0 is an element of any ideal?
Yup. An ideal is a subring. Subrings have 0 in 'em.
>E.g. in 14 we assume
> I (eye) is an ideal in a field F
> 0 is in I (eye)
>
>( I feel like a pirate with all these eye's)
Yes you can assume that.
--Patch I
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, November 11, 1998 9:01 PM
Subject: Re: Modern 15a
-----Original Message-----
To: Monks Kenneth G <monks@lion.UOFS.EDU>
Date: Wednesday, November 11, 1998 8:31 PM
Subject: Modern 15a
>Is it I is not an ideal in R
> then for any r in R and i in I
>is it true that ri is not in I and ir is not in I?
I can't parse your question...
I think you are asking:
>If I is not an ideal in R
>then is it true that for any r in R and i in I,
>ri is not in I and ir is not in I?
If so then the answer is HECK NO!
I is an ideal of R <=> I is a subring of R and @r in R,@i in I,(ri in I and ir
in I)
So
~(I is an ideal of R) <=>
~(I is a subring of R and @r in R,@i in I,(ri in I and ir in I)) <=>
~(I is a subring of R) or ~(@r in R,@i in I,(ri in I and ir in I)) <=>
~(I is a subring of R) or #r in R,#i in I,~(ri in I) or ~(ir in I)
So I is not an ideal of R iff either I is not a subring or there exists at
least ONE element r of R and at least ONE element i of I such that either ri is
not in I or ir is not in I.
--Logical Idealist
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, November 12, 1998 10:28 AM
Subject: Re: Modern 31 p143
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Thursday, November 12, 1998 8:21 AM
Subject: Modern 31 p143
>On p143 pblm 31 states let "a" be in R and show that
>A={ ra + na | r in R and n in Z (integers)}
>Now, assuming I can show A is a subset of R I would like to apply THM 6.1
>So, if I want to show (v,u are in I) => ( (v - u) is in I)
>Do I use the same "a" value? i.e.
>let v in A then
>v = ra + na for some r in R n in Z
>let u in A then
>u = ca + ba for some c in R b in Z
Yep.
-Easy "a" Monks
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, November 12, 1998 10:22 PM
Subject: Re: Modern 35 p143
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Thursday, November 12, 1998 3:45 PM
Subject: Modern 35 p143
>The pblm states that R us a commutative ring with identity 1 != 0 whose only
>ideals are (0) and R. I'm not sure what the above statement means. How is
>R an ideal?
R is trivially an ideal of R because it satisfies both conditions for being an
ideal... it is a subring of R and @r in R, @i in R, ri in R and ir in R.
(0)={0R} has the same properties and so trivially is always an ideal also.
--Trivially Pursuit
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, November 15, 1998 1:49 PM
Subject: Re: Modern 4b p151
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, November 15, 1998 1:30 PM
Subject: Modern 4b p151
>Dr. Monks:
>Please tell me if I am interpreting this problem correctly:
>
>e.g. let a = 3
>Then the congruence class of 3 mod 12 is
>{... 3,15,27,39,51,....}
>
>The congruence class of 3 mod 4 is
>{...3,7,11,15,....}
>
>But f: z12 -> z4 is
>f(3) = 3 mod 4 = 3
>f(15) = 15 mod 4 = 3
>f(27) = 27mod 4 = 3
>.....
>
>Is this how I should be looking at f:Z12 -> Z4?
Well, if you are taking the abbreviation that we sometimes use (where [a] is
just denoted by a) then this isn't really wrong except that you are mixing
integers and equivalence classes from two different rings in the same equation
using the same symbols for all three. So a better way to look at it is this
way:
f([3] )=[3]
12 4
i.e.
f({... 3,15,27,39,51,....})={...3,7,11,15,....}.
So if you are using the canonical equivalence class representatives to
represent the equivalence classes in each case and using the abbreviations
above then you would have things like:
f(3)=3
f(9)=1
which is ok as long as the reader (i.e. ME) knows what you mean from context.
--never in any context
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, November 15, 1998 2:09 PM
Subject: Re: Modern 2 p151
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, November 15, 1998 1:39 PM
Subject: Modern 2 p151
>Dr. Monks:
>I don't understand pblm 2 on page 151 at all. I am trying to use your
>recipes to solve the problem. Therefore is the following a correct start?
>
>let F be a field.
>let f be a homo. that maps F to S
>
> >Now since f is a homo. are we given for free that some function
>g maps S to F that is a homo.?
Yes, but what you are asking is not what you mean to ask. Since the function
g(x)=0 for all x, is ALWAYS a homomorphism of rings, such a g exists, because S
is a ring by Cor 3.13.
> >If yes then all I need to do is show that g is surjective by
>the recipes right?
No, this is not the way to attack the problem. Besides, while there will
always exists a homo. g from S to F (namely the zero homomorphism) there is NOT
always going to be a homo. g:S->F which is ONTO.
I would use the Hint's given in the problem and possibly some other really
famous and important theorem about isomorphism.
>if this is indeed the case I'll take my best stab at these problems.
>However, I still don't understand the problem/see the point of the question.
I don't see what there is not to see about the question? You have a field F.
You know that the image of F under a homomorphism is always itself a ring, and
you are curious to know which, of the infinitely many rings out there, could
possibly be the image of F under a homomorphism. So you check and it turns out
that there are only two possibilities... either the homomorphic image is
isomorphic to {0} or its isomorphic to F itself.
For example, if F=Q then you CANNOT have an onto homomorphism from, say, Q to
Z2. (Because the image can't be Z2 since it has to be isomorphic either to Q or
to {0}.) This is very important. For example, if we have a ring R and a
homomorphism f from R onto Z2, then we can define ODD and EVEN in our ring by
saying that x in R is odd iff f(x)=1 and x is even otherwise. But since we
know by this problem that there DOES NOT EXIST ANY homomorphism from Q onto Z2,
we see that it is impossible to define ODD and EVEN for rational numbers in
general (in a way that is consistent with what we mean by odd and even). So
not only does this homework problem make sense, but it has important
implications.
--odd prof
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, November 15, 1998 3:26 PM
Subject: Re: Modern p151 6b
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, November 15, 1998 2:45 PM
Subject: Modern p151 6b
>Dr. Mod:
>
>If I did part a correctly, I need 24 tables (12 addition and 12
>multiplication). Now I would just like to make sure that I am on the right
>track before I do 24 tables incorrectly:
No, you don't have 24 tables. Because in many cases the principle ideals (a)
and (b) will be the same ideal, i.e. they will be equal as sets. Thus Z12/(a)
and Z12/(b) will be the same thing in that case. So you won't need 24 tables.
>In Z12 there is the principle Ideal (4) = {0,4,8}
>The addition table would look like the following:
> 0 1 2 3 4 5 6 7 8 9 10 11
>0
>1
>2
>3
>4
>5
>6
>7
>8
>9
>10
>11
NO! This table is TOO BIG. How many elements are in Z12/(4)? I claim there
are only 4 elements...
[0]={0,4,8}
[1]={1,5,9}
[2]=(2,6,10}
[3]={3,7,11}
So that the table is only 4x4, not 12x12.
--4x4 runner
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, November 15, 1998 4:23 PM
Subject: Re: Modern p151 6b
Regarding the following comment I made in my last email message:
>NO! This table is TOO BIG. How many elements are in Z12/(4)? I claim there
>are only 4 elements...
>
>[0]={0,4,8}
>[1]={1,5,9}
>[2]=(2,6,10}
>[3]={3,7,11}
I am using the [] notation for equivalence classes here. If I wanted to use
the coset notation that is in the book, I would instead write:
0+(4)={0,4,8}
1+(4)={1,5,9}
2+(4)={2,6,10}
3+(4)={3,7,11}
It means the same thing, but I figured I should mention this since that is the
notation used in the book.
--K+(Monks)
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, November 17, 1998 7:25 PM
Subject: Re: Modern 13b p 172
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Tuesday, November 17, 1998 5:12 PM
Subject: Modern 13b p 172
>Dr. Congruent:
>
>In the problem 13b, are all sides of the figure congruent?
>
>
> A------------------B I.e is AB congruent to CD
> \ \ CD congruent to AB
> \ \ AC congruent to BD
> \ \ etc? thanx
> C------------------D
AB is congruent to CD and AC is congruent to BD but AB is not congruent to AC
(according to my 2 cent plastic ruler).
--Givin my 2 cents worth
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Wednesday, November 18, 1998 8:37 AM
Subject: Re: #30
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Tuesday, November 17, 1998 10:58 PM
Subject: #30
>One more question about # 30, but I guess this applies to number 10 also. How
>would one represent and infinite T. Do the elements of T have to be in the
>reals?
NO! The subsets of the set of real numbers are not the only infinite sets.
There are LOTS of infinite sets... the set of all 3x3 matrices with integer
entries, the set of all functions from the rationals to itself, the set of all
subsets of points in the plane, the set of all triangles, etc etc etc. So you
can't "represent" an arbitrary infinite set T in any specific manner other than
to just call it T. But you can prove things about every element of T even if
you don't know what the elements are. For example:
Thm: T is a subset of T.
Pf:
Let x be arbitrary.
Assume x in T.
x in T by stupidity rule
x in T => x in T =>+
@x,x in T => x in T @+
T is a subset of T def of subset
QED
So here we proved a fact about the set T without knowing what was in T, or even
if T is infinite or not. So sometimes it is just enough to know that T is a
set and leave it at that. That is the case in these questions.
--Mr. T
--------------------------------------------------------------------
From: Ken Monks [monks@UofS.edu]
Sent: Wednesday, November 18, 1998 8:42 AM
Subject: Re:
-----Original Message-----
To: MONKS@EPIX.NET <MONKS@EPIX.NET>
Date: Tuesday, November 17, 1998 10:12 PM
>I HAVE A QUESTION ABOUT PROBLEM ON PG 173 #24. WHAT CAN WE TAKE AS GIVEN AND
>WHAT PART ARE WE TO PROVE?
You are given that G and H are groups and you are given the definition of the
product on GxH. You must then prove that GxH is a group with this operation.
Then given that G and H are abelian, prove that GxH is too.
Then given that G and H are finite, prove that GxH is too.
--Given Take
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, November 21, 1998 5:33 PM
Subject: Re: Modern p188 4
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Saturday, November 21, 1998 1:10 PM
Subject: Modern p188 4
>Dr Monks:
>I was wondering if the following is true:
>let G be a Group
>let K,H be nonempty subgroups of G
>let H union K be a subset of G
>let a be in K and b in H
>a,b are both in H union K
>Since H union K is a subgroup of G, ab is in H union K
>So, ab is in H or ab is in K
I assume you are talking about Part b and trying to prove the => direction.
If so then your argument so far is correct.
>Here's the question:
>If ab is in H, does that imply that a and b are in H?
No.
>by def of closure if a,b are in H and H is a group then ab is in
>H, but does the converse hold?
No.
Here is a counterexample:
Let G=(Z,+)
Let H=<2>
Let a=1, b=1.
--Party Pooper
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, November 21, 1998 10:31 PM
Subject: Re: Modern 0189 pblm 33
-----Original Message-----
To: Monks Kenneth G <monks@lion.UOFS.EDU>
Date: Saturday, November 21, 1998 9:28 PM
Subject: Modern 0189 pblm 33
>Prof Sunshine:
>Can you shed some light on pblm 33? I'm not sure what is going on in the
>problem. Please let me know if the following is correct:
>Nh is the set of all x in G that make the set x^(-1)Hx equal to the set H?
Yes.
>(now show Nh is a subgroup according to the recipe sheet)
Glad people are still finding the recipe sheet helpful. :)
>let m,n be in Nh then
>m^(-1)Hm = H and n^(-1)Hn = H by def of Nh
Ok so far...
>(m^(-1)Hm) (n^(-1)Hn ) = (m^(-1)m)HH(n^(-1)n)
> = eHHe
> = e^(-1)HHe (since e^(-1)= e)
> = e(-1)He (since H is
>a subgroup it is closed so multiplying any element by any other element is
>still in H
Yuk! :(
What is HH ? Where is it defined? If it ain't defined you can't use it unless
you define it yourself. Of course if you define it yourself then you better
prove any properties of it that you want to use too. How are you getting from
the left hand side of the first equation to the right hand side? What Theorems
are you using? You can't treat the SUBGROUP H like it is just another
element of the group like m and n are. You also can't assume that the group
is Abelian, which you seem to be indicating in the above computation.
> mn is in Nh by def of Nh right?
Hardly. mn is in Nh iff (mn)^(-1)H(mn)=H. To show this you need to prove these
SETS are equal. Try the recipe for showing SETS are equal.
--Sat Night Chef
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, November 21, 1998 10:39 PM
Subject: Re: Modern 0189 pblm 22b
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Saturday, November 21, 1998 10:34 PM
Subject: Re: Modern 0189 pblm 22b
>Dr. Monks:
>The hint in this part of the problem states "let b be the congruence class
>of a
>in Zp and use part a."
>Does that mean that we should let [a] = [b]
>or does it mean that we should substitute [a] in for b in part a of the
>problem?
It means you should let b=[a] and then use the result of part (a).
--ez as abc
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, November 22, 1998 11:05 AM
Subject: Re: Modern 38 p 190
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, November 22, 1998 6:49 AM
Subject: Modern 38 p 190
>The hint in this problem tells us to show a^d is a^d power of a^m. Just for
>clarifications sake, this means show that a^d = (a^m)^k where k is some
>integer right?
Right.
--Already left
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, November 22, 1998 11:06 AM
Subject: Re: Modern 38 p190
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, November 22, 1998 7:35 AM
Subject: Modern 38 p190
>Dr. Monks:
>
>Do we know that a cyclic group <a> is an equivalence class?
For what equivalence relation?
--befuddled
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Sunday, November 22, 1998 11:11 AM
Subject: Re: Modern 38 p190
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Sunday, November 22, 1998 7:52 AM
Subject: Modern 38 p190
>Dr. Last_Question_on_This_Problem:
>
>We are given that <a> is a cyclic group of order n. This means that the set
><a> has n elements,
>not that a^n = e right?
Yes, but that implies a^n=e by Thm 7..8 and Thm 7.14.
--Motor-cyclic group member
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Tuesday, November 24, 1998 12:14 PM
Subject: orders
I had to rush out of the math lab before I proved this Lemma, so here it is:
Lemma: If G is a group and a in G has finite order then |<a>|=|a|.
Pf. By Thm. 7.14b, if |a|=n then |<a>|=n as well. So they are equal.
QED
I told you it was easy ...
--Happy Turkey
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, November 25, 1998 2:58 PM
Subject: Re: Modern 9 p196
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Wednesday, November 25, 1998 2:55 PM
Subject: Modern 9 p196
>Dr. Monks:
>In showing that g of f:G -> K is isomorphic, we need to show
>that
>g of f is a bijection. Do we need to prove this again or can we
>just take it as fact by this point that function composition is
>bijective?
We proved long ago that the composition of bijective functions is a bijection.
Use it at will.
--Gobble gobble
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Wednesday, November 25, 1998 6:13 PM
Subject: Re: Modern 13a p196
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Wednesday, November 25, 1998 3:44 PM
Subject: Modern 13a p196
>Dr. Gobble:
>In proving that P = a^(-1)Ha is a subgroup of G, I need to show
>that for all m^(-1)Hm in P,
> (m^(-1)Hm)^(-1) is an element of P
No you don't. a^(-1)Ha is equal to P, not an element of P. P is a subset of
G. You want to show it is a subgroup.
--is (HaHa)^(-1) crying?
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, December 03, 1998 7:56 PM
Subject: Re: Modern p215 29
>-----Original Message-----
>To: monks@epix.net <monks@epix.net>
>Date: Thursday, December 03, 1998 2:25 PM
>Subject: Modern p215 29
>
>
>Dr. Patton:
>
>Just a general question on subgroups that relates to pblm 29.
>
>let H be a subgroup of G
>let Nh (the normalizer) be a subgroup of G
>let H be a subset of Nh
>(show H is a subgroup of Nh)
> let a,b be in H
> ab in H since H is a subgroup of G
>
>Now is this suffient to show for the first part of the recipe?
> I.e (let a,b in H show ab in H)
Well, first of all, for email purposes we probably should write N_H for the
normalizer of H, since Nh looks like an equivalence class.
Second, you don't have to prove that H is a subgroup of N_H since you already
proved that in the homework for section 7.3. So you can assume it is a subgroup
by that problem and just show it is normal.
--Abby Normal
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Thursday, December 03, 1998 8:02 PM
Subject: Fw: Modern p215 pblm 27
>-----Original Message-----
>To: monks@epix.net <monks@epix.net>
>Date: Thursday, December 03, 1998 2:35 PM
>Subject: Modern p215 pblm 27
>
>
>Dr. Monks:
>
>This question is also related to pblm 27. Specifically in section 7.3 pblm
>33,
>>a problem we had to prove for homework, did we show that Nh is a subgroup
>of G and Nh contains H or
>that Nh is a subgroup of G and G contains H? I cannot tell from the book.
Problem 33 in 7.3 says that N_H is a normal subgroup of G and that H is a
subset of N_H, but it doesn't say that H is a subgroup of N_H. Since H is a
group, that it is a subgroup of N_H follows immediately.
--Needs a Normalizer
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Saturday, December 05, 1998 2:23 PM
Subject: Re: Modern p220 14
-----Original Message-----
To: monks@epix.net <monks@epix.net>
Date: Saturday, December 05, 1998 12:16 PM
Subject: Modern p220 14
>Dr. Monks:
>If I assume in this problem that G is a cyclic group and N is a
>subgroup of G, by THM 7.6 I know that N is also cyclic. Now, I
You mean Thm 7.16.
>was wondering what these groups look like. Is following
>correct?
>
>for a in G, G = {a^n | n in Z}
>and so for b in G N = {b^n | n in Z}
>but b in G implies b = a^k for some k in Z so
> N = {a^(kn) | n in Z}
Well this is ok if you keep your quantifiers straight. i.e.
For some k, N = {(a^k)^n) | n in Z}
is correct.
--straight man
--------------------------------------------------------------------
From: Ken Monks [monks@epix.net]
Sent: Friday, December 11, 1998 1:27 PM
Subject: Fw: Modern first example p 235
-----Original Message-----
To: Ken Monks <monks@epix.net>
Date: Friday, December 11, 1998 12:29 PM
Subject: Modern first example p 235
>This question is related to 6c but not directly. I was trying to figure out
>what A4 is. In order to do that I was trying to understand what A3 was by
>looking at the first example on page 235. Basically, I do not know how (1)
>is in An.
(1) is e which is also () since it doesn't permute anything... it's just the
identity map... so it is the product of an even number of transformations as we
proved in class., e.g. (12)(12)=(1). If you like, you can also think of it as
being a product of no transpositions, and zero is even, so either way (1) is in
An.
>Now, S3 is the set of all permutations of length {1,2,3} which has order 3!
>= 6 so we have:
>1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
>1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
>Now, in cycle notation these are (respectively)
>
>(1)(2)(3), (2 3), (1 2), (1 2 3), (1 3 2), (1 3)
>
>So far so good?
Yes. Except I would just write e or (1) instead of (1)(2)(3).
>Ok: Now, it is easy to see by making (1 2 3) and ( 1 3 2) 2 cycles that
You mean "by writing them as a product of transpositions", not "making them
2-cycles", since they don't EQUAL a two cycle.
>they are even and therefore in A3 by definition of A3
>so (1 2 3) = (1 3)(1 2)
> (1 3 2) = (1 2)(1 3)
>
>But how the heck is (1) in An when it is not in Sn?
It is in Sn. (1)=(1)(2)(3).
>Or is (1) in Sn because
>(1)(2)(3) is in Sn?
Yes, because they are equal functions. Both map every integer in Tn to itself.
>If (1) is in Sn because (1)(2)(3) is in Sn, then isn't (2) in Sn by similar
>reasoning?
Yep, because (2)=(1).
>Additionally then, isn't (2) in An because
>(2) = ( 1 2) (1 2)
> i.e. (1 2)(1 2)[2] is 2 -> 1-> 2?
Yep, (2) is in An and so is (j) for 1<=j<=n because they are all the SAME
element, namely the identity function from Tn to Tn. So
(1)=(2)=(3)=...=(n)=(1)(2)(3)=(1)(n)(1)(n)(n-1)(4)(7)(7)(7) since no matter how
many times you compose the identity map with itself you still get the identity
map... e!
Notice that (2)[2]=2 but also (2)[1]=1 and (2)[3]=3 etc since any number which
does NOT appear in a permutation is mapped to itself by definition of
permutation notation.
--solving your identity crisis