Loading [MathJax]/jax/output/HTML-CSS/jax.js

Discrete Mathematics Study Center

Home Course Notes Exercises Mock Exam About

Methods of proof

How do we go about forming arguments (proofs)?

• Direct proofs: to prove an implication $p \rightarrow q$, start by assuming that $p$ is true, and then prove that $q$ is true under this assumption.
  • Prove that if $n$ is an odd integer, then $n^2$ is an odd integer.

    Assume that $n$ is an odd integer. Therefore, we can write $n=2k+1$ for some integer $k$. So $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$. This has form $2k'+1$ for an integer $k'$ and is therefore odd.

• Indirect proof: Recall that $p \rightarrow q \equiv \neg q \rightarrow \neg p$. Therefore, to prove $p \rightarrow q$, we could instead prove $\neg q \rightarrow \neg p$ using a direct proof: assume $\neg q$ and prove $\neg p$.
  • Prove that if $3n + 2$ is odd, then $n$ is odd.

    We instead prove that if $n$ is even, then $3n + 2$ is even. Assume $n$ is even; then $n = 2k$ for some integer $k$. So $3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$, which has the form $2k'$ for an integer $k'$ and is therefore even.

  • Prove that the sum of two rational numbers is rational.

    We will attempt to prove this directly: if $r$ and $s$ are rational numbers, then $r + s$ is a rational number. Assume that $r$ and $s$ are rational numbers. Then $r = a/b$ and $s = c/d$ where $a,b,c,d \in \mathbb{Z}$ and $b,d \neq 0$ by the definition of rational numbers. Now, $r + s = (ad + bc)/bd$. Since $a,b,c,d \in \mathbb{Z}$, $ad + bc$ and $bd$ are both integers. Since $b,d \neq 0$, we have $bd \neq 0$. Therefore, $r + s$ is rational. A direct proof succeeded!

  • Prove that if $n$ is an integer and $n^2$ is odd, then $n$ is odd.

    We will attempt to prove this directly. Assume $n$ is an integer and $n^2$ is odd. Then $n^2 = 2k + 1$ and so $n = \pm\sqrt{2k + 1}$. It is not obvious how to proceed at this point, so we will turn to an indirect proof. Assume $n$ is even. Then $n = 2k$, and so $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$. Therefore, $n^2$ is even. An indirect proof worked!

• Vacuous/trivial proofs: When trying to prove $p \rightarrow q$ and $p$ is false, then the statement follows automatically.
  • Let $P(n)$ denote "if $n>1$, then $n^2>n$". Prove $P(0)$.

    The statement is "if $0>1$, then $0^2 > 0$. But it is not the case that $0>1$, so the hypothesis is false and therefore the implication is true.

• Proof by contradiction: Suppose we want to prove the proposition $p$. If we can instead show that $\neg p \rightarrow F$ (that is, $\neg p$ leads to a contradiction), then $\neg p$ must be false. Thus, $p$ is true. Observe that if we want to prove $p \rightarrow q$ by contradiction, we assume $\neg(p \rightarrow q) \equiv \neg(\neg p \vee q) \equiv p \wedge \neg q$.
  • Prove that $\sqrt{2}$ is irrational.

    Instead, assume that $\sqrt{2}$ is \emph{rational} and try to derive a contradiction. If $\sqrt{2}$ is rational, then $\sqrt{2} = a/b$ for some integers $a,b$ with $b \neq 0$. We can further assume that $a$ and $b$ have no common factor, since if they do, we can divide through by this common factor to produce new values of $a$ and $b$.

    Now, since $\sqrt{2} = a/b$, we have $2 = a^2 / b^2$ and so $2b^2 = a^2$. Therefore, $a^2$ is even and so $a$ is even. Since $a$ is even, we have $a = 2c$ for some integer $c$. Now, substitute this value of $a$ into $2b^2 = a^2$ to get $2b^2 = (2c)^2 = 4c^2$. We now have that $b^2 = 2c^2$, so $b^2$ is even and thus $b$ is even. Therefore, both $a$ and $b$ are even, so they have a common factor of $2$. This contradicts the assumption that $a$ and $b$ have no common factor, and so our assumption that $\sqrt{2}$ is rational must be wrong. Therefore, $\sqrt{2}$ is irrational.

