0.0: Introduction to proofs

Introduction to Proofs/Contradiction

How to Prove a Mathematical Statement

A mathematical proof is a logical explanation showing why a statement must be true under its stated assumptions. A proof is different from checking several examples: examples can help us discover a pattern, but a proof must establish the claim in every case covered by the statement.

Throughout a proof, define your variables, state the assumptions clearly, use complete sentences, and explain why each important step follows from the preceding ones.

In this section, we will explore different techniques for proving a mathematical statement, "If \(p\) then \(q\)". (\(p \to q\)). This is a conditional statement.  

 

From  DR. Thi Dinh's Proof Writing Handbook, this Bible:

 

In the beginning...

Let \(P\) and \(Q\) be statement variables. When needed, suppose that P = P(x) depends on a variable x. The symbol "\(\forall\)" means "for all" or "for any". The symbol \(\exists\) means "there exists". 

 

Type of statement	What must we do to prove that it is true
(1) If \(P\), then \(Q\) (2) \(\forall x P(x)\), \(Q\)	Suppose that \(P\) is true. Prove that \(Q\) is true.
(3) \(\exists x P(x) \) such that \(Q\)	Choose \(x\) so that \(P(x)\) is true. Prove that \(Q\) is true. Note: You need not explain how you find \(x\).

The first (and only) commandment

To prove that a statement is false, thou shalt write out the negation of the statement and prove that.

The five cardinal sins

• When proving any of the types of statements (1), (2), or (3):

1. Thou shalt not: suppose that \(Q\) is true.

2. Thou shalt not: overuse symbols and violate the rules of English grammar. You must write in full sentences and use symbols correctly.

• When proving a statement of the form (2) \(P, Q\):

3. Thou shalt not: choose or exhibit an example in place of a proof.

• When proving a statement of the form (3) "\(\forall x P(x)\) such that \(Q \):

4. Thou shalt not: attempt to construct all possible \(x\) so that \(P(x)\) and \(Q\) are true.

• When proving a statement by contradiction:

5. Thou shalt not: claim a contradiction has been reached without explanation. You must clearly identify the contradiction being made by making a statement of the form "\(P\) and NOT \(P\), which is a contradiction".

 

Direct Proof

To prove that \(p\) implies \(q\), assume that \(p\) is true and use definitions, known facts, and logical reasoning to establish \(q\). In this technique, we shall assume \(p\) and show that \(q\) is true.

Theorem \(\PageIndex{1}\)

Let \(n\) be an integer. If \(n\) is even then \(n^2\) is even.

Proof

Let \(n\) be an integer. Assume that \(n\) is even. Then \(n=2m\) for some integer \(m \).

Consider \(n^2=(2m)^2=4m^2=2(2m^2).\) Since \( m \) is an integer, \( (2m^2)\) is an integer.

Thus \(n^2\) is even.\(\square\)

Example \(\PageIndex{1}\)

Show that for all integers \( n\), if \(n\) is odd then \(n^2\) is odd.

Proof

Let \(n\) be an integer. Assume that \(n\) is odd. Then \(n=2m+1\) for some integer \(m \).

Consider \(n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.\)

Since \( m \) is an integer, \( (2m^2+2m)\) is an integer.

Thus \(n^2\) is odd.\(\square\)

Proof by Contrapositive

To prove that \(p\) implies \(q\), it is sometimes easier to assume that \(q\) is false and show that \(p\) must also be false. This works because \(p\to q\) and \(\not q \to \not p\) are logically equivalent. In this technique, we assume \(\neg q\) and show that \(\neg p\) holds.

Theorem \(\PageIndex{2}\)

Let \(n\) be an integer. If \(n^2\) is even then \(n\) is even.

Proof

Let \(n\) be an integer. We shall prove this statement by assuming \(n\) is odd. Then \(n=2m+1\) for some integer \(m \).

Consider \(n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.\)

Since \( m \) is an integer, \( (2m^2)+2m\) is an integer.

Thus \(n^2\) is odd.\(\square\)

Example \(\PageIndex{2}\)

Show that for all integers \( n\), if \(n^2\) is odd then \(n\) is odd.

Proof

Let \(n\) be an integer. We shall prove this statement by assuming \(n\) is even. Then \(n=2m\) for some integer \(m \).

Consider \(n^2=(2m)^2=4m^2=2(2m^2).\)

