Math, M-242, Methods of Proof

Math, M-242, Methods of Proof, Fall 2013
This site updated Nov. 25, 2013.
[Originally the most recent update was at the top, above the first horizontal line, so students would see the current HW and advice first. This has been reversed so you can see the natural order and frequency of updates.] (Somelinks are broken because the pages have been moved. Maybe someday I will fix the links.)
Contact information and course policies are here.

Read the course policies.

First day of class: Monday, August 26, 2013. We will discuss the course and cover Section 1.1.

For Wedneday, August 28: Read all of Section 1.1. Mathematics is a written language (much more than it is a spoken language). Therefore, this is a reading and writing course. You learn to read and write by reading and writing. Read the text thoroughly. Every section, learn the meaning of the terms listed at the end of the section's conclusion (just above the "Exercises." If you don't recall where a term was introduced in the text, use the index at the back to look it up). For this section, hand in written homework at the beginning of class Friday:
    Bring your text to class every day. We will use it in class every day.
HW Due Wednesday, August 28: (1.1) A2, 3, 4, 7, 9, 11, B1, 2, 5, 7, 8, 12, 14, 23, 26, 29.
    Label your homework with your name at the very top right of the page and the section number (e.g. "1.1") of the homework just below it.
Also for Wednesday, read: "Is the internet making us stupid?"
  http://www.npr.org/templates/story/story.php?storyId=91543814  [Broken link]
    (Really, it is short, so read it!)
