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” (LF) 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\)”)

“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\)”)

“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))\)
P(a) is \(“a^2 > 0”\)
Q(a) is “a = 0”

“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)))\)
P(n) is \(“n \geq 11” \)
Q(n, s, t) is \(“2s + 5t = n”\)

Proofs #

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.
\(\blacksquare, \square, \triangle, QED\) at the end.

Let x be an arbitrary integer Let y = -x. As \(-x = (-1)(x) \text{ and } -1 \text{ and } x\) are int, and the integers are closed under multiplication, -x is an int, so y is an int. Now: \(x + y = x + (-x) = x - x = 0.\) Hence x+y=0. QED.

In a proof, the following are always allowed:

• 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}\)

• State tautologies

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

• State any assumptions that you are making

  • “Assume that…”
  • “Suppose that…"
    Note: Make sure you don’t assume what you want to show.

• State something you wrote earlier in the proof (possibly in a different but equivalent way).

• Use algebraic manipulation to re-write equations/inequalities/expressions/etc… in equivalent ways.

• State a “previously proven result.”

• Use a definition to re-write a statement in an equivalent way.

  • (A definition is a statement/predicate that gives a precise/unambiguous meaning to a concept/term.)

• Use “Modus Ponens” to make deductions.

  • If you have both A and (A \(\implies\) B), then you may conclude/state you have B.

When writing a proof of a theorem:

• Determine/write the logical form (in predicate calculus) of the theorem.
• This form should have no free-variables. If a quantifier is “hidden”/“isn’t clearly stated”, it is most likely the universal quantifier “\(\forall\)”.

“Identifying Phrases”:

• “\(\forall\)”: Every, All, Each, Let \(x\) be, …
• “\(\exists\)”: There is, There exists, For some, …

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))\):

• “Let \(x\) in \(\mathcal{U}\) be arbitrary.” or “Fix an arbitrary \(x\) in \(\mathcal{U}\).”
• Show/Prove \(P(x)\).

To Show/Prove \((\exists x \in \mathcal{U}) (P(x))\):

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

To Show/Prove \((A \Rightarrow B)\):

• “Assume A.” OR “Suppose A.”
• Show B.

Note: If we are assuming/supposing a statement, we take it as true and do not need to show/prove it.

• If we assume \((\forall x \in \mathbb{U})(P(x))\), then any \(x\) in \(U\) will make \(P(x)\) true.
• If we assume \((\exists x \in \mathbb{U})(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”).

Example Outline: \((\forall x \in \mathbb{R})(\forall y \in \mathbb{R}) (x < y \Rightarrow (\exists w \in \mathbb{R})(x < w < 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\), there exists a real number \(w\) such that \(x < w < y\). \(\square\)

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

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.

Now \(\dots\):

Hence, \(x \leq y\). As \(y\) was arbitrary, for all whole numbers \(y\), \(x \leq y\).

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

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

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.

Now, \(\dots\):

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}\))

Divisibility is a classical problem in number theory and in general.

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)\)

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)

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

Our Outline: Proof: Let \(x\) be an arbitrary integer. Assume that \(3|x\).

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\).
For \(3|x^2\), we need to find an integer \(j\) such that \(x^2 = 3j.\)

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\). QED.

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.)

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. QED.

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.

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

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

Essentially, we can’t guarentee the set inclusion and proving that the square root is in the integers is too much trouble.

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. QED.

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\):

\((2k^2 + 2k)\) 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:

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. QED.

To Show/Prove (\(A \land B\)):

• Show/Prove A
• Show/Prove B
• Conclude (\(A \land B\))

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:

• Show (\(A \implies B\)):

  • Assume \(A\), then show/prove \(B\).
  • Use contrapositive: (\(\neg B \implies \neg A\)).

• Show (\(B \implies A\)):

  • Assume \(B\), then show/prove \(A\).
  • Use contrapositive: (\(\neg A \implies \neg B\)).