Since \( m \) is an integer, \( (2m^2)\) is an integer. Thus \(n^2\) is even.\(\square\)

Proof by Contradiction

Assume that the statement to be proved is false. If this assumption leads to a contradiction, then the original statement must be true. In this technique, we assume the negation of the statement and derive a contradiction.

Theorem \(\PageIndex{3}\)

\(\sqrt{2}\) is irrational.

Proof

Assume that \(\sqrt{2}\) is rational. Then \(\sqrt{2}= \dfrac {b}{a}\), where \(b \in \mathbb{Z}, a \in \mathbb{Z}\setminus \{0\}\), with no common factors between \(a\) and \(b\). Now, \( \sqrt{2} a=b\). Then \( 2a^2=b^2\). Since  \(2a^2  \mathbb{Z}\),  \(b^2\) is even. Therefore, \(b\) is even (by Theorem 2). Since \( b\) is even, \(b=2m\) for some integer \(m\in \mathbb{Z}\). Therefore,  \(b^2=4m^2\).

Since \(2a^2=b^2\), \(2a^2=4m^2\). Therefore, \(a^2=2 m^2\). This implies \(a\) is even. This contradicts the fact that \(a\) and \(b\) have no common factors. Thus \(\sqrt{2}\) is irrational. \(\square\)

Proof by Counterexample

To disprove a claim that something holds for every element of a set, it is enough to find one element for which the claim fails.

Example \(\PageIndex{3}\):

Decide whether the statement is true or false and justify your answer:

For all integers \(a,b,u,v\), and \(u\ne 0, v \ne 0\), if \(au+bv =0\) then \(a=b=0.\)

Solution: The statement is false.

Counterexample: Choose \(a=1,b=-1, u=2,v=2\), then \(au+bv =0\), but \(a\ne 0. b \ne 0, a \ne b.\)

Mathematical Induction

To prove a statement for every integer \(n \ge n_0\), first establish the base case \(n =n_0\). Then show that whenever the statement holds for an arbitrary integer \(k \ge n_0\), it also holds for \(k+1\). Together, these steps establish the statement for all integers \(n \ge n_0\).

Throughout a proof, define your variables, state the assumptions clearly, use complete sentences, and explain why each important step follows from the preceding ones.

Process of Proof by Induction:

To prove that \(P(n)\) is a mathematical statement for all integers \(n \ge n_0\).

1. Base case: Prove the statement is true for the lowest value of \(n\) (i.e., prove \(P(n_0)\)).

2.  Induction hypothesis: Fix an arbitrary \(k\ge n_0\) and assume \(P(k)\).

3. Inductive step: Use the hypothesis to prove \(P(k+1)\).

4. Conclusion: By induction, \(P(n)\) is true for every integer \(n\ge n_0\).

Example \(\PageIndex{4}\)

Prove \(2^n>n+4\) for every integer \(n\ge 3\).

Proof

Let \(n=3\).  Then \(2^3 >3+4\) is true since clearly \(8>7\).  Thus the statement is true for \(n=3\).

Assume that \(2^n > n+4\) is true for some \(n=k\).

We will show that \(2^{k+1} > (k+1)+4\).

Consider \(2^{k+1}=2 \cdot 2^{k} >2 \cdot (k+4)=2k+8\).

Since \(2k > k+1\) and \(8 >4\), we have \(2k+8>(k+1)+4\).

Thus, the statement is true for all \(n=k\).

By induction, \(2^n > n+4\) for every integer \(n\ge 3\).

Example \(\PageIndex{5}\)

Show that \(9|(10^{n+1}+3(10^n)+5), \forall n\in \mathbb{Z} n \ge 1\). \(\square\)

Proof

Let \(n=1\).  Then \(9|(10^2)+3(10)+5\), which is \(9|135\), which is true since \(135=9(15)\) and \(15 \in \mathbb{Z}\).

