Module 2: Equivalent Statements & Proofs #

A (mathematical) theorem is a statement/sentence that describes a relationship/pattern between mathematical objects & structures.

A theorem will be a proposition (i.e., a statement that is either true or is false), and can then be written in a “Logical Form” using predicate calculus.

(* Generally a “theorem” is known to be true and has a “proof” as justification)

Examples: #

“$\sqrt{2}$ is irrational” L.F.: P (P is “$\sqrt{2}$ is irrational”)

“There are real numbers $x$ and $y$ such that $x+y = 10$.” L.F.: $(\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(P(x,y))$ ($P(x,y)$ is “$x+y = 10$”)

\medskip

“There are (two) whole numbers whose product is 15.” L.F.: $(\exists a \in \mathbb{W})(\exists b \in \mathbb{W})(P(a,b))$ ($P(a,b)$ is “$ab = 15$”)

\medskip

“Let $a$ be a real number. Either $a^2 > 0$ or $a = 0$.” L.F.: $(\forall a \in \mathbb{R})(P(a) \lor Q(a))$

$\begin{aligned} & P(a) \text{ is } “a^2 > 0” \ & Q(a) \text{ is } “a = 0” \end{aligned}$

\medskip

“Every natural number greater than or equal to 11 can be written in the form $2s + 5t$ for some natural numbers $s$ and $t$.” L.F.: $(\forall n \in \mathbb{N})(P(n) \implies (\exists s \in \mathbb{N})(\exists t \in \mathbb{N})(Q(n, s, t)))$

$\begin{aligned} & P(n) \text{ is } “n \geq 11” \ & Q(n, s, t) \text{ is } “2s + 5t = n” \end{aligned}$

Key improvements and explanations:

A proof is a logical justification/verification of the truth of a theorem.

Our proofs will be written in full (English) sentences with proper grammar and punctuation.

This means in paragraph form and not as a bulleted list. (Some “mathese”/math notation will (usually) appear.)

Our proofs will be stand-alone:

The reader should be able to begin reading at the start of the proof, not needing to know any prior information, and understand what is being proved.

Every proof must begin with: Proof:

Every proof must end with one of the following in the bottom right:

$\blacksquare, \square, \triangle, QED$

“Quod Erat Demonstrandum”

“General Structure/Outline: Proof: (Set-up/un-weaving” quantifiers) (Get to a point where you are needing to show/prove a “quatifier-free” statement) (Logical Reasoning/Definitions to show statement) (Re-weave quantifiers) (Conclude with original/full statement of theorem.

\begin{equation*} (\exists x \in \mathbb{R})(P(x)) \end{equation*}

\begin{equation*} \Big[(\exists x \in \mathbb{R})(P(x)) \land (\forall y \in \mathbb{R})(\forall z \in \mathbb{R})(P(y) \land P(z) \implies y = z)\Big] \end{equation*}

\begin{equation*} (\exists x \in \mathbb{R})(x^2 = -1) \end{equation*}

Let $x = i$. Note that \begin{equation*} x^2 = i^2 = -1 \end{equation*}

Hence, we have $x^2 = -1$. Thus, there exists a real number $x$ such that $x^2 = -1$.

[ ( \forall x \in \mathbb{Z}) (\exists y \in \mathbb{Z}) (x + y = 0)]

\text{Let } x \text{ be an arb. int. Let } y = -x. \text{ As }

$-x = (-1)(x) \text{ and } -1 \text{ and } x$ \text{ are int- and } \text{ the int. are closed under mult, } -x \text{ is an int,} \text{so } y \text{ is an int. Now:}

$x + y = x + (-x) = x - x = 0.$

\text{Hence, } x+y=0.

In a proof, the following are always allowed:

\begin{itemize} \item State an axiom/postulate (i.e., statements that are given to be true without needing additional justification)

For example: "Closure" Properties of \\(\mathbb{N}, \mathbb{W}, \mathbb{Z}, \mathbb{Q} \\) and \\(\mathbb{R}\\)

              "Lower Bound" Properties of \\(\mathbb{N}\\) and \\(\mathbb{W}\\)

\item State tautologies

For example (if U = Z): "Either x is odd or x is not odd" \\((P \vee \neg P)\\)

\item State any assumptions that you are making \end{itemize} \begin{itemize} \item “Assume that…” \item “Suppose that…” \end{itemize}

Note: Make sure you don’t assume what you want to show.

\begin{itemize} \item State something you wrote earlier in the proof (possibly in a different but equivalent way). \item Use algebraic manipulation to re-write equations/inequalities/expressions/etc… in equivalent ways. \item State a “previously proven result.” \item Use a definition to re-write a statement in an equivalent way. \item (A definition is a statement/predicate that gives a precise/unambiguous meaning to a concept/term.) \item Use “Modus Ponens” to make deductions. \end{itemize} \begin{itemize} \item If you have both A and (A $\implies$ B), then you may conclude/state you have B. \end{itemize}

When writing a proof of a theorem: \begin{itemize} \item Determine/write the logical form (in predicate calculus) of the theorem. \item This form should have no free-variables. If a quantifier is “hidden”/“isn’t clearly stated”, it is most likely the universal quantifier “$\forall$”. \end{itemize}

“Identifying Phrases”: \begin{itemize} \item “$\forall$”: Every, All, Each, Let $x$ be, … \item “$\exists$”: There is, There exists, For some, … \end{itemize}

Key Idea: “The structure of a proof of a theorem will follow the structure of the logical form or of an equivalent logical form of the theorem.”

To Show/Prove $(\forall x \in \mathcal{U}) (P(x))$: \begin{itemize} \item “Let $x$ in $\mathcal{U}$ be arbitrary.” or “Fix an arbitrary $x$ in $\mathcal{U}$.” \item Show/Prove $P(x)$. \end{itemize}

To Show/Prove $(\exists x \in \mathcal{U}) (P(x))$: \begin{itemize} \item Use scratch work to find a value of $x$ in $\mathcal{U}$ that makes $P(x)$ true. \item “Let $x = $ (the value you found in scratch work).” or “Define $x$ to be the value you found in scratch work).” \item Show/State that $x$ is in $\mathcal{U}$. \item Show/Prove $P(x)$ \end{itemize}

To Show/Prove $(A \Rightarrow B)$: \begin{itemize} \item “Assume A.” OR “Suppose A.” \item Show B. \end{itemize} Note: If we are assuming/supposing a statement, we take it as true and do not need to show/prove it. \begin{itemize} \item If we assume $(\forall x \in \mathbb{C})(P(x))$, then any $x$ in $U$ will make $P(x)$ true. \item If we assume $(\exists x \in \mathbb{C})(P(x))$, then we can let $\hat{x}$ be some element of $U$ that makes $P(x)$ true (we say $\hat{x}$ is a “witness”). \end{itemize}

Example Outline: $(\forall x \in \mathbb{R})(\forall y \in \mathbb{R}) (x < y \Rightarrow (\exists w \in \mathbb{R})(x < w < y))$

Proof: Let $x$ and $y$ be arbitrary real numbers. Suppose $x < y$.

Let $w = \dots$ (found in scratch work). Notice that $\dots$ so that $w$ is a real number.

Now, $\dots$

“Weaving” back to the full theorem. Hence, $x < w < y$.

Therefore, as $w$ is a real number, there exists a real number $w$ such that $x < w < y$. Hence, if $x < y$, then there exists a real number $w$ such that $x < w < y$. As $x$ and $y$ were arbitrary, for all real numbers $x$ and $y$, if $x < y$, then there is a real number $w$ such that $x < w < y$. $\square$

\noindent Example Outline: $(\exists x \in \omega) (\forall y \in \omega) (x \leq y)$

\noindent Proof: Let $x = \dots$ (Found in scratch work). Note that \dots, so we have that $x$ is a whole number. Let $y$ be an arbitrary whole number.

\noindent Now \dots :

\noindent Hence, $x \leq y$. As $y$ was arbitrary, for all whole numbers $y$, $x \leq y$.

\noindent As $x$ was a whole number, there exists a whole number $x$ such that for all whole numbers $y$, $x \leq y$ . $ \square$

\noindent Example Outline: $(\forall x \in \mathbb{Q}) (\exists y \in \mathbb{Q}) (x + y = 0)$

\noindent Proof: Let $x$ be an arbitrary rational number. Let $y = \dots$ (Found in scratch work and may “depend” on $x$). Note that \dots, so we have that $y$ is rational.

\noindent Now, \dots:

\noindent Hence, $x + y = 0$. As $y$ is a rational number, there exists a rational number $y$ such that $x + y = 0$. As $x$ was arbitrary, for all rational numbers $x$, there exists a rational number $y$ such that $x + y = 0$.$ \square$

“Divides” Definition & Notation (for integers / $\mathbb{Z}$)

Let $a$ and $b$ be integers.

We say “$a$ divides $b$” and we write $a|b$ exactly when there is an integer $k$ such that $b=ak$.

Logical Form: $a|b$ iff $(\exists k \in \mathbb{Z}) (b=ak)$

We say $b$ is even iff $2|b$ iff $(\exists k \in \mathbb{Z}) (b=2k)$

We say “$a$ does not divide $b$” and write $a\nmid b$ exactly when there is an integer $k$ and a natural number $r$ such that $r<a$ and such that $b=ak+r$. ($r$ is called the remainder.)

Logical form: $a\nmid b$ iff $(\exists k \in \mathbb{Z}) (\exists r \in \mathbb{N}) (r<a \wedge b=ak+r)$

Comment: We can “break” this up by either:

$(\exists k \in \mathbb{Z}) (b=ak+1 \vee b=ak+2 \vee \dots \vee b=ak+(a-1))$

$(\exists k \in \mathbb{Z}) (b=ak+1) \vee (\exists k \in \mathbb{Z}) (b=ak+2) \vee \dots \vee (\exists k \in \mathbb{Z}) (b=ak+(a-1))$

We say $b$ is odd iff $b$ is not even iff $2 \nmid b$ iff $(\exists k \in \mathbb{Z}) (b=2k+1)$

\textbf{Example:} We will prove the theorem “If $3|x$, then $3|x^{2}$”.

As we have a “hidden” quantifier, we will use the universal for $x$. (we cannot have a free variable in our logical form)
The “divides” notation indicates $x$ will be an integer. (Note: This notation could be used for subsets of $\mathbb{Z}$, such as $\mathbb{N}$ and $\mathbb{W}$, but without specification, it is assumed to be on integers)

\textbf{Logical Form:} $(\forall x \in \mathbb{Z}) (3|x \Rightarrow 3|x^{2})$

\textbf{Our Outline:} \textbf{Proof:} Let $x$ be an arbitrary integer. Assume that $3|x$. We need to fill this part in: $$\begin{cases} \textrm{Now,…}\ \textrm{Hence,} 3|x^2.\textrm{Thus, if}3|x, \textrm{then} 3|x^2. \textrm{As $x$ was arbitrary, for all integers x, if 3|x, then 3|x².} \end{cases}$$

\textbf{Strategy:} We have that $3|x$ and need to get to $3|x^2$. By using the definition of divides we can rewrite these in different but equivalent ways: $3|x$ iff there is some integer $k$ such that $x = 3k$

$3|x^2$ iff there is some integer $j$ such that $x^2=3j$

This means we need to get from $x = 3k$ to $x^2 = 3j$. Also, as we have assumed $3|x$, we know that there is an integer $k$ such that $x = 3k$. As $3|x^2$, we need to find an integer $j$ such that $x^2 = 3j.$

\begin{align*} &3/12 \longrightarrow 12=3\cdot k k=4 \ &3/13 \longrightarrow 13 = 3k + r \ & 13 = 3(4) + 1 \ & 3/17 \longrightarrow 17 = 3(5) + 2\ & 3/15 \longrightarrow 15 = 3k + 3 \quad \text{where } k=4 \ & “v = 3” k=4 \end{align*}

Now, as we have $x = 3k$ (for some integer $k$), we will use this to “examine” $x^2$:

$x^2 = (3k)^2 = 9k^2 = 3(3k^2)$

$ \uparrow \text{ This is the “j” we need. }$

If we set $j = 3k^2$, then we have $x^2 = 3j$. However: We need $j$ to be an integer.

Closure Properties: $\mathbb{Z}$ is closed under addition, subtraction, and multiplication. This means that if $a$ and $b$ are integers, $a + b$, $a - b$, and $ab$ are all also integers. ($\mathbb{Z}$ is not closed under division).

As $3$ is an integer and as $k$ is an integer, $3k^2$ is also an integer as the integers are closed under multiplication. (Hence, we do have that $j$ is an integer.)

We can now put the whole proof together:

Proof: Let $x$ be an arbitrary integer. Assume that $3 | x$. Now, there exists an integer $k$ such that $x = 3k$. Now: $x^2 = (3k)^2 = 9k^2 = 3(3k^2)$.

As $3$ and $k$ are integers and as the integers are closed under multiplication, $3k^2$ is an integer. Let $j = 3k^2$. Notice that $x^2 = 3j$ and that $j$ is an integer by our previous comments. Hence, $3 | x^2$. Thus, if $3 | x$, then $3 | x^2$. As $x$ was arbitrary, for all integers $x$, if $3 | x$, then $3 | x^2$.

In many cases, the “logical reasoning” portion of a proof / the part that needs to be filled in after forming the outline could be very difficult. In these cases it may be helpful to find an equivalent statement to prove instead of the original. (as equivalent statements are true exactly at the same time, if you have shown one, you have also shown the other.)

\textbf{Contraposition:}

Recall that ($A \Rightarrow B$) is equivalent to ($\neg B \Rightarrow \neg A$)

To Prove $A \Rightarrow B$ by contraposition:

Assume/suppose $\neg B$ (i.e., that B is false)
Show/prove $\neg A$ (i.e., that A is false)
Conclude “If $\neg B$, then $\neg A$.”
State that by contraposition, if $A$, then $B$.

Example: We will prove “If $x^2$ is even, then $x$ is even.”

Logical Form: $(\forall x \in \mathbb{Z}) (2 | x^2 \Rightarrow 2 | x)$

Initial Outline Attempt: Proof: Let $x$ be an arbitrary integer. Suppose $x^2$ is even.

Now,…

Hence $x$ is even. Thus, if $x^2$ is even, then $x$ is even.

As $x$ was arbitrary, for all integers $x$, if $x^2$ is even, then $x$ is even.

For this attempt, we have that $x^2 = 2k$ for some integer $k$ (such a value does exist as we assume $x^2$ is even). We need to show that there is an integer $j$ such that $x=2j$ (we’ll need to find this value).

If we had $x = 2j$, then we could use substitution to write $x^2 = (2j)^2$, but here we have $x^2 = 2k$ and we need to somehow get $x$ from this.

[ x = \frac{x^2}{x} = \frac{2k}{x} = 2\left(\frac{k}{x}\right) ]

$\frac{k}{x}$ need not be in $\mathbb{Z}$ as $\mathbb{Z}$ not closed under division, and don’t know that $x\neq 0$.

[ x = \pm \sqrt{x^2} = \pm \sqrt{2k} = \pm 2\sqrt{\frac{k}{2}} ]

$\sqrt{\frac{k}{2}}$ may not be in $\mathbb{Z}$ ($\mathbb{Z}$ not closed under division nor under square roots).

Instead, we can use contraposition:

$(\forall x\in \mathbb{Z})(2 \nmid x^2 \implies 2\nmid x)$ is equivalent to: $(\forall x \in \mathbb{Z})(2 \mid x \implies 2\mid x^2)$.

Outline: Proof: Let $x$ be an arbitrary integer. Suppose $x$ is not even. Now,…

Hence, $x^2$ is not even. Thus, if $x$ is not even, then $x^2$ is not even. By contraposition, if $x^2$ is even, then $x$ is even. As $x$ was arbitrary, for all integers $x$, if $x^2$ is even, then $x$ is even.

With this outline, our assumption is now that $x$ is not even (is odd), so we know that there is an integer $k$ such that $x = 2k+1$.

We need to show that $x^2$ is not even, i.e., that $x^2$ is odd, i.e., that there is some integer $j$ such that $x^2 = 2j+1$. (Goal: Find this integer $j$)

As $x = 2k+1$: $$ x^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 $$ $\uparrow$ substitution

This will be the $j$ that we need.

If $j = 2k^2 + 2k$, we have that $x^2 = 2j + 1$. We still need to confirm/show that $j$ is an integer. As both 2 and $k$ are integers, and as the integers are closed under multiplication and addition, $2k^2 + 2k$ is an integer, so that $j$ is an integer.

Putting this together:

Proof: Let $x$ be an arbitrary integer. Suppose $x$ is not even. Then $x$ is odd so that there is some integer $k$ such that $x=2k+1$. Now:

$$ x^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. $$

As 2 and $k$ are integers and as the integers are closed under multiplication and addition, $2k^2 + 2k$ is an integer. Let $j = 2k^2 + 2k$. Notice that $x^2 = 2j+1$ and that $j$ is an integer by our previous comments. Hence, $x^2$ is odd, and is therefore not even. Thus, if $x$ is not even, then $x^2$ is not even. By contraposition, if $x^2$ is even, then $x$ is even. As $x$ was arbitrary, for all integers $x$, if $x^2$ is even, then $x$ is even.

To Show/Prove ($A \land B$): \begin{itemize} \item Show/Prove A \item Show/Prove B \item Conclude ($A \land B$) \end{itemize}

To Show/Prove ($A \iff B$): We generally use the equivalence:

% ($A \iff B$) is equivalent to: (($A \implies B$) $\land$ ($B \implies A$))

% By this equivalence: % \begin{itemize} % \item Show ($A \implies B$): % \begin{itemize} % \item Assume $A$, then show/prove $B$. % \item Use contrapositive: ($\neg B \implies \neg A$). % \end{itemize}

% \item Show ($B \implies A$): % \begin{itemize} % \item Assume $B$, then show/prove $A$. % \item Use contrapositive: ($\neg A \implies \neg B$). % \end{itemize} % \end{itemize}

\section{Logical Equivalence}

To show or prove that $A \iff B$, we typically show both implications:

\begin{itemize}[noitemsep] \item Show ($A \implies B$): \begin{itemize} \item Assume $A$, then show or prove $B$. \item Or, use the contrapositive: $\neg B \implies \neg A$. \end{itemize}

\item Show (\\(B \implies A\\)):
\begin{itemize}
    \item Assume \\(B\\), then show or prove \\(A\\).
    \item Or, use the contrapositive: \\(\neg A \implies \neg B\\).
\end{itemize}

\end{itemize}

``We have shown both directions of the biconditional, hence A iff B.''

Note: There is another method, a ``biconditional proof’’, that is a string of equivalent statements: $A$ iff $A_1$ iff $A_2$ iff $A_3$ iff … iff $B$.

This method is not generally recommended initially as it is much easier to have an error.

Outline: Proof: (Set-up) \begin{itemize} \item ($\implies$) Suppose A. Now… Hence, B. Therefore, if A, then B. \item ($\impliedby$) Suppose B. Now… Hence, A. Therefore, if B, then A. \end{itemize} We have proven both directions of the biconditional, hence A iff B. $\Box$

\noindent Example: We will prove “$2|n \iff 2|n^2$”.

\noindent Logical Form: $(\forall n \in \mathbb{Z}) (2|n \iff 2|n^2)$

\noindent This is equivalent to: $(\forall n \in \mathbb{Z})((2|n \implies 2|n^2) \land (2|n^2 \implies 2|n))$

\noindent In our previous example, we used contraposition to show $(2|n^2 \implies 2|n)$, so we will do the same here, and we will use the following equivalent form.

\noindent $(\forall n \in \mathbb{Z}) ((2|n \implies 2|n^2) \land (2 \nmid n \implies 2 \nmid n^2))$

\noindent \textbf{Proof:} Let $n$ be an arbitrary integer.

\noindent $(\implies)$ Suppose $2|n$. Then $n = 2k$ for some integer $k$. Now:

\noindent $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$.

\noindent As 2 and $k$ are integers, and as the integers are closed under multiplication, $2k^2$ is an integer. Let $j = 2k^2$. Notice that $n^2 = 2j$ and that $j$ is an integer by our previous comments. Hence $2|n^2$. Thus, if $2|n$, then $2|n^2$.

\noindent $(\impliedby)$ Now, suppose $2 \nmid n$. Then, there is some integer $k$ such that $n = 2k + 1$. Now:

\noindent $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$.

\noindent As 2 and $k$ are integers and as the integers are closed under multiplication and addition, $2k^2 + 2k$ is an integer. Let $j = 2k^2 + 2k$. Notice that $n^2 = 2j + 1$ and that $j$ is an integer by our previous comments. Hence, $2 \nmid n^2$. Thus, if $2 \nmid n$, then $2 \nmid n^2$. By contraposition, if $2|n^2$, then $2|n$.

\noindent We have shown both directions of the biconditional, hence $2|n$ iff $2|n^2$. As $n$ was arbitrary, for all integers $n$, $2|n$ iff $2|n^2$.

Now, recall the equivalence:

$A$ is equivalent to ($\neg A \Rightarrow (B \land \neg B)$)

In many cases, if we are trying to prove/show a theorem A, it may be easier to prove the above equivalent statement.

This is called a \textit{proof by contradiction} (Notice that $(B \land \neg B)$ is a contradiction)

To Prove A by Contradiction: Assume $\neg A$, i.e., assume A is false.

Show/prove B
Show/prove $\neg B$ (i.e., that B is false)
“This is a contradiction, hence A (is true).”

Comments: This method is often used if the logical form is just “A” (without any logical connectives)

If A is more “complex” this method still can be used.

Suppose A is of the form $(X \Rightarrow Y)$:

$A$ is equiv. to: $(\neg A \Rightarrow (B \land \neg B))$

is equiv. to: $(\neg (X \Rightarrow Y) \Rightarrow (B \land \neg B))$

is equiv. to: $((X \land \neg Y) \Rightarrow (B \land \neg B))$

Here, to assume $\neg A$, we assume $X$ is true and $Y$ is false.

It may take some work/playing around to determine the “B” that will give you the contradiction.

Example: We will prove the theorem: ``$\sqrt{2}$ is irrational''

The logical form of this theorem is just: $P$

We will prove the equivalent: $(\neg P \implies (B \land \neg B))$

Initial Proof Outline:

Proof: Suppose $\sqrt{2}$ is not irrational. Then $\dots$

\dots

Hence, $B$ (which we still need to determine)

Thus, $\neg B$.

This is a contradiction. Therefore, $\sqrt{2}$ is irrational. $\square$

For this example, we will use the following:

Every rational number can be written in the form $\frac{p}{q}$ where $p$ and $q$ are integers (with $q \neq 0$) and $p$ and $q$ have no common factors greater than 1 (i.e., $\frac{p}{q}$ is in lowest terms).
``Our previous result’’: $(\forall n \in \mathbb{Z}) (2 \mid n^2 \iff 2 \mid n)$

1=3 \ % \searrow \ % B \

\text{Notice that }1\neq3 \text{. Thus, we have a contradiction} \ % fix this % \downarrow \ \neg B

\begin{align*} &\text{To Show/Prove } (A \lor B) \rightarrow \text{Much more complicated than } (A \land B) \ & n = 2k \implies n^2 = (2k)^2 = 4k^2 = 2(2k^2) \ & \neg A \implies (B \land \neg B) \ & \begin{array}{c|c} A & \ \hline 1 & 0 \ 0 & 1 \end{array} \end{align*}

((A \vee B) \Rightarrow C) \ ((A \Rightarrow C) \wedge (B \Rightarrow C))

\textbf{Proof:} Towards a contradiction, suppose that $\sqrt{2}$ is not irrational. Then, we have that $\sqrt{2}$ is rational, so that there exist integers $a$ and $b$, with $b \neq 0$, such that $$\sqrt{2} = \frac{a}{b}$$ and $a$ and $b$ have no common factors greater than 1. Now, as $\sqrt{2} = \frac{a}{b}$, we have that $b\sqrt{2} = a$, so that $(b\sqrt{2})^2 = a^2$, and $2b^2 = a^2$. As $b$ is an integer, and as the integers are closed under multiplication, $b^2$ is an integer. Hence, $2|a^2$. By our previous result, as $a$ is an integer and $2|a^2$, we have that $2|a$. Hence, there is some integer $k$ such that $a=2k$.

Now, as $2b^2 = a^2$ and $a=2k$, we have that $2b^2 = (2k)^2$ so that $2b^2 = 4k^2$, and $b^2 = 2k^2$. As $k$ is an integer, and as the integers are closed under multiplication, $k^2$ is an integer. Hence, $2|b^2$. Again, by our previous result, as $b$ is an integer and $2|b^2$, we have that $2|b$. Notice that we have that $2|a$ and $2|b$. Hence, $a$ and $b$ have a common factor, greater than 1 (namely 2). This is a contradiction; hence, we have that $\sqrt{2}$ is irrational.

$\blacksquare$

\textbf{Proof By Cases:}

Recall that we have the following equivalence: [ ((A \lor B) \Rightarrow C) \text{ is equivalent to } ((A \Rightarrow C) \land (B \Rightarrow C)) ]

Note: This can be extended: [ ((A \lor B \lor C) \Rightarrow D) \text{ is equivalent to } ((A \Rightarrow D) \land (B \Rightarrow D) \land (C \Rightarrow D)) ] [ ((A \lor B \lor C \lor D) \Rightarrow E) \text{ is equivalent to } ((A \Rightarrow E) \land (B \Rightarrow E) \land (C \Rightarrow E) \land (D \Rightarrow E)) ] etc…

For some theorems of the form $(A \Rightarrow B)$, we may be able to “break-up” the antecedent $A$ into “more precise” propositions connected by “$\lor$” (OR)

For example: \begin{itemize} \item (n is an integer) can be written: (n is even) $\lor$ (n is odd) \item (x is a real number) can be written: (x is a positive real number) $\lor$ (x = 0) $\lor$ (x is a negative real number) \end{itemize}

If we can rewrite $(A \Rightarrow B)$ as $((A_1 \lor A_2) \Rightarrow B)$, then we can prove the equivalent: $((A_1 \Rightarrow B) \land (A_2 \Rightarrow B))$: \begin{itemize} \item Prove/Show $A_1 \Rightarrow B$ \item Prove/Show $A_2 \Rightarrow B$ \end{itemize}

Comment: As $A_1$ & $A_2$ are more precise, when you are assuming them, you will have more information to work with.

Using these equivalencies is called a “Proof by Cases” Outline: If ($A \Rightarrow B$) can be written as (($A_1 \lor A_2 \lor A_3$) $\Rightarrow$ B) : Here we have three “cases”

Proof: Suppose A. We will consider (three) cases.

Case 1 ($A_1$): Suppose $A_1$. Then…. Hence, B.

Therefore, if $A_1$, then B.

Case 2 ($A_2$): Suppose $A_2$. Then…. Hence, B.

Therefore, if $A_2$, then B.

Case 3 ($A_3$): Suppose $A_3$. Then…. Hence, B.

Therefore, if $A_3$, then B.

These cases are exhaustive. Hence, B.

Therefore, if A then B.

$\boxtimes$

Comment: Recall we mentioned that ($\forall x \in \mathcal{U}$)(P(x)) is equivalent to

($\forall x \in \mathcal{U}$)($x \in \mathcal{U} \Rightarrow P(x)$).

If we can break-up $x \in \mathcal{U}$ into cases, we can use this method here as well.

Example: We will prove the theorem: $(\forall n \in \mathbb{Z}) (3 \nmid n \implies 3 \nmid n^2)$

Recall that we have $3 \nmid n$ is equivalent to/defined to be:

$\big( (\exists k \in \mathbb{Z}) (n = 3k + 1) \lor (\exists k \in \mathbb{Z}) (n = 3k + 2) \big)$

Case 1 \hskip2cm Case 2.

Proof: Let $n$ be an arbitrary integer. Suppose $3 \nmid n$. We will consider two cases.

Case 1 $((\exists k \in \mathbb{Z}) (n = 3k + 1))$: Suppose $n = 3k + 1$ for some integer $k$. Now:

$n^2 = (3k + 1)^2 = 9k^2 + 6k + 1 = 3 (3k^2 + 2k) + 1$.

As $2, 3$ and $k$ are integers and as the integers are closed under multiplication and addition, $3k^2 + 2k$ is an integer. Hence, $3 \nmid n^2$. Thus, if $n = 3k + 1$ for some integer $k$, then $3 \nmid n^2$.

Case 2 $((\exists k \in \mathbb{Z}) (n = 3k + 2))$: Suppose $n = 3k + 2$ for some integer $k$. Now:

$n^2 = (3k + 2)^2 = 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1 = 3 (3k^2 + 4k + 1) + 1$.

As $1, 3, 4$, and $k$ are integers and as the integers are closed under multiplication and addition, $3k^2 + 4k + 1$ is an integer. Hence, $3 \nmid n^2$. Thus, if $n = 3k + 2$ for some integer $k$, then $3 \nmid n^2$.

These cases are exhaustive. Hence, $3 \nmid n^2$. Therefore, if $3 \nmid n$, then $3 \nmid n^2$.

As $n$ was arbitrary, for all integers $n$, if $3 \nmid n$, then $3 \nmid n^2$.

\begin{align*} & 3(3k^{2}+4k)+4. \ & (n \in \mathbb{Z}) \begin{cases} 5\vert n \implies 5\vert n^{2} \implies 4 cases \ 13 \vert n \implies 13\vert n^{2} \implies 12 cases \end{cases} \ & R\begin{cases} \vert x \vert \begin{cases} x<0 \ x=0 \ x>0 \end{cases} \ x < 0 \ x \geq 0 \end{cases} \end{align*}

Assume X is false, B is true

get $\neg$B

$(\neg X \land B) \Rightarrow (\neg B \to X)$

\begin{array}{c|c|c|c|c|c|c} \neg & X & \land & B & \Rightarrow & (\neg & B \to X) \ \hline 1 & 0 & 1 & 1 & 1 & 0 & 0 \ 0 & 1 & 0 & 0 & 1 & 1 & 1\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \ 1 & 0 & 1 & 0 & 0 & 1 & 0 \end{array}

\begin{tabular}{ |l | l | } \hline $(A \Rightarrow B)$ & $(A \Rightarrow (B \Rightarrow C))$ \ Assume A & Assume A \ Show B & Show $(B \Rightarrow C)$ \ & Assume B \ & Show C \ \hline $(A \wedge B) \Rightarrow C$ & $(A \Rightarrow (B \wedge C))$ \ & Assume A \ & Show B \ & Show C \ \hline $(A \Rightarrow (B \vee C))$ equiv to: $\neg (B \vee C) \Rightarrow \neg A$ & $((A \Rightarrow B) \wedge (A \Rightarrow C))$ \ \hline \end{tabular}

\noindent \textbf{Equivalence:} $(A \Rightarrow (B \lor C))$ is equivalent to: $((A \land \neg B) \Rightarrow C)$

\noindent If we need to prove a statement of the form: $(A \Rightarrow (B \lor C))$

\noindent We often prove the above equivalent statement.

\noindent To prove/show $(A \Rightarrow (B \lor C))$ using this equivalence:

\begin{itemize} \item Assume/suppose both $A$ is true and $B$ is false (i.e., assume $A$ and $\neg B$) \item Show/Prove $C$ \item Conclude “Therefore, if $A$, then $B$ or $C$.” \end{itemize}

\noindent \textbf{Comments}: Showing a disjunction $(B \lor C)$ is difficult, so this equivalence avoids this.

\noindent We could also prove $(A \Rightarrow (B \lor C))$ by contraposition!

\noindent $(\neg (B \lor C) \Rightarrow \neg A)$

\noindent $((\neg B \land \neg C) \Rightarrow \neg A)$

\noindent Assume both $B$ and $C$ are false, then show/prove that $A$ must also be false.

\textbf{Example:} “Let $x$ be a real number. If $x^2 + 7x = 9x + 15$, then $x \leq 2$ or $\frac{x-4}{x-3} > 0$.”

\textbf{Logical Form:} $(\forall x \in \mathbb{R})(P(x) \Rightarrow (Q(x) \vee R(x)))$

\textbf{Equivalent Form:} $(\forall x \in \mathbb{R})((P(x) \wedge \neg Q(x)) \Rightarrow R(x))$

where $$ \begin{cases} P(x) : x^2 + 7x = 9x + 15 \ Q(x) : x \leq 2 \ R(x) : \frac{x-4}{x-3} > 0 \end{cases} $$ \textbf{Proof:} Let $x$ be an arbitrary real number. Suppose we have that $x^2 + 7x = 9x + 15$ and that $x \neq 2$. Then, we have that $x^2 - 2x - 15 = 0$ and that $x > 2$. As $x^2 - 2x - 15 = 0$, we have that $(x-5)(x+3) = 0$ so that either $x-5 = 0$ or that $x+3 = 0$. Then, we have $x=5$ or $x = -3$. As $x > 2$ and either $x = 5$ or $x=-3$, we must have that $x=5$. (If we had $x=-3$, we would have $x \nless 2$, which would contradict $x > 2$). Now: $$ \frac{x-4}{x-3} = \frac{5-4}{5-3} = \frac{1}{2} > 0. $$ Hence, $\frac{x-4}{x-3} > 0$. Therefore, we have that if $x^2 + 7x = 9x + 15$, then either $x \leq 2$ or $\frac{x-4}{x-3} > 0$. As $x$ was arbitrary, for any real number $x$, if $x^2 + 7x = 9x + 15$, then either $x \leq 2$ or $\frac{x-4}{x-3} > 0$.

\begin{align*} & \left(\exists_{new}\right) \left(n \leq 129^{(37^{100})}\right) \implies \text{False} \ \implies & \neg \left( \left(\forall_{new}\right) \left(n > 129^{(37^{100})}\right) \right) \ \implies & \left(\exists_{new}\right) \left(n \leq 129^{(37^{100})}\right) \implies \text{True} \ & \left(\exists_{new}\right) \left(n > 129^{(37^{100})}\right) \end{align*}

\noindent \textbf{Example:} For any integers $x$ and $y$, if 6 divides $xy$, then either 2 divides $x$ or 2 divides $y$.

\noindent \textbf{Logical Form:} $(\forall x \in \mathbb{Z})(\forall y \in \mathbb{Z}) (6|xy \Rightarrow (2|x \vee 2|y))$

\noindent \textbf{Equivalent Form:} $(\forall x \in \mathbb{Z})(\forall y \in \mathbb{Z})((6|xy \wedge 2 \nmid x) \Rightarrow 2|y)$

\noindent \textit{Assuming more & showing less}

\noindent \textbf{Proof:} Let $x$ and $y$ be arbitrary integers. Suppose that 6 divides $xy$ and that 2 does not divide $x$. Then, there are integers $k$ and $j$ such that $xy = 6k$ and $x = 2j + 1$. Now:

\begin{align*} xy &= 6k \ (2j + 1)y &= 6k \ 2jy + y &= 6k \ y &= 6k - 2jy \ y &= 2(3k - jy) \end{align*}

\noindent As 3, $k$, $j$ and $y$ are integers, and as the integers are closed under multiplication and subtraction, $3k - jy$ is an integer. Thus, 2 divides $y$.

\noindent Hence, if 6 divides $xy$, then either 2 divides $x$ or 2 divides $y$. As $x$ and $y$ were arbitrary, for any integers $x$ and $y$, if 6 divides $xy$, then either 2 divides $x$ or 2 divides $y$.

\noindent \textbf{Proving ($\forall x \in U$) (P(x)) is False by Counter Example:}

\noindent If we are proving a universal statement is false, then we are proving that the negation is true. Recall that: $\neg (\forall x \in U) (P(x))$ is equivalent to: $(\exists x \in U) (\neg P(x))$. This gives us the following outline:

\noindent \textbf{Proof:} Let $x$ = (found in scratch work). Now,… Hence we have $x$ is in U. Now:

\noindent Thus we have that P(x) is false. As $x$ is in U, it is not the case that every $x$ in U makes P(x) true.

\noindent \textbf{Example:} We will prove that $(\forall x \in w) (x^2 + x + 41 \text{ is prime})$ is false by counter example.

\noindent \textbf{Proof:} Let $x = 41$. Notice that $x$ is a whole number. Now:

\noindent $x^2 + x + 41 = 41^2 + 41 + 41 = 41(41 + 1 + 1) = 41(43)$.

\noindent As $x^2 + x + 41 = 41(43)$ and both $41$ and $43$ are integers greater than 1, we have that $x^2 + x + 41$ is a composite number, that is, $x^2 + x + 41$ is not prime.

\noindent As $x$ is a whole number, it is not the case that $x^2 + x + 41$ is prime for all whole numbers.

\noindent \textbf{Note:} In these proofs, the value of $x$ that we find is called a “counter example.”

\[ \]