• Proof by cases: To prove a statement of the form $(p_1 \vee p_2 \vee p_3 \vee \cdots) \rightarrow q$, we can instead prove $(p_1 \rightarrow q) \wedge (p_2 \rightarrow q) \wedge (p_3 \rightarrow q) \wedge \cdots$, since it is logically equivalent to the original proposition.
  • Prove that if $x$ and $y$ are real numbers, then $|xy| = |x||y|$.

    We can consider the following cases:

    1. $x \ge 0$ and $y \ge 0$. Then $|xy| = xy = |x||y|$, and so the statement holds.
    2. $x \ge 0$ and $y \lt 0$. Then $|y| = -y \gt 0$, and so $|xy| = x(-y) = |x||y|$, and so the statement holds.
    3. $x \lt 0$ and $y \ge 0$. Then $|x| = -x \gt 0$, and so $|xy| = (-x)y = |x||y|$, and so the statement holds.
    4. $x \lt 0$ and $y \lt 0$. Then $|x| = -x \gt 0$ and $|y| = -y \gt 0$, and so $|xy| = (-x)(-y) = |x||y|$, and so the statement holds.

    Observe that these four cases cover all possible choices for $x$ and $y$. Since the statement holds in every case, the statement must be true for all real numbers.

• Equivalence proofs: To prove the biconditional $p \leftrightarrow q$, prove $(p \rightarrow q) \wedge (q \rightarrow p)$. The phrase "if and only if" indicates that an equivalence proof will be needed; a common error is to prove $p \rightarrow q$ but not $q \rightarrow p$.
  • Prove that $n$ is odd if and only if $n^2$ is odd.

    We must prove two things. First, we show that if $n$ is odd then $n^2$ is odd. We will do so directly: assume that $n$ is odd. Then $n = 2k + 1$ for some integer $k$. Thus, $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which has the form $2k' + 1$ and is thus odd.

    We now show that if $n^2$ is odd then $n$ is odd. We will do this indirectly: assume $n$ is even. Then $n = 2k$ for some integer $k$. Thus, $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$, which has the form $2k'$ and is thus even.

• Existence proofs: To prove that something exists, one must prove the proposition $\exists x\;{P(x)}$. Such proofs can be either constructive, where one finds an $a$ such that $P(a)$ is true, or non-constructive, where we prove $\exists x\;{P(x)}$ without finding an $a$ such that $P(a)$ is true.
  • Prove that there exists a positive integer that can be written as the sum of cubes in two different ways.

    We simply observe that $1729 = 10^3 + 9^3 = 12^3 + 1^3$. This is an example of a constructive existence proof because we have found an integer with the desired property.

  • Prove that there are two irrational number $x$ and $y$ such that $x^y$ is rational.

    We know that $\sqrt{2}$ is rational by a previous example. Consider $\sqrt{2}^{\sqrt{2}}$. It is not immediately obvious if this number is rational or irrational. If it is rational, then we have proved the statement correct by taking $x = y = \sqrt{2}$. If $\sqrt{2}^{\sqrt{2}}$ is irrational, then we are not yet done. Instead, take $x = \sqrt{2}^{\sqrt{2}}$ and $y = \sqrt{2}$. By our assumption, both of these numbers are irrational, but $x^y = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$, which is rational. We therefore know that either $x = y = \sqrt{2}$ or $x = \sqrt{2}^{\sqrt{2}}$ and $y = \sqrt{2}$ satisfy the requirements of the statement. This is an example of a non-constructive existence proof because we do not know which of these pairs has the desired property, only that one of them does.

• Uniqueness proofs: To prove that an object is unique, we must first prove that it exists. Suppose the object is $x$. To show it is unique, we then prove that if $y \neq x$, then $y$ does not have the property.
  • Prove that if $p$ is an integer, then there exists a unique integer $q$ such that $p + q = 0$.

    To show existence, we let $q = -p$ and observe that $p + q = p + (-p) = 0$. We must now show uniquess; we do so using contradiction. Suppose that $p + q = 0$ and $p + r = 0$ with $q \neq r$. Then $p + r = p + q$, and so $q = r$, which is a contradiction.