Assume that \(9|(10^{n+1}+3(10^n)+5\) is true for some \(n=k\).

We will show that \(10^{k+1+1}+3(10^{k+1})+5=9m\) for some \(m \in \mathbb{Z}\).

Consider \(10^{k+1+1}+3(10^{k+1})+5=10(10^{k+1}+3(10^k)+5)-9(5)\)

       \(=10(9m)-9(5)\)

       \(=9(10m-5)\), where \(10m-5 \in \mathbb{Z}\).

By induction, \(9|(10^{n+1}+3(10^n)+5), \forall n \ge 1\). \(\square\)

Example \(\PageIndex{6}\)

Show that \(1+2+3+\cdots + n=\frac{n(n+1)}{2}, \; \forall  n\in \mathbb{Z} \; n\ge 1,\).

Proof

Let \(n=1\).  Then \(1=\frac{1(1+1)}{2}\) which is true.

Assume \(1+2+3+\cdots + n=\frac{n(n+1)}{2}\) is true for some \(n=k\).

We will show that \(1+2+3+\cdots + n +(n+1)=\frac{(n+1)(n+1+1)}{2}\)

Consider \(1+2+3+\cdots +n+(n+1)=[1+2+3+\cdots+n]+(n+1)\).

        \(=\frac{n(n+1)}{2} +(n+1)\)

        \(=\frac{n(n+1)+2(n+1)}{2}\)

        \(=\frac{(n+1)(n+1+1)}{2}\).

By induction, \(1+2+3+\cdots + n=\frac{n(n+1)}{2}, \; \forall n\in \mathbb{Z} \; n\ge 1\).\(\square\)

Example \(\PageIndex{7}\)

 Prove that \(3\mid (10^{n+1}+10^n+1), \; \forall n\in \mathbb{Z} \; n\ge 1\).

Proof

Let \(n=1\).  Then \(3|(10^2+10+1)\) is true since \(111=3(37)\) and \(37 \in \mathbb{Z}\).

Assume that \(3|(10^{n+1}+10^n+1)\) for some \(n=k\).

We will show that \(10^{k+1+1}+10^{k+1}+1=3m, m\in \mathbb{Z}\).

Consider \(10^{k+1+1}+10^{k+1}+1=10(10^{k+1}+10^k+1)-9(1)\)

  \(=10(3m)-3(3)\)

  \(=3(10m-3)\) where \(10m-3 \in \mathbb{Z}\).

By induction, \(3|(10^{n+1}+10^n+1), \; \foralln\in \mathbb{Z}  \; n\ge 1\).\(\square\)

Bi-conditional statements 

Bi-conditional statements are conditional statements that depend on both component propositions. They read "\(p\) if and only if \(q\)" and are denoted \(p \leftrightarrow q\) or "p iff q", which is logically equivalent to \((p \to q) \wedge (q \to p)\).

Example \(\PageIndex{8}\)

Consider the statement: "Two lines are perpendicular if and only if they intersect to form a right angle."

The component propositions are:

1. \(p\): Two lines are perpendicular
2. \(q\): [The lines] intersect to form a right angle

Logically, if two lines are perpendicular, they must intersect at a right angle. Also, if two lines form a right angle, they are perpendicular.

If two lines are not perpendicular, then they cannot form a right angle. Conversely, if two lines do not form a right angle, they cannot be perpendicular. This is why, if both propositions in a biconditional statement are false, the statement itself is true!

Proof Do's and Don'ts

Do's:

1. Write the statement to be proved. It should be clear what you are proving.
2. Clearly mark the beginning of your proof with the word "Proof".
3. Make your proof self-contained. In particular, identify all variables used in your proof in the body of your proof.
4. Write the proof in complete English sentences.

Example \(\PageIndex{9}\): Acceptable

Proof: Let \(n\in \mathbb{Z}\). Assume \(n\) is an even integer. Then \(n=2k,\) for some \(k \in \mathbb{Z}\).

Example \(\PageIndex{10}\): Unacceptable

Proof: \(n\) is even \(\implies\) 2k.

5. Indicate what method of proof you are using. (The default assumption is that it is a direct proof).

6. Learn the definitions and how they come into play when proving various types of statements.

Don'ts:

1. Argue from examples. A general statement can't be proved true by showing it is true for special cases.
2. Use the same letter to mean two different things within a proof.

Example \(\PageIndex{11}\):

Proof: Let \(n\in \mathbb{Z}\). Assume \(n\) is even. Then \(n=2k,\) for some \(k \in \mathbb{Z}\). So \(n^2=4K^2=2(2k^2)\). Thus \(n^2=2k, k \in \mathbb{Z}\) is even. (The reader asks: does \(n=n^2?\)

3. Assume what you are trying to prove. This is also known as begging the question. You can do it inadvertently in the middle of a proof if you are not careful.