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.
https://www.youtube.com/watch?v=Ao43b4N1C48
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.
https://www.youtube.com/watch?v=yOYt2yejn6U
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
Proof of Existence and Uniqueness (JRW)
(The universe is ℝ R.) There is a unique function f(x) f(x)
such that f′(x)=2x f′(x)=2x and f(0)=3 f(0)=3.
Proof.
Existence: f(x)=x2+3 works.
Uniqueness: If f0(x) f0(x) and f1(x) f1(x) both satisfy these conditions, then f′0(x) = 2x = f′1(x) f0′(x) = 2x = f1′(x), so they differ by a constant, i.e., there is a C such that f0(x)= f1(x)+C f0(x)=f1(x)+C. Hence, 3= f0(0) = f1(0)+C = 3+C 3 = f0(0)= f1(0) + C = 3 + C. This gives C=0 and so f0(x) = f1(x)f0(x) = f1(x).
Sometimes we can do both parts of an existence and uniqueness argument at the same time. This is usually accomplished by proving ∀x(P(x)⇔x=x0)∀x(P(x)⇔x=x0), where x0x0 is some particular value.
https://www.whitman.edu/mathematics/higher_math_online/section02.05.html
https://www.youtube.com/watch?v=vVBzzzwpeSQ
Application of the Chinese Remainder Theorem (JRW)
Find all integers x which leave a remainder of 1, 2, 3, and 4 when divided by 5, 7, 9, and 11 respectively.
We are asked to solve the system of congruences:
x ≡ 1 (mod5)
x ≡ 2 (mod7)
x ≡ 3 (mod9)
x ≡ 4 (mod 11)
Notice that the moduli are pairwise relatively prime, as required by the theorem. We have M = 5·7·9·11 = 3465 and M1 = M/5 = 693, M2 = M/7 = 495, M3 = M/9 = 385, and M4 = M/11= 315. A small calculation gives y1 = 2, y2 = 3,y3 = 4, and y4 = 8. Hence x=1·693·2+ 2·495·3+3·385·4+4·315·8 = 19056. So x = [19056]M = [1731]M. In fact, 1731 is the smallest positive integer solution. The full solution is x ≡ 1731 (mod M). The inverses can all (in this case) be guessed mentally. Notice carefully how we do not actually need to work with the large numbers Mk for k = 1, 2, 3, 4 in order to find the desired inverses.
http://gauss.math.luc.edu/greicius/Math201/Fall2012/Lectures/ChineseRemainderThm.article.pdf
Extra Point Opportunity from Class
1. Let 𝛼 be in F, p(x) be in F[x]. Show that (x - 𝛼) divides p(x) if and only if 𝛼 is a root of p(x).
Assume (x - 𝛼) divides p(x)
Then, p(x) = (x - 𝛼) * q(x)
p(𝛼) = (𝛼 - 𝛼) * q(x)
p(𝛼) = 0 * q(x)
p(𝛼) = 0
Assume 𝛼 is a root of p(x)
p(𝛼) = 0
p(x) = (x - 𝛼) * q(x) + r
r = 0 if and only if (x - 𝛼) * p(x)
if (x - 𝛼) | p(x), then p(𝛼) = 0 + r = 0
r = 0