• “We have shown both directions of the biconditional, hence A iff B.”

To show or prove that \(A \iff B\), we typically show both implications: 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)

• (\(\implies\)) Suppose A. Now… Hence, B. Therefore, if A, then B.
• (\(\impliedby\)) Suppose B. Now… Hence, A. Therefore, if B, then A.

We have proven both directions of the biconditional, hence A iff B. \(\Box\)

Example: We will prove “\(2|n \iff 2|n^2\)”.

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

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

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.

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

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

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

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\).

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

\(n^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 \(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\).

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\). QED

Contradiction #

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 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\)
\(\vdots\)

Hence, \(B\) (which we still need to determine)
\(\vdots\)

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)\)

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

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\)

Proof By Cases: #

Recall that we have the following equivalence:

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:

• (n is an integer) can be written: (n is even) \(\lor\) (n is odd)
• (x is a real number) can be written: (x is a positive real number) \(\lor\) (x = 0) \(\lor\) (x is a negative real number)

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))\):

• Prove/Show \(A_1 \Rightarrow B\)
• Prove/Show \(A_2 \Rightarrow B\)

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 or Case 2 respectively.

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\). QED.

Equivalence: \((A \Rightarrow (B \lor C))\) is equivalent to: \(((A \land \neg B) \Rightarrow C)\)

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

We often prove the above equivalent statement.

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

• Assume/suppose both \(A\) is true and \(B\) is false (i.e., assume \(A\) and \(\neg B\))
• Show/Prove \(C\)
• Conclude “Therefore, if \(A\), then \(B\) or \(C\).”

Comments: Showing a disjunction \((B \lor C)\) is difficult, so this equivalence avoids this.

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

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

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

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

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

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

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

where

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:

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\). QED.

Review :

We’re going to use a negation to show how the negation changes the statement. \[ \begin{aligned} & \left(\forall n \in \omega \right) \left(n \leq 129^{(37^{100})}\right) \leftarrow \text{False} \\ & \neg \left( \left(\exists n \in \omega\right) \left(n > 129^{(37^{100})}\right) \right) \leftarrow \text{Same and still False}\\ & \left(\exists n \in \omega \right) \left(n \leq 129^{(37^{100})}\right) \leftarrow \text{True} \\ & \left(\exists n \in \omega \right) \left(n > 129^{(37^{100})}\right) \leftarrow \text{Same and still True} \end{aligned} \]

Example: For any integers \(x\) and \(y\), if 6 divides \(xy\), then either 2 divides \(x\) or 2 divides \(y\).

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

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

Assuming more & showing less

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:

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\).

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\). QED.

Proving (\(\forall x \in U\)) (P(x)) is False by Counter Example:

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:

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

Now: …

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. QED.

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

Proof: Let \(x = 41\). Notice that \(x\) is a whole number. Now:

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

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.

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

Note: In these proofs, the value of \(x\) that we find is called a “counter example.”

Cool Proof #

Another cool “proof” of irrationality of square roots of primes in general.
Proof: Let n be a prime integer. Toward contradiction, suppose that \(\sqrt{n}\) is rational. Then, we have that \(\sqrt{n}\) is rational, so that there exist integers \(a\) and \(b\), with \(b \neq 0\), such that \(\sqrt{n} = \frac{a}{b}\) and a and b have no common factors greater than 1 (i.e., \(\frac{a}{b}\) is in lowest terms). Now, as \(\sqrt{n} = \frac{a}{b}\), we have that \(b\sqrt{n} = a\), so that \((b\sqrt{n})^2 = a^2\), and \(nb^2 = a^2\). That is, \(nb^2\) is a perfect square. Using the factorization of \(nb^2\), we see that \(n\) is a perfect square. As a perfect square greater than 1 cannot be prime, we have a contradiction. Hence, \(\sqrt{n}\) is irrational. \(\blacksquare\)