Proofs

Overview

A direct proof is a sequence of statements, either givens or deductions of previous statements, whose last statement is the conclusion to be proved. An indirect proof works by assuming the denial of the desired conclusion leads to a contradiction in some way.

Conditional Proofs

A conditional proof is a proof method used to prove a conditional statement, i.e. statements of form:

P_{1} \land \dots \land P_{n} ⟹ Q

Note we can assume all the hypotheses are true since if one were false, the implication holds regardless. Direct proofs of the above form are called conditional proofs (CP).

These conditional are often expressed in different (but "equivalent") ways. Common English expressions and their interpretation include:

" $P$ if $Q$ " meaning $(Q ⟹ P)$ .
" $P$ only if $Q$ " meaning $(P ⟹ Q)$ .
" $P$ is necessary for $Q$ " meaning $(Q ⟹ P)$ .
" $P$ is sufficient for $Q$ " meaning $(P ⟹ Q)$ .

Proof by Contraposition

Since a conditional and its contrapositive are logically equivalent, we can instead prove the negation of the conclusion leads to the negation of our hypotheses.

Proof by Contradiction

To prove a proposition $P$ by contradiction, we assume $\neg P$ and derive a statement known to be false. Since mathematics is (in most cases) consistent, $P$ must be true.

Existence Proofs

An existence proof is a proof method used to prove an existential statement, i.e. statements of form:

\exists x, P (x)

An existence proof is said to be constructive if it demonstrates the existence of an object by creating (or providing a method for creating) the object. Otherwise it is said to be non-constructive.

Induction

Proof by induction involves inferring that a subset $B$ of set $A$ actually coincides with $A$ based on membership properties of smaller sets. The formal justification of proof by induction is intimately tied to the idea of inductive sets and the well-ordering principle.

Weak Induction

Let $P (n)$ be a predicate depending on a number $n \in N$ . Assume that

Base case: $P (n_{0})$ is true for some $n_{0} \geq 0$ , and
Inductive case: for all $k \geq n_{0}$ , $P (k) ⟹ P (k + 1)$ .
- $P (k)$ is called the inductive hypothesis.

Then $P (n)$ is true for all $n \geq n_{0}$ .

Strong Induction

Let $P (n)$ be a predicate depending on a number $n \in N$ . Assume that

Base case: $P (n_{0})$ is true for some $n_{0} \geq 0$ , and
Inductive case: for all $k \geq n_{0}$ , $P (n_{0}) \land P (n_{0} + 1) \land \dots \land P (k) ⟹ P (k + 1)$ .

Then $P (n)$ is true for all $n \geq n_{0}$ .

More simply stated, let $A$ be a subset of $ω$ and assume that for every $n \in ω$ , if every number less than $n$ is in $A$ , then $n \in A$ . Then $A = ω$ .

Well-Ordering Principle

Let $A$ be a nonempty subset of $ω$ . Then there is some $m \in A$ such that $m \underset{―}{\in} n$ for all $n \in A$ .

Transfinite Induction

Let $<$ be a strict well ordering on set $A$ . We say that $B \subseteq A$ is a $<$ -inductive subset of $A$ if and only if for every $t \in A$ ,

{seg}_{<} t \subseteq B ⟹ t \in B .

The transfinite induction principle states that if $<$ is a strict well ordering on set $A$ , any $<$ -inductive subset of $A$ must coincide with $A$ .

The "converse" also holds true. Assume $<$ is a strict total ordering on $A$ . Furthermore, assume the only $<$ -inductive subset of $A$ is $A$ itself. Then $<$ is a well ordering on $A$ .