Cs 225 - Ch. 4.2 & 4.4 & 4.6 & 4.7 - Basic Proofs Continued

Front 1

The _______ of an integer refers to whether the integer is even or odd.

Back 1

The parity of an integer.

For instance, 5 has odd parity and 28 has even parity. We call the fact that any integer is either even or odd the parity property.

Front 2

The _________ into cases in a proof is like the transfer of control for an if-then-else statement in a computer program.

Back 2

Division into cases

Example:

Case 1 (m is even):

Case 2 (m is odd):

Front 3

To prove a statement of the form “If A1 or A2 or . . . or An, then C,” prove all of thefollowing:

• If A1, then C,
• If A2, then C,...
• If An, then C.

This process shows that C is true regardless of which of A1, A2,..., An happens to be the case.

This is called the Method of Proof by ______ into _______

Back 3

Method of proof by division into cases

Front 4

A second form of indirect argument (the first being proof by contradiction), argument (or proof) by __________, is based on the logical equivalence between a statement and its _________________.

Back 4

argument bycontraposition

• based on the logical equivalence between a statement and its contrapositive.
  

Front 5

To prove a statement by contraposition, you take the contrapositive of the statement, prove the contrapositive by a direct proof, and conclude that the original statement is _____.

Back 5

Prove the contrapositive, and

....conclude that the original statement is true.

Front 6

Steps for Method of Proof by Contraposition:

• 1. Express the statement to be proved in the form: ∀x in D, if P(x) then Q(x)
  
• 2. Rewrite this statement in the contrapositive form: ____________.
  
• 3. Prove the contrapositive by a direct proof. (suppose x in Q(x) is false, show that p(x) is also false)
  

Back 6

2. Rewrite this statement in the contrapositive form:

∀x in D, if Q(x) is false then P(x) is false.

Front 7

The parity of an integer refers to whether the integer is ____ or ____.

Back 7

The parity of an integer refers to whether the integer is even or odd.

For instance, 5 has odd parity and 28 has even parity. We call the fact that any integer is either even or odd the parity property.

Front 8

A second form of ___________ argument (the first being proof by contradiction), argument by contraposition, is based on the logical equivalence between a statement and its contrapositive.

Back 8

form of indirect argument

Front 9

Two forms of indirect arguments:

• argument (proof) by _____________.
  
• argument (proof) by _____________.
  

Back 9

Two forms of indirect arguments:

• argument (proof) by contradiction.
  
• argument (proof) by contraposition.
  

Front 10

Two forms of _______ arguments:

• argument (proof) by contradiction.
  
• argument (proof) by contraposition.
  

Back 10

Two forms of indirect arguments:

argument (proof) by contradiction.

argument (proof) by contraposition.

Front 11

Steps for Method of Proof by Contraposition:

• 1. Express the statement to be proved in the form: ∀________________
  
• 2. Rewrite this statement in the contrapositive form: ∀x in D, if Q(x) is false then P(x) is false.
  
• 3. Prove the contrapositive by a direct proof. (suppose x in Q(x) is false, show that p(x) is also false)
  

Back 11

1. Express the statement to be proved in the form:

∀x in D, if P(x) then Q(x)

Front 12

Steps for Method of Proof by Contraposition:

• 1. Express the statement to be proved in the form: ∀x in D, if P(x) then Q(x)
  
• 2. Rewrite this statement in the contrapositive form: ∀x in D, if Q(x) is false then P(x) is false.
  
• 3. Prove the contrapositive by a direct proof. (suppose x in Q(x) is false, show that ______________)
  

Back 12

3. Prove the contrapositive by a direct proof.

(suppose x in Q(x) is false, show that p(x) is also false)

Front 13

_________ ad ___________ is one of a mathematician’s finest weapons. It is a far finergambit than any chess gambit: a chess player may offer the sacrifice of a pawn or evena piece, but the mathematician offers the game.

Back 13

Reductio ad absurdum

means: "reduction to absurdity"

Front 14

In a ________ proof you start with the hypothesis of a statement and make one deduction afteranother until you reach the conclusion. _________ proofs are more roundabout.

Back 14

direct proofs

indirect proofs