• Counterexamples: The previous proof methods showed how to prove that a statement is true. To prove a statement of the form $\forall x\;P(x)$ is false, we need only find one $a$ such that $P(a)$ is false. Such an $a$ is called a counterexample.
  • Show the statement "every positive integer is the sum of the squares of three integers" is false.

    We simply need to come up with an integer where this is not true. To do this, observe that it is clear that the three squares must be smaller than the number. Consider the integer $7$; the squares smaller than $7$ are $0$, $1$ and $4$. We can exhaustively try all combinations of three of these squares. It is not too difficult to see that no combination of three of these numbers add to $7$, since we have $4+1+1 = 6$ and $4 + 4 = 8$, and there is no way to add one or subtract one from either of these numbers. Therefore, $7$ is a counterexample.

  It is important to note that counterexamples have two components: first, one must come up with the counterexample $a$, and then one must prove that $P(a)$ is false.

Here are some more examples of proofs:

• If $x$ and $y$ are rational, then $x^y$ is rational.

  This is false. A counterexample is $x = 2/1$ and $y = 1/2$. Then $x^y = 2^{1/2} = \sqrt{2}$, which is irrational.

• If $x$ is an integer and $x^3 + 35$ is odd, then $x$ is even.

  We use an indirect proof and show that if $x$ is odd then $x^3 + 35$ is even. If $x$ is odd, then $x=2k+1$ for some integer $k$. Therefore, $x^3 = (2k+1)^3 = 8k^3 + 12k^2 + 6k + 1 = 2(4k^3 + 6k^2 + 3k) + 1$. Since $4k^3 + 6k^2 + 3k$ is an integer, $x^3$ must be odd. Since $35$ is also odd, and the sum of two odd numbers is even, we have that $x^3+35$ is even.

  We could instead use a proof by contradiction. Assume that the conclusion is false, so that $x$ is odd. Since $x$ is odd, $x^2$ must be odd since the product of two odd numbers is odd. This implies that $x^3$ is odd for the same reason. Since $35$ is also odd, and the sum of two odd numbers is even, we have that $x^3+35$ is even, which contradicts the premise that $x^3+35$ is odd. Therefore, $x$ must be even.

• If $x$ is rational, then $1/x$ is rational.

  This is an example where you must pay close attention to the universe of discourse (in this case, the rational numbers). Notice that $x=0$ is a rational number, but $1/x$ is not defined (and therefore not a rational number).

  If we restrict $x$ to non-zero rational numbers, then the statement is true: if $x$ is rational, then $x=a/b$ for some integers $a \neq 0$ and $b \neq 0$, and so $1/x = b/a$ which is a rational number.

• Between any two rational numbers, there is a rational number.

  Suppose we have two rational numbers $x$ and $y$. Assume that $x \lt y$ (if this is not the case, just switch $x$ and $y$). Since $x$ and $y$ are rational, we have $x = a/b$ and $y = c/d$ for some integers $a,b,c,d$. We need to show that there is a rational number $z$ such that $x \lt z \lt y$. Define $z$ to be: $$z = \frac{x+y}{2} = \frac{\frac{a}{b} + \frac{c}{d}}{2} = \frac{\frac{ad + bc}{bd}}{2} = \frac{ad + bc}{2bd}$$

  We have expressed $z$ as the ratio of two integers, so $z$ is rational. We still have to show that $z > x$ and $z \lt y$. (Recall we assumed that $x \lt y$.) Notice that $z = (x+y)/2 \gt (x+x)/2 = x$, so $z > x$. Similarly, $z = (x+y)/2 \lt (y+y)/2 = y$. Therefore, $x \lt z \lt y$.

• The real number equation $5x + 3 = a$ has a unique solution.

  We first prove that the solution exists: we can rearrange $5x+3=a$ to be $x = (a-3)/5$, which is a solution. To show it is unique, suppose we have two solutions $x$ and $y$. Then $5x+3=a$ and $5y+3=a$. Therefore, $5x+3=5y+3$. Subtracting $3$ from both sides gives $5x=5y$, and dividing both sides by $5$ gives $x=y$: this means that any other solution other than $x$ is equal to $x$, which is another way of saying that $x$ is the unique solution to the equation.