false

Class Notes
(839,297)

Canada
(511,254)

University of Waterloo
(18,600)

Mathematics
(1,919)

MATH 135
(334)

Mukto Akash
(53)

Lecture

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

Related notes for MATH 135

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

Unlock DocumentJoin OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.