Validating Statements and Methods of Proof

1. What is a Proof?

A mathematical proof is a logical argument that demonstrates a statement is true. It is a sequence of statements, each one logically following from the previous ones, starting from a set of axioms (assumed truths) and definitions.

2. Validating Statements

To validate a statement of the form $p \implies q$, we need to show that whenever $p$ is true, $q$ must also be true. There are several standard methods to do this.

A. Direct Proof

In a direct proof, we assume that the hypothesis $p$ is true and use logical deductions, definitions, and previously known facts to show that the conclusion $q$ must also be true.

• Structure: Assume $p$ is true $\implies$ …logical steps… $\implies$ Show $q$ is true.
• Example: Prove that if $n$ is an odd integer, then $n^2$ is an odd integer.

1. Assume $p$ is true: Let $n$ be an odd integer.
2. Use definition: By definition, $n = 2k+1$ for some integer $k$.
3. Logical deduction: $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$.
4. Show $q$ is true: Since $2k^2+2k$ is an integer, $n^2$ is of the form $2m+1$ (where $m=2k^2+2k$). Therefore, $n^2$ is an odd integer.

B. Proof by Contrapositive

This method relies on the fact that an implication $p \implies q$ is logically equivalent to its contrapositive, $\sim q \implies \sim p$. So, to prove $p \implies q$, we can instead prove its contrapositive.

• Structure: Assume $\sim q$ is true $\implies$ …logical steps… $\implies$ Show $\sim p$ is true.
• Example: Prove that if $n^2$ is an even integer, then $n$ is an even integer.

1. Identify Contrapositive: The contrapositive is "If $n$ is not an even integer (i.e., $n$ is odd), then $n^2$ is not an even integer (i.e., $n^2$ is odd)."
2. Prove the contrapositive: This is exactly what we proved in the direct proof example. Since the contrapositive is true, the original statement must also be true.

C. Proof by Contradiction (Reductio ad absurdum)

In this method, we assume that the statement we want to prove is false and then show that this assumption leads to a logical contradiction.

• Structure: Assume the statement is false (i.e., assume $p$ and $\sim q$ are true) $\implies$ …logical steps… $\implies$ Arrive at a contradiction (e.g., $R \land \sim R$).
• Example: Prove that $\sqrt{2}$ is an irrational number.

1. Assume the opposite: Assume $\sqrt{2}$ is a rational number.
2. Use definition: Then $\sqrt{2} = a/b$ where $a$ and $b$ are integers with no common factors and $b \neq 0$.
3. Logical deduction: $2 = a^2/b^2 \implies a^2 = 2b^2$. This means $a^2$ is even, so $a$ must also be even. Thus $a=2k$ for some integer $k$.
4. Substitute back: $(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$. This means $b^2$ is even, so $b$ must also be even.
5. Find the contradiction: If both $a$ and $b$ are even, they have a common factor of 2. This contradicts our initial assumption that $a$ and $b$ have no common factors. Therefore, our assumption that $\sqrt{2}$ is rational must be false.

D. Proof by Counterexample

To prove that a universally quantified statement ($\forall x, P(x)$) is false, we only need to find a single instance where it is not true. This single instance is called a counterexample.

• Example: Disprove the statement "All prime numbers are odd."
• Counterexample: The number 2 is a prime number, but it is not odd. Therefore, the statement is false.