Theorems and Proofs

flashcards from Andrei Bulotov's MACM 101 class

What are the two meanings of “theorem”?

(1) An important mathematical statement; (2) Any proposition inferred within an axiomatic theory.

What is an axiom?

A starting proposition assumed true to derive theorems.

What does an axiomatic theory specify?

A set of axioms and explicit rules of inference.

How do we prove ∀x P(x) by exhaustion over universe U?

Verify P(a) for every a ∈ U.

How do we prove ∃x P(x) by exhaustion?

Search a ∈ U until finding a with P(a) true.

Universal Specification (US)

From ∀x P(x), infer P(c) for any c ∈ U.

Universal Generalization (UG)

If P(c) holds for generic c ∈ U, conclude ∀x P(x).

Existential Specification (ES)

From ∃x P(x), take a witness a ∈ U with P(a).

Existential Generalization (EG)

From P(a) for some a ∈ U, infer ∃x P(x).

Why is assuming “c is even” a UG error?

c must be generic; restricting c to a subset violates ∀x.

Direct proof (template)

Assume P(c) for generic c ∈ U ⇒ derive Q(c) ⇒ by UG, ∀x (P→Q).

Contraposition (template)

To prove ∀x (P→Q), prove ∀x (¬Q→¬P).

Contradiction (template)

Assume ¬p ⇒ derive a contradiction ⇒ conclude p.

Chain implication example

From ∀x (S→M), ∀x (M→F), ∀x (F→L) infer ∀x (S→L).

Parity example (contraposition)

If 3n+2 is even ⇒ n is even; equivalently, if n is odd ⇒ 3n+2 is odd.

Barber (definition)

A “strict” barber shaves those and only those who do not shave themselves.

Barber paradox (result)

No strict barber exists (assumption yields q ∧ ¬q).

√2 irrationality (outline)

Assume √2 = a/b in lowest terms ⇒ both a,b even ⇒ contradiction ⇒ √2 ∉ ℚ.

Proving ∃x P(x) constructively

Exhibit a specific a ∈ U with P(a).

Proving ∃x P(x) non-constructively

Assume ∀x ¬P(x) and derive a contradiction.

When to note the universe U

Whenever quantifiers/symbols are ambiguous, state U and c ∈ U explicitly.

Modus Ponens (MP)

From P and (P→Q), infer Q.

Hypothetical syllogism

From (P→Q) and (Q→R), infer (P→R).