Many mathematics files on this site are in pdf format.
If your browser does not display pdf files, click here for
assistance.
This page was last updated on Monday, August 20, 2001 11:11:55 PM. © Ken Monks
|
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 2000 course -------------------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Saturday, September 02, 2000 3:32 PM Subject: [FAQ] RE: toy proofs question Well, well, well. The first FAQ question of the Fall 2000 Modern Algebra course has arrived! Let the new FAQ list begin! > -----Original Message----- > Sent: Saturday, September 02, 2000 2:09 PM > To: monks@UofS.edu > Subject: toy proofs question > > > Dr. Monks > > i had a question about the first assignment. Are we allowed to use the > rules and/or axioms within a line? For example, > o|o|.|.|o|.|. can i take the third thru 7th term and use rule 3? > Then I would have o|o|o|. No! Rule 3 says: w|v|. ----- w|o This means that you can choose w and v anyway you like, as long as your input line is of the form "w|v|." . Once you choose w and v to match the input line, then you MUST get w|o as the output line. Thus in your situation, if the line you want to apply Rule 3 to is: o|o|.|.|o|.|. Then you can only make the following choices: w v Conclusion of Rule 3 --------- --------- --------------------- o o|.|.|o|. o|o o|o .|.|o|. o|o|o o|o|. .|o|. o|o|.|o o|o|.|. o|. o|o|.|.|o o|o|.|.|o . o|o|.|.|o|o In each case, the output is whatever you chose for w with a |o tacked on the right. Once you pick w, then v is determined for you automatically. > Or are you only allowed to use Rule 3 when you have a . on the end of a > string of formulas? Yes, you can only apply Rule 3 to a formula that has a . on the end since the input must be of the form w|v|. where w and v are any formulas. The axioms have nothing to do with Rule 3 in the toy proof system. --still plays with toys ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 04, 2000 10:30 AM Subject: [FAQ] RE: Assignment #2 Question #1 > -----Original Message----- > Sent: Sunday, September 03, 2000 11:21 PM > To: monks@epix.net > Subject: Assignment #2 Question #1 > > > Dr. Monks, > > I've been trying to figure out assignment #2 ?#1 and I don't know if I'm > using the recipes correctly or not. Here it goes: > > Prove (P or Q)=>(Q or P) > PF: > 1.Assume (P or Q) > 2. P Line 1 > 3. Q or P or +;2 > 4.<- > 5.(P or Q)=>(Q or P) =>+;1,3,4 > QED Bzzzzzzt. Sorry, but that is not right. You can't use "Line 1" as a reason. For propositional logic proof the ONLY REASONS you can use on a line are: a. One of the 16 Recipes listed in the "Propositional Logic" section of the Prof Recipes sheet. b. The name of a previously proven theorem (that you proved or that I proved in class or in the FAQ's). That's it. Nothing else. Every line MUST have one of the above reasons unless it is: a. an Assume line b. an End Assume (<-) line c. a "Given" line (we don't have any of these yet). So those are the rules of the game... you can't break them. It's like playing chess.. you can't move a Rook along a diagonal. Why? Cuz it is the rules! Same here. You HAVE to have either one of the 16 Recipes or a previously proven theorem name for every line in your proof that is not an Assume or an <-. You also must indicate which lines in your proof satisfy the requirements of the rule (if any). "Line 1" is not a valid reason. In addition, there is NO rule of inference which will allow you to deduce P in line 2 from (P or Q) in line 1 directly. For example, if Q is true and P is false, then (P or Q) would be true, but P would be false. So P does NOT follow from P or Q. The rest of your proof is ok, except that you should indent lines 1 and 4 to be even with lines 2 and 3 since they are all in the same "pretend world" like this: > PF: > 1. Assume (P or Q) > 2. P Line 1 > 3. Q or P or +;2 > 4. <- > 5.(P or Q)=>(Q or P) =>+;1,3,4 > QED However, the proof is still wrong because line 2 is wrong. So you have to find another way to do it. > Am I showing things properly and does the proof use the recipes > correctly? No. Line #2 is wrong because it doesn't use any recipe at all. It used the "wishful thinking" recipe. :) --plays by the rules -------------------------------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 04, 2000 12:45 PM Subject: [FAQ] clarification of my comments Regarding the last email message where I said the rest of the student's proof was correct except for the fact that his reason for line 2 was wrong, I think I should clarify what I meant by that. What I mean is, every line in his proof follows from previous lines by correct rules of inference, except for line #2. But that is not the same thing as saying that his proof is "almost correct" in the sense that he only needs to fix line 2! No way! If ONE line in a proof is wrong the WHOLE PROOF IS WRONG! It's not partly wrong, it's totally wrong. So while he might have the rest of the reasons correct for his other lines, the mere fact that he has a wrong line #2 (on which the many of the rest of the lines depend) indicates that it is just plain wrong. So DO NOT assume that it is "easy" to fix his proof to get it to be correct... it might require hundreds of extra lines (or it might not). So I wanted to clarify it lest people thing he is "close" to a correct solution. To illustrate, I could give the following wrong proof: Pf: 1. Assume (P or Q) - 2. (Q or P) by the "Wishful Thinking" Rule 3. <- 4. (P or Q)=>(Q or P) =>+;1,2,3 "QED" Now in this case I can say that the rest of the lines in this proof are correct except for line 2, because each of the other lines either doesn't require a reason or it has a valid reason for deducing it (like line 4). But even though the reason for line 4 is correct, it depends on line 2, and line 2 is wrong! So this proof is TOTALLY wrong. It is obvious that a lot of work will be needed to "fix" it. Or if I really want to be a nudnik I could just say: Pf: 1. (P or Q)=>(Q or P) by the "Wishful Thinking" Rule "QED" Which also only has one wrong line in it! But you could do ANY proof incorrectly this way. :) Moral: if even one line in a proof is wrong, you might be hundreds of lines away from a correct proof. I hope that clarifies things. --clear headed ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 04, 2000 10:24 PM Subject: [FAQ] RE: Math 448 - Assignment #2, Question 3 (and then some) > -----Original Message----- > Sent: Monday, September 04, 2000 9:15 PM > To: monks@epix.net > Subject: Math 448 - Assignment #2, Question 3 (and then some) > > > Dr. Monks .. > > Though I must be warped in the head for doing homework on Labor > Day, I could use a little input. Hey, I'm answering questions about math on Labor Day, so I guess I am just as warped. :) Long live the warped people! :) > This is a two-part question, though the first is probably more > significant. > > A) This is in regard to Assignment #2, Question 3 .. (P<=>Q)<=>(Q<=>P) > I have gotten as far as what I'm putting below, and I'd like to > know if I'm on the right track. > > Pf: > 1. Assume P<=>Q - > 2. Assume Q - > 3. Assume P - > 4. <- - > 5. Q=>P =>+; 2,3,4 > 6. <- - > 7. P=>Q =>+; 3,2 > 8. Q<=>P <=>+; 5,7 > 9. <- - > 10. (P<=>Q)=>(Q<=>P) =>+; 1,8,9 > > My number one concern is about line 7 .. Well, you should be concerned sooner than that! Line 5 is wrong. It doesn't follow from lines 2,3,4 by the =>+ rule as you claim it does. The =>+ rule requires that you assume Q and show P in order to conclude line 5. But you didn't show P, you assumed P, which isn't the same thing. To "show" it means to prove it, while "assuming" it means that you are just pretending it is true, not showing it is true. Also, even if you HAD proven P after line 2, then according to the =>+ recipe, you would have had to end the assumption from line 2 and unindent one level to the left when you concluded line 5. So that is the second problem with line 5... its on the same "pretend world" that line 2 is in, whereas the conclusion of an =>+ rule must be one level higher. > I am not sure if I am allowed to make use of assumptions that I have already > ended. No, you are not. Once you end an assumption with <-, you cannot use the lines in that assumption anymore in the proof (except for the line immediately following the <- if it is the conclusion of a rule of inference that allows it). Once you close an assumption, those lines are "dead" for the remainder of the proof (except for the rules of inference that allow it). > Nor am I sure if there is a way to include that statement before I end the > assumptions. Line 7 is not correct as you show it either, even given your errors above it in the proof. If your lines 2-6 were correct (they are not!!!) then you could conclude on line 7 that Q=>(Q=>P) by =>+;2,5,6. But the reason you give is wrong because P is no longer accessible at line 7 and cannot be referenced any longer. > Also, how is my indentation? See my comments above. > B) This is just a general question: > Do we have to use the Stupidity Rule that you mentioned in one of > your most recent e-mails? I looked for it in the FAQs and sometimes it > appears and sometimes it doesn't. You NEVER EVER have to use the Stupidity Rule... hence its name! It is a stupid rule because you never need it. However, sometimes when you are writing a proof, just for the sake of making the proof easier to read, you might want to make a copy of, say, line 4 on line 125, so the reader doesn't have to scroll all the way up to line 4 to find the line you are referring to. But you never NEED to use it EVER and in particular you don't need it on this homework assignment. I just told you about it because I changed the Recipe sheet to include it, and any time I change something at the website I inform you guys so you can always have the latest versions of things if you are the kind of person who likes to print things out. > Thanks for your help! No problem. See ya'll tomorrow. --Labor Day laborer ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 06, 2000 10:24 AM Subject: [FAQ] RE: Math 448: Assignment #2, Question 3 > -----Original Message----- > Sent: Tuesday, September 05, 2000 9:41 PM > To: monks@epix.net > Subject: Math 448: Assignment #2, Question 3 > > > Dr. Monks .. > > I am having severe mental blocks. I have a feeling this is > wrong, but I was hoping that maybe you could help me fix it. I don't want to get in the business of "helping" people to do the homework. There is a fine line here somewhere. On the one hand I am glad to answer technical questions related to the homework assignments. On the other hand I don't really want to open a "homework hint service" where students keep asking questions in the hope of "fishing for hints", nor do I want to get into the business of "pre-grading the homework" whereby people keep sending me their attempted solutions before they are due so that I can tell them if it is correct or not. It also presents a problem when replying to the whole class if I forward students entire proof's to the rest of the class, especially if the proof is correct. So what I prefer is that if you have a question about a particular math concept, or the application of a particular rule of inference/recipe/thm/definition, then ask that specific question. You can ask to clarify what a question is asking. But I want to discourage people from sending me entire attempted proofs with the hope of getting either hints or having me pre-grade it. Otherwise it will get out of hand. There are already three years worth of FAQs posted, and I am starting to feel that there are more than enough hints in them to do these assignments. So use your judgment when asking questions to distinguish between when you are trying to get hints on the homework and have me pre grade the homework, vs asking actual academic mathematical questions about the subject matter and the problems. It's a fine line, I know, but you are all brilliant, so you will know the difference! Thanks! > This is to prove (P<=>Q)<=>(Q<=>P). > > 1. Assume P<=>Q - > 2. Assume ~(Q<=>P) - > (I am not even sure if this is the right approach!) I will not discuss if this is the right "approach" or not. But I will comment on the whole general idea of "right approach". It is like I said in lecture. There are MANY ways to do a given proof. If you have used nothing but the rules of inference and you have used them correctly, and if you succeed in proving the theorem, then your "approach" was right. On the other hand if you can't prove what you want, well then you haven't found the right approach yet. So how do you find the "right approach"? Well, that is similar to asking a chess master "How do you play chess well?". While the rules of the game are well defined and easy to learn, playing well is not easily defined and easy to learn. It takes a lot of practice, a lot of trial and error, and a lot of studying proofs done by others (e.g. me) to see what "approaches" are effective. Finding the "right approach" is where the ingenuity and creativity and inspiration is involved. Otherwise math proofs would just be done by computers. That having been said, there are some "strategies" you can use in developing the "right approach". Some of the main strategies are: 1. Try working backwards. Sometimes instead of starting at the top of the proof and working down towards a conclusion, try starting at the conclusion (what you want to prove) and ask yourself what kind of things you could do to prove it, then work backwards up the proof to see if you can make a whole proof. 2. Try to meet in the middle. Sometimes you can work backwards and forwards at the same time and try to get the proof to meet up somewhere in the middle. 3. Process of elimination. In deciding what rule of inference you want to use to prove something, you can look at the entire list of rules of inference that are available to you and eliminate ALL of the rules that can't possibly be used to prove what you want. For example, if you are trying to show "P and Q", then you can't use the "=>+" rule, because there is no "=>" in your conclusion. Once you eliminate all the rules that CAN'T be used, there might only be one or two rules left that CAN be used. If there is only ONE rule left that can be used, then you don't have much choice! If there are only a couple of rules that can be used then you can try each one in order by brute force until you fid one that works. 4. Memorize the recipes! Especially the ones for logic! You will use them in EVERY proof! There is NO proof that doesn't use logic. You have to know them BY HEART! It is too inefficient to keep looking them up on the recipe sheet to see which ones will work in a problem. It would be like trying to do long division without knowing your times tables. It makes it much easier to "see" the right approach if you carry around all of your "tools" in your head. You will used the logic recipes a ZILLION times in the rest of the course, so just learn them by heart. Internalize them. Try to understand WHY the recipe is what it is. 5. Use what you have. When you are "stuck" at a certain line in a proof, look at the lines above it that are still active. These are your "raw materials" that you have to work with. In most cases the line you are proving isn't true in its own right, but is only true GIVEN the lines above it. Thus if you are not using those lines as your raw materials you might not be able to prove what you want. Thus you might ask yourself what rules of inference can the lines above be INPUT's for. This is the counterpart to the strategy of "Process of Elimination". 6. Break everything down into pieces and put the pieces back together again. If you have complicated statements that are already in your proof, try using the "minus" rules to break them down into smaller "pieces".. tinier bite-sized statements. Then try using the "plus" rules to put the pieces back together in a way that produces the statement you are trying to prove. It's like working with Lego's... if you have a Lego house and a Lego car and want to build a Lego boat, you can't just stick the car on the house to make the boat, you have to break apart the Lego house and car into its little individual Lego pieces and put the pieces back together to make a boat. For example, if you have "P and Q" as one of the lines in your proof, you might use the "and-" rule to break it apart into P on a line by itself and/or Q on another line by itself. 7. Never under any circumstances let your intuitive knowledge get in the way. Keep your intuition out of it. Pretend you don't know ANYTHING. Don't say to yourself "My goodness, "P or ~P" is true, because I KNOW intuitively that it is true. It doesn't matter what you think you know intuitively. That is irrelevant. All that matters is if you can PROVE it is true or not. This goes for any line in the proof. Logic is the study of the relationship between statements which is INDEPENDENT OF THEIR MEANING! It doesn't matter what the statements mean as far as proving them goes. Look at the Toy Proof system. What do the "statements" in the Toy Proof System mean? They don't mean ANYTHING! Yet you can still prove some of them by simply following the rules of inference. The same is true for all of your proofs. While "meanings" we assign to the symbols might be helpful to us in remembering the rules of inference or in deciding on an "approach" to doing a proof, the meanings we assign to the statements are IRRELEVANT in determining whether or not the proof is indeed a proof. If the proof is constructed using only the rules of inference, then it is a proof regardless of what "meaning" you try to assign to the statements. So try to keep your intuitions out of it. As I said before, I have a computer program which can verify proofs. The program has no "intuition" about the "meaning" of the statements. It is just following rules mechanically. This ability to divorce yourself from your intuition when doing proofs is an essential objectivity that you need to be good mathematicians. --proof strategist ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 06, 2000 10:50 AM Subject: [FAQ] RE: assgn 2, ques 4 > -----Original Message----- > Sent: Tuesday, September 05, 2000 10:55 PM > To: monks@epix.net > Subject: assgn 2, ques 4 > > > okay .. here's a quick one .. or so i hope! > > if you have P and ~P, must the next line ALWAYS include the > contradiction statement? > > if this is not always the case, how wrong is this: > > 1. Assume P and ~P - > 2. P and -; 1 > 3. Assume Q - > 4. <- - > 5. P=>Q =>+; 2,3,4 > > in case it wasn't obvious, this little piece is from question 4. > thanks for the help. How wrong is it? Completely wrong. :) Proofs are either completely wrong or completely right. Line 5 does not use the recipe for =>+ correctly. In order to deduce line 5 you would have to assume P and show Q, but you assumed Q and showed P (on line 2). This brings up a couple of points I want to mention. A. If you want to use the Stupidity Rule (which is on the recipe sheet but we didn't discuss it in class, you can. All it does is let you copy only active line to another location in your proof. For example, suppose we are doing this: 1. Assume P and Q - 2. P and-;1 3. Assume Q - 4. <- - 5. Q=>P =>+;3,2,4 This is correct as is, but it looks a bit strange because you are proving P BEFORE you make the assumption Q, even though the recipe says we should first assume Q and then show P. So to make such a proof more readable, we can use the Stupidity rule as follows: 1. Assume P and Q - 2. P and-;1 3. Assume Q - 4. P S;2 5. <- - 6. Q=>P =>+;3,2,4 Here I used the Stupidity Rule on line 4 to copy the P from line 2 to line 4. It makes the proof look more readable that way. B. There is a simple way to check your lines following an <-. If you look at the recipes you will see that the only logic recipes that have a <- in their input are: =>+ ~- ~+ That's it!! Only three rules! [Note: the "alternate expanded version of or- also has a <- in it, but that rule is never needed because you can use the regular or- (proof by cases) instead.] So the bottom line is this: 1. THERE IS NEVER ANY REASON TO MAKE AN ASSUMPTION IN A PROOF UNLESS YOU ARE GOING TO DISCHARGE THAT ASSUMPTION WITH ONE OF THE THREE RULES ABOVE. 2. THE LINE IMMEDIATELY FOLLOWING A "<-" MUST HAVE ONE OF THE THREE RULES LISTED ABOVE AS IT'S REASON (with the exception of the alternate or- rule). Since ~- and ~+ are both "proof by contradiction" rules what this says is that THE ONLY REASON FOR YOU TO MAKE AN ASSUMPTION IS IF YOU ARE GOING USE EITHER PROOF BY CONTRADICTION OR IMPLIES PLUS!!! This is a very important thing to keep in mind! Thus whenever you make an assumption, you should immediately write down below it what you intend to prove with it, i.e. which of the three rules of inference you intend to use. If you don't know which rule you intend to use then DON'T make then assumption! --pain in the assumption ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 06, 2000 12:05 PM Subject: [FAQ] RE: math448 assign #2 > -----Original Message----- > Sent: Wednesday, September 06, 2000 11:03 AM > To: monks@epix.net > Subject: math448 assign #2 > > > Dr. Monks > > I was wondering if i assume a '<=>' statement am i allowed to use what > it implies? Mainly, > > Ex. 1. assume P <=> Q > 2. P => Q If you can give a valid reason for line 2, i.e. one of the 16 rules of inference, then yes. Otherwise, no. > Can i take that from the definition because that is what you have to show for > <=> anyways? We have no definitions yet. None (that we can use in a proof, I gave some in defining the propositional logic syntax but they aren't part of the formal logic system we doing our proofs in). The only thing we have are the 16 tiny rules of inference listed on the recipe sheet in the Propositional Logic section (I think there are 16, but you can count them to be sure). 16 little Rules of inference. That's all you can use in a proof. Nothing else. There are no other reasons allowed. For any reason X, if (you ask me if X is a valid reason for a line) and (X is not one of the 16 recipes) then (the answer is NO). The only "exceptions" are that you can insert a previously proven theorem into your proof at any line and you can use the stupidity rule if you want to. However, these aren't really an exceptions, they are just a shorthands, because if you already have a proof of a theorem you could have just insert the entire proof of that theorem into your proof in order to get the thm as a line in your proof and keep expanding as needed until you get a proof that only has the 16 recipes for reasons for every line that requires a reason, and you can always do a proof without the stupidity rule if you can do it with the stupidity rule. There are no meanings. There are no definitions. There is nothing available that you have ever learned in any math class before this one except for the 16 recipes. They are the only reasons you can use on a line. If you put any other reason other than one of the 16 recipe names and the appropriate line numbers then the proof is wrong, wrong, wrong!! (with the "exceptions" that you can include previously proven theorems and you can use the stupidity rule if you want to). Oh, and don't forget... you are only allowed to use the recipes for reasons! > And if so would that be under the realm of the > Stupidity Rule or would i cite the definition of <=>? There are no definitions!!! See above! There is no "realm of the Stupidity Rule". The Stupidity Rule doesn't have a "Realm". It is a very particular concrete well-defined specific rule of logic. It says: To show P 1. Show P That is the only rule or recipe that can be referred to as the Stupidity Rule. If you use the Stupidity Rule in your proofs then you MUST use it in EXACT ACCORDANCE with the recipe! It can ONLY be used for copying one active line to another in a proof. It cannot be used to justify "obvious" facts or "definitions" especially since we don't have any definitions yet. Did I mention that? :) --Master of Stupidity ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 06, 2000 8:56 PM Subject: [FAQ] RE: Assignment 2 problem 4 > -----Original Message----- > Sent: Wednesday, September 06, 2000 4:35 PM > To: monks@epix.net > Subject: Assignment 2 problem 4 > > > Dr. Monks, > Quick question: > Assuming I can get to this pt and that I proved Problem 2, is this true > or not allowed for us to use: > > 11. (P&~P)=>(~~Q=>Q) =>+;1,9,10 > 12. (P&~P)=>Q Homework Assignment 2 Problem 2 > > Note: Problem 2 is this P=>(Q=>P) > > -Praying for a miracle No!! You CAN use a previous homework problem in your proof, but the ONLY way to use it (at this point) is to insert it directly into the proof. Thus, if Problem # 2 says P=>(Q=>P) then the ONLY WAY you can use it in your proof is like this: n-1. :
n. P=>(Q=>P) Homework Assignment 2 Problem 2
n+1. :
Since what you have on line 12 doesn't exactly match Assignment 2 Problem 2, you can't do that on line 12 with the reason you give. -not a miracle worker ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 06, 2000 9:05 PM Subject: [FAQ] RE: assgn 2, #1 > -----Original Message----- > Sent: Wednesday, September 06, 2000 5:22 PM > To: monks@UofS.edu > Subject: assgn 2, #1 > > > Are (P or Q) and (Q or P) interchangeable? No. > For example, I know > (P or Q) and ~(P or Q) is a -><-, > but is (P or Q) and ~(Q or P) a -><- ? Also no. Right now we are doing formal proofs. When we relax our requirements and become a bit more "sloppy" in our proofs later in the term, then both of the things you ask about would be allowed. But for now, they are not because there is no rule of inference that allows you to do what you are suggestion. The only thing you are allowed to do in these formal propositional logic proofs is use the 16 rules of inference. Nothing else. That's the only thing. You can't "interchange", you can't "say" things, you can't "know" things, or "swap" things, or "substitute" one thing for another, or even say one thing "equals" another since we didn't even DEFINE "equals" yet! So the ONLY THING YOU CAN DO IS USE THE RULES OF INFERENCE EXACTLY AS WRITTEN (and the two abbreviations of inserting a previous theorem and using the stupidity rule, neither of which is ever actually needed). --Ruler of Inference ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 06, 2000 9:06 PM Subject: [FAQ] RE: Assgn 2, #3 > -----Original Message----- > Sent: Wednesday, September 06, 2000 6:09 PM > To: monks@UofS.edu > Subject: Assgn 2, #3 > > can you use an assume line as a reason for two different lines? Yes, you can use any line as a reason for as many lines as you like. --reasonable ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 06, 2000 9:31 PM Subject: [FAQ] RE: number 5 > -----Original Message----- > Sent: Wednesday, September 06, 2000 8:39 PM > To: monks@epix.net > Subject: number 5 > > Prof Monks > > i wanted to know if something that i tried here would be a valid > contradiction. > > Assume (~p & ~q) > Assume (p or q) > (~p & ~q) > > Now i want to use this as a contradiction. Is this valid? No. None of the three statements you have listed is the negation of one of the other two, so there is no contradiction. > It seems to be fairly evident to me that you cannot have (p or q) when you already > assumed you dont have either of them. It doesn't matter if it is "evident" or not. It doesn't matter what you think the "meaning" of the statements is. It is irrelevant. Think of the Toy Proofs. What string of o's and .'s is "evidently" true? None of them, because there is no meaning. It doesn't matter what you THINK a contradiction is. That is not what we are doing in these proofs. All that matters is that there is only one rule of inference (two versions) for producing a contradiction... To show -><- 1. Show P and ~P or equivalently To show -><- 1. Show P 2. Show ~P So if you don't have a statement of the form (P and ~P) or a statement and it's negation, then you CAN'T have a contradiction symbol -><- in your proof because the ONLY WAY TO GET IT IS BY USING THE ONLY ONE OF THE 16 RULES OF INFERENCE THAT ALLOWS YOU TO GET IT! You can ONLY USE THE 16 RULES OF INFERENCE! If you can't justify your argument with those rules, then no amount of intuition, insight, wishful thinking, creativity, imagination, hopefulness, or sheer genius will make the proof correct! The WHOLE POINT of doing formal proofs is that there should be NO SUBJECTIVITY in verifying whether a proof is correct or not. What if a certain reason is "evident" to you but not to someone else? If we allowed reasons based on if they are "evident" to various individuals we would never arrive at any certain conclusions because there would always be someone that would disagree. That is what they have in politics and theology and art appreciation and psychology... a whole bunch of people with different opinions arguing about which one is right. But in mathematics we don't have that problem because we have come up with a way that is as close as possible to being totally non-subjective... a way in which we can arrive at conclusions in a purely mechanical means... so mechanical that a machine with no intuition or opinions at all can actually verify our claims. That is the beauty of formal proofs. Certainly we will be using our "intuitions" and "meanings" throughout the course to help us to appreciate and motivate and even to come up with ideas for proving the theorems and results we will obtain. But even when we do an informal sloppy proof later on, it is only going to be considered a "correct" proof if it could, with a little work, convert it into a totally rigorous formal proof if we "had" to. > Thanx ol' grand Wizard Your welcome!! --likes the "grand Wizard" but isn't to crazy 'bout the "ol'" part :) ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Thursday, September 07, 2000 8:09 AM Subject: [FAQ] RE: Assignment 2, Question 4 > -----Original Message----- > Sent: Wednesday, September 06, 2000 10:36 PM > To: monks@UofS.edu > Subject: Assignment 2, Question 4 > > > Dr. Monks, > > I am not sure that I understand the ~- rule. I know that if you want to > show P, you must assume ~p and then show a contradiction. Does this > contradiction have to do with P? No, it doesn't. > Second question....this one is quick. Can I use something that I have > assumed once I have moved out of that particular assume? > > For example. > > Assume P > -><- > <- > ~P > P ( this is the P I am unsure of....I assumed it earlier, can I still use > it even though I am no longer in the assumption?) No. Once you end the assumption with <- it means you are no longer pretending that that statement (or any statement between it and the <-) is true. So you can't use it. The ONLY exceptions are that the line IMMEDIATELY after a <- can be a ~-,~+, or =>+ rules. These three rules are the only ones that allow you to use what has been proven in an assumption-<- block after the lines are no longer valid. > Thanks! See you tomorrow! No problem! See you... uh today! --early bird ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Thursday, September 07, 2000 1:10 PM Subject: [FAQ] RE: ? regarding arbitrary statements Categories: Backed Up > -----Original Message----- > Sent: Thursday, September 07, 2000 11:27 AM > To: Ken Monks > Subject: Re:? regarding arbitrary statements > > > Let's say I have a theorem that reads: > (P and Q) =>R > Now since P, Q and R are all arbitrary statements does that mean that as > long as I can show P and show Q I can conclude whatever I want for R > even if what I want as R is a compound statement including P and Q in > some fashion? > ie > > Stupid theorem: (P and Q) => R > > Thm: (~Q or (P and ~P)) > Proof > 1 P (by some previous argument) > 2 Q (by some previous argument) > 3 P and Q and+;1,2 > 4 P and Q => (~Q or (P and ~P)) by Stupid theorem > 5 ~Q or (P and ~P) =>-;4 > QED > > OR is this wrong because the Stupid Theorem implies that R does not > contain P or Q? This is a very good question. The short answer is: Yes, I will allow this as another kind of "abbreviation". The long answer is that you probably shouldn't do it until we have quantifiers available and the @- rule. Here is the actual explanation. Let's look at a simpler example: Suppose I prove: Thm Cool: P=>P Pf. 1. Assume P - 2. <- - 3. P=>P =>+;1,1,2 QED Now I want to prove: Thm: P=>(Q=>Q) So you are asking if I can do it like this: Pf. 1. Assume P - 2. Q=>Q Thm Cool 3. <- - 4. P=>(Q=>Q) =>+;1,2,3 QED?? You are asking if I can replace the statement P in Thm Cool, with some other statement before I insert the theorem into my proof. For example, on line 2 we have replaced the P in Thm Cool with a Q. Well, we can allow this as an abbreviation because, if our back was against the wall, we could just as easily prove Q=>Q by replacing all of the P's in the proof of Thm Cool with Q's. So in this example we can think of it as an abbreviation for: Pf. 1. Assume P - 2. Assume Q - 3. <- - 2. Q=>Q =>+;2,2,3 3. <- - 4. P=>(Q=>Q) =>+;1,2,3 QED!! So as you can see, instead of inserting Thm Cool directly into the proof, we could insert the entire PROOF of Thm Cool into the proof, except with all of the P's changed to Q's. This works no matter WHAT statement we "substitute" for P, for example: Thm Cooler: ((Q and ~R)<=>W)<=>((Q and ~R)<=>W) Pf. 1. Assume ((Q and ~R)<=>W) - 2. <- - 3. ((Q and ~R)<=>W)=>((Q and ~R)<=>W) =>+;1,1,2 QED If you compare Thm Cool with Thm Cooler, you will see that they are identical, except in cooler we have replaced all the P's in Thm Cool and it's proof with ((Q and ~R)<=>W). This will ALWAYS work, so instead of us having to constantly rewrite the same proof over and over again with different statements substituted into it, we can just agree that as an abbreviation, we can allow the use of any previously proven theorem of propositional logic with any statement at all substituted for free variables in the thm. Since we COULD just write out the entire proof again with the new variables, I will allow this abbreviation. Now if we have quantifiers available, then we can actually do the substitution in our proofs rather than doing it behind the scenes. In the above example we could do it this way: Thm Coolest: @P,P=>P Pf. 1. Let P be arbitrary - 2. Assume P - 3. <- - 4. P=>P =>+;2,2,3 5. @P,P=>P @+;1,4 QED Then we can prove: Thm: P=>(Q=>Q) Pf. 1. Assume P - 2. @P,P=>P Thm Coolest 3. Q=>Q @-;2 4. <- - 5. P=>(Q=>Q) =>+;1,3,4 QED without the need to do any substitution-like abbreviations. However, many times our theorems in the course will contain free variables like Thm Cool does, and we will always allow the substitution mechanism described above because we could justify it by the means I just explained. --likes shortcuts that are rigorous ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, September 08, 2000 10:15 AM Subject: [FAQ] RE: Clarification of Quantifiers reguarding Problem #2 > -----Original Message----- > Sent: Thursday, September 07, 2000 10:56 PM > To: monks@epix.net > Subject: Clarification of Quantifiers reguarding Problem #2 > > > Dr. Monks, > > My question is over the proper use of @+. I was wondering if these are > allowed statements: > > A: > 1) Assume @x,@y,P(x,y) > 2) Let y be arbitrary. > 3) P(y,y) @-;1 > 4) @y,P(y,y) @+;2,3 > 5) @y,@y,P(y,y) @+;2,4 Several things are wrong here. First off, you can't make two substitutions at once like you are trying to do on line 3 (even though what you have is true, it doesn't follow from the @- rule of inference which allows you to remove only only @ at a time. Second, if you do it in two steps then you break one of the restrictions on the @- rule, namely that the y that you substitute for x when you remove the @x becomes bound by the @y (see the restriction on @- in the recipe): A:
1) Assume @x,@y,P(x,y)
2) Let y be arbitrary.
3) @y, P(y,y) @-;1 <- no, because the y you
replaced the x with becomes
a bound variable here
However, you can conclude P(y,y) from the assumption in line 1, so it isn't "wrong" in that sense, it just requires a lot more work to do it formally. So your "reasoning" is ok, but your formal use of the quantifier recipes isn't. Later in the course when we do "sloppier" proofs, we will allow a lot of things like this, as long as they CAN be proven without doing the formal proof. But this is the part of the course where you convince yourself (and me!) that it CAN be proven formally using only the rules of inference in the exact way they are specified. Third, wile line 5 is technically correct, it is sort of a silly statement, because the outermost @y is not really quantifying anything. There are no free variables in @y,P(y,y) to quantify since all of the y's are already quantified by the existing @y. So it is similar to saying something like "@w,@x,x^2>=0". What is the point of the @w? There are no w's in the statement. So even though it is true, it is for most purposes useless. > I think lines 3 and 4 are correct but can I use @+ for line 5. Line 3 is wrong. Line 4 is correct given your wrong line 3. Line 5 is correct given the other lines. > Therefore what I'm truly wondering is in the recipe @+ it states that I > have to: > To show @x,P > 1. Let x be arbitrary. > 2. Show P > Can P be: > 1) @y,P(y,y) > or > 2)@a,@b,@c,@d,F(a,b,c,d) > or > 3)MathisCool > or > 4)Does it have to be just P(...) P can be any statement or open statement at all. (except for the restrictions on the @+ rule). > I think it should be allowed to be anything just like previous P's we've > been working with, but it's better to be sure. I'm glad you think it should, because it is. :) > --MathIsCool --agrees with you ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, September 08, 2000 10:30 AM Subject: [FAQ] RE: => problem and such > -----Original Message----- > Sent: Friday, September 08, 2000 12:11 AM > To: monks@epix.net > Subject: => problem and such > > > Dr. Monks, > > I was just working on #3 Assign 3 when I decided I must be doing > something wrong with the style and structure of my proof. I say this > because from what it seems to me is that no matter what type of problem > I'm given as long as it's in the form P=>Q using my proof it seems they > should all be provable. Well if this were true we would all be out of business in mathematics. :) > I'll give two examples, I'm sure I must be > wrong because I don't think you should be able to always show P=>Q, I'm glad you think that, because I agree. For example, you shouldn't even be able to show P=>Q itself! Remember you can only prove a statement of propositional logic if it is a tautology. Thus P=>Q is not provable because it is not a tautology. > anyway 2 examples: This should be interesting... :) > This first example is from the first part of #3 Assignment 3 > I'm trying to show (~@x,P(x))=>(#x,~P(x)) > 1. Assume ~@x,P(x) > 2. Assume #x,~P(x) > 3. <- > 4. (#x,~P(x))=>(#x,~P(x)) =>+;2,2,3 > 5. Assume #x,~P(x) > 6. <- > 7. #x,~P(x) =>-;5,4 > 8. <- > 9.(~@x,P(x))=>(#x,~P(x)) =>+;1,7,8 > QED > > Now in General Form you could say: > > To show P=>Q > 1. Assume P > 2. Assume Q > 3. <- > 4. Q=>Q =>+;2,2,3 > 5. Assume Q > 6. <- > 7. Q =>-;5,4 > 8. <- > 9.P=>Q =>+;1,7,8 > QED > > Am I being miss guided? Is this true? Where am I using an incorrect > recipe? Yes. No. In line 7. Line 5 is no longer active after line 6 because you stopped assuming it. As I said in my previous email , the only rules of inference that can use and Assumption that is no longer active are =>+ and the two proof-by- contradiction rules. =>- is not one of those rules so it can't use line 5 at line 7 because you already killed off the Assumption on line 5 with the <- on line 6. If you wanted to use =>- the way you do on line 7, you would have to do it before you kill off the Q on line 5, for example, like this: 1. Assume P 2. Assume Q 3. <- 4. Q=>Q =>+;2,2,3 5. Assume Q 6. Q =>-;5,4 7. <- 8 ??? This is correct, but it doesn't do you any good towards "proving" P=>Q because the Q is at the wrong indentation level for the =>+. > --Good chef or not good chef? that is the question. Good chef, just poison ingredients. --prefers natural (deduction) ingredients ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Sunday, September 10, 2000 7:22 PM Subject: [FAQ] RE: Assignment #3 > -----Original Message----- > Sent: Sunday, September 10, 2000 4:33 PM > To: monks@epix.net > Subject: Assignment #3 > > > Dr Monks > > I had a quick question about using the "let _ be arbitrary" line. > When we use that, can we just use the same variable that was already in > the problem? > Ex. @x @z P(x,z) > let x be arbitrary > @z P(x,z) @-;1 Yes, as long as you aren't already using x for something else in the proof. > Or do we have to declare a new variable? > ex. @x @z P(x,z) > let t be arbitrary > @z P(t,z) @-;1 Either way is ok. > But if we do it the second way, when would we be able to put x back in > the equation when we are building the other side of the proof (as you > put it) back up to what we want? That isn't how I put it. But I know what you are trying to ask. If you want to use the @+ rule to create a statement of the form @x,P, you should declare x to be arbitrary, since the recipe for @+ requires that they match. However we can prove (@x,P(x))=>(@y,P(y)). This allows us to justify the following alternate version of the @+ rule: ; @+ (alternate version) To show @y,P(y) 1. Let x be arbitrary. 2. Show P(x) where by P(x) we mean a statement involving x and by P(y) we mean the statement P(x) with all the free occurances of x replaced by y. There are lots of little restrictions to worry about and it is a little bit more complicated of a rule than the original, but you can use it if you use it correctly. But the bottom line is you can do it either way and its ok. --Prof. Monks (alternate version) ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Sunday, September 10, 2000 7:35 PM Subject: [FAQ] RE: math 448, assgn 3, ques 3 > -----Original Message----- > Sent: Sunday, September 10, 2000 4:46 PM > To: monks@epix.net > Subject: math 448, assgn 3, ques 3 > > > dr. monks .. > > i'd like to know if you can use the same letter when you are declaring a > constant and then again when you are picking an arbitrary expression. > since that was probably badly worded, here's an example: > > 1. Assume #x, ~P(x) - > 2. Let t be a constant such that - > 3. ~P(t) #-; 1 > 4. Assume @x, P(x) - > 5. Let t be arbitrary - > 6. P(t) @-; 4 > > in other words, is it okay to have a t both on lines 2 and 5. NO! You can't declare t to be arbitrary on line 5 because t is NOT arbitrary, it is already declared to be a particular constant on line 2. You can't declare a variable to be arbitrary if it is already in use in the proof. [Note: The above form of the #- rule is what I used to use in the course, so you must have read it in the old FAQ's. That form is fine with me. You can also use the new form in which case line 2 would be "~P(t) for some constant t" with the reason you have on line 3.] > if the answer > is no and then assuming that i would have to change the t on line 5 to an s > (or some other letter), if i conclude P(s) on line 6, can i justifiably > conclude a contradiction with line 3 (that still has the t in it). No. "~P(t) and P(s)" is not a contradiction. For example, suppose P(x)="x>3", t=2, and s=5. Then "~P(t) and P(s)" says: ~(2>3) and 5>3 which is clearly true, not a contradiction. > also, i got the notation used on lines 2 and 3 from past FAQs. is it > acceptable? Yes, quite acceptable. > -- minding my s's and t's --doesn't mind your minding ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 11, 2000 8:50 AM Subject: [FAQ] RE: Substitution Rule > -----Original Message----- > Sent: Sunday, September 10, 2000 10:20 PM > To: monks@epix.net > Subject: Substitution Rule > > > Dr Monks > > I am not quite sure how to use the substitution recipe.i know i can > replace x by y after i show x=y. But what is the P i have to show? Any P you like. > Am I correct in thinking, for example, that if I show x=y and then I > can show A=x that in the next line I can say A=y by the substitution > rule (with appropriate reasons of course)? Yes. --Substitute teacher ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 11, 2000 10:59 PM Subject: [FAQ] RE: Recipe clarification, handy symbols, ?s about homework feedback, ?s about appedix b ?s > -----Original Message----- > Sent: Monday, September 11, 2000 7:39 PM > To: monks@UofS.edu > Subject: Recipe clarification, handy symbols, ?s about homework > feedback, ?s about appedix b ?s > > Chef Monks - > I'm not much of a cook, and I must follow every recipe step by step > exactly as it says. It was clear how to do this in the logic recipes > (i.e six cups <=>, two cups ~), but now the recipes are somewhat > "fuzzy," (i.e. a pinch of @, a dash of #). They aren't really fuzzy, because we have a computer program that does them just fine, so if a computer can do it without ambiguity, they can't be fuzzy. They just SEEM fuzzy because I am not able to spend the time in lecture going through all of the fine-point restrictions on those rules or this course will become a course in logic instead of a course in modern algebra. > So I have to ask lots of questions to know EXACTLY what all the *s mean: > 1.) What does "free variable in t" mean? (I thought that "in" meant > containment) Well, regarding "in", there are two "in"s, the normal everyday "in" which we need to use in English sentences, and the "is an element of" operator, which we also call "in" as in "x in A". Regarding free variables, we said that the scope of a quantifier is the largest string to the right of the quantifier that doesn't reach a right-) whose matching left-( is on the lefth hand side of the quantifier. For example in a statement like: (@x,blah1(blah2)blah3)morestuff the scope of the quantifier @x is "x,blah1(blah2)blah3" but morestuff is not quantified by x. An occurrence of a variable x in a statement P is "free" if it is not in the scope of any quantifier of the form @x). Example: In the following statement: x=3 => (@x,x=2) or x=7
^ ^ ^ ^
1 2 3 4
I have numbered the occurrences of the variable "x" in the statement. The occurrences numbered 1 and 4 are free occurrences. The occurrences numbered 2 and 3 are bound occurrences which because they are in the scope of the @x. > 2.) What does "may become bound" mean? It means that this is illegal: : : 5. #x,x>y ?? 6. y=x ?? 7. #x,x>x substitution;5,6 : Knowing that there is a number x which is bigger than y on line 5 and knowing that the "actual" number named x in line 6 is equal to y, doesn't imply that there is a number which is greater than itself. So you have to change the dummy (bound) variable if you want to make the substitution like this: : : 5. #t,t>y ?? 6. y=x ?? 7. #t,t>x substitution;5,6 : this use of substitution is ok, of course. The problem is that the free variable x in line 6 "became bound" in the first example when we substituted it for y. > 3.) What do you mean by x cannot appear as a free variable in any > assumption or premise? It means that x cannot appear as a free variable in any line that begins with "Assume" that is still active at the given point in the proof where you are trying to apply the rule. The same is true for a premise, which is just a "Given" statement in your proof, like: Thm: Let x in A. Then x in A union B. Pf: 1. x in A Given : : Line 1 in this proof is an example of a premise which contains the free variable x. > 4.) What is the difference between an assumption and a premise? See above. > 5.) What is a free occurrence? An occurrence which is not bound. See above. > 6.) What does "no variable in t may become bound" mean? It means that you can't do this either: : : 5. #x,x>y ?? 6. y=x+1 ?? 7. #x,x>x+1 substitution;5,6 : because in this substitution the expression t (which is x+1 in this example) contains a free occurrence of x which becomes a bound occurrence after you make the substitution. > That should clear that up. Thanks. Here are a few examples that might clear it up even further. Let's talk about the natural numbers for concreteness. "Thm": n=10 => @n,n>5 "Pf":
1. Let n be arbitrary.
2. Assume n=10 -
3. 10>5 arithmetic
4. n>5 substitution*;2,3
5. @n,n>5 @+;1,4 (WRONG! Because n appears free
in the assumption on line 2)
6. <- -
7. n=10 => @n,n>5 =>+;2,5,6
"QED"???
This is clearly "proving" something false because we are showing that if n is ten then every natural number is greater than 5!?! The error occurs on line 5 because of the restriction on the @+ rule... n appears free in the assumption on line 2. * note: in order not to confuse the issue I am using an alternate version of the substitution rule here so I don't have to change the n=10 into a 10=n before making the substitution. You can't use this alternate version on the quantifier homework, but as we will discuss tomorrow, you can use it on the homework after that. > I have an idea as to what you mean in ?3, but I want to know exactly > what is going on. Consider the following "proof": > > 1. -> ~@x P(x) > 2. Let s be arbitrary > 3. -> P(s) > 4. @x P(x) @+; 2,3 > 5. -><- -><-+;4,1 > 6. <- > 7. ~P(s) ~+;3,5,6 > 8. @x ~P(x) @+; 2,7 > 9. <- > 10.(~@x P(x)) => (@x ~P(x)) > > This is clearly wrong. Line 10 is not a tautology. I agree that it is wrong. But it is not because line 10 is not a tautology. The fact that the only thing we can prove are tautologies only applies to Propositional Logic, which is logic using only the recipes for and, or, not, implies, and <=> (i.e. everything before we introduce quantifiers). Once we introduce quantifiers into the picture it is no longer possible to make a truth table to determine the truth value of a statement, so the whole idea of a tautology no longer applies. The error occurs at line 4, because the variable s is free in the assumption on line 3. > This alerted me to > the importance of the *s, so I wanted to know exactly what they meant. > I know that we have to follow the rules, and I'm almost sure that I did > in my proofs, but I just don't want to break the rules because I didn't > know exactly what they are. > > Next, I read the e-mail regarding the @+ rule. If I remember correctly, > you said in class that our arbitrary variable can be different than the > one in the @x P(x). In my mind it makes more sense to do it like that > rather than keeping it as the same variable because it allows me to > understand the difference between showing it for the case of the > arbitrary variable and the existential statement that is the result. > Would you permit the following as a valid recipe: ? > > To show @x P(x) > 1. Let r be arbitrary > 2. Show P(r) > > I have done all of my proofs like this, including the first one. Is > this ok? This is not allowed in Problem #1. Once you have proven Problem #1, then you can use this rule for the rest of the course. > Next, I am disheartened to hear that we might not be able to use ->. In > fact, I came up with more symbols for "Let x be arbitrary" (for any x, > of course), "for some constant", injection, surjection, bijection, and > much, much more. They make proofs go by faster, more fun, and easier to > read and understand. They are easy to understand from the context of > their usage and I've been using them in my proofs. Is it ok to hand in > proofs like this? In my opinion, it's easier to use these symbols > rather than English words. In fact, if enough people start using these, > the mathematical community might realize how bad it is to use English > words in their proof and adopt the new system. I encourage your enthusiasm and creativity. I also enjoy making symbols that make math go faster and look cleaner. However there is a practical matter here that is beyond the aesthetics... grading. I have to grade these proofs. Lots of proofs. Lots and lots of the SAME proofs. If everyone defines their own notation, it just slows me down too much when grading because I have to translate everyone's individual notation first. On the other hand, if we all use the SAME notation uniformly, then I don't have to pause to look up what this individual's notation for "injection" is. So I think I am going to have to assert my rights as overworked instructor here and insist that we stick to the same notation as much as possible. I will mention two related items, however. First of all, I realize that different people work and think in different ways, and that as far as your own work goes, I encourage people to make their own notation and use it and try to proliferate it. I have strong feelings about notation as well, and I sometimes try to "sell" it and defend it as being advantageous. I have an entire paper written on my web site that explains how using the notation ` instead of the definite integral notation makes calculus much easier. In fact, when Nathan Carter and I wrote Lurch, we built in the capability for a user to use whatever notation he pleases, as long as he defines it for Lurch up front. (But Lurch is a computer program and can interpret notation faster than your ageing instructor can!). Second, I will mention that there are standard mathematical symbols for bijective and injective and surjective. For injective people often use f : A >-> B for surjective: f : A ->> B and of course bijective: f : A >->> B > Next, in the homework feedback, formatting section, you comment on > improper indenting. (A problem which the -> symbol can handle very > nicely, by the way :) ) You give an example of the proper way to > indent, but it looks exactly like the example of what not to do. Uh oh... must be a cut and paste error... I'll have to recheck it. Thanks! > In part 3 of the homework feedback section you say that our staples > shouldn't hide any of the work on subsequent pages. I find that > stapling in the upper right hand corner usually takes care of this > problem. :) But it introduces a new problem... nonuniformity when grading. Most of the formatting requirements are certainly NOT mathematical... they are to assist me in being able to grade your homework. The more time I have to spend grading the less time I have to answer email questions and prepare exciting handouts to post on the web and prepare spectacular in-class computer displays to assist you all in learning the material. So it is in all of our best interest to minimize the effort needed to grade the assignments. > Next, in assignment #4, i.e. questions from Appendix B, we have to go > outside of the recipes and set theory, etc. and make knowledge of such > things as (x in R and y in R and x^3 = y^3) => x = y. How do you want > us to show things like this. i.e. what are the rules for this exactly? This is exactly the topic of tomorrow's lecture. > Next, the proofs seem to become lengthy fast. How much do we have to > show. Do we have to state every definition exactly as it appears on the > sheets and use the <=>- rule then the =>- rule? Can we use x=y as y=x > or do we have to say x=y => y=x from the Theorem, then use the =>- rule? > You say that we have to be able to show something from just the recipes > if we had to, but how rigorous do you want these proofs to be? I want the proofs on the current homework assignments to be *totally* rigorous. Tomorrow I will explain what "sloppiness" and "shortcuts" we will allow. Stay tuned for an EXCITING lecture: "How to be a slob... rigorously." > Next, in Assignment #5, i.e. also in Appendix B, it asks about Im f, > which is not defined. The Set Theory sheet only defines image in terms > of f(S). I'm assuming that (f:B->C => Im f = f(B)), but I'm not sure. I already answered this question in a previous FAQ. Please read the FAQ's. > I'm pretty sure that I had many more questions, but this is all that I > can remember. Thanks in advance. > > -can't make a Poptart without a recipe No problem! -teaches his students how to be slobs ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 11, 2000 11:02 PM Subject: [FAQ] RE: Assign 3 #3 > -----Original Message----- > Sent: Monday, September 11, 2000 12:26 PM > To: monks@epix.net > Subject: Assign 3 #3 > > Dr. Monks > > I am trying to get ~@x P(x) in my problem. > If i Assume @x P(x) then take ~P(x) from a previous assumption that i > am still under am i allowed to conclude ~@x P(x)? > > Like........1. let x be arbitrary -- > 2. Assume @x P(x) -- > 3. ~P(x) from previous line > 4. ~@x P(x) @+;1, 3 > > If i am not allowed to do this you can just reply NO --NO ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 11, 2000 11:03 PM Subject: [FAQ] RE: #3 again from Assign 3 > -----Original Message----- > Sent: Monday, September 11, 2000 12:35 PM > To: monks@epix.net > Subject: #3 again from Assign 3 > > Dr. Monks > > Sorry but i forgot to put in something in the message i just sent you > about problem #3. If what i just sent oyu is not valid am i allowed to > say..... > > 1. Assume @x P(x) -- > 2. ~P(n) for some constant n from previous line > 3. -><- -><-+; 1, 2 > > again sorry to send two messages back to back and again you can just > say NO if this is not legal --NO ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 11, 2000 11:07 PM Subject: [FAQ] RE: @- Rule > -----Original Message----- > Sent: Monday, September 11, 2000 1:21 PM > To: monks@UofS.edu > Subject: @- Rule > > > Dr. Monks, > > I have two quick questions for you. > > 1. I know that the @- Rule says that I can show P with x replaced > by t if I show @x, P. Can I show P with x replaced by x? Can I just > substitute x back in because if it is true for all x it must be true for > x? Yes. > 2. Would the following be a contradiction: @x,P(x) and ~@x,P(x) or > does it have to be @x,P(x) and ~(@x,P(x))? I don't understand the rules > regarding the parentheses. Both are contradictions. ~@x,P(x) is just an abbreviation for ~(@x,P(x)). > Thanks for your time!! Your welcome! --avoids () when possible ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 11, 2000 11:14 PM Subject: [FAQ] RE: assignment #3, #2 > -----Original Message----- > Sent: Monday, September 11, 2000 2:59 PM > To: monks@UofS.edu > Subject: assignment #3, #2 > > > Is it true that you can't let x be arbitrary if it is already used in > the proof? Yes, but by "already used in the proof" we mean that x is a FREE variable in a previous line that is still active. > For example > 1. Assume @x,@y,P(x,y) > 2. Let x be arbitrary. > > B/c if you can't let x be arbitrary how can you ever get P(x,y) on the > other side if the @+ rules requires you to let x be arbitrary? You example is ok because x isn't already "used" in the proof. The "x" that is in line 1 is a bound x, not a free one. Bound variables are "dummy" variables or "local" variables. They can't be referred to beyond the expression in which they exist. Only free variables can be considered to be "already in use". --free thinker ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 11, 2000 11:23 PM Subject: [FAQ] RE: Assignment 3, #3 > -----Original Message----- > Sent: Monday, September 11, 2000 7:02 PM > To: monks@epix.net > Subject: Assignment 3, #3 > > > Dr. Monks, > > I have two questions. > > First of all, when trying to show a contradiction, is it correct that > #x,~P(x) contradicts #x,P(x)? No. The negation of #x,~P(x) is ~#x,~P(x) > Secondly, when applying the ~- rule, is it okay if you apply it to the > term following the quantifier? For example: > > 16. Assume ~@x,~P(x) -- > 17. -><- -><-+;a,b > 18. <- -- > 19. ~@x,P(x) ~-;16,17,18 No, you removed the wrong ~ in line 19. The conclusion on line 19 should be: 19. @x,~P(x) ~-;16,17,18 according to your lines 16,17,18, and the reason you give on line 19. > Of course, assuming that everything in between would be accurate and > more detailed. This just being a brief synopsis, so as to show you > what I am trying to do. That's all I need! It's all I want! Short questions! Yeah!! :) > Thanks in advance for your assistance. You are welcome in hindsight for my assistance. --can't always get what he wa-a-nts ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Tuesday, September 12, 2000 9:58 AM Subject: [FAQ] RE: Quantifier Proofs, # 3 > -----Original Message----- > Sent: Tuesday, September 12, 2000 9:13 AM > To: monks@epix.net > Subject: Quantifier Proofs, # 3 > > > Dr. Monks, > > Is it possible to do the following: > > 1. Assume #x,~P(x) -- > 2. Assume @x, P(x) -- > 3. Let x be arbitrary -- > 4. P(x) @-; 2 > 5. ~P(x) #--;1 > 6. -><- -><-; 4,5 > 7. <- -- > 8. ~@x, P(x) ~+; 2,6,7 > ... > > Is this accurate so far? No. Line 5 is wrong. You can't do a #- without declaring the variable in it to be a new constant in the proof. The variable x in line 5 is not a new variable in the proof because it is already in use in line 4 as a free variable and it is already declared on line 3. The recipe states that you need to have a line like: 5. ~P(t) for some constant t #-;1 if you want to use the #- rule at that point. Of course, that doesn't do you any good for getting the contradiction! --drinks t constantly ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 9:16 AM Subject: [FAQ] RE: [FAQ] when t is not x Categories: Backed Up > -----Original Message----- > Sent: Tuesday, September 12, 2000 11:41 AM > To: Ken Monks > Subject: Re: [FAQ] when t is not x > > > I have a question regarding when it is correct to use t instead of x as > it pertains to the following psuedo-proof snippet... > > : > 4 Assume @x, Q(x) > 5 Let t be arbitrary > 6 Assume P(t) > 7 @x,P(x) @+;5,6 > : blah, blah > 11 -><- whatever reason > 12 <-- > 13 ~P(t) ~+;6,11,12 > 14 #x,~P(x) #+;13 > : > > So my question is: If I claim t arbitrary in 5 can I still conclude the > @x statement in 7? No you can't do a @+ on line 7 because the restriction on the @+ rule says that t cannot appear free in any assumption or premise... but it does on line 6. > But then if I declare x arbitrary in 5, can I still apply the #+ rule in > 14 if I show ~P(x) in 13? because the rule says... > > ; #+ > To show #x,P > 1. Show P with the free occurrences of x replaced by t > > Does this mean that it is Necessary that t be a new variable (other than > x declared arbitrary before applying the rule)? No, t can be equal to x in the #+ rule. In fact it can be any expression at all. --a man of many expressions ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 9:20 AM Subject: [FAQ] RE: assignment 3, #3 > -----Original Message----- > Sent: Tuesday, September 12, 2000 11:44 AM > To: monks@UofS.edu > Subject: assignment 3, #3 > > > Is it okay to do this? > > 1. Assume @x,P(x) > 2. ~P(t) for some constant t #-;(from a previous line) > 3. Assume ~P(t) > 4. P(t) @-;1 > 5. -><- -><-+; 3,4 > 6. <- > > my confusion is on line 3, i am not sure if i can assume this given > that t is already used in the proof. You can assume whatever you like. But there isn't any motivation for assuming something you already know is true. Since you already know ~P(t) on line 2, why would you want to pretend its true on line 3? -pretends to know ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 9:40 AM Subject: [FAQ] RE: assign 4 questions > -----Original Message----- > Sent: Tuesday, September 12, 2000 9:40 PM > To: monks@epix.net > Subject: assign 4 questions > > > Dr. Monks > > I had quick question about one of the tautologies you said we could > use freely. > > (P and Q) or R <=> (P or R) and (Q or R) > > can i use that in this sense? > > (P and Q) or (R and S) <=> ((P or R) and (P or S)) and ((Q or R) and (Q > or S)) > > If i can use it in this way but i did it wrong could you please tell me > how i would be able to. If you want to know if you CAN use it then the to PROVE it. If you can prove it, then I guess you can use it. If not then I guess you better be concerned. Moral: The way to tell if you can "use" something or not, is to ask yourself if you can prove it if your back is to the wall. If you can, then you can use it. If you can't then you had better not. I am not the "Oracle of Useability". Whether or not you can or cannot use something like this in a proof isn't determined by me by my personal whim, it's determined by logic and mathematics. I can clarify rules you don't understand, and I can specify the format I want the proofs to be in in order to make grading easier, but as far as what is mathematically correct or not, I am not the one who says if it is... it is either correct or it isn't. So what I want you to learn, in addition to the other things in the course, is how to know for yourself if something like this is useable or not. You, as mathematicians, need to be able to tell the difference between something that is correct and something that isn't. If you aren't sure (which your question indicates you are not) then you MUST prove it and NOT use it until you do prove it. Something like the above should be easy enough for you by now to prove it to yourself without asking me if its right or not. If you don't know if it is right then prove it. Otherwise I might not believe you and think you are just doing wishful thinking. > And one more question. Some of the questions on the homework dont seem > to ask for proofs like #18, 23, 24. Do you want us to write up a proof > for those or just do them without a formal proof? You don't have to give a proof in #18. In #23, you should answer then question and give an explanation, but don't need to prove it. In #24 you should give a proof for the ones that are associative and commutative, but you can just give a counterexample for the ones that are not (although you can also write counterexamples in the form of a proof if you like). If you want recipe's for showing an operator is commutative: ;commutative
To show *:AxA->A is commutative
1. Let a,b in A
2. Show a*b=b*a
;associative
To show *:AxA->A is associative
1. Let a,b,c in A
2. Show (a*b)*c=a*(b*c)
Note that these proofs are a very good place to use the "string of equalities" proof format I mentioned yesterday, e.g. : 5. a*b=blah 6. =wah 7. =fah 8. =b*a : --the Oracle of Wisdom, not Useability ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 12:22 PM Subject: [FAQ] yesterday's lecture... con't Math-o-nauts: As promised, here is the rest of the proof I wasn't able to finish at the end of class because we ran out of time. But first, in order to make life easier on all of us in this proof and in the future, I want to give you two "gifts" that we can use in our proofs from now on. Thm (Distributivity of # over OR):
(#x,P(x) or Q(x)) <=> (#x,P(x)) or (#x,Q(x))
Pf. (=>) 1. Assume #x,P(x) or Q(x) - 2. P(t) or Q(t) for some constant t #-;1 3. Assume P(t) - 4. #x,P(x) #+;3 5. (#x,P(x)) or (#x,Q(x)) or+;4 6. <- - 7. Assume Q(t) - 8. #x,Q(x) #+;7 9. (#x,P(x)) or (#x,Q(x)) or+;9 10. <- - 11. (#x,P(x)) or (#x,Q(x)) or-;2,3,5,7,9,10 12. <- - 13. (#x,P(x) or Q(x))=>(#x,P(x)) or (#x,Q(x)) =>+;1,11,12 (<=) 14. Assume (#x,P(x)) or (#x,Q(x)) - 15. Assume (#x,P(x)) - 16. P(t) for some constant t #-;15 17. P(t) or Q(t) or+;16 18. #x,P(x) or Q(x) #+;17 19. <- - 20. Assume (#x,Q(x)) - 21. Q(t) for some constant t #-;21 22. P(t) or Q(t) or+;21 23. #x,P(x) or Q(x) #+;22 24. <- - 25. #x,P(x) or Q(x) or-;14,15,18,19,20,23,24 26. <- - 27. (#x,P(x)) or (#x,Q(x))=>(#x,P(x) or Q(x)) =>+;14,25,26 28. (#x,P(x) or Q(x)) <=> (#x,P(x)) or (#x,Q(x)) <=>+;13,27 QED and while we are at it we might as well prove its "partner": Thm (Distributivity of @ over AND)
(@x,P(x) and Q(x)) <=> (@x,P(x)) and (@x,Q(x))
Pf: (=>) 1. Assume @x,P(x) and Q(x) - 2. Let x be arbitrary - 3. P(x) and Q(x) @-;1 4. P(x) and-;3 5. @x,P(x) @+;2,4 6. Q(x) and-;3 7. @x,Q(x) @+;2,6 8. (@x,P(x)) and (@x,Q(x)) and+;5,7 9. <- - 10. (@x,P(x) and Q(x)) => (@x,P(x)) and (@,Q(x)) =>+;1,8,9 (<=) 11. Assume (@x,P(x)) and (@x,Q(x)) - 12. @x,P(x) and-;11 13. @x,Q(x) and-;11 12. Let x be arbitrary - 13. P(x) @-;12 14. Q(x) @-;13 14. P(x) and Q(x) and+;13,14 15. @x,P(x) and Q(x) @+12,14 19. <- - 20. (@x,P(x)) and (@x,Q(x)) => (@x,P(x) and Q(x)) =>+;11,15,19 21. (@x,P(x) and Q(x))<=>(@x,P(x)) and (@x,Q(x)) <=>+;10,20 QED So we can use these (and recipes derived from them) in our proofs from now on. Here is the completed example that I started in lecture. I will use U for the union symbol and C for the subset symbol here for brevity. I will do this proof in our new semi-formal style. Note: this is problem #33a on page 518. Thm: Let f:B->D and S,T subsets of B. Then f(S U T) C f(S) U f(T) Pf. 1. Let f:B->D and S,T C B Given 2. Let b in f(S U T) - 3. #a in S U T, b=f(a) Def of image;2 4. a in S U T and-,#-;3 5. a in S or a in T def of U;4 6. (a in S or a in T) and b=f(a) and+;5,3 7. (a in S and b=f(a)) or (a in T and b=f(a)) distr of and/or;6 8. #x,(x in S and b=f(x)) or (x in T and b=f(x)) #+;7 9. (#x,(x in S and b=f(x))) or (#x,(x in T and b=f(x))) dist of #/or;8 10. b in f(S) or b in f(T) def of image;subst;9 11. b in f(S) U f(T) def of U;10 12. f(S U T) C f(S) U f(T) def of subset;2,11 QED Note that we used the Theorem that we proved above on line 8. Also notice how much shorter and readable a semi-formal proof is than it's formal counterpart. By skipping all of the "uninteresting" steps we get a much nicer proof. While we are at it, let's do one other example. Here is problem #34. We will use ^ temporarily for the intersection symbol since it is the closest thing I can find on the keyboard and we don't have to use it for exponentiation in this situation. Thm: Let f:B->D. Then f is injective <=> f(S ^ T)=f(S) ^ f(T) for all subsets S,T of B. Pf.
1. Let f:B->D
(=>)
2. Assume f is injective -
3. Let S,T C B -
4. Let b in f(S ^ T) -
5. #a in S ^ T, b=f(a) def of image;3
6. a in S ^ T and-;#-;5
7. a in S and a in T def of ^;7
8. a in S and b=f(a) and+;and-;#-;5,7
9. #x in S,b=f(x) #+;8
10. b in f(S) def of image;9
11. a in T and b=f(a) and+;and-;#-;7,5
12. #x in T, b=f(x) #+;11
13. b in f(T) def of image;12
14. b in f(S) and b in f(T) and+;10,13
15. b in f(S) ^ f(T) def of ^;14
16. f(S ^ T) C f(S) ^ f(T) def of C;4,15
17. @S C B,@T C B, f(S ^ T) C f(S) ^ f(T) @+;3,16
18. <-
19. f is injective => f(S ^ T)=f(S) ^ f(T) for all subsets S,T of B.
=>+;2,17,18
(<=)
20. Assume @S C B,@T C B, f(S ^ T) C f(S) ^ f(T)
21. Let x,y in B
22. Assume f(x)=f(y)
23. Let S={x}
24. Let T={y}
25. S C B and T C B Def of C;21,23,24
26. Assume x~=y -
27. S ^ T = {x} ^ {y} subst;23,24
28. = {} Def of ^;26
29. S ^ T = {} transitivity;27,28
30. {}=f({}) def of image
31. =f(S ^ T) subst;29
32. =f(S) ^ f(T) @-;subst;20,25
33. =f({x}) ^ f({y}) subst;23,24
34. ={f(x)} ^ {f(y)} def of image
35. ={f(x)} ^ {f(x)} subst;22
36. ={f(x)} def of ^
37. {}={f(x)} transitivity;30-36
38. f(x) in {f(x)} def of set notation
39. f(x) in {} subst;37,38
40. ~(f(x) in {}) def of empty set
41. -><- -><-+;39,40
42. <-
43. x=y ~-;26,41,42
44. <-
45. f is injective def of injective;21,22,43,44
46. <-
47. (f(S ^ T)=f(S) ^ f(T) for all subsets S,T of B) => f is injective.
=>+;20,45,46
48. f is injective <=> f(S ^ T)=f(S) ^ f(T) for all subsets S,T of B <=>+;19,47 QED So there is another example of a semi-formal proof. Try to detect all of the shortcuts being used. (Just think how long this proof would be if we did it formally!). Notice that I am using another shortcut in this proof that I didn't mention in class yesterday... namely, if you are working with FINITE sets, you can do "computations" with them within your proof without going through a formal definition using "cases" for each of the elements in the sets (which would be horrendously tedious!) as the formal definitions require. I used this shortcut on lines 28,30,34,36, and 38. Also notice that in the "chain of equalities" notation (e.g. lines 30-36) if the reason for a line only refers to the previous line we can omit that line number since the chain-of-equals notation implies that you are working with the previous line. I hope these examples help you with your homework! This concludes today's electronic lectures on set theory. Tomorrow I will start on Chapter 1.1. Enjoy!! --virtual lecturer ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 12:37 PM Subject: [FAQ] RE: assignment 4, #25 > -----Original Message----- > Sent: Wednesday, September 13, 2000 12:20 PM > To: monks@UofS.edu > Subject: assignment 4, #25 > > > I'm having some problems provinf injection. > For example if you have f: Z->Z f(x)= 7x > should the first line read > 1. Let x,y in Z > then can you go from line 2 to line 3? > 2. Assume f(x)=f(y) > 3. 7x=7y def of f(x) Sure. Except you probably should state the "givens" on line 0, then you could refer to that line when you say "def of f" on line 3. You are also using substitution and @- on line 3. Shortcuts, shortcuts, shortcuts... :) --likes short AND correct ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 12:41 PM Subject: [FAQ] RE: appendix B, numbers 21 and 24, pp. 516-517 > -----Original Message----- > Sent: Wednesday, September 13, 2000 11:17 AM > To: monks@epix.net > Subject: appendix B, numbers 21 and 24, pp. 516-517 > > dr. monks .. > > 1) for question 21 .. if i let y be in [(A U B)-(A I B)] and i need to > show y in [(A-B) U (B-A)], does it suffice to simply show y in (A-B)? No. You must show the whole thing. --prefers complete and short and correct ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 1:50 PM Subject: [FAQ] RE: question about when we can say "Arithmetic" > -----Original Message----- > Sent: Wednesday, September 13, 2000 1:02 PM > To: monks@epix.net > Subject: question about when we can say "Arithmetic" > > > Dr. Monks > > You said yesterday since we have not defined any basic operations yet, > like +, -, *, /, that if we use them we can just cite the reason for a > step by one of them as "by Arithmetic." So would this be a good > example of how to use that properly.... > > x^2 = y^2 > x = y by arithmetic > > Thanks all powerful and knowing one It would be a good example if it weren't for the fact that it is false (if x,y are real vars). --apparently learned different "arithmetic" ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 1:53 PM Subject: [FAQ] RE: Grading Question > -----Original Message----- > Sent: Wednesday, September 13, 2000 1:36 PM > To: monks@epix.net > Subject: Grading Question > > > Doc Monks, > > For number 26 in assignment 4 there exists 4 parts: a,b,c,d. Let's say I > could only get a,b,c done and you grade that number would it be wrong? > > --Quick Question=>QQ I usually grade each part of each question as a separate problem, selected randomly, of course. --Rand-y! ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 9:06 PM Subject: [FAQ] RE: [FAQ] RE: assign 4 questions > -----Original Message----- > Sent: Wednesday, September 13, 2000 4:21 PM > To: Ken Monks > Subject: Re: [FAQ] RE: assign 4 questions > > > Dr. Monks, > For question # 24, we are to prove whether the operations are commutative > or associative. Well, I have finished the commutative part but I am having > trouble figuring out how it could be associative when there are only two > variable terms. How would I add in the c variable to prove associativity? > Could you give me an example of something similar? > Thanks > Bewildered Sure. 1. @a,b in R,a*b=b+a Given 2. Let a,b,c in R - 3. (a*b)*c=c+(a*b) @-;1 (or Def of *;1);subst 4. =c+(b+a) " 5. =(c+b)+a assoc of + in R 6. =(b*c)+a Def of *;subst;1 7. =a*(b*c) " 8. * is associative def of ass.;2,3,7 QED See the recipe for associativity I sent in a recent email. --the ass. man ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 9:08 PM Subject: [FAQ] RE: Assign 4 # 21 > -----Original Message----- > Sent: Wednesday, September 13, 2000 6:21 PM > To: monks@epix.net > Subject: Assign 4 # 21 > > > Dr Monks > > I wanted to know if this would be acceptable or if it would be in one > of those grey areas that you said you would question whether or not we > could get that if we had a gun to our head > > x not in (A intersection B) <=> ~(x in (A intersection B)) > > Thanx a bunch You can treat "z not in S" and "~(z in S)" as if they are the same statement in your proofs. No guns will appear. --slow to draw ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 13, 2000 9:14 PM Subject: [FAQ] RE: assignment 4,#23 > -----Original Message----- > Sent: Wednesday, September 13, 2000 2:01 PM > To: monks@UofS.edu > Subject: assignment 4,#23 > > > I am having trouble understanding what #23 is asking. > They want to know if rule defines a function R**->R. > Does the rule say c->sqrtC or sqrtc->c or do i have it all wrong? The question says what it says. The term "sqrt" does not appear anywhere in the question in my copy of the textbook. --can spell both square and sqrt ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Thursday, September 14, 2000 8:36 AM Subject: [FAQ] RE: [FAQ] =>, or, substitution Categories: Backed Up > -----Original Message----- > Sent: Wednesday, September 13, 2000 11:26 PM > To: monks@epix.net > Subject: [FAQ] =>, or, substitution > > If we have > 5. (P or Q) > 6. P=>R > 7. Q=>S > then can we conclude without an extra tedious proof (ie is this a legal > shortcut)... > 8. R or S by substitution of lines 6 and 7 into 5 I wouldn't do this as a shortcut. I would do it like this: 5. (P or Q) 6. P=>R or S 7. Q=>R or S 8. R or S or-;5,6,7 If you can prove R by assuming P then you can prove R or S by assuming P by the or+ rule. Similarly for the other case. So it's only two lines longer but makes it clearer what's going on. Remember, you should be able to write out the entire formal proof if a gun is to your head. When you are writing your proofs and asking yourself if a "shortcut" is allowed or if you are NOT sure of what reason to write for a line, then that is a very good indication that you CAN'T write out a formal version. If you CAN write out a formal version then you WILL know what the reasons should be because you can just think about all the reasons you would have used in the formal version. Dig? Speaking of shortcuts and formatting, there is one common form of the or- rule that is often used. Since "P or ~P" is a tautology for any statement P, we can always do a proof by cases argument like this: (Case 1:)
5. Assume P
: :
16. R
<-
(Case 2)
17. Assume ~P
: :
23. R
<-
24. R or-;5,16,17,23
If you want to write the (P or ~P) on line 4 just to make the or- complete, that is ok too. Another example of this is the trichotomy law: 4. x>y or x=y or x<y
(case 1)
5. Assume x>y
:
16. R
<-
(case 2)
17. Assume x=y
:
23. R
<-
(case 3)
24. Assume x<y
:
35. R
<-
36. R or-;4,5,16,17,23,24,35
This is another example of reformatting or-; so it looks like a proof by cases (which is what it is!). --getting on your cases ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, September 15, 2000 10:30 AM Subject: [FAQ] RE: assignment 5, #28 > -----Original Message----- > Sent: Thursday, September 14, 2000 7:11 PM > To: monks@UofS.edu > Subject: assignment 5, #28 > > if you are trying to prove something is injective and you know g o f is > injective, would you still say > @x,@y,f(x)=f(y) => x=y > or would it be > @x,@y, (gof)(x)=(gof)(y) => x=y If you know gof is injective then you know this: @x,@y, (gof)(x)=(gof)(y) => x=y --gof'y ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Saturday, September 16, 2000 5:05 PM Subject: [FAQ] RE: [FAQ] yesterday's lecture... con't > -----Original Message----- > Sent: Saturday, September 16, 2000 4:07 PM > To: Ken Monks > Subject: Re: [FAQ] yesterday's lecture... con't > > Dr. Monks, > I am looking over the the example problem you gave us over email: f(S U T) > C f(S) U f(T). I don't understand how you derived line 10. I guess it's > because I don't understand the image definition. Could you give a quick > example that may help me learn it. > Thanks OK, here is the proof I sent you: Thm: Let f:B->D and S,T subsets of B. Then f(S U T) C f(S) U f(T) Pf. 1. Let f:B->D and S,T C B Given 2. Let b in f(S U T) - 3. #a in S U T, b=f(a) Def of image;2 4. a in S U T and-,#-;3 5. a in S or a in T def of U;4 6. (a in S or a in T) and b=f(a) and+;5,3 7. (a in S and b=f(a)) or (a in T and b=f(a)) distr of and/or;6 8. #x,(x in S and b=f(x)) or (x in T and b=f(x)) #+;7 9. (#x,(x in S and b=f(x))) or (#x,(x in T and b=f(x))) dist of #/or;8 10. b in f(S) or b in f(T) def of image;subst;9 11. b in f(S) U f(T) def of U;10 12. f(S U T) C f(S) U f(T) def of subset;2,11 QED You don't understand how I got line 10. Well, let's see. The definition of image is: y in g(A) <=> #x, x in A and y=g(x) so in getting from line 9 to line 10, we are just using this definition twice, namely (#x,(x in S and b=f(x))) is the same as saying "b in f(S)" and (#x,(x in T and b=f(x))) is the same as saying "b in f(T)". So it is exactly the definition of image. What does it mean? Well, if g:A->B and S is a subset of A, then g(S) is the subset of B that you get if you compute g(s) for every s in S and put them into a set. For example, suppose g:R->R by g(x)=x^2 and S={1,2,3,4}. Then g(S)={1,4,9,16}.
Notice that there is a difference between g(W) when W is an element of the domain and g(W) when W is a subset of the domain. So in the example above we would have: g({2,5})={4,25}
g({5})={25}
g(5)=25
See the difference? So you have to know if your argument is a set or an element of the domain before interpreting an expression of the form g(W). --helps with your image ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Saturday, September 16, 2000 5:42 PM Subject: [FAQ] RE: Assign 5 #28 > -----Original Message----- > Sent: Saturday, September 16, 2000 4:47 PM > To: monks@epix.net > Subject: Assign 5 #28 > > > Dr. Monks > > If I were to have something like this > > g(f(x)) = g(f(y)) for some functions g and f is it true enough to say > this.... > > g(f(x)) = g(f(y)) > f(x) = f(y) by arithmetic > x = y by arithmetic > > since the composite function is already given to be injective? No. Its not "true enough". In fact, it's not true at all. You only know gof is injective, yet it does not appear in any of the three statements above, so how do you expect to be able to conclude anything from the fact that it is injective? If the recipe for a cake calls for flour and you have no flour, you aren't going to make much of a cake. As a second point... you CAN'T use the reason "by arithmetic" for such lines, even if they are right. "by arithmetic" has a very very specific meaning in our course at this point. It ONLY refers to facts about N,Z,Q,R, and C that we haven't proven or defined in the course. IT DOES NOT APPLY TO ANYTHING ELSE! In particular, it doesn't apply to functions, sets, logic, other number systems beyond those mentioned above, geometry, literature, or famous movies of the 70's. In order to encourage you to realize that "by arithmetic" is not a "WILDCARD" reason that you can put on any old line as a reason when you can't think of a reason, I will tell you the following secret... I WILL MARK COMPLETELY WRONG ANY PROOF THAT USES "by arithmetic" to justify a line which does not use a fact about the number systems N,Z,Q,R, or C that you learned prior to this course. If it refers to anything else, then the entire proof will be wrong. "by arithmetic" is only the reason we use to describe facts about N,Z,Q,R, or C that we are assumed to know as a prerequisite for the course by the author of your book. Note that you also can't use "by arithmetic" to refer to properties of N,Z,Q,R, or C that are PROVEN or STATED in your book or in lecture. For example, if you use the Division Algorithm, then you should use "Division Algorithm" for the reason, and not "arithmetic", since the Division Algorithm is a theorem about Z that we proved in the course and is stated and proved in your book (even though it is a fact about Z. > Or in order to do that would i have to assume that g has an inverse or > show that it has an inverse or declare its inverse? A function only has an inverse if it is bijective. If you want to Assume g has an inverse, go ahead... you can Assume whatever you like in a proof. Heck you can Assume f is injective if you like! But the real question is whether or not Assuming such things is going to do you any good. Remember, the only motivation for Assuming anything in a proof is to either do a =>+ or a proof by contradiction. So if you aren't planning to do either one of them, then you should consider whether or not you want to Assume what you are suggesting. --hates wildcard reasons ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 18, 2000 10:05 AM Subject: [FAQ] RE: appendix b - #28b > -----Original Message----- > Sent: Sunday, September 17, 2000 3:38 PM > To: monks@epix.net > Subject: appendix b - #28b - p. 518 > > > dr. monks .. > > in all of these questions where we have to give specific examples, > what exactly do we have to define? for example, in 28a, would i have to > define B, C, and D for f:B->C and g:C-D and then define a f(x) and a g(x)? Yes! > these questions are giving me more headaches than the proofs! > > thanks for your help! --headache doctor ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 18, 2000 11:34 AM Subject: [FAQ] RE: Assign #5 #35 > -----Original Message----- > Sent: Monday, September 18, 2000 10:35 AM > To: monks@epix.net > Subject: Assign #5 #35 > > > Dr. Monks > > Are we allowed to use a "let" statement for the thing that we are > trying to prove. For instance, in #35, > > n. Let (gof)inverse = f(inverse)og(inverse) > > I am trying to use this with the definition of inverse. > > Thanks There are currently only three uses for the word "Let" in your proofs: ---------------------------------------------- A. Let x be arbitrary (the "declarative" form) ---------------------------------------------- where x can be any new variable in the proof. This merely declares that you are introducing a new variable in the proof that is arbitrary (and thus a valid candidate for use in the @+ rule). ------------------------------------------ B. Let P(x) (the "hidden assumption" form) ------------------------------------------ where P(x) is a statement about a new variable x in the proof. This is the same as saying: Let x be arbitrary
Assume P(x)
So it contains a hidden assumption. For example: Let x in R means: Let x be arbitrary.
Assume x in R.
There are a few variations on this form of "Let". First you can use it to declare several variables at once: Let a,b,c in N and a>0 means: Let a be arbitrary
Let b be arbitrary
Let c be arbitrary
Assume a in N and b in N and c in N and a>0
The second variation is that you can use this form to declare "Given" information in the theorem you are proving (premises). For example, if you have a thm that says: Thm: Let x be white and y be red. Then [x.y] is blue. You can start it by: Pf: 1. Let x be white and y be blue Given This doesn't have a hidden assumption, because the statement is a premise (which is effectively the same thing as a hidden assumption. ------------------------------ C. Let x=E (definition form) ------------------------------ where E is any expression and x is any variable. This is the same as saying: Define x=E The purpose of this statement is to allow the proof author to define short symbols to represent messy expressions in his/her proof for readability. Since the author is defining the symbol x to stand for the expression E in his proof, there is no hidden assumption in this form of "Let". It is considered to be an axiom or definition that the author is declaring on the spot. This form can also be extended to define more complicated notation. ------------------------------- Now if you look at what you are asking above, you can ask which of the three forms you mean. Well, you can't possible mean any of the three forms of let because (A) you aren't declaring a new arbitrary variable (B) you aren't declaring a new variable and Assuming the conclusion of your theorem and (C) you aren't defining a new symbol or notation since the symbols are already defined in the problem. What is even less subtle is that you seem to be asking if you can assume what you are trying to prove in a theorem. The answer to this is technically, yes, and practically, no. Technically, you can assume whatever you like in a proof... even what you are trying to prove. But in practice it does you no good whatsoever to assume what you want to prove because (as he takes a deep breath before typing it for the zillionth time this semester in email...) the ONLY reason to make an assumption is if you intend to use a recipe that requires it, like =>+ or proof by contradiction. Otherwise you just bury yourself into a fantasy world that you can never get any useful information out of. Let me give you a concrete example: "Thm": 1+1=3 Pf: 1. Assume 1+1=3 - 2. ??? Where are we going to go from here? We assumed what we are trying to prove, but it does us no good. In fact, there is no way to prove this because it is clearly a false fact about the integers. But we CAN assume it in line 1, that is allowed. We just can't use it for anything useful. This is the situation with what you are asking. There is never any reason to assume what you are trying to prove in a theorem because you are just pretending it, but you need to prove it in the real world, not pretend it. So if you want to assume that (gof)^(-1)=f^(-1)og^(-1) go right ahead... but it won't do you any good. --David "Let"-R-Monks ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 18, 2000 1:01 PM Subject: [FAQ] RE: Assignment #5: Appendix B, #32, p.517 > -----Original Message----- > Sent: Monday, September 18, 2000 12:37 PM > To: monks@UofS.edu > Subject: Assignment #5: Appendix B, #32, p.517 > > > Are we allowed to prove #32 using induction? Thanks in advance. Yes, if you want to. --inductee of the math hall of fame ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 18, 2000 3:18 PM Subject: [FAQ] RE: Assignment #5 - #32, p.517 > -----Original Message----- > Sent: Monday, September 18, 2000 2:14 PM > To: monks@UofS.edu > Subject: Assignment #5 - #32, p.517 > > > Are we allowed to use the pigeonhole principle? Thanks in advance. > > - never seen a holey pigeon, only seen a holey penguin For this proof, yes. --searching for a holey mackerel ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 18, 2000 3:39 PM Subject: [FAQ] RE: Assignment #5 - #32, p.517 > -----Original Message-----
> Sent: Monday, September 18, 2000 2:32 PM
> To: monks@UofS.edu
> Subject: Assignment #5 - #32, p.517
>
> Are we allowed to use cardinality in our proofs? Thanks in advance.
>
> - | { x | x is a correct proof in my homework } | = 0
For finite sets you can use cardinality. One of the shortcuts I mentioned was that you can do normal operations with finite sets in your proof all at once without going through the all the details of starting from the definitions and doing proof by cases for each element and so on. For example, you can just do this: :
5. {a,b,c} U {b,c,d} = {a,b,c,d} Def of Union
:
in your proof because these are finite sets and we assume the reader of the proof can verify that this is true by "brute force" inspection. Otherwise we would have to do crazy things like: :
5. Let x in {a,b,c} U {b,c,d}
6. x in {a,b,c} or x in {b,c,d} Def Union;5
7. (x=a or x=b or x=c) or (x=b or x=c or x=d) Def {} notation;6
:
: (a whole bunch of nonsense, or- rules and
: maybe lemmas like P or P => P)
123. x in {a,b,c,d} after much work
124. {a,b,c} U {b,c,d} subset {a,b,c,d} Def subset;5,123
125. Let x in {a,b,c,d}
126. x=a or x=b or x=c or x=d Def {} notation;
:
: (lots of more nonsense)
:
287. x in {a,b,c} U {b,c,d} after much work
288. {a,b,c,d} subset {a,b,c} Def subset;125,287
289. {a,b,c} U {b,c,d} = {a,b,c,d} def of set =;124,288
:
So I think you will agree, we should allow operations involving finite sets similar to what I did in the first example. :) Does cardinality fall in this "realm"? Well, we never defined cardinality and
we have no theorems about it. But we are supposed to know about arithmetic and
the natural numbers and I said you could use the pigeonhole principle if you
like, and this certainly assumes you can say things about cardinality in some
sense. Officially, a finite set S has cardinality n iff there exists a
bijection f:{1,2,...,n}->S. For a finite set, say, {a,b,c,d}, if you want to
say that this set has 4 elements, then you will get no argument from me. :)
--can count to 4 ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 20, 2000 11:00 AM Subject: [FAQ] RE: sec 1.1, question about even > -----Original Message----- > Sent: Tuesday, September 19, 2000 11:24 PM > To: monks@epix.net > Subject: sec 1.1, question about even > > here's a hypothetical situation: > > let's say that i have 4k(k+1)+1. then i know that either k is even or > k+1 is even. How do you "know" that? Did you prove it? If not then you don't "know" it, you just think you know it. :) > if i assume that k is even, i know that 2|k. This is true by the definition of even. > if i assume that k+1 is even, i know that 2|k+1. This is also true. > can i then conclude that, either > way, 8|4k(k+1)? No, not unless you prove it. > -- "even" after your definition, still unsure The trick with these problems is to FORGET EVERYTHING YOU THINK YOU KNOW about even and odd. The problem is that we THINK we know things about these concepts intuitively, but that isn't the point. The point is to use ONLY the definitions to prove what you think you know. Perhaps the best way to attack these problems is this: Replace the word "Even" with "Zoop" and "Odd" with "Blep". Then n is zoop <=> 2|n and n is blep <=> n is not zoop. Now, ask yourself: is it true that for any integer k, either k is zoop or k+1 is zoop? When you say it this way (forgetting that zoop means even) it is clear that there is something you need to prove. So perhaps you should do the whole proof using zoop and blep and then translate back to odd and even before you hand it in. (Don't hand in proofs with "zoop" and "blep" in them!!!) But be careful not to "think" of zoop and blep as even and odd when doing the proof. --a Blep from the planet Zoop ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 20, 2000 11:26 AM Subject: [FAQ] RE: assignment #6, #5 & assing 7, #16 > -----Original Message----- > Sent: Wednesday, September 20, 2000 11:09 AM > To: monks@UofS.edu > Subject: assignment #6, #5 & assing 7, #16 > > > when we are proving #5 can we use a table like you did in the example in > class? Yes. > Does the table go in the proof, or do you keep it to the side a > refer to it? IT IS PART OF THE PROOF! It is only a convenient way to do proof by cases (or- ). If you have a table like this: x x^2 ------- 0 0 1 1 2 4 3 9 4 16 5 25 Then this is just a shorthand for: Assume x=0 x^2=0 <- Assume x=1 x^2=1 <- Assume x=2 x^2=4 <- etc So if you know x=0 or x=1 or x=2 or ... or x=5 and you show in each of the above cases that some statement R holds, then by or- rule you can conclude R. That is what I did in the example. Using a table is NOT a new thing you can do in a proof, it is only a reformatting of something you already can do in your proof. --not fooled by appearances ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 20, 2000 2:07 PM Subject: [FAQ] RE: Assign #6 > -----Original Message----- > Sent: Wednesday, September 20, 2000 12:15 PM > To: monks@epix.net > Subject: Assign #6 > > > Dr. Monks > > I understand the definition that you gave for even and odd. But, how > can we use divisibility in section 1.1 when we dont define it until 1.2? > Shouldn't we be able just to say n=2k for some integer k if n is even > and n=2k+1 for some integer k if n is odd like we always have. I know > we have to throw out what we have always learned in a sense but we > havent learned the new way in section 1.1 yet > > Thanks > > Trying to make my life a little easier Well, this is true, Section 1.2 isn't until after Section 1.1 and divisibility is in 1.2. So if it is bothering you you can always define "even" this way without using the defined-in-the-next-section concept of "divisibility": Def (for the "divisibility impaired"): An integer n is even <=> 2k=n for some k in Z. So there it is, without the evil | symbol. Of course, it says exactly the same thing since the statement to the right of the <=> is the definition of 2|n. :-) The definition of odd, remains the same since it doesn't use |. So if you want to use the above definition, that is fine. --likes | ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Thursday, September 21, 2000 12:45 PM Subject: [FAQ] RE: Assign #6 #8 > -----Original Message----- > Sent: Wednesday, September 20, 2000 9:28 PM > To: monks@epix.net > Subject: Assign #6 #8 > > > Dr Monks > > For number 8, after i already put one of those CASE tables in my proof > am i allowed to put in a line like this > > r^2 = 8d + E , d is integer, E = 1, r ~= 2n, n is integer > > I guess the main point of the question is about the last part > I want to know if that r ~= 2n is sufficient to restrict r to odd. > > Thanx All powerful and knowing one Well, no, not the way you are stating it. In order to say r is odd you must show that it is not even. In order to show r is even you must show #n in Z,r=2n. Thus to show it is odd you have to show ~(#n in Z,r=2n) which, by DeMorgan's law is equivalent to @n in Z, r~=2n. Thus in order to show that r is odd you must show that r~=2n FOR EVERY INTEGER n, not r~=2n where n is some integer. For example, if n=3 and r=2 then r~=2n but r is no odd either. --only semi-powerful and knowing ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, September 22, 2000 12:55 PM Subject: [FAQ] RE: FAQ > -----Original Message----- > Sent: Friday, September 22, 2000 11:18 AM > To: monks@UofS.edu > Subject: FAQ > > > i have a general question. I found parts of a proof in the FAQ's, but i > don't think all of it is correct and i am changing some of it around. > So what should i do, should i say what lines i got from the FAQ's or > since i'm changing it around do i have to cite the FAQ's at all? As long as you are rewriting the whole proof in your homework you don't have to refer to the FAQ's at all. The only time you have to refer to the FAQ's are when the WHOLE proof occurs in the FAQ and you don't include the whole proof in your assignment, just refer to the FAQ. Otherwise you can get all the free hints and info you like from there, but the writeup has to be yours and doesn't need to reference the FAQ's at all. --getting the FAQs straight ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 8:57 AM Subject: [FAQ] RE: example using euclidean algorithm > -----Original Message----- > Sent: Sunday, September 24, 2000 7:59 PM > To: monks@epix.net > Subject: example using euclidean algorithm > > > dr. monks .. > > if you wouldn't mind, i would really appreciate it if you could do an > example that uses the Euclidean algorithm. thank you! Sure. Here is a cute one. Ex: Reduce the fraction 9017 ----- 12319 while trapped on a desert island (no Maple or calculators available... it's not a resort island apparently. :) ). Now before we solve this, try reducing this by hand for a minute or two... : ok, give up? It's freakin hard, right? But using the Euclidean algorithm makes it easy. To reduce the fraction, we need to find the gcd of the numerator and denominator and divide both by it. So we use the Euclidean algorithm. We divide 9017 into 12319 and get a remainder of 3302 which we replace the 12319 with and iterate: gcd(12319,9017)=gcd(9017,3302)
=gcd(3302,2413)
=gcd(2413,889)
=gcd(889,635)
=gcd(635,254)
=gcd(254,127)
=gcd(127,0)
=127
So 127 is the gcd. Thus dividing 127 into the numerator and denominator we obtain: 71 -- 97 QED! So there is an application of the Euclidean algorithm to third grade arithmetic... reducing fractions. --third grade math teacher ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 9:11 AM Subject: [FAQ] RE: Assign 7 #18 > -----Original Message----- > Sent: Sunday, September 24, 2000 5:22 PM > To: monks@epix.net > Subject: Assign 7 #18 > > > Dr. Monks > > With problems set up like 18 on page 13, do we have to treat that as an > <=> or only have to start with one side and show its equals the other? Well let's see... here is what it says in my book: "18. If c>0, prove that (ca,cb)=c(a,b)." So my problem has no <=> in it, either explicitly or implied. Does yours? <=> is not =. --knows ~(<=> = =) ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 9:14 AM Subject: [FAQ] RE: Assign 7 #21 > -----Original Message----- > Sent: Sunday, September 24, 2000 5:42 PM > To: monks@epix.net > Subject: Assign 7 #21 > > > Dr. Monks > > I have already shown that c | d. Now can i assert from that the fast > that c <= d? After all, you cannot divide a number with another number > larger than it in the way divides is used with '|'. See your lecture notes for exciting and relevant information ... --gives exciting and relevant lectures ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 11:07 AM Subject: [FAQ] homework tip After grading your recent semi-formal proofs, there is one SIGNIFICANT source of error that is causing a LOT of you to lose points in your proofs, and so I want to mention it and try to "plug the hole" in your understanding so that you don't loose points for that reason in the future. The number one reason that people are getting proofs wrong is not handing in the problem. But there is no easy fix for that. The number two reason that people are getting proofs wrong is: NOT KNOWING WHAT EVERY VARIABLE STANDS FOR! and this problem we can fix! There is widespread confusion about what each variable in your proof represents. Many people are confusing variable that appear in a proof or definition with a variable that appears in the statement of the problem with a variable that they are making up in their proof, and this is leading to logical errors in the proof itself. A sub-symptom of this is that people are sometimes using the same variable for two different things in the proof, sometimes in the SAME LINE! I have been "liberal" in grading these problems and I haven't taken off points for misuse of variable names or undeclared variables unless its misuse made the logic of the proof entirely wrong. However, this problem is going to keep causing you to loose points unless we do something to stop its proliferation. So in order to cure this plague that has infected my otherwise brilliant class, I will now inoculate you with what I hope will be the cure! Thus I must make the following new RULE which MUST be followed or else I will just mark the problem wrong. ------------------------------------------------------------------------------- The New Declare-Everything Rule that MUST be followed under penalty of -0.1ness: I. EVERY FREE VARIABLE* that appears in your proof MUST be declared. (Bound variables don't have to be declared!) There are only three possible ways to declare a variable: a. You can declare it to be arbitrary. There are two formats for doing this:
i. You can simply say: "Let x be arbitrary".
ii. You can use the shorthand "Let P(x)" where P(x) is a statement
about x and x is a new free variable in the proof. This is an
abbreviation for:
"Let x be arbitrary
Assume P(x)"
b. You can declare it to be a constant using the #- rule. There are
several formats for doing this:
i. You can simply say "P(x) for some constant x" (if the #- rule allows it)
ii. You can drop the word "constant" from the previous format.
iii. You can use the shortcut which uses the bound variable in a # statement
as being implicitly declared as a new constant in the proof.
c. You can define a new variable to represent anything you like. The only format
that will be allowed to do this from now on is "Define x=Expression". You may
NOT use the word LET to define variables anymore.
*Note: this does not include free variables which are defined permanently in mathematics to represent constant objects, e.g. Z always represents the integers, pi represents the number 3.14..., etc. These mathematical symbols are considered to be universally defined and don't have to be declared in your proofs. -------------------------------------------------------------------------------- Any proof containing any free variable which is NOT declared by one of the three methods above will immediately be marked wrong. Thus, as a consequence of this: 1. There is only ONE possible use for the word "LET" in your proof. You can only use "LET" when you are declaring variables to be ARBITRARY. This is true whether you are using it to state the "Givens" in your proof or just preparing to do a @+ rule of your own. You can make assumptions on the arbitrary variables you are declaring as in format I.a.ii in the rule above, but in this case you are still declaring these variables to be arbitrary. So the word LET is ONLY used when you are declaring arbitrary variables. 2. When you DEFINE a new variable in your proof, you must use the keyword "Define" not "LET" from now on. This way you will know the difference between defining a new symbol as a shorthand and picking an arbitrary variable. 3. The first time you write ANY free variable in your proof, it MUST be in either a Let, Define, or #/#- declaration. No other variable can magically appear in your proof out of nowhere. If you are going to use x in the proof, then, by Jove, you better say what x is! So this should help to cure the rampant confusion about variables. All variables must be declared, there are only three ways to declare them (arbitrary, constant, and defined), and LET no longer can be used for anything OTHER than defining arbitrary variables (and making an assumption about the arbitrary variable). Here is an example using all three. Thm: a|b and b|c => a|c Pf. 1. Let a,b,c in Z. Given 2. Assume a|b and b|c - 3. ak=b and bj=c for some k,j in Z Def of |;2 4. akj=bj subst;3 5. =c subst;3 6. Define m=kj - 7. kj in Z closure *;3,6 8. m in Z subst;6,7 9. am=c subst;6,7 10. a|c def |;8,9 11. <- - 12. a|b and b|c => a|c =>+ QED In the above, we declared: * a,b,c to be arbitrary integers in line 1 (notice the "Let"). * k,j to be new constants obtained (implicitly) from a #- (notice the "for some"). * m to be a new defined symbol to make the proof more readable (notice the "Define"). So that proof uses all three types. Notice there are no other free variables in the proof (besides Z, which is a mathematical constant). Notice that if we want to use the formatting of part I.b.iii of the above rule we could format it this way: Thm: a|b and b|c => a|c Pf. 1. Let a,b,c in Z. Given 2. Assume a|b and b|c - 3. #k,j in Z, ak=b and bj=c Def of |;2 4. akj=bj subst;3 5. =c subst;3 6. Define m=kj - 7. kj in Z closure *;3,6 8. m in Z subst;6,7 9. am=c subst;6,7 10. a|c def |;8,9 11. <- - 12. a|b and b|c => a|c =>+ QED This is ok too, even though k,j are technically bound variables in line 3, because we agreed that one of the shorthands for #- was to assume we declared the new constants to be whatever the bound variables are. So the two proofs are identical, its just a matter of formatting style. I think that by following this new rule you will eliminate a LOT of the confusion and the resulting errors that I am seeing in your proofs. --declared ruler ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 11:15 AM Subject: [FAQ] RE: = recipe? > -----Original Message----- > Sent: Monday, September 25, 2000 10:15 AM > To: monks@UofS.edu > Subject: = recipe? > > > I am having trouble proving problems such as 18 and 22. I am not sure > what kind of recipe to follow. For example in #22 can you let gcd(a,b) > =d and then show that the gcd(a,b+at)=d, to show they are equal to each > other. If this is not correct, can you give me a hint on where to > start or what recipe to follow. The recipe's for equal are listed on the recipe sheet, namely the reflexive law and substitution. If you define (not let!) d=gcd(a,b) and then show that gcd(a,b+at)=d then is gcd(a,b)=gcd(a,b+at)? This is so easy I won't insult you by telling you! :) --knows you know this ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 9:26 PM Subject: [FAQ] ban on fractions I forget if I mentioned this or not.. but there is a BAN ON FRACTIONS in your proofs. The only time you can use the fraction symbol in your proofs is when the proof deals with a set which contains some subset of Q-Z or if the author of your textbook has placed a fraction symbol directly in the statement of the problem itself. Otherwise they are BANNED BANNED BANNED! In particular, if you are doing a proof that involves only integers (which is almost every proof in chapter one) you CANNOT use fractions at all! The educational and mathematical reasons for this are many, so I won't go into them here, but you can read all about why I ban fractions in the the FAQ's from previous years. One important reason related to your homework is that divisibility is not defined for rational numbers because every nonzero rational number "divides" every other one, i.e. if r,s in Q and r<>0 then r*(s/r)=s, so r "divides" s. This is true about the rationals even if r,s are both integers, since s/r is certainly rational. Thus they whole concept of divisibility, and consequently the whole idea of gcd, prime, and the division algorithm (i.e. all of chapter 1!) goes right out the window if you use fractions, and all your proofs will be wrong. --rescuing you from death by fraction ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 9:26 PM Subject: [FAQ] RE: prime help! > -----Original Message----- > Sent: Monday, September 25, 2000 11:25 AM > To: monks@epix.net > Subject: prime help! > > > dr. monks .. > > could you please, please do an example with primes? maybe something > along the lines of 12a in section 1.3 (without giving the homework > problem away, of course!)? i am having severe mental blocks! thanks. How about something simple... Thm: Let p in Z. p is prime => -p is prime Pf:
1. Let p in Z Given
2. Assume p is prime -
3. Let d in Z -
4. Assume d|-p -
5. dk=-p for some k in Z Def |;4
6. d(-k)=p arith;5
7. -k in Z arith (+ inverse in Z);5
8. d|p def |;6,7
9. d in {1,-1,p,-p} def prime;2,8
10. -(-p)=p arith
11. d in {1,-1,-p,-(-p)} subst;10,9
12. <-
13. -p is prime def prime;3,4,11 (see recipe)
14. <-
15. p is prime => -p is prime =>+2,13
QED
This used the definition of prime "both ways". In line 9 we are using the definition (prime- rule) to "break apart our legos" that are given on line 2, then we put back together the lego pieces in a different way in line 11 and use the definition the other way (prime+) to create what we are after. --plays with legos ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 9:26 PM Subject: [FAQ] RE: Assign 8 #14 > -----Original Message----- > Sent: Monday, September 25, 2000 6:13 PM > To: monks@epix.net > Subject: Assign 8 #14 > > Dr. Monks > > In #14, after i assume that n is a perfect square can i write it as this? > > n = k^2 for some k in integers > > That is what i am reading as the "definition" of a perfect square it > that sense. IF not could you give me a correct way to use 'Perfect > square'? That is the correct definition. --hopefully not a perfect "square" ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, September 25, 2000 9:32 PM Subject: [FAQ] RE: Least Common Multiples > -----Original Message----- > Sent: Monday, September 25, 2000 8:19 PM > To: Ken Monks > Subject: Least Common Multiples > > > Dr. Monks > I am working on # 31 from page 14 and realize that I have nothing on least > common multiples. How about an example? > Thanks The whole point of problem #31 is to see if you can grasp the concept of lcm after studying a related concept, the gcd without being taught it by example in either the chapter or by me first. I don't like their notation, however. So I encourage you to use the following notation: 1. Write gcd(a,b) instead of (a,b) like they do in the book. 2. Write lcm(a,b) instead of [a,b] as they do in the book. 3. In #31b, get rid of the DARN FRACTION!!! by rewriting it this way: (b) gcd(a,b)lcm(a,b)=ab if a>0 and b>0 --giving notation notes ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Tuesday, September 26, 2000 9:43 AM Subject: [FAQ] RE: Fraction question > -----Original Message----- > Sent: Monday, September 25, 2000 11:23 PM > To: monks@epix.net > Subject: Fraction question > > > Dr. Monks > I received your ban on fractions but had one quick question about it. > For #20 b in assign 8, i did it by contradiction as i have always done > the proof before. BUt when i assume that 2^0.5 is rational, can we > conclude that 2^0.5 can be represented by a/b by the definition of a > rational number? > If not, what can we conclude after we assume that it is rational? The ban on fractions does not apply to problem #20b because the problem DOES deal with actual fractions, i.e. with elements of the set Q-Z. That was one of the exceptions in the ban when I stated it. You CAN use fractions if the problem is ABOUT fractions. You can't use them if the problem is about integers (or some other number system which does not have fractions in it) and in those cases you NEVER need to use them. See the FAQ's for details. --allows fractions for fractions ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 27, 2000 10:07 AM Subject: [FAQ] RE: [FAQ] p531,#7,13 > -----Original Message----- > Sent: Tuesday, September 26, 2000 9:42 PM > To: monks@epix.net > Subject: [FAQ] p531,#7,13 > > > Hi Dr. Monks! > > I am thoroughly confused at this moment because I just looked at the > assignment for Thursday and I think that I can do ALL of the problems! > This can't be correct. So, I have a question... > > In numbers 7 and 13, both of the equivalence relations have equal signs in > them. (#7 says u~v iff f(u)=f(v) and #13 says f(x)~f(g) iff f'(x)=g'(x)) > I guess I am not understanding what the significance of the stuff around > the equal sign is, since I thought that = was a fairly simple equivalence > relation to prove. Am I misunderstanding? > > -hoping that you won't rain on my modern parade :) = is a simple equivalence relation to prove. But in these problems you aren't proving that = is an equivalence relation... you are proving that ~ is an equivalence relation. --knows ~ ~= = ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 27, 2000 10:11 AM Subject: [FAQ] RE: [FAQ] : arith Categories: Backed Up > -----Original Message----- > Sent: Tuesday, September 26, 2000 6:08 PM > To: Ken Monks > Subject: [FAQ] : arith > > > You said today in class that we can only use arithmetic as a reason for > statements that deal with integers...did you really mean that or can I > use arith as a reason for a statement about reals ie: > Let p,q,r in R > (p/r)-(q/r)=(p-q)/r arith > > -- "real"ly hopes so That was a slip of the tongue on my part... you can use "arithmetic" to justify facts (other than those topics being studied and proven like gcd, |, prime, etc) about any of the five number systems we take for granted in the course, N, Z, Q, R, and C. I was thinking of the ban on fractions, which applies only to Z and not to Q, R, or C. But a word of warning... if you are going to use "arithmetic" to justify "facts" about R, then the better be true facts! For example in your above example, what if r=0? Then your second statement is not correct because its not even defined! --doesn't like arithmetic ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 27, 2000 10:24 AM Subject: [FAQ] RE: ApndxD.p530.#4 Categories: Backed Up > -----Original Message----- > Sent: Tuesday, September 26, 2000 9:20 PM > To: Ken Monks > Subject: ApndxD.p530.#4 > > > Can we answer #4 simply with "yes" or "no" and give a brief verbal > explanation or do we need to prove it 'psuedo-formally' and if so can > we take as given the point slope eq for a line? ie should we say that > if two lines are parallel then the slope "m" must be equal in y=mx+b? > > -- wishing I were boarding down a snow covered slope Ahh, yes, the infamous #4. The problem with #4 is that they don't give a definition of parallel in the text. So I will give you a definition. Def: Let L1 and L2 be lines in the plane. L1 is parallel to L2 <=> L1 does not intersect L2. Notice that your suggestion of using slope and y=mx+b won't work because you can't write the equation of a vertical line in the form y=mx+b, so you would be missing all the vertical lines. To answer this problem, you should prove your answer. You may use facts from "geometry" if you like in a manner analogous to using facts from "arithmetic". Similarly, if you have a problem about continuous functions or derivatives and you need to use some fact about derivatives or continuity you can use "calculus" as a reason. Or if you have a problem that deals with matrices with real entries, you can use "linear algebra" as a reason. The rule is simple: If the question asks about a topic not covered in our textbook and the author assumes you know it from a previous course, then you can just use that fact from the previous course as long as there is really no way to prove it (because we don't have the definitions, etc from that course). But if it is a fact that you learned in a previous course, but that fact deals with topics that ARE covered either in my lectures or in the text, then those facts must be proven. For example, if you studied equivalence relations in a previous course, you can't use ANY facts about equivalence relations from the previous course... you have to prove all those facts because that is the topic we are studying. You dig? --making parallels with other subjects ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 27, 2000 10:55 AM Subject: [FAQ] RE: pg 530, #2 > -----Original Message----- > Sent: Wednesday, September 27, 2000 12:10 AM > To: monks@UofS.edu > Subject: pg 530, #2 > > First i have a general question. I am getting confused about when to > use Let, Define and Assume. I noticed on the FAQ's that most of the > problems in this section start out with assume, however #2 defines the > relation in the question, so do we use define or assume. In the other > problems, should we use assume since they are saying let or if and not > really defining them? You can't go by the examples in the FAQ's for this, because this is the first year I am implementing the distinction between Let and Define. In the past I used Let to mean both things, but now I realize that (as usual) using the same word or symbol for two different things is only a source of additional confusion for students. So I want to distinguish between the two by using different words, so you can see the difference for yourselves and get a clearer understanding of what is going on. In these problems, if they are defining a relation, then you should use define. However, it is also not wrong to use Assume, as long as you declare the variables to be arbitrary first. This is because there is more than one way to interpret a informally stated problem as an equivalent formal statement. Let me illustrate. Ex: Q1. Let a be a nonzero integer and s=a^2. Show a|s. Suppose we want to prove Q1. Well there are several "interpretations" of this we could take: Thm 1: Given a in Z-{0} and s=a^2. a|s
Thm 2: Given a in Z-{0}, define s=a^2. a|s
Thm 3: @a in Z-{0},@s in Z, s=a^2 => a|s
Now if we interpret Q1 as Thm 1, we would do the proof like this: Pf1:
1. Let a in Z-{0} and s=a^2 Given
2. a<>0 and a in Z Def set difference;1
3. a*a=a^2 def ^ (arith)
4. a|a^2 def |;3,2
5. a|s subst;1,4
QED
Pf2:
1. Let a in Z-{0} Given
2. Define s=a^2 -
3. a<>0 and a in Z Def set difference;1
4. a*a=a^2 def ^ (arith)
5. a|a^2 def |;4,3
6. a|s subst;2,5
QED
Pf3:
1. Let a in Z-{0} and s in Z Given
2. Assume s=a^2 -
3. a<>0 and a in Z Def set difference;1
4. a*a=a^2 def ^ (arith)
5. a|a^2 def |;3,2
6. a|s subst;1,4
7. <- -
8. s=a^2 => a|s =>+;2,6,7
9. @a in Z-{0},@s in Z, s=a^2 => a|s @+ (twice);1,8
QED
Any of these interpretations and proofs is fine. The distinction is subtle... in the first and last case we are picking arbitrary things a and s and assuming they have the given properties, whereas in the second case we are picking a arbitrarily and the defining s to be a^2. If I had to choose, I prefer the first proof over the last two. The real distinction between Let and Define doesn't appear when stating the Given's (premises) in a problem in your proofs, the distinct appears when you define your OWN NEW symbols in your proof. In that case the distinction becomes important because you don't want a defined variable to introduce another level of Assume which you can't escape from. Thus Define is a way to introduce new symbols in your proofs as axioms rather than as assumptions. --Defining Define ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, September 27, 2000 12:33 PM Subject: [FAQ] RE: Appendix D, #4 > -----Original Message----- > Sent: Wednesday, September 27, 2000 11:59 AM > To: monks@UofS.edu > Subject: Appendix D, #4 > > More questions about #4. What is the definition of intersects? Does it > mean (l intersects m) <=> (l and m have a point in common)? Yes. --making a common point ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, September 29, 2000 8:58 AM Subject: [FAQ] notation I forgot to mention one thing about the "very bad notation" which allows us to abbreviate [a] by the integer a in Zn. If you are using this abbreviation then you must distinguish when you are talking about an element of Zn and when you are talking about an integer Z. For example if you want to indicate two classes are equal in Zn there are three ways to indicate you are working in Zn: I. [a]=[b] (where n is assumed from context)
II. a =n b (where =n is my email notation for congruent mod n,
the triple equals sign with the n under it)
III. a=b in Zn
We discussed the first two notations in class, but we didn't mention the third explicitly. Thus a statement like: 3+4=1 in your proof would just be plain incorrect because it is about integers while the statements [3]+[4]=[1] 3+4 =6 1 3+4 = 1 mod 6 3+4 = 1 in Z6 are all acceptable ways to indicate that the given equalities are equalities of elements of Z6, not of the integers themselves. So you should take care to distinguish actual integers from integers you are using in Zn. Notation III is sometimes the "cleanest" looking, so I thought I would mention it to you. But you can use whatever notation you like. --monks in ZHazleton ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 02, 2000 9:56 PM Subject: [FAQ] RE: Page 29 # 5 > -----Original Message----- > Sent: Monday, October 02, 2000 11:20 AM > To: monks@epix.net > Subject: Page 29 # 5 > > > Dr. Monks > > I have already shown that (n^2)|(a-b)^2. Now, from this can i then > conclude that n|(a-b)? just by using the notation of | as shown > > thanks No way, dude. --Know Way Dude ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 02, 2000 10:04 PM Subject: [FAQ] RE: Page 36 #7 > -----Original Message----- > Sent: Monday, October 02, 2000 11:21 AM > To: monks@epix.net > Subject: Page 36 #7 > > > Dr. Monks > > For number 7, I have gotten down he the first line below but was unsure > if the next line was allowed by the same reasoning that we have always > had > > [xy] = [xz] > [y] = [z] > > I am unsure if we are allowed to use those same reasons that we have > been using when we had brackets when we have integers in the brackets. The same reasoning you have always had? You mean the same reasoning you used in the past the last time that you studied equivalence classes of integers with respect to the congruence relation? They aren't just "brackets"... [y] is the equivalence class of the integer y with the congruence relation, which makes it a set of integers. So ANYTHING that has to do with arithmetic is out of the question. There is NO "arithmetic" that we "have always had" about Zn, only about Z (and N,Q,R,C). So ANYTHING you want to do with equivalence classes you have to prove (or reference a previously proven theorem). > Also, for number 2 in the same assignment, part a can we take that as > the x has to come from Z8 and then use a multiplication table to find > when x^2 = 1 then give you a formula for each solution we find? Then > can we so the same reasoning process for parts b and c? You don't need to give a formula for the solutions in the solution set, just give the entire solution set (with proof that it IS the solution set). > Thanks again You're welcome! -- ~[monks] ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 04, 2000 9:28 AM Subject: [FAQ] RE: sec 2.3, pg. 39, #4 > -----Original Message----- > Sent: Tuesday, October 03, 2000 11:42 PM > To: monks@epix.net > Subject: sec 2.3, pg. 39, #4 > > > dr. monks .. > > i was wondering if you could help me reword number 4. i am finding it > difficult to set up the problem because i don't think i'm interpreting > it correctly. the best interpretation that i came up with is the > following: > > n composite => #a,b in Zn such that (ab=0 => a~=0 and b~=0) > > wrong??? any suggestions? > > thanks > > --trying to obtain a grade ~=0 No, the way you are stating it is not what it is asking. In fact your statement is trivially true, just take a=b=[1] and you will see that your statement above is true because ab=0 is false in that case and "false => anything" is true, so #a,b, such that ab=0=>a~=0 and b~=0 regardless if n is composite or not. What question #4 is asking you to prove is this: n is composite => #a,b in Zn, ab=[0] and a~=[0] and b~=0. So the word "but" in #4 means "and". --knows his "but" from a hole in the ground ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 04, 2000 10:04 PM Subject: [FAQ] composite There seems to be a lot of confusion about what composite means for integers. The definition was: Def: Let n in Z-{0,1,-1}. n is composite <=> n is not prime.
So to be able to use the definition of composite in your proofs, you should just negate the definition of prime. Let n in Z-{0,1,-1}
n is composite <=> ~(n is prime)
<=> ~@c in Z, c|n => c in {1,-1,n,-n}
Now if you just use DeMorgan's Law a couple of times, the tautology (P=>Q)<=>(~P or Q) a couple of times, and the definition of "@x in S" and "#x in S" and you can almost mindlessly simplify this last statement into a "useful" definition of "composite" that you can use in your proofs. Try it and see what you get! Logic is Way COOOOL! -- ~ in his prime ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 04, 2000 10:08 PM Subject: [FAQ] RE: Assign 12 page 40 #11 > -----Original Message----- > Sent: Wednesday, October 04, 2000 11:06 AM > To: monks@epix.net > Subject: Assign 12 page 40 #11 > > > Dr. Monks > > # 11 says to use exercise 9 to solve it. But, Theorem 11 on the > previous page is proved by exercises 8-10. So, do we have to use > exercise 9 explicitly or can we just use the statement of the theorem > 11 which you stated in class. That is, > if d = gcd (a,n) then [a]x=[b] has > a) d solutions if d|b > b) no solutions if d ~| b > > Trying to make my life just a little bit easier You can use the theorem if you like, but I don't see how it will help you. You are asked to solve the equations, which means you must FIND ALL the solutions. You can't do this with the Theorem because it only tells you how many solutions there are, not what the solutions actually are. Problem #9 tells you exactly what the solutions actually are. In addition, you can't solve this by trial and error or Maple because the instructions explicitly tell you to use exercise 9, so that is what you have to do. It is important that you see the result of exercise #9, which is why I assigned this problem in the first place. --revolution #9 ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 04, 2000 10:23 PM Subject: [FAQ] RE: Assign #12 page 39 #4 > -----Original Message----- > Sent: Wednesday, October 04, 2000 12:50 PM > To: monks@epix.net > Subject: Assign #12 page 39 #4 > > > Dr. Monks > > I have already defined x, y in Z (integers). Now, can i do this > > Let a = [x] in Zn, since x is integer > Let b = [y] in Zn, since y is integer > > I didnt see anything wrong with doing that but if this is wrong could > you tell me the correct way to "define" a and b in Zn this way by > example. This isn't correct. The correct way to do it is: Define a = [x] in Zn Define b = [y] in Zn Since, if I understand you correctly, you are interested in defining a and b to be the equivalence classes of the integers x and y in Zn. There is a difference between this and what you did above, namely that we agreed that the word "Let" can only be used to declare ARBITRARY variables which we can then use in a @+ rule later in the proof if we like. But if x and y are already defined, you don't want to declare a and b to be ARBITRARY equivalence classes in Zn, and then assume that they are equal to [x] and [y] because you will never be able to get anything useful out of that assumption. So you want to use Define and not Let. --Define and dandy ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 04, 2000 10:33 PM Subject: [FAQ] RE: Page 40, #12 > -----Original Message----- > Sent: Wednesday, October 04, 2000 5:34 PM > To: monks@epix.net > Subject: Page 40, #12 > > > Dr. Monks, > > I have two questions- > > First of all, we had talked about when x was a congruence class > and when x was an integer. In #12 it says "ax=b(mod n)", so in this case x > would be an integer, correct? Correct. > My other question is that I am unsure as to what the question is > asking for. > It does not require a proof, correct? It is just asking for a > description of x. I am thoroughly confused. If it is possible could you > explain it in a little more detail? It is asking for you to describe the solutions, i.e. the solution set. So all
you have to do is determine which integers are in the solution set and which
ones aren't and then describe the set in a way that clearly indicates which
numbers it contains in an "explicit" manner, i.e. you can't just say: The
solution set is {x : ax=b(mod n)} even though this is true, it isn't what they
mean by describe.
For example, if someone asks you to solve 3x^2=2 in R, you would say the
solution set is {sqrt(2/3),-sqrt(2/3)}. You wouldn't say the solution set is {x
in R : 3x^2=2} even though technically this is correct. So this is the sense
in which they mean "describe".
I don't expect a lengthy formal proof for this one, just "describe" the solution set and explain why your answer is correct informally. --description of monks ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 09, 2000 1:57 PM Subject: [FAQ] RE: pg 51 #8 > -----Original Message----- > Sent: Sunday, October 08, 2000 5:22 PM > To: monks@UofS.edu > Subject: pg 51 #8 > > > In #8 they are telling you what R bar equals. So when we are using it > in the proof should we use let..... ? It doesn't matter if you use Let or Define in the case where a symbol is defined in the question as it is in #8. It only alters the way the question is worded slightly (are you letting Rbar be arbitrary and then assuming it is equal to the given set to show that IF Rbar equals the given set THEN the rest is true, or are you defining Rbar to be the given set and then just proving the conclusions outright?) > If we have (b+c,0s) can we let m=b+c for some m in R and then say > (b+c,0s) = (m,0s)? You didn't say what you know about b anc c above. If you know that "b+c in R" then you can "Define m=b+c" and then use substitution to get (b+c,0s)=(m,0s). On the other hand, if you don't know that b+c in R but you know that "#m in R, m=b+c" then you can conclude that "m=b+c for some m in R" by #- rule. However under NO circumstance can you combine a "Let" and a "for some" in the same statement when referring to the same variable as in "Let m=b+c for some m in R". --knows no let with for some ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 09, 2000 1:57 PM Subject: [FAQ] RE: pg 51 #10 > -----Original Message----- > Sent: Sunday, October 08, 2000 5:29 PM > To: monks@UofS.edu > Subject: pg 51 #10 > > whne we get to #3 on the recipe sheet to show s is a subring of R, > #3 say let a,b in S > > In #10 should this be: let k+ji and s+ti in Z[i]? No. You should say: Let a,b in Z[i]. --follows his recipes ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 09, 2000 1:57 PM Subject: [FAQ] RE: Question #18, pg 52 > -----Original Message----- > Sent: Sunday, October 08, 2000 9:04 PM > To: monks@epix.net > Subject: Question #18, pg 52 > > Dr. Monks, > > I have a question about integral domain. Part of showing a ring is an > integral domain is: > > Let a,b in R > Assume ab=0 > Show a=0 or b=0 > > Does that mean "there exists" an a=0 or b=0 or it is "for every" a,b in > R, a=0 or b=0. Neither. It means "For every a,b in R, if ab=0 then either a=0 or b=0". --king of his integral domain ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 09, 2000 4:47 PM Subject: [FAQ] RE: Assign 13 p 52 #14 > -----Original Message----- > Sent: Monday, October 09, 2000 4:27 PM > To: monks@epix.net > Subject: Assign 13 p 52 #14 > > > Dr. Monks > > You had said in class that we aren't allowed to use arithmetic as a > reason anymore. But with number 14, the elements of the ring are > integers. So, i was wondering if we should use arithmetic or the > algebra theorem as a reason for some the the vital steps we make. I NEVER said that. I said you can't use arithmetic anymore for reasons in a proof that has to do with a ring OTHER than Z,Q,R, or C (or any subring of these). This includes problems about arbitrary rings, since there is no guarantee that an arbitrary ring is Z,Q,R or C or a subring of these. This has ALWAYS been the only thing you could use arithmetic for. So if R is just a ring (but you don't know which one) and you have elements a,b,c in R, and you know that a+b=a+c you can't conclude b=c by arithmetic... you have to refer to what I called the Algebra Theorem, because that is where we proved it is true for rings. If you say that -(-a)=a in the same situation then you can't say "arithmetic" for the reason... you have to refer to what I called the "Sign Theorem" (these are theorems in the book. Thm 3.4 and 3.5 resp, but it is easier to remember them if we give them a name. Also, you cannot use ANY fact that LOOKS like arithmetic when talking about arbitrary rings unless we have a PROOF of that fact in a theorem. For example, in the above situation we have that ab=ac we CAN'T say that b=c and give "arithmetic" as the reason, for the simple reason that it is not TRUE! (2*3=2*7 in the ring Z8 but 3~=7 in Z8). So go ahead and continue to use arithmetic for elementary facts about integers and rational numbers and real numbers and complex numbers... but be careful when doing proofs about arbitrary rings. The reason I warned you about this in class is because students in previous courses ALWAYS used arithmetic for things that it doesn't apply to and lost a lot of points that way... so I am trying to prevent that by warning you before you do it not to. --ends sentences on a split infinitive ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 09, 2000 4:58 PM Subject: [FAQ] RE: pp. 51-54: questions about reasons > -----Original Message----- > Sent: Monday, October 09, 2000 3:32 PM > To: monks@epix.net > Subject: pp. 51-54: questions about reasons > > > not a very understandable subject header, but here's what i mean .. > > let's say i have the situation described in exercise 7b. i have the > following: > > let a, b in R* > define a=(x,x) and b=(y,y) for some x, y in R > a+b=(x,x)+(y,y) > =(x+y,x+y) > > now, my question is in regards to the reason for my last line. since i > obviously can't say "arithmetic," Ha! But you are "tempted" to aren't you! :) Hence my warnings! :) > is the reason "addition in R*", "addition in RxR" or "addition in R". > if i say that RxR is a ring based on theorem 3.1, i would be tempted to > choose "addition in RxR". any advice? Yes, I have two bits of advice: First, you should not use "define" in the same line as "for some". I reiterate... there are three ways to declare a variable: (a) Let (b) Define (c) for some These are all different and CAN'T be combined with each other in the same sentence to declare the same variable. So you don't want to say: define a=(x,x) and b=(y,y) for some x, y in R but rather just: a=(x,x) and b=(y,y) for some x, y in R Second, regarding the reason for the last line, the definition of addition and multiplication in RxR is given in Theorem 3.1. So the right reason is "def + in RxR". But if someone wrote "arithmetic" for this line, I would DEFINITELY mark it wrong. I will also mark it wrong for people who don't put any reason because I would be checking for this sort of understanding in the reasons at this point in the proof as I know it is a point that students often miss. -reasonable ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 11, 2000 10:21 AM Subject: [FAQ] RE: Assign 13 question on subrings > Dr. Monks > > I had just sort of a general question on some questions dealing with > subrings. If we are asked to show that something is a subring of > another, in step two of your recipe you have show that 0 is in S where > 0 is the zero element of R (showing S is subset of R). Now, if we > already know the zero element of R can we just put that as a line in > the proof? What does "we already know the zero element of R" mean? That you are an acquaintance of the zero element of R? That you are good buddies from back in high school? How can you "know the zero element of R"? > For example, in #4, we are asked to show a subring of Z. How can you "show a subring"? You mean like "show and tell" where you bring your subring up in front of the class and show the subring to everyone? I am not saying these things to be facetious, but rather to point out that part of your confusion is due to the fact that you don't understand what the questions are asking. You can't "show a subring" and you can't "know a zero element". You CAN try to "show that a subset of a ring is a subring" and you CAN try to "show that the zero element of R is in a subset S" of R. > can we put that 0 is the zero element of Z since we "already know that?" Yes. But that is not what the recipe for showing S is a subring is asking you to do in step two. It is asking you to show that the zero element of R is in S, not asking you to show that the zero element of R is in R. OF COURSE it is in R! > Also, what would be a sufficient reason for this line? To say "0 is the zero element of Z" you can just say "arithmetic" for the reason because this is a fact about Z (that isn't a fact that we proved like facts about gcd, divisibility, or primality). A shorter way to say this would be: : n. 0z=0 arith : where 0z denotes zero with the subscript Z (in blackboard bold font) since I can't type the subscript here. -wizard of 0z ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Sunday, October 15, 2000 11:45 AM Subject: [FAQ] RE: Pg 62 #3,  > -----Original Message----- > Sent: Friday, October 13, 2000 4:13 PM > To: monks@UofS.edu > Subject: Pg 62 #3,  > > > Do we have to answer #3 and #5 with a proof, or can we just answer yes > or no and then explain why? You must prove everything. A counterexample is also a form of proof. I explained this before in a previous email message. -deja monks ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Sunday, October 15, 2000 8:55 PM Subject: [FAQ] RE: Pg 62 #5 > -----Original Message----- > Sent: Friday, October 13, 2000 4:16 PM > To: monks@UofS.edu > Subject: Pg 62 #5 > > > If we are proving something is a subring of R, can you give and example > of how to show that it is a nonempty subset of R? To show a set is nonempty you have to prove there is something in it. Ex 1: Define S={x : x = y^2+z^2 for some y,z in Z}. To see that S is nonempty
we could do this:
Define S={x in Z: x = y^2+z^2 for some y,z in Z}
1 in Z arith
2=1^2+1^2 arith
2 in S def of S (prev 2 lines)
S is nonempty def of empty set (prev line)
Ex 2: Define S={x : x in Z and x^2+1<0 }
In this case, since x^2+1>0 for all integers by arithmetic, we see that there is no integer, the set S IS the empty set, thus you can't possibly show it's nonempty. Moral: You need to check if a subset is nonempty or not! --empty headed ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Sunday, October 15, 2000 8:55 PM Subject: [FAQ] RE: pg 62 #8a > -----Original Message----- > Sent: Friday, October 13, 2000 5:49 PM > To: monks@UofS.edu > Subject: pg 62 #8a > > > I am confused witht the definition of C. Does r have to be the same > for each different value of a or can r be different also? What is r? What is a? They are not declared in the problem, nor are they declared in your question, so I can't know what they are. There are LOCAL BOUND variables in the question called a and r, but they aren't declared because they are just local "dummy" variables. So I can't possibly answer this question unless you tell me what they are. -can't talk about unknown quantities ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Sunday, October 15, 2000 8:55 PM Subject: [FAQ] RE: distributive laws > -----Original Message----- > Sent: Saturday, October 14, 2000 3:02 PM > To: monks@UofS.edu > Subject: distributive laws > > > Are the distributive laws only for + ? > Can they be used with - or do you have to change the - to a + ? Let R be a general ring, and a,b,c in R. The distributive laws tell us that: a(b+c)=ab+ac and (b+c)a=ba+ca There is also the Sign Thm about a generic ring R which you can read in your notes and in the book. It allows us to move signs around in some of the "usual" ways. For example: (-a)b=-(ab) etc. Finally, there is the definition of subtraction which is that a-b is defined to be a+(-b), i.e. any subtraction is just an addition in disguise. Combining all three of these you can prove that a(b-c)=ab-ac, but this is NOT a distributive law, it is a Theorem (or Lemma) that is proven from the other facts above. So if you just state a(b-c)=ab-ac in your proof and give "Distributive Law" for your reason you are incorrect. We must verify all these laws we usually take for granted because some of them will hold and others won't. --setting down the Distributive Law ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Sunday, October 15, 2000 8:55 PM Subject: [FAQ] RE: sect. 3.2 #5b > -----Original Message----- > Sent: Saturday, October 14, 2000 11:57 PM > To: monks@epix.net > Subject: sect. 3.2 #5b > > > Just a brief question on a late Saturday night (I am sure your get many) > If we were to think a yes or no question were wrong because we thought the > answer was only at under specific conditions..what is the format for > answering? Do we just use words, or does it have to be in proof format? > If I am way off base, just let me know...I am not asking how far off base > (i.e. I don't need names like Who, What, I Don't Know or Today :) ). > Thanks! > > -Listens to Abbott and Costello This is the second time this question is being asked, so even though I have answered this several times in the past, I will answer it again to refresh everyone's memory: You must PROVE ALL of your answers to the homework questions. HOWEVER, sometimes giving a counterexample can be a proof and sometimes a calculation can be a proof. The bottom line is you must give reasons and indicate WHY your answer is what it is. You can't just say "YES" or "NO" even if the question is worded as a Yes/No question. Example: Prove or disprove that every integer is a product of two distinct primes. Proof by Counterexample:
Assume @n in Z, n is a product of two distinct primes.
2 is a product of two distinct primes @-
2=pq where p,q are prime integers and p<>q def of product and distinct
p|2 and q|2 def |
2 is prime arith
p in {-2,2} and q in {-2,2} def prime
pq in {-4,4} arith
2 in {-4,4} subst
~2 in {-4,4} arith
-><-
not all integers are a product of two distinct primes.
or more succinctly: Counterexample: 2 in Z arith the prime factorization of 2 is 2 arith 2 is not the product of two distinct prime by uniqueness of prime factorization thm In the second case I am writing the Counterexample more informally like a traditional counterexample found in textbooks and in the first case I am writing it more like a proof, but the idea is the same in both cases, we are showing that the statement is not true for all integers by showing that it isn't true for 2. For counterexamples you can be informal when producing as in the second example above, but you still must give reasons so that the counterexample is a proof of what you are claiming. But a simple "Yes" or "No" answer will never suffice. For situations where the statement they are asking about it true, your must prove it with a complete proof. --I Don't Know Who's distant cousin ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 16, 2000 9:08 AM Subject: [FAQ] RE: [FAQ] RE: pg 62 #8a > -----Original Message-----
> Sent: Monday, October 16, 2000 12:22 AM
> To: Ken Monks
> Subject: Re: [FAQ] RE: pg 62 #8a
>
>
> In 8a it says let C={a in R : ra=ar @r in R}
>
> If a is 3 1 then a is in R and if r is 1 0 then ar=ra and a is in C
> 2 4 0 1
>
> am i understanding this correctly so far?
No, by the definition of set builder notation, a is in C iff ar=ra for ALL r in R. You only showed that ar=ra for a one particular r in R. --knows one isn't all unless all is one ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 18, 2000 10:59 AM Subject: [FAQ] RE: p.525: 11 > -----Original Message----- > Sent: Wednesday, October 18, 2000 9:06 AM > To: monks@epix.net > Subject: p.525: 11 > > dr. monks .. > > just checking to see if we are supposed to start at 0 or 1 for exercise > 11. if we start at 0 then the set B would be empty. since 0!=1, then > we would have 1 possible injective function from B to B. is that > possible? maybe it is, but it does not make sense to me if the set has > nothing in it. thanks for your help! You should start at zero. See the ORIGINAL official definition of function on the set theory definitions sheet to see why you can start at zero. --the official starter ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 18, 2000 1:15 PM Subject: [FAQ] RE: p525 #6 > -----Original Message----- > Sent: Wednesday, October 18, 2000 12:48 PM > To: monks@UofS.edu > Subject: p525 #6 > > > I am getting confused with either showing P(0) or P(1). > For #6 do we show P(1) b/c when n=0 4^0-1 =0 and 0 is not a positive > integer? Yes. -has a positive attitude ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, October 20, 2000 8:16 AM Subject: [FAQ] RE: [FAQ] RE: p.525: 11 > -----Original Message----- > Sent: Wednesday, October 18, 2000 7:54 PM > To: Ken Monks > Subject: Re: [FAQ] RE: p.525: 11 > > > Dr. Monks > > ques. 1 3! =6 so does this mean we will have six possible > injective functions from B to B? Only if B has 3 elements. > ques. 2. Do we have to apply the definition the def of Inj. to this > prove? I'm not sure what exactly they are asking us to do in this > proof. Can you tell me? Yes, in fact we had a theorem in the beginning of the course that said that a function from an n element set to itself is injective iff it is bijective. You can use this result if you like. So counting the number if injections is the same as counting the number of bijections or the number of surjections for finite sets. But whichever you count, the problem is asking you to prove that if your set B has n elements then there are exactly n! injections/bijections/surjections from B to B. --busy B ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, October 20, 2000 8:20 AM Subject: [FAQ] RE: p88 #6 > -----Original Message----- > Sent: Thursday, October 19, 2000 1:12 PM > To: monks@UofS.edu > Subject: p88 #6 > > > It says all polynomials with constant term OR. Would one example be > x+x^2+OR, or ORx+ORx^2 ? Yes, and as usual we don't need to write terms in a polynomial that have zero coefficients, so we could abbreviate these as: x+x^2 or OR respectively. -- 0R + monks ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, October 20, 2000 8:29 AM Subject: [FAQ] RE: p88 #7 > -----Original Message----- > Sent: Thursday, October 19, 2000 1:18 PM > To: monks@UofS.edu > Subject: p88 #7 > > > can you tell me if I am starting out okay? > > 1. Assume R is commutative > 2. ab=ba @a,b in R def of comm ring I would write this: 2. @a,b, in R, ab=ba def of comm ring it sounds better in English to put the forall at the end, but mathematically its better to have the quantifier at the beginning so you can see it's scope. If you want to write it on the right, then it would be better to write: 2. ab=ba for all a,b in R def of comm ring This is just a tip about good mathematical writing style, not an error in the mathematics of course. Its like a math grammar lesson. So the general rule is, @ and # always go on the left, but if you want to quantify on the right to sound more Englishy then use the words "for all" or "for some". > 3. Let a,b in R[x] This is fine. If you want to use the books notation you can also say: 3. Let a(x), b(x) in R[x] I don't care which notation you use, just so you use it correctly. > 4. a=cx+cx^2, b=m1+mx^2 for some c,m in R def of R[x] No way, Jose! You can't say that a and b are quadratic polynomials! They are ARBITRARY polynomials so you don't know what degree they are. The definition of R[x] tells you that a=a0+a1*x+a2*x^2+...+ak*x^k for some k in N and some a0,a1,...,ak in R and similarly for b. --thinks modern should be writing intensive ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, October 20, 2000 9:11 PM Subject: [FAQ] RE: pg 94 #5 > -----Original Message----- > Sent: Friday, October 20, 2000 11:44 AM > To: monks@UofS.edu > Subject: pg 94 #5 > > > Is It possible to get a remainder or gcd that equals a constant? Is it > okay to have a polynomial of degree 0 as the answer? Sure, as long as it's monic. -monkic ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Friday, October 20, 2000 9:31 PM Subject: [FAQ] RE: pg88 #6d > -----Original Message----- > Sent: Friday, October 20, 2000 12:10 PM > To: monks@UofS.edu > Subject: pg88 #6d > > > a and b are in R[x] in which the odd poweres of x have zero > coefficients. I am having a problem defining a and b. > Is it correct to say > a=a0+aox+a2x^2+a0x^3+...+akx^k? > my problem is, how do we know if k is odd or even? Well, there are many different ways to attack this, but I would suggest the following as being the simplest for doing proofs: a=a0+a1*x+a2*x^2+...+ak*x^k for some a0,...,ak in R and some k in N and @i, i odd => ai = 0R I think that will make your proofs the simplest rather than trying to write a=a0+a2*x^2+...+ak*x^k for some a0,a2,...,ak in R and some even k. The reason is that it is not easy to "argue" clearly with the ... in the middle of your polynomial in this situation unless you state and arbitrary term of the polynomial. So I think its easier and more accurate to do it the first way. The second method isn't really wrong, but I think if you try the proof both ways you will find it easier to give reasons and hence more rigorous the former way that the latter. --Friday night hint machine ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 23, 2000 8:00 PM Subject: [FAQ] RE: P 88 # 6 > -----Original Message----- > Sent: Monday, October 23, 2000 3:25 PM > To: Ken Monks > Subject: P 88 # 6 > > > Dr. Monks, > For this question, it says to justify your answer whether or not is > a subring of R[x]. Now does this mean we can give an example which > would be a subset with the given properties and explain why it is a > subring or do we have to prove it full out like we have been doing > previously. Justify means prove it (or give a counterexample if it's not, but as I said a zillion times before, a counterexample is just a proof in disguise). > If we do have to fully prove it when we say a(x), b(x) in S > can we say a(x)= a(0) + a(1)x + a(2)x^2+.........+a(k)x^k > and b(x) = b(0) + b(1)x +.......................+b(k)x^k > > or do we have to use b(0) + b(1)x + .................b(m)x^m > and assume that m is greater than or equal to k? Well, you either have to do the latter (which is what I did in class) or else you can do the former as long as you allow the possibility that one of the degrees of the polynomials aren't necessarily k or m, i.e. you must allow for the possibility that a(k)=0R or b(k)=0R etc in either case. Then you could say the former case by qualifying it by "for some k" since that is certainly true for some k. For example, the polynomials 1+x and 1+2*x^3 could be written in the former format as: 1+0x+0x^2+2x^3 and 1+x+0x^2+0x^3. --could also choose k=14 for this example ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 23, 2000 8:08 PM Subject: [FAQ] RE: p 89 #16 > -----Original Message----- > Sent: Monday, October 23, 2000 5:15 PM > To: Ken Monks > Subject: p 89 #16 > > > Dr. Monks, > #18: Let @: R[x] implies R be the function that maps each polynomial > in R[x] onto its constant term. Show that @ is a surjective > homomorphism. > > Does this mean that if I have the polynomial, a(0) + a(1)x + a(2)x^n > +.......a(n)x^n, it gets mapped to a(0) + a(1) + a(2) +.....+a(n). > If not, could you tell me what it becomes. Thanks No its gets mapped onto its constant term, i.e. it gets mapped onto a(0). --onto something ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 25, 2000 1:22 PM Subject: [FAQ] RE: pg 98 #5 > -----Original Message----- > Sent: Wednesday, October 25, 2000 12:05 PM > To: monks@UofS.edu > Subject: pg 98 #5 > > > At one point in the proof I have f(x)h(x)=g(x) for some h(x) in F[x]. > If I show that h(x) is nonzero, can I say since h(x) is nonzero and F[x] > is a field, h(x) is a unit? F[x] isn't a field. See problem #11 page 89 which you were assigned in yesterday's homework. --fielding questions ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 25, 2000 1:30 PM Subject: [FAQ] RE: pg 98#6 > -----Original Message----- > Sent: Wednesday, October 25, 2000 12:11 PM > To: monks@UofS.edu > Subject: pg 98#6 > > > If I want to show that Q[x] is a field do i have to prove it or can i > just state it b/c i know for all a in R ax=1R? Q[x] isn't a field. See problem #11 page 89 which you were assigned in yesterday's homework. > Also, If I show that x^2+1 is a nonconstant, but i also show that > x^2+1=0, can I then say that x^2+1 is a constant which gives me a > contradiction? Yes, if you show that x^2+1 is nonconstant and also *IF* you show that x^2+1=0 then you certainly can say that x^2+1 is a constant and therefore conclude you have a contradiction. But that is A MIGHTY BIG "IF" because you can't possibly show it! --answering your question literally ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, October 25, 2000 9:09 PM Subject: [FAQ] RE: Question about showing uniqueness > -----Original Message----- > Sent: Wednesday, October 25, 2000 1:28 PM > To: monks@epix.net > Subject: Question about showing uniqueness > > > Dr. M > > I am trying to show that a unit, which i have already found, is unique > in a field F. Huh? Are you saying you are trying to show that a certain field F has only one unit, namely 1F? In that case the field must have no other nonzero elements, since by definition of field, they would also be units. But the only field with just one nonzero element is Z2.. my favorite field. > Now, in trying to use theorem 3.8 on page 60, > Given that F is a field, it has identity by definition of a field. True. > Also, i have an, 1 in F (where an is a coefficient and 1 the identity) > Since F a field, #u in F, (an)u = 1 = u(an). Not if an=0F. > This means that an is a unit in F by the definition of a unit Every nonzero element of a field is a unit by definition of field... a field is a commutative ring with identity in which every nonzero element is a unit. > and now i can apply the Theorem 3.8 since F has identity, an and 1 are in F, and > an is a unit. Thm 3.8 tells you that every unit has a unique inverse, it doesn't say anything about the "uniqueness of units". > Am i correct int his argument? I think the argument is ok, but I am not sure at all what you are trying to conclude. I think you are confusing "unit" and "inverse". > I don't see any corners that i might have missed but maybe you can see > one if i have missed any. > > Thank you almighty one No problem... I think. :) --more confused now than ever ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Thursday, October 26, 2000 8:55 AM Subject: [FAQ] RE: p. 98 # 5 > -----Original Message----- > Sent: Wednesday, October 25, 2000 11:01 PM > To: monks@epix.net > Subject: p. 98 # 5 > > > Dr. Monks > > For the right to left direction of #5, do we have to show that > f(x) = d(x)g(x), for some unit d(x) in F[x] and > g(x) = c(x)f(x), for some unit c(x) in F[x] That's one way to do it. > or does is it sufficient just to show one of them in order to show that > they are associates. The book used "prove that f(x) and g(x) are > ASSOCIATES..." and the plural use was throwing me off. > > Thanks That's because <> (my associate symbol) is an equivalence relation. If you understand what that means you can answer your own question. --associates with modern students ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, October 30, 2000 4:42 PM Subject: [FAQ] RE: Assign 20 #24 page 106 > -----Original Message----- > Sent: Monday, October 30, 2000 12:56 PM > To: monks@epix.net > Subject: Assign 20 #24 page 106 > > > Dr. Monks > > I am trying to use the fact from calculus that every polynomial is > defined everywhere. Now, can I use that fact here, or is that fact only > pertaining to the real numbers which is just one example of a field? > > Thanks I choose option (b), Monty. The reals are only one field, so you can't use any facts from calculus to prove something about and arbitrary field F. F might be Z7 for example. I don't think you studied Z7 in calculus. You should look at the definition of polynomial function for an arbitrary F to see if you can get what you need. --doesn't want anyone to get an arbitrary F ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, November 08, 2000 12:42 PM Subject: [FAQ] RE: p151 #6b > I am getting confused on what the set Zn/I would be. Can you give me an > example for Z5/I? In Z5 there are only two ideals, (0)={0} and Z5 itself, because Z5 is a field.
Z5/{0} is just isomorphic to Z5 because the only time that a-b in (0) is if a-
b=0 , so that a=b. Hence
Z5/(0)={0+(0),1+(0),2+(0),3+(0),4+(0)} and these equivalence classes are
distinct. If you make the + and * tables for this you will see it is isomorphic
to Z5.
On the other hand, if you consider Z5/Z5 then for any a,b in Z5, a-b in Z5, so
that every element is equivalent to zero. Thus in this case, Z5/Z5={0+Z5} and
the + and * tables are, well, pretty boring. :)
> If they want you to write table for each ideal, do > you find sets for Z12/1, Z12/2,......,Z12/11? or does the I stay I. I > am very confused. They want the tables for Z12/(0),Z12/(1),...,Z12/(11), i.e. Z12/I where I ranges over all of the set of all principal ideals. However, many of these ideals are equal, so the corresponding quotient rings are the same. Thus you will have a lot less than twelve different pairs or +,* tables. --likes to play in fields ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, November 08, 2000 12:43 PM Subject: [FAQ] RE: p151 #6c > -----Original Message----- > Sent: Wednesday, November 08, 2000 10:59 AM > To: monks@UofS.edu > Subject: p151 #6c > > > Give you give me a hint on how to show every homorphic image of Z12 is > isomorphic to one of the rings? i don't even know where to start. Yes, the FIRST ISOMORPHISM THEOREM! --told you it was important ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Saturday, November 11, 2000 4:53 PM Subject: [FAQ] RE: p 172 #13b > is it possible to only be able to put the shape back into the hole one > way? That is for you to determine. Why not photocopy or trace it twice, cut out the shapes and see how many different ways you can map one on top of the other? Good old fashioned physics! --thinks the physical world is just a tool for studying math ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, November 13, 2000 10:43 AM Subject: [FAQ] RE: Assign 26 #28 p 173 > -----Original Message----- > Sent: Sunday, November 12, 2000 7:39 PM > To: monks@epix.net > Subject: Assign 26 #28 p 173 > > > Dr. Monks > For number 28, I have completed the table so that G is a field but have You mean: "so that G is a group". > a quick question. Is there only one way in which we can complete this > table or are there multiple solutions? The way that I have it right now > it satisfies all the requirements for a field but I'm not sure if there > is a way to check for another solution. There is only one solution to this problem, and again, you mean "group"... not "field". --fielding questions about groups ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Monday, November 13, 2000 9:30 PM Subject: [FAQ] RE: Assign 27 # 34 p 180 > Dr. Monks > > I am trying to use that for a in G, |a| = |a^-1|, as it is in problem > 26 (on page 180). NOw my question is, if i want to use that, since we > are not assigned number 26 for homework, do I have to prove it before i > use it? Something tells me that i would have to prove it to use it and > i dont want to use something it without proving it if i have to prove > it. > > Thanks > (doesnt want to lose that double jeopardy 0.2 on something stupid) Hmm, I thought I answered this in the FAQ's but I can't find it anywhere... does anyone know where it is? Anyway, the rule is this: you can used any previously assigned homework problem in your proofs, whether or not you got it correct when you did it. We will just assume you got it right (since I can't go back and check anyway). However, homework problems that you were not assigned cannot be used without proving them first. I am SURE I typed this somewhere before, but perhaps it didn't make it to the FAQ's. --can't get his FAQ's straight ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Wednesday, November 15, 2000 12:34 PM Subject: [FAQ] RE: Assign 28 #46 p190 > Dr. Monks > > I had a few questions for #46. What does the book mean by GL(2,R)? is > that the set of all 2x2 matrices with real entries? No. PG 170. > What is the operation we are supposed to use to show it is a subgroup? PG 170. > I have tried it with matrix multiplication but i would essentially get > the same thing if i did matrix addition. Really? > Finally, if i call the subgroup S, to show that it is cyclic subgroup i > have to show that #a in S, <a> = S right? Yep. Also see the recipes. Note: there was a typo on the recipe sheet for showing a group is cyclic. I fixed it now. Please use the revised version. --group leader ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Saturday, November 18, 2000 10:57 AM Subject: [FAQ] RE: isomorphism > -----Original Message----- > Sent: Saturday, November 18, 2000 9:24 AM > To: monks@UofS.edu > Subject: isomorphism > > > I have a question about something we did in class. When we did the > example to show tha f:U(Z5)->(Z4,+) is an isomorphism we made tables. > Why did you change the table for U(Z5) from 1 2 3 4 to 1 2 4 3? To show that (U(Z5),*) is isomorphic to (Z4,+) we need to show there is an isomorphism f:U(Z5)->Z4 (or vice versa). So I defined f:U(Z5)->Z4 by f(1)=0, f(2)=1, f(4)=2, and f(3)=3, i.e. x f(x) ------- 1 0 2 1 3 3 4 2 Now it is clear from the table that f is onto, because each element of
Z4={0,1,2,3} is f(something) and it is injective because no two distinct elements
in U(Z5)={1,2,3,4) map to the same element of Z4. Since there are only four
elements this can be seen directly by looking at the table and we said we would
allow such a "proof" in finite cases like this. However, if someone put a gun
to our heads we could write a formal proof that f is onto and injective by doing
a proof by cases (e.g. Let y in Z4, then y=0 or y=1 or y=2 or y=3, Case 1:
Assume y=0, etc). Thus f is bijective.
Now, how are we going to show that f is a homomorphism? Well, we need to show that for all a,b in U(Z5), f(a*b)=f(a)+f(b). Since there are four elements of U(Z5), that means that we need to check 4*4=16 pairs of elements a,b for this property. Wel to write out 16 cases would be a horrendous messy task, so we consolidate those cases by checking all cases at once in nice table notation. So we write the multiplication table for U(Z5) and the addition table for Z4: * 1 2 4 3 + 0 1 2 3 1 1 2 4 3 0 0 1 2 3 2 2 4 3 1 1 1 2 3 0 4 4 3 1 2 2 2 3 0 1 3 3 1 2 4 3 3 0 1 2 Since for every a,b in U(Z5), a*b appears in the left table, we can now check all sixteen cases to see if f(a*b)=f(a)+f(b), i.e we want to see if EVERY ENTRY in the right table is f(the corresponding entry in the left table). If you compare the two tables you will see that that is true... each entry on the right is f of the corresponding entry on the left. Thus we can easily check all 16 cases rather than writing out a huge messy proof by cases. So why did I switch the columns in the left table? Because if I didn't then the entries in the two tables wouldn't match up, i.e. we would not easily be able to check the property f(a*b)=f(a)+f(b) because the entries in one of the tables would no longer correspond to the entries in the same location in the other table. This would make it very difficult to check if f was an isomorphism (while you could still do it in theory, it would require so much effort on the part of the reader that it wouldn't really be a proof... it would almost be tantamount to saying to the reader "just check it yourself". So I wouldn't give credit for such a "proof" unless you showed clearly that the property f(a*b)=f(a)+f(b) holds for all a,b by making the tables match up with each other via f.) Note that there are other ways to reorganize the tables so the entries match up, the way I chose isn't the only way. There are also other choices for the isomorphism f. So this isn't the only way to do this. But the other ways are all similar. In any event, once we show that f(a*b)=f(a)+f(b) for all a,b, in U(Z5) (through proof by "cases" using the tables), we can conclude that f is a homomorphism. Hence it is an isomorphism, and thus the groups are isomorphic. QED. -Dr.QED ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Saturday, November 18, 2000 11:01 AM Subject: [FAQ] RE: p 198 #28 > -----Original Message----- > Sent: Saturday, November 18, 2000 9:26 AM > To: monks@UofS.edu > Subject: p 198 #28 > > > How do we show that something is not isomorphic? Can we use tables to > show this? If we used tables, what operation do we use? You can't do it with tables! If you make mult tables and say "see, they don't match up" then you haven't shown anything because maybe you just wrote the tables in the wrong order... maybe they do match up for some other reason. How can you show groups are not isomorphic? Well there are lots and lots of way... proof by contradiction, for example. Or find a property that isomorphic groups must have in common and then show that your two groups differ on that property (for example do the sets have the same number of elements). But you rarely do it by showing that all bijections between the sets are not isomorphisms on a case by case basis because there are usually far too many bijections to consider. So tables are out. --eats on a multiplication table ----------------------------------------------------------- From: Ken Monks [monks@epix.net] Sent: Tuesday, November 21, 2000 9:26 AM Subject: [FAQ] RE: p. 208 #24 and #25 (Section 7.5) > -----Original Message----- > Sent: Monday, November 20, 2000 10:04 PM > To: monks@epix.net > Subject: p. 208 #24 and #25 (Section 7.5) > > > Hello Dr. Monks, > > I can't seem to make any progress on problems #24 and #25 in > section 7.5, p. > 208. Any advice? I tried using techniques like those in the proof of > Theorem 7.30, but didn't get anywhere... Or, if you're not in the mood to > give out hints, could you maybe show how to do #30 on p.180, which was not > assigned, but might give some insight (I hope?) > > --Hates Lagrange Well, I'll let you decide if it helps or not, but here is a proof for #30 on pg 180 since it wasn't assigned. Thm: If |G| is even then G has an element of order two. Sketch of Pf:
Let G be a finite group and |G| even.
G={a1,...,an} for some a1,...,an and some even integer n.
Assume @a in G-{e}, a~=a^(-1)
Define a relation ~~ on G by @a,b in G, a~~b iff a=b or a=b^(-1)
~~ is an equivalence relation (exercise: prove it as an easy Lemma)
Let c in G.
[c]={c,c^(-1)} by def of ~~
|[c]|=2 if c<>e by our assumption
e=e^(-1)
|[e]|=1
G is a disjoint union of its equivalence classes
|G| = the sum of the number of elements in its equivalence classes
= |[b1]|+|[b2]|+...+|[bk]|+|[e]| where [b1],...,[bk] are the
distinct equivalence classes
other than [e]
= 2 + 2 + 2 + ... + 2 + 2 + 1
= an odd number.
|G| is even.
-><-
~@a in G-{e}, a~=a^(-1)
#a in G-{e}, a=a^(-1) by DeMorgan
a^2=a*a
=a*a^(-1) subst
=e
Let 1<=j<2.
j=1 arith
a^1 = a
~= e def of G-{e}
|a|=2
G has an element of order 2
QED
So the rough idea is that if all the non-e elements are not equal to their inverses then we can pair up every element with its inverse, but e is its own inverse so it pairs up with itself. Thus we have collected the elements of G into disjoint pairs except for e so the total number of elements of G is odd, but that is a contradiction to the assumption that |G| is even. --maintains group order |
|
Many mathematics files on this site are in pdf format.
If your browser does not display pdf files, click here for
assistance. |