Examples

Examples of proofs we have discussed in lecture

The “Domino Effect” (JRW)

Step 1. The first domino falls. (Show it is true for n=1)
Step 2. When any domino falls, the next domino falls. (Show that if n=k is true then n=k+1 is also true)

So all dominos will fall. This is how Mathematical Induction works.

There Is No Horse of a Different Color (JRW)

All horses have the same color.
Proof. The theorem clearly holds in the case where n = 1; after all, there is only one horse. We would, of course, consider whatever markings one horse has to be its “color”. Suppose the theorem holds for some positive integer k, that is, suppose that for some positive integer k, all the horses in every set of k horses have the same color. Consider a set of k + 1 horses and assign each one a number from 1 to k + 1. If we set aside the (k + 1)st horse, the remaining k horses (numbered 1 through k) all have the same color, by the inductive hypothesis. Similarly, if we set aside the 1st horse, the remaining k horses (numbered 2 through k + 1) all have the same color, again by the inductive hypothesis. Thus, the 1st and (k + 1)st horses have the same color: the color of the remaining k − 1 horses. It immediately follows that all k + 1 horses have the same color. By the principle of mathematical induction, for every positive integer n, all the horses in a set of n horses have the same color. This is just a formal way of saying that all horses have the same color.

James Lynch In-Class Notes Make-up for #15, 17

17. (Preliminary for Th, Feb 22; finalized Sat, March 3) Prove that for all sets x,y, it is impossible for both x∈y and y∈x to hold.

We prove by contradiction. Suppose there exists a set z such that z={x,y} and both x∈y and y∈x hold. It follows that y∈x\$\cap\$z and x∈y\$\cap\$z. Since z is not disjoint with either of its elements x,y, foundation is violated.

15. (Preliminary for Th, Feb 22; finalized Sat, March 3) a. Prove that for all x,y∈ℕ, if x<y, then either Succ(x)<y or Succ(x)=y. (We say that Succ(x) is an immediate successor of x.)) Hint: Use induction on y.

We induct on y. The statement is vacuously true for y=0. Assume p(k). For k>0, if y=k and x<y, then either succ(x)=y or succ(x)<y. Let y=k+1 and let it remain that x<y. Either x<k+1 or x=k+1. If x<k then by transitivity either succ(x)<k<y or succ(x)=k<y. If x=k then succ(x)=succ(k)=k+1=y. In either case, succ(x)<y or succ(x)=y.

b. Prove that (ℕ,<) satisfies trichotomy: For all x,y∈ℕ, exactly one of the following holds: x<y,x=y, or y<x. Hint: Again use induction on one of the variables. Apply the lemma in part a. at an appropriate point.

To show uniqueness, by the definition of <, three cases exist: x∈y, x=y, or y∈x. We induct on y. Let y=1. We must show that \$\forall\$x(x<y \$\vee\$ x=y), or y<x to show disjunction. We may begin with y=0 because this implies \$\emptyset\$. We use the lemma 0<succ(x) \$\forall\$x∈ℕ to show that if y<1 and y\$\nless\$x then x=1. This implies that x=y. The base case thus holds. Assume p(k): if x<y, then either x=y or x<y \$\forall\$x∈ℕ. Assume that trichotomy holds for all k. We will then show that trichotomy holds for succ(k). We must thus show that x<succ(k), x=succ(k), or x>succ(k). By the inductive hypothesis, x<k, x=k, or k<x. By transitivity, if x<k then x<succ(k). If x>k then by the lemma in 15(a) x>succ(k) or x=succ(k). Thus, p(k+1) holds true.

Trichotomy and Axiom of Choice (JRW)

Prove that the Law of Trichotomy is equivalent to the Axiom of Choice.
Proof: We know that the Axiom of Choice is equivalent to the statement that every infinite cardinal is an aleph. Therefore we need to reduce the Law of Trichotomy to the statement that every infinite cardinal is an aleph.
We want to prove the following theorem using Corollary 4.2.
Corollary 4.2 ensures that any two alephs are comparable which implies that any two cardinals are comparable. Trichotomy is the statement that any two cardinals are comparable. Now we can assume Trichotomy and consider any infinite cardinal m. By Theorem 4.1, א(m) m. By Trichotomy, א(m) > m. This inequality implies that m is strictly less than some aleph and is therefore an aleph. Therefore, all infinite cardinals are alephs. Since the Axiom of Choice and the Well Ordering Theorem are equivalent and the Well Ordering Theorem is equivalent to the statement that every infinite cardinal is an aleph, the Axiom of Choice is equivalent to Trichotomy.

https://sites.math.washington.edu/~morrow/336_12/papers/martha.pdf

Equivalence Relations and Partitions (JRW)

Proposition: Define a relation on Z by x ∼ y if and only if x + 2y is divisible by 3.

Proof:
2 ∼ 11, since 2 + 2 · 11 = 24, and 24 is divisible by 3.
7 ∼ −8, since 7 + 2 · (−8) = −9, and −9 is divisible by 3.
However, 6 ̸∼ 14, since 6 + 2 · 14 = 34, and 34 is not divisible by 3.
If x is an integer, x + 2x = 3x is divisible by 3. Therefore, x∼x for all x ∈ Z, and ∼ is reflexive. Suppose x and y are integers. If x ∼ y, then x + 2y is divisible by 3. Say x + 2y = 3n, where n ∈ Z.

Now,

y + 2x = (3x + 3y) − (x + 2y)

= (3x + 3y) − 3n

= 3(x + y − n)

Therefore, y + 2x is divisible by 3, so y ∼ x. Hence, ∼ is symmetric.

http://sites.millersville.edu/bikenaga/math-proof/equivalence-relations/equivalence-relations.pdf

page revision: 12, last edited: 20 Mar 2018 23:37