Proof

A proof is a method of communicating a mathematical truth. It is a series of convincing arguments that leaves no doubt that a given proposition is true.

TODO: How to prove algorithms?

Some Definitions

Proposition: Mathematical claim posed in the form of a statement that either needs to be proven or demonstrated false by a valid argument. Theorem: A particularly significant true proposition. Lemma: Subsidiary proposition that is used in the proof of a theorem Corollary: Proposition that follows from a theorem

3.1. Proving Universally Quantified Statements

Proof

To prove the universally quantified statement ”$\forall x\in S,P(x)$“:

Choose a representative mathematical object $x\in S$. This cannot be a specific object. It has to be a placeholder, that is, a variable, so that our argument would work for any specific member of the domain $S$.

Then, show that the open sentence $P$ must be true for our representative $x$, using known facts about the elements of $S$.

Disproof

To disprove the universally quantified statement “$\forall x\in S,P(x)$”:

Show that $(\exists x\in S,\neg P(x))$ is true. In other words, find an element $x\in S$ for which the open sentence $P(x)$ is false. This process is called finding a counter-example.

3.2 Proving Existentially Quantified Statements

Proof

To prove the existentially quantified statement “$\exists x\in S,P(x)$”:

Provide an explicit value of x from the domain $S$, and show that $P(x)$ is true for this value of $x$. In other words, find an element of $S$ that satisfies property $P$.

Disproof

To disprove the existentially quantified statement “$\exists x\in S,P(x)$”:

Show that the universally quantified statement $(\forall x\in S,\neg P(x))$ is true.

3.3 Proving Implications

1. To prove the implication “$A⟹B$”, assume that the hypothesis $A$ is true, and use this assumption to show that the conclusion $B$ is true. The hypothesis $A$ is what you start with. The conclusion $B$ is where you must end up.

2. To prove the universally quantified implication “$\forall x\in S,P(x)⟹Q(x)$”: Let $x$ be an arbitrary element of $S$, assume that the hypothesis $P(x)$ is true, and use this assumption to show that the conclusion $Q(x)$ is true.

3.5 Proof by Contrapositive

1. If we want to prove that $A⟹B$, we can prove that $(\neg B)⟹(\neg A)$
2. To prove $(\forall x\in S,P(x)⟹Q(x))$, prove $(\forall x\in S,(\neg Q(x))⟹(\neg P(x)))$

3.6 Proof by Contradiction

Let A be a statement. Note that either $A$ or $\neg A$ must be false, so the compound statement $A\wedge (\neg A)$ is always false. The statement “$A\wedge (\neg A)$ is true” is called a contradiction.

Ex: Prove that $\sqrt{2}$ is irrational.

Prove if and only if

For proving an if and only if statement:

1. To prove the statement $A⟺B$, it is equivalent to prove both the implication $A⟹B$ and its converse $B⟹A$

2. To prove the universally quantified statement $(\forall x\in S,P(x)⟺Q(x))$, it is equivalent to do either a or b below

   $(a)$ Let $x$ be an arbitrary element of $S$. and prove both the implication ”$P(x)⟹Q(x)$” and its converse ”$Q(x)⟹P(x)$” $(b)$ Prove both the universally quantified implication ”$\forall x\in S,Q(x)⟹P(x)$” and ”$\forall x\in S,P(x)⟹Q(x)$”

Prove Subset

see Set Theory

Other proof Methods:

• Proof by Induction