The original article, "Is Google making us stupid?", in The Atlantic magazine is not short (I don't expect you to read it, but I did):
  http://www.theatlantic.com/doc/200807/google [link still works!]
It provoked quite a buzz, so search on the title will get many hits.

Additional comments: Do you multitask well? Here is a summary of some surprising research on multitasking. [Link works!]

    Some special emphases of this course are listed here is a pdf copy.

This web site will be updated frequently. Upcoming HW will be listed, quiz and exam dates will be posted, mathematical advice will be posted, and homework listed as due in the future might be modified or postponed if it will improve the class.

Due Friday, August 30: Section 1.2: A1, 6 (both parts!), 11, 25, 29, B1, 5.

In this course you will learn how to learn math by reading it. One way we teach you to read is to require you to do it. You learn to read by reading. Therefore, many days there will be homework due on material we have not yet covered in class. You will read the section and learn how to answer the questions. Then the following lecture will clarify any remaining issues.

If you have tried, but are still uncertain about a problem, on your HW put a big question mark, ?, in the margin. Also, put the problem number on the side chalk board before class and I will try to make sure it is covered in class. If it is not covered in class, when I mark papers I will note those problems and possibly devote time during the next class to them.

Aug 28
HW due Wednesday, Sept. 4: (1.2, part 2): B3, 4, 18, 21, 22, 26, 42, (1.3) A1, 6, 9, 14, 18. Be sure you can pronounce all the mathematical expressions and grasp all the "grammar" exercises. Little typographical differences can make a big difference in the referent (the thing being named or referred to). For example, there is a major difference between a and A and a major difference between (, [, and {.

Mathematics is a written language. To get good at math, you must read it. Read!
If you are coming to class and feel yourself slipping even the slightest bit behind, please come see me in the office. I want to help!
Fortunately, we will use the language of mathematics every day and we never drop any topic, so you will see every usage and hear every pronunciation again and again. Pay attention and notice what is giving you trouble. Let me know and I will help.

HW due Friday, Sept. 6: (1.3, part 2) B1 [one wide table] (1.4) A1-4, 6, B15.
Quiz Friday Sept. 6 on 1.1-1.3. Know the terms.
Here is a similar quiz for study purposes.

Sept. 4
HW due Monday, Sept. 9: (1.3, part 3) B2 (1.4, part 2) B1 (do a good job), 2, 6, 10, 11 (1.5) A3, A22
One more problem: (1.4) C9

HW due Wednesday, Sept. 11: (1.5) A7, 9, 16, 19, 26, 30, B1 [be convincing], 2, 3, 8, 17

Sept. 9
HW due Friday, Sept. 13: (1.5) B4 (1.6) A1-7, B1, 10, 15, 27, 29, 51 (2.1) A1, 2, 6, 8
Learn the results from logic and their names (pages 88-90).

HW due Monday, Sept. 16: Read the section (of course, every time!) (2.1) A10-11, 17, B1, 2, 3, 5, 6, 7, 18, C2

Here is a link to an Exam 1

Wednesday, Sept. 18: (2.2, part 1) (2.2) A1, 2, 3, 8, 18, 31, 37

Friday, Sept. 20: No HW due. Exam in class on Chapter 1 (only Chapter 1).

HW due Monday, Sept. 23: (2.2, part 2) B1, 2, 10, 15 19, 21, 30,

If you mean "there exists" do not omit saying it. For example, the negation of "If |x| > 5, then x > 5" is not "|x| > 5 and x ≤ 5." It is "There exists x such that "|x| > 5 and x ≤ 5." It is common to suppress "for all" when it is intended, but it is not okay to omit "there exists" when it is intended.

Suppose you are to give the negation of "If ab = ac, then b = c." It is not "ab = ac and b ≠ c." The negation is "There exists a, b, and c such that ab = ac and b ≠ c." Never omit "there exists" if you mean it!

HW due Wednesday, Sept. 25: (2.3) A1, 2, 3, 8, 12, 15, 64, B1, 7, 10, 14, 27, 40

HW due Friday, Sept. 27: (2.4) A2, 10, 12, 16, 18, 19, B1, 2, 12, 14, 15

Sept. 26
HW due Monday, Sept. 30: (2.5) A1, 3, B1, 2, 14, 17, 18

HW due Wednesday, Oct. 2: (2.2 [sic]) B59-62, B73, 78, 83, 84 (2.5) B20

HW due Friday, Oct. 4: Review for the exam by doing and handing in a previous version of Exam 2 (here) and coming to class with questions.

Exam 2, Monday, Oct. 7, on Chapters 1 and 2. Memorize the Quadratic Theorem and the definitions related to bounded, increasing, even, and rational. Be sure you know the logic of quantifiers and negations, and the technical terms we have discussed (e.g. placeholder).

HW due Wednesday, Oct. 9: Read some of 3.1 and do (3.1) A3, 5, B1, B3

Oct. 11
HW due Monday, Oct. 14: (3.1) B42, 47 (3.2) A2, 5, 8, 10, 14, 19, 25, B 6, 7
Begin to read 3.2. In Section 3.2, pay attention to the order in which the results are listed. Each one joins the list of prior results for purposes of proving the next. The inequality facts from Section 3.1 are also prior.

On prior results and citations. In this course, you are expected to cite prior results from the current and immediately previous sections, but not from sections on lower-level material studied long ago. At some point you get to stop citing old and well-known results. For example, when doing a calculus proof you do not need to cite results on inequalities from 3.1. By then, you are supposed to know what is true and what is not, and inequalities are supposed to be so much lower level and so far prior to calculus that we can assume you use them correctly, even without citation. (I know, from experience, that this is an incorrect assumption because some students manipulate inequalities and absolute values incorrectly in the context of calculus. Nevertheless, I will not expect citations of prior results that are much lower level than the current work.)

Oct. 8
Here is a handout on writing proofs. I will give you are hard copy in class.

Don't omit "there exists" when you mean it!
Counterexamples should be specific and complete. Give specific values to each letter. Don't just give "the reason"-- give a specific example!

Comment: Much of low-level math is algorithmic. That is, there is a method that will do the problems and you learn the method. Then you do umpteen problems with the same method. Boring! That is simply being a human calculator! (Value of a great calculator: less than $100. On the web--free!)
    Real math is more like exploration. You don't know what you will find and you don't know how to get there. Some people love exploration and discovery. Proof is more like that. Real math is more like that. I sincerely hope that you enjoy trying to put together proofs of things you (at first) don't know how to prove.

Upcoming homework: Please do your exploration on scratch paper and select the good parts to recopy and hand in. We do not want to see the things you wrote down that did not work. Just show us the good parts! Use scratch paper to begin proofs.

Methods of Proof: By the end of Section 3.5 you will have seen all the common methods of proof. You will have seen the different way proofs are arranged. But you will need a lot of practice to recognize when a given method or arrangement might apply. For now, try anything that comes to mind--but try it as scratch work. Then, from all the ideas you have, select the ones that work, and arrange them so each is true and prior and the result follows from them.
    Do not expect your work to be algorithmic. Proofs are not algorithmic. They are often creative. Enjoy your creativity!

Attitude Goal: Be sure or be skeptical. Do not just "do" steps. Pause at each to be sure it is true. If you are not sure, don't write that step (except as scratch work)! If it is not clearly prior, be skeptical! Do not be accepting without understanding. That is too passive and not the way mathematicians think. Be aware that assertions can be false. Every "=" makes an assertion. Every "<" makes an assertion. Every "=>" makes an assertion. Be certain yours are true!
    When you read (and you must read), if you are not certain a line is true, work with it until you are. Do not accept steps just because they are in print. Be sure or be skeptical.

HW due Friday, Oct. 11: (3.1) B10, B18, 19, 20, 21, 24, 36 (For B36, don't use anything after Definition 3) [HW will be put on the board by students before class each day. Put something up once in a while.]
In Section 3.1, study the given proofs line-by-line. Make sure you know the reason for each assertion. Every "=" requires a reason. Every ">" requires a reason. Every sentence requires a reason. For this section, the work you need to do is to read carefully. You need to seek justifications for every step and realize how details are important. The homework to be handed in is only a small part of what you are to do. Read (slowly and thoroughly) first. Then apply the lessons to the homework. (You may use lower-numbered results to prove higher-numbered results.) If you find anything hard to read, I hope that you will ask questions about it in class.

Future HW will be posted day by day, adapting to what we cover in class. I intend to announce just before the end of each class what it due for next time. Then I will also post it here.

Oct. 14
HW due Wednesday, Oct. 16: (3.2) B7 [again], 8, 11, 12, 13, 14, 37
    One goal of Chapter 3 is to instill an attitude change. You should become skeptical.
    Some things you know well and are certain about. Good. However, anytime something new and similar appears, you must develop the attitude that it might be false. Perhaps you can prove the new variant from your list of prior results. Then you know it is true. Or, perhaps it is false and you can prove it false with a counterexample.
    You need to learn how proofs work. There are many deceptive arguments that can masquerade as proofs. In order to make sure you do not accept false assertions as true, you need to learn to recognize errors in proofs. Read the proofs in Chapter 3 with an eye toward both prior results and logic (the two components of proof). By the end of Chapter 3, you will have studied examples of all the major types of proofs. Then Chapters 4 and 5 will provide practice.

How to do proofs: There is no simple algorithm. We will compile advice as we progress through the course. Here is one important idea:
Use scratch paper. Write down ideas and definitions, especially of the conclusion, on scratch paper without expecting that what you write will be the final organization. After you have written enough that you can see most of the proof, create a final copy by selecting and organizing the useful parts from all that you have written.

Oct. 16
HW due Friday, Oct. 18: Section 3.2: B14 if you didn't get it before (using B13 works, but there is also another way), 16, 17, 22, 27. Read Section 3.3 (of course). Also hand in: (3.3) A1, 2, B1, 2, 5, 11, 12, 16

Advice: Things not to do in proofs. Things to do in proofs. Advice from students in a previous class.

HW due Monday, Oct. 21: (3.3) B57. Read Section 3.4. Be sure you understand Example 1. Then also hand in (3.4) A1, 3, B2, 4, 5

HW due Wednesday, Oct. 23: Read Section 3.5 and do (3.3) B68, (3.4) B8, 18, 23

Oct. 28
        Here is a copy of an exam on Chapter 3. Wednesday and Friday we will have some time to discuss your questions about it.

About homework.

Due Friday, Oct. 25:  (3.5) A3, 5, B2, 7

HW due Monday, Oct. 28: (3.5) B10, 12, 19

    For an extensive list of things you cannot do in proofs, see here.
    For an extensive list of things to do in proofs, see here.

HW due Wednesday, Oct 30: (3.6) A1, 2, 7, 8, 9, 10, 11, 12, 15, 19, B26, 33 [Judge arguments, not truth! Counterexamples may exist, but they do not address the fault in the arguments, which you are supposed to do.]

Due Friday, Nov. 1: Read 4.1. (4.1) Memorize the sentence-form definitions of the set-theory terms. A1, B6, 7 B11

Monday, Nov. 4: Exam on Chapter 3.

Oct. 29

HW due Wednesday, Nov. 6: Read 4.1. (4.1) Memorize the sentence-form definitions of the set-theory terms. A2, B27

Nov. 6
HW due Friday, Nov. 8: Correct your exam on a separate sheet. In addition, do the proof you did not attempt. Hand in the original exam with your corrections so I can see what needed correcting.
    Here is the bulk of your work for Friday and the most important for you. Read this article:
http://chronicle.com/article/article-content/138079/
It is made waves because all faculty are concerned about the impact of modern media on learning.
    By Friday at class time write me up a description of how you study for this class, what you think works and what doesn't, and what you intend to do differently in the future. Please be specific. I would be interested to hear how you have successfully learned things in the past, or any analysis of the situation you want to do.
    Does media distract you?
    Here is one thought you may or may not choose to address.Most people are really good at something (and I don't mean just academic things). How did you get good?
    I think such an analysis of your own learning might be beneficial to you--that's why I'm asking. But, before you do this, I want you to read the article above.
    You might also do some googling about good study habits, or how memory works.
     I'd like this to be clearly typed up and handed in electronically, in a reply e-mail or attached doc file or text file.
     I care and am taking this seriously. I hope you will too.

Monday, Nov. 11, is a holiday. World War I ended on Nov. 11, 1918. It was so terrible that mankind hoped it would be "the war to end all wars." For example, in 1916 the "Battle of the Somme" in France resulted in over one million dead and wounded, and on the single day July 1 the British army suffered 60,000 casualties. US losses in recent wars pale in comparison. Nov. 11 used to be called "Armistice Day" but as memories of WWI faded it became "Veteran's Day." Many people have served in the military and many people have sacrificed to preserve our way of life. We honor them on Veteran's Day.

HW due Wednesday, Nov. 13: (4.1) A12, 14, B14, 34, 41, 42, 53 [This might be revised based on class Friday]

Nov. 8
The final exam is 4:00-5:50, Dec. 12, Thursday of Exam Week. Arrange your winter break schedule so you can take the final at the scheduled time.

Take a look at some of the comments of your peers about distraction and how they study.

HW due Friday, Nov. 15: Read all of Section 4.2. (4.1) B54 (4.2) A17, 25, 28, 29, 32, 35, 36, 45 (prove it), B1, 3, 14, 16, 17, 30, 32

HW due Monday Nov. 18: (4.2) B31, 33, 35, 36, 37, 41.

HW due Wednesday, Nov. 20: Read 5.1 at least through the definitions of "one-to-one" and "onto". (5.1) A2, 8, 11, 14, 17, 19
Here is last semester's exam on Chapter 4. If you look at it before Wednesday's class, we can talk about it in class.

Friday, Nov.22: Exam on Chapter 4. It has definitions, counterexamples, and proofs. It does not ask for creative proofs--rather proofs that are very similar to those you have seen. Study the forms of the proofs we have done and notice what they have in common. Mastery of the definitions is critical. So is mastery of alternative logical forms.

HW due Monday, Nov. 25: (5.1) Read 5.1 closely, including the proof of Conjecture 7 and the bad proof of Conjecture 9. [Learn to recognize characteristics of bad proofs.] Make sure you follow the given examples closely. Hand in (5.1) A15, 18, 21, B7.

HW due Monday, Dec. 2, after Thankgiving: Correct your exam on a separate sheet. In addition, do the problems you did not attempt. Hand in the original exam so I can see what needed correcting. Also, Hand in (5.1) B2, 3, 5, 8, 22. Read part of Section 5.2.

HW due Wednesday, Dec. 4: (5.2) A1, 7, B1, 3, 4, 5, 11, 14

HW due Friday, Dec. 6: (5.2) B8, 10, 12, 15, 19.

Here is a copy of last semester's final exam.

Course policies for Methods of Proof, M-242, at Montana State University, Fall 2013.

Goals: You will learn to read, write, and think like an advanced mathematician. You will learn to read symbolic mathematics with comprehension, express mathematical thoughts clearly, reason logically, recognize and employ common patterns of mathematical thought, and read and write proofs.

Instructor: Dr. Warren Esty Office hours: I love this material and am happy to help.
Mondays, Wednesdays, and Fridays: 9:00-10:50 MWF and many other hours, including Thuesdays and Thursdays. You are more than welcome whenever I am in the office. If you want to arrange to meet some other hour, just ask in class, call (994-5354), or drop in.

Required text: Proof: Introduction to Higher Mathematics, sixth edition, available at the bookstore, by Warren W. Esty and Norah C. Esty.
This course has almost nothing to do with calculation, so no calculator is required.
Bring your text to class every day. We will use it in class.

Course Content: We will proceed straight through the text, covering every section through Chapter 5.
Chapter 1: Preview of proof, sets, logic for mathematics (including truth tables and important logical equivalences that provide alternative forms).
Chapter 2: generalizations, existence statements, negations, reading symbolic mathematics with full comprehension, logical form and deduction, and practice with alternative forms in the context of rational and irrational numbers.
Chapter 3: Proof of theorems about inequalities and absolute values, theory of proofs, proofs by contradiction or contrapositive, proofs by mathematical induction, and common types of mistakes in proofs.
    Chapters 1 through 3 complete the theory. The rest of the course provides practice in several content areas of mathematics.
Chapter 4 is Set Theory including bounds and suprema.
Chapter 5 is about the concepts of one-to-one and onto, functions applied to sets, and cardinality.
    We will cover through Chapter 5.

Prerequisite: Math 172 (two semesters of calculus). The mathematical sophistication provided by additional mathematics such as Math 221 (Matrix Theory) and Math 224 (Calculus of Functions of Several Variables) would be very welcome, but the material covered in those courses is not a prerequisite. In fact, the material in Calculus is not a prerequisite either--we just want you to have read a lot of mathematics.
    This course is primarily for students who wish to be math teachers or math majors, and others, such as computer science students, who need to grasp proof. It is a through discussion of the most important types of thought processes in mathematics.

Etiquette. Proper etiquette is required. During class, students will not engage in any potentially distracting behavior such as reading a newspaper, text-messaging, or whispering about non-math subjects. Cell phones must be turned off and unavailable. Pagers or watches that make a sound, however quietly, must have the sound off. No type of earphones is allowed.

Attendance: Attendance every day is expected. More than a couple unexcused absences is unacceptable. Of course, excuses for academic reasons, illness, participation in university sporting events, and significant life events will be accepted. Every day in class you will learn about common mistakes and how to avoid them. It is not possible to recognize your own errors in logic, so you must take every opportunity to see deceptive errors in reasoning explained and to get feedback about your own and your classmates errors in reasoning. Students who miss a day are missing a significant lesson that cannot easily be recovered from the text alone.
If you miss a day, I will not be able to recreate the class experience for you. Find a friend who can help you catch up, read the text thoroughly, and then I will be glad to help you with specific questions

Cheating: I give you permission to work on homework jointly with others in the class. In fact, I encourage you to work with others because math is a language and learning to communicate in the language helps meet the goals of this course. In this course, learning by working with others is not cheating. However, you must hand in your own work and copying someone else's work to get the homework done is unacceptable. The purpose of homework is not "to get it done," rather, "to learn how to do it." If your homework results in learning, that is all I can ask of it.
    In contrast, exams must be entirely your own work.

Homework. There will be homework due almost every day. It is important that it be attempted on time. The work you hand in need not be all correct, but it must display serious effort. More than a few late homeworks is not acceptable. I will give you important and useful feedback on all the HW you do on time.
    You may work on homework with other current students. You are even encouraged to work with others. You may ask previous students about individual problems. But obtaining work from others and presenting it as your own is unethical and forbidden.
    You are expected to work, on average, about two hours outside class for each class hour.
You must read the assigned sections. Learning to read math with full comprehension is one of your goals, and you learn to read by reading. Reading is part of those two hours.
    Bring your text to class every day. We will use it in class regularly.

Exams and Grading. There will be unit exams, frequent quizzes, regular homework, class participation, and a comprehensive final.
   To receive full credit, daily homework must be handed in on time. Homework handed in late will receive three-fourths credit.
Exam dates will be announced on this site.
Homework and its due dates will be announced on this site.
Your course letter grade will be based primarily on exams and quizzes. Homework is necessary. Not regularly handing in the homework, or handing in work that displays little appropriate effort, will lower your letter grade. However, homework is intended to help you learn and its impact on your grade is primarily that it serves as evidence of your attempt to learn. Getting a few problems wrong or incomplete will not lower your grade if you display appropriate effort. I want to help if you have difficulties.

The final exam is 4:00-5:50 Dec. 12, Thursday of Exam Week. Arrange your winter break schedule so you can take the final at the scheduled time.
(You can find final exam times for other classes at:
http://www.montana.edu/registrar/Schedules.php )

Conflicts. You are required to take all exams and the final exam at the scheduled hours (unless you have another exam or class scheduled at that hour, in which case we will make arrangements). Any exceptions must be approved well in advance, and in no case will exceptions be made for two exams.

Attitude. Some students think math is merely a list of procedures--a succession of algorithms for "how to do" things. Proof is a major part of mathematics that is not at all like that conception of mathematics. So, you may need to change your attitude about what math really is. It is hard for anyone to change their attitude about anything, so this part may be difficult for you.
    Mathematics is a written language (much more so than a spoken one). One goal is to have you learn to read with comprehension. Then you will be able to grasp what mathematical sentences really say (They probably say more than you think!) and learn without relying on the teacher. How can we help you reach this goal? By making you read and work with material even before there is a lecture on it. You learn to read by reading. So, expect to learn by reading. Lectures will clarify things, but not always introduce things.

Success. Higher mathematics requires a significantly different way of thinking. There is a much greater focus on the truth, or falsehood, of statements and connections between facts. There is much less focus on algorithms (methods for doing problems).
    Here is advice about how to learn math.

Read each section. Do not skip the harder parts. In fact, when the going gets rough you need to slow down and read it several times until it makes sense. If it remains unclear, ask me!

This is hard! But, you will be learning an extremely valuable skill.
Don't skim.

Don't expect that only high points are important (Don't read only the bold parts).

Don't skip the rest of the paragraph because you want to move along to the next high point.

Really do read the next paragraph in the text. Mathematics is a written language and you learn it by reading (and writing), not by listening in class.

Homework: If something on your homework is wrong, I will mark it wrong at the place where it goes wrong. Please make sure you understand why. Do not treat your homework as just part of your grade. Treat it as an occasion to learn. Anything you got wrong must be looked at again and studied much harder than anything you easily got right. Some things are easy. It is not much of an accomplishment if you can learn the easy stuff. Some things are harder. Put substantial effort into making sure you understand the harder stuff too.

This site will be updated frequently at the top as the course progresses.

The end. Check for updates at the top of the page.