Front 15

In a direct proof you start with the ___________ of a statement and make one deduction after another until you reach the conclusion. Indirect proofs are more roundabout.

Back 15

In a direct proof you start with the hypothesis of a statement, and make one deduction after another until you reach the conclusion.

Front 16

Argument by contradiction, is based on the fact that either a statementis true or it is false but not both. So if you can show that the assumption that a givenstatement is not true leads logically to a ______________, impossibility, or absurdity, thenthat assumption must be false: and, hence, the given statement must be true.

Back 16

Argument by Contradiction

The assumption that a given statement is not true leads logically to a contradiction. Then that assumption must be false, and hence, the given statement must be true!

Front 17

Argument by contradiction, is based on the fact that either a statement is true or it is false but not both. So if you can show that the assumption that a given statement is not true leads logically to a contradiction, impossibility, or absurdity, then that assumption must be _____: and, hence, the given statement must be _____.

Back 17

Argument by Contradiction

...then that assumption must be false: and, hence, the given statement must be true.

Front 18

An example of argument by contradiction in debate:

"Suppose for a moment that what my opponent....."

Back 18

"Suppose for a moment that what my opponent says is correct."

Starting from this supposition, thedebater then deduces one statement after another until finally arriving at a statement thatis completely ridiculous and unacceptable to the audience.

Front 19

The point of departure for a proof by contradiction is the supposition that the statement to be proved is _______. The goal is to reason to a _____________.

Back 19

The point of departure for a proof by contradiction is the supposition that the statement to be proved is false. The goal is to reason to a contradiction.

Front 20

There are no clear-cut rules for when to try a direct proof and when to try a proof bycontradiction, but there are some general guidelines. Proof by contradiction is indicatedif you want to show that there is no object with a certain property, or if you want to showthat a certain object does not have a certain property.

Back 20

Proof by contradiction is indicated if you want to show that there is no object with a certain property, or if you want to show that a certain object does not have a certain property.

Front 21

Proof by contradiction is indicated if you want to show that there is no object with a certain property, or if you want to show that a certain object does not have a certain __________.

Back 21

Proof by contradiction is indicated if you want to show that there is no object with a certain property, or if you want to show that a certain object does not have a certain property.

Front 22

Staring Point for a Proof (or argument) of contradiction:

"Suppose..."

Back 22

"Suppose not. Suppose ~P(x)."

Front 23

After a contradiction has been reached, the logic of the argument is always the same:

“This is a contradiction. Hence the __________ is false and the ____________ is true.”

Back 23

"This is a contradiction. Hence the supposition is false and the theorem is true.”

Front 24

When using proof by contradiction:

Begin by supposing the negation of what you are to prove. WARNING: be careful when writing down what this means. If you write the _________ incorrectly, the entire rest of the proof will be flawed.

Back 24

Proof by contradiction:

If you write down the negation incorrectly, the entire rest of the proof will be flawed.

Front 25

The quotient-remainder theorem says that when any integer n is divided by any positive integer d,

the result is a _________ q and a nonnegative remainder r that is smallerthan d.

Back 25

...the result is a quotient q and a nonnegative remainder r that is smaller than d.

Front 26

The ________-________ theorem says that when any integer n is divided by any positive integer d, the result is a quotient q and a nonnegative remainder r that is smaller than d.

Back 26

The quotient-remainder theorem:

Given any integer n and positive integer d,

n = dq + r and

0 ≤ r < d.

Front 27

n mod d = the nonnegative integer remainder obtainedwhen _ is divided by _.

Back 27

n mod d

n % d

remainder when (n is divided by d)

Front 28

they usethe word __________ to refer to a statement that is somewhat less consequential butnonetheless worth writing down.

Back 28

proposition:

A statement that is somewhat less consequential but nonetheless worth writing down.

Front 29

When you use proof by ____________, you know exactly what conclusion you need to show, namely the negation of the hypothesis;

whereas in proof by ____________, it may be difficult to know what contradiction to head for.

Back 29

Proof bycontraposition

Proof by contradiction

Front 30

In a proof by ______________, it may be difficult to know what ___________ to head for, but once you have deduced a ___________ whatsoever, you are done.

Back 30

Proof by contradiction

Front 31

The disadvantage of a proof by contraposition as compared with contradiction is that you can use contraposition only for a specific class of statements—those that are ________ and ___________.

Back 31

universal and conditional

Front 32

Any statement that can be proved by ______________can be proved by _____________. But the converse is not true.

Back 32

Any statement that can be proved by Contraposition can be proved by contradiction.

But the converse is not true:

Being able to solve by contradiction DOES NOT mean you can solve by contraposition.

Front 33

Psychologists who have studied problem solving have found that the most successful problem solvers are those who are _________ and willing to use a variety of approaches without getting stuck in any one of them for very long.

Back 33

The best problem solvers areflexible.

Front 34

Learning the skills of proof and disproof is much like learning other skills, such as those used in swimming, tennis, or playing a musical instrument. When you first start out, you may feel bewildered by all the rules, and you may not feel confident as you attempt new things. But with practice, the rules become internalized.

Back 34

But with practice, the rules become internalized.

Front 35

You need to know how direct and indirect proofs and counterexamples are structured.

But to use this knowledge effectively, you must use it in conjunction with your imaginative powers, your intuition, and especially your common sense.

Back 35

To use this knowledge effectively, you must use it in conjunction with your imaginative powers, your intuition, and especially your common sense.

Front 36

For all elements in a domain, if (hypothesis) then (conclusion),

Can I imagine any elements that satisfy the hypothesis and conclusion? If yes, the statement is true and your insight will form the basis for a ________ proof.

Back 36

direct proof

Front 37

For all elements in a domain, if (hypothesis) then (conclusion),

If I cannot clearly find elements that satisfy the hypothesis and conclusion, look for elements that satisfy the hypothesis and not the conclusion. If I find one or some examples, the statement is false and I have a ____________.

Back 37

counterexample.

Front 38

For all elements in a domain, if (hypothesis) then (conclusion),

Perhaps you can show that assuming the existence of elements in the domain that satisfy the hypothesis and not the conclusion leads logically to a contradiction. If so, then the given statement is true and you have the basis for a proof by ______________.

Back 38

proof by contradiction

Front 39

For all elements in a domain, if (hypothesis) then (conclusion),

Imagine elements of the domain for which the conclusion is false and ask whether such elements also fail to satisfy the hypothesis. If the answer in all cases is “yes,” then you have a basis for a proof by _____________.

Back 39

proof by contraposition

Front 40

two of the most famous theorems in mathematics: that √ 2 is irrational and that there are infinitely many ______ numbers.

Back 40

infinitely many prime numbers

Front 41

In the fourth or fifth century B.C.E., the followers of the Greek mathematician and philosopher ______________ discovered that √ 2 was not rational. This discovery was very upsetting to them, for it undermined their deep, quasi-religious belief in the power of whole numbers to describe phenomena.

Back 41

Greek mathematician and philosopher Pythagoras

Front 42

Many theorems can be proved by either a direct or indirect proof. Usually, however, when both types of proof are possible, a(n) _______ proof is clumsier than a(n) _________ proof.

Back 42

indirect proof is clumsier than a direct proof.

Front 43

1. In the absence of obvious clues suggesting indirect argument, try first to prove a statement ___________.
   
2. Then, if that does not succeed, look for a counterexample.
   
3. If the search for a counterexample is unsuccessful, look for a proof by contradiction or contraposition.
   

Back 43

1. Try first to prove a statement directly

Front 44

1. In the absence of obvious clues suggesting indirect argument, try first to prove a statement directly.
   
2. Then, if that does not succeed, look for a ________________.
   
3. If the search for a counterexample is unsuccessful, look for a proof by contradiction or contraposition.
   

Back 44

2. If proving a statement directly does not work, then look for a counterexample.

Front 45

1. In the absence of obvious clues suggesting indirect argument, try first to prove a statement directly.
   
2. Then, if that does not succeed, look for a counterexample.
   
3. If the search for a counterexample is unsuccessful, look for a proof by __________ or ___________.
   

Back 45

3. If the search for a counterexample is unsuccessful, look for a proof by contradiction or contraposition.