Class Notes (839,297)
Canada (511,254)
Mathematics (1,919)
MATH 135 (334)
Lecture

How To Read and Do Proofs - SUMMARIZED.docx

5 Pages
393 Views

Department
Mathematics
Course Code
MATH 135
Professor
Mukto Akash

This preview shows pages 1 and half of page 2. Sign up to view the full 5 pages of the document.
Description
Math 135 Textbook summary, Natasha Park Math 135: How to read and do proofs The universe of discourse is the set from which the “objects” are taken. It is the domain of the objects. Chapter1: The truth of it all  A and B are statements that are either true or false  Conditional statements are statements that are true, sometimes  Proof is a convincing argument expressed as a language of mathematics. Proof should have enough mathematical details to be convincing to the people to whom the proof is addressed  In A implies B, statement A is called the hypothesis (everything that you are assuming to be true), and statement B is the conclusion (everything you are trying to prove)  To prove that A implies B is true, you must assume A is true to reach the conclusion that B is true A B A implies B T T T T F F F T T F F T Chapter 2: The Forward-Backward Method  All other proof techniques rely on this method  In attempting to reach the conclusion B, you’ll use the backward process. By using information from hypothesis A, you’re using the forward process. Backward process 1. Key question: Begin by asking “how or when can I conclude that B is true?”  propose the question in an abstract way, using your general knowledge, clearing away details, allowing you to focus on the aspects of the problem that actually matter  no specific notations/symbols 2. Answer the key question: abstract answer, with no specific notations/symbols 3. Apply the abstract answer to the question, using appropriate symbols/notations  this answer is statement B1  if B1 is true, B is true 4. Once you have the statement B1, all your efforts must be directed toward reaching the conclusion that B1 is true, for then it will follow that B is true 5. Make a key question for B1 - Problem: there may be multiple. Let the information in A help you choose the key question. 6. Make an answer for the key question - Problem: there may be more than one answer 7. Once you apply the answer to B1, the answer becomes statement B2 8. Continue making key questions and abstract answers until you do not know how to ask/answer Forward process 1. Deriving statement A1 from A (which you assume to be true)  A1 is true since A is true 2. Keep deriving statements, and direct them toward linking up with the last statement obtained in the backward process - Problem: you might derive useless statements 3. The forward process should ultimately produce the elusive answer to the key question associated with B2 Reading proofs  You know the author is working forward when he says “from the hypothesis…”  To read a condensed proof, you must discover the thought processes that went into the proof  determine which techniques are used and verify all steps involved by filling in blanks Math 135 Textbook summary, Natasha Park - Steps in the proof aren’t always presented in the same order in which they were performed - Names of techniques are often omitted - Several steps are combined into a single statement with little/no explanation Chapter 3: Definitions & Mathematical Terminology Definitions  An agreement, by all parties concerned, as to the meaning of a particular term  One of the simplest/most effective ways of answering a key question  Definitions are not made randomly  are motivated by a mathematical concept that occurs repeatedly  an abbreviation that is agreed on for a particular concept  Used in the backward process to answer a key question and in the forward process to derive new statement  If there’s overlapping notation between the 2, rewrite the definition using a set of symbols that don’t overlap with those of the current proposition  Sometimes there’s more than one definition for the same concept - Choose a definition - Establish the equivalence of the definition and the alternatives (A implies B and B implies A)  A iff B (if and only if) - Advantageous in forward-backward method because more ammunition available Notational issues  Occurs when the definition uses one set of symbols and notation while the specific problem under consideration uses a second set of symbols and notation  if there is overlap  Avoid notational errors by first rewriting the definition using a new set of symbols that do not overlap with the specific problem under consideration. Then when you apply the definition to the specific problem, the matching up of notation will be clear. Using previous knowledge in backward process  Use previous knowledge in the form of a previously proven implication  In order to use previous knowledge in the backward process to prove that A implies B is true, you should look for a previously proved proposition of the form C implies B  same conclusion as current proposition except for notation - Match up the notation of the current and previous propositions - Verify that the hypothesis of the previous notation are satisfied for the current proposition  prove that A implies C is true Using previous knowledge in forward process  When trying to prove that A implies B is true, look for a previously proved proposition of the form A implies C  proposition with the same hypothesis as the current proposition, for which it is possible to work forward from C (previous conclusion) to get to B (current conclusion) - Match up the notation of the current and previous proposition - Write, as a new statement in the forward process, the conclusion of the previous proposition using the notation of the current proposition (write a forward statement that C is true) - Complete the proof that A implies B by working forward from C and backward from B Mathematical terminology  Proposition: true statement of interest that you are trying to prove.  Theorems: very important propositions (subjectively) Math 135 Textbook summary, Natasha Park  Lemma: when the proof of a theorem I long, the proof I often easier to communicate in pieces. A lemma is a preliminary proposition that is used in the proof of a theorem - Ex: when proving A implies B, it may first be convenient to show that A implies C, then C implies D, and D implies B. Each of these supporting propositions is a lemma.  Corollaries: once a theorem is proved, certain propositions usually follow almost immediately as a result of knowing that the theorem I true  propositions that follow a theorem  Contrapositive statement: technique for proving that A implies B in which you prove that NOT B implies NOT A by working forward from NOT B and backward from NOT A  Converse statement: the converse of the statement A implies B is the statement B implies A.  Inverse statement: the inverse of the statement A implies B is the statement NOT A implies NOT B.  Quantifiers: 2 forms of statements that appear repeatedly throughout all branches of mathematics 1. Existential: there is 2. Universal: for all  A set is a collection of items. Each item is called a member/element of the set. - Defining property of the set: (in proofs, this plays the same role as a definition) everything following the “su
More Less
Unlock Document

Only pages 1 and half of page 2 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit