Proofs

Question 1

Lecture 01

Define “Proof:”

Answer 1

A proof is a sequence of statements that are connected by inferences

Question 2

Lecture 01

Define “Theorem:”

Answer 2

A theorem is a statement that is the last line of the proof

Question 3

Lecture 01

Define “lemma:”

Answer 3

A lemma is a theorem that is usually used within another proof

Question 4

Lecture 01

What are conditional proofs?

Answer 4

The starting points of proof are not definitions, axioms, or theorems but assumptions or hypotheses of which we don’t know whether they are true or false.

To prove a conditional statement:

Claim: if A then B

Assume A and show B

Question 5

Lecture 01

What are biconditionals?

Answer 5

Claim: A if and only if B

1. Assume A and show B
2. Assume B and show A

Abbreviate “if and only if” by ‘iff”

Question 6

Lecture 01

What are proof by cases?

Answer 6

Proof by cases the original problem is divided into two or more different problems that are smaller and thus easier to deal with, that can be attacked separately.

Must be finite cases (exhaustive)

Ex:

Claim: Every day of the weed has a “d” at the end

Proof: list the days of the week

The general structure of the Proof:

• Claim: Either A1 or A2 or … or A_n holds
• Case (1): Uner the assumption A1, we conclude C
• Case (2) Under the assumption A2, we conclude C

…

• Case (n): Under the assumption An, we conclude C
• Conclusion: C

Question 7

Lecture 01

What is the Simplest case distinction?

Answer 7

Either A or not -A

• Formally: A v ¬A
• Tertium non datur,
  Based on the principle of bivalence: every proportion is either true or false
  Note: not all accept this!
• Sometimes not able to determine which one of the cases actually holds, not necessary for the proof to work
• Bring a certain non-constructive element into proof technique
• Non-classical forms of reasoning

Question 8

Lecture 01

What is the formal system of Natural Deduction?

Answer 8

Inference rule that corresponds to this type of proof:

Question 9

Lecture 01

Proof by contradiction/reductio ad absurdum:

Answer 9

Structure:

• Claim: A
• Assumption (for the sake of contradiction): Negation of A
  
  • Argument (reductio)
  • Contradiction (absurdum) Symbolically: ⊥
• Conclusion: A