Mathematical topics and references


Logic and formal proof systems (a nice article about formal proof systems as well as the semantic side of logic. Sections 2 and 4, especially 4, are the most relevant to our class. The notation is a little different, but the basic ideas are the same)

"Basic Set Theory":
"Zermelo-Fraenkel Set Theory":

Proof by Induction (JRW)

  • Begin any induction proof by stating precisely, and prominently, the statement (“P(n)”) you plan to prove. A good idea is to put the statement in a display and label it (e.g., by an asterisk (∗) as above), so that it is easy to spot, and easy to reference.
  • Be sure to properly begin and end the induction step. From a logical point of view, an induction step is a proof of a statement of the form (∀k ∈ N)[P (k) ⇒ P (k + 1)]. To prove such a statement, you need to start out with the “∀k ∈ N” part (“Let k ∈ N be given”), then assume P(k) is true (“Suppose (∗) is true for n = k”), and, after a sequence of logical deductions, derive P (k + 1) (“Therefore (∗) is true for n = k + 1”).
  • Use different letters for the general variable appearing in the statement you seek to prove (n in the above example) and the variable used for the induction step (k in the above example). The reason for this distinction is that in the induction step you want to be able to say something like the following: “Let k ∈ N be given, and suppose (∗) is true for n = k. …. [Proof of induction step goes here] … Therefore (∗) is true for n = k + 1.” Without introducing a second variable k, such a statement wouldn’t make sense.
  • Always clearly state, at the appropriate place in the induction step, when the induction hypothesis is being used. E.g., say “By the induction hypothesis we have …”, or use a parenthetical note “(by induction hypothesis)” in a chain of equations as in the above example. The induction hypothesis is the case n = k of the statement we seek to prove (i.e., the statement “P (k)”) and it is what you assume at the start of the induction step. The place where this hypothesis is used is the most crucial step in an induction argument, and you must get this hypothesis into play at some point during the proof of the induction step.

Equivalence Relations (JRW)

Outline the forms for proving or disproving that a relation ≃ is reflexive, symmetric, or transitive.
Let ≃ be a relation on a set S.

Proving ≃ is reflexive.
To Prove: (∀a∈S) a≃a.
Form of Proof:

  • Let a be an arbitrary (variable) element of S.
  • Give an argument which concludes that a ≃ a.

Proving ≃ is not reflexive.
To Prove: (∃a∈S)a̸≃a.
Form of Proof:

  • Let a be a specific element of S.
  • Verify that a ̸≃ a.

Let ≃ be a relation on a set S.

Proving ≃ is symmetric.
To Prove: (∀a,b∈S)a≃b → b≃a.
Form of Proof:

  • Let a and b be arbitrary (variable) elements of S.
  • Assume that a ≃ b.
  • Expand if its helpful. (It usually is.)
  • Give an argument which concludes that b ≃ a.

Proving ≃ is not symmetric.
To Prove: (∃a,b∈S)(a≃b) ∧ (b̸≃a).
Form of Proof:

  • Let a and b be specific elements of S.
  • Verify that a ≃ b.
  • Verify that b ̸≃ a.

Let ≃ be a relation on a set S.

Proving ≃ is transitive.
To Prove: (∀a,b,c∈S)(a≃b) ∧ (b≃c) → (a≃c).
Form of Proof:

  • Let a, b and c be arbitrary (variable) elements of S.
  • Assume that a≃b and b≃c.
  • Expand if its helpful. (It usually is.)
  • Give an argument which concludes that a ≃ c.

Proving ≃ is not transitive.

To Prove: (∃a,b,c∈S)(a≃b) ∧ (b≃c) ∧ (a̸≃c).
Form of Proof:

  • Let a, b, and c be specific elements of S.
  • Verify that a ≃ b.
  • Verify that b ≃ c.
  • Verify that a ̸≃ c.

Proving Existence and Uniqueness (JRW)

General Case

Goals of Uniqueness:
To prove a goal of the form ∃!x P(x), i.e. that there is a
unique x that makes P(x) true, construct two separate proofs:

  • Existence: Prove ∃ x P(x).
  • Uniqueness: Prove ∀y ∀z ((P(y) ∧ P(z)) → y = z).

The form of the formal proof will have the form:

Existence. [Proof of ∃ x P(x) goes here.]
Uniqueness. [Proof of ∀y ∀z ((P(y) ∧ P(z)) → y = z) goes here.]

Givens of Uniqueness:

To use a given of the form ∃!x P(x), i.e. that there is a
unique x that makes P(x) true, use two separate givens

  • Existence: ∃ x P(x). Select an existential

instantiation x0 and assert P(x0).

  • Uniqueness: ∀y ∀z ((P(y) ∧ P(z)) → y = z).

If during the proof you can show P(y) and P(z) are both true, then
you can assert y = z.

Existence and Uniqueness of the Division Algorithm

Theorem (The Division Algorithm). Let n and m be natural numbers. Then there exist
integers q (for quotient) and r (for remainder) such that m = nq + r
and 0 ≤ r ≤ n − 1. Moreover, if q, q′ and r, r′ are any integers that satisfy m = nq+r

nq′+r′ with 0 ≤ r, r′ ≤ n − 1, then q=q′ and r=r′.

  • Prove the existence part of the Division Algorithm.

Proof. Let n and m be natural numbers. Consider the set S of all integer multiples of n
that are greater than (but not equal to) m. In set-builder notation this is S = {j ∈ Z |jn > m}.
Note that mn ≥ m·1=m for all m and n. This tells us that (m+1) n > m and there are integer multiples of n that are strictly greater than m. Hence, the set S is non-empty. Note too that S consists of integers greater than m, a natural number. So S is a non-empty set of Natural Numbers. We can apply the WOA to S to obtain a smallest (or least) element. Let’s call this element l.
Since l is in S, we have l·n>m. Because l−1< l and l is the least element of S, we must have (l − 1) · n ≤ m.

Now to be creative! We know that l·n overshoots m and that (l−1)·n is less than or equal to m. To show The Division Algorithm works, we need to find q and r.
Define q = l−1. Then q·n = (l−1)·n ≤ m. Now define r = m−q·n. This automatically gives us that m = n · q + r. What remains to be shown is that r has the necessary properties.
Is r nonnegative? Looking at how we define r and q, we know that m ≥ nq s or=m−nq≥0 and r is definitely nonnegative.
Is r less than n? Because l ∈ S we know m < nl. We also have r = m − nq < nl − nq = n(l−q). Remember that q = l−1, so l−q = l−(l−1) = 1. Putting these pieces together gives r < n(l − q) = n · 1 = n.
So 0 ≤ r < n. Because r and n are natural numbers, r < n implies that r must be less than or equal to n−1. So 0 ≤ r ≤ n−1. We have verified the existence of integers q and r satisfying all necessary properties.

  • Prove the uniqueness part of the Division Algorithm.

Proof. Let m and n be given as in the statement of the theorem and suppose that m = nq + r = nq′ + r′ for some integers q, q′, r, r′ satisfying the properties of The Division Algorithm.
If follows easily that nq − nq′ = r′ − r. Because r′ and r each satisfy The Division Algorithm, we must have 0 ≤ r < n and 0 ≤ r′ <n.

If r ̸= r′ then one has to be bigger, either r < r′ or r′ < r. (We are setting up a contradiction argument and will eventually show the assumption r < r′ or r′ < r leads to something crazy!) If r < r′ then 0 < r′ − r < n − r < n. But r′ − r = nq − nq′ = n(q − q′), so n|(r′ − r). To summarize, r′ − r is an integer greater than 0 and less than n that is divisible by n. This is impossible! An almost identical conclusion occurs if we assume r′ < r. We must have made some crazy assumption and the only one that we didn’t know for certain was r < r′ or r′ < r. These must be false and therefore we must have r = r′. So r=r′ and nq−nq′ =0. Because n(q−q′)=0 and n>0, we must have q−q′ =0. It then follows that q=q′ and r=r′.

Chinese Remainder Theorem (JRW)

The significance of the Chinese remainder theorem is that it often reduces a question about modulus mn, where (m, n) = 1, to the same question for modulus m and n separately. In this way, questions about modular arithmetic can often be reduced to the special case of prime power moduli. We will see how this works for several counting problems, often using two features of modular arithmetic with two moduli:

  • if d | m it makes sense to reduce integers mod m to integers mod d: if x ≡ y mod m then x ≡ y mod d. For example, if x ≡ y mod 10 then x ≡ y mod 5 since if x − y is divisible by 10 then it is also divisible by 5. (In contrast, it makes no sense to reduce x mod 10 to x mod 3, since there are congruent numbers mod 10 that are incongruent mod 3, such as 5 and 15.)
  • if x ≡ y mod m and x ≡ y mod n and (m,n) = 1 then x ≡ y mod mn. This was used in the uniqueness part of the proof of the Chinese remainder theorem.

Our first application is to counting units.

Theorem: For relatively prime positive integers m and n, φ(mn) = φ(m)φ(n).

Proof: We work with the sets

Um = {a mod m, (a,m) = 1}, Un ={b mod n, (b,n) = 1}, Umn = {c mod mn, (c,mn) = 1}.

Then | Um | = φ(m), | Un | = φ(n), and | Umn | = φ(mn). To show φ(mn) = φ(m)φ(n), we will write down a bijection between Umn and Um × Un, which implies the two sets have the same size, and that is what the theorem is saying (since |Um × Un| = φ(m)φ(n)).

Let f : Umn → Um × Un by the rule

f(c mod mn) = (c mod m,c mod n).

For c ∈ Umn, we have (c,mn) = 1, so (c,m) and (c,n) equal 1, so c mod m and c mod n are units. Let’s stop for a moment to take a look at an example of this function.
Take m = 3 and n = 5: U3 = {1,2}, U5 = {1,2,3,4}, and U15 = {1,2,4,7,8,11,13,14}. The following table shows the values of the function f on each number in U15. Notice that the values fill up all of U3 × U5 without repetition.

c mod 15 f(c mod 15)

1 (1,1)

2 (2,2)

4 (4, 4) = (1, 4)

7 (7, 7) = (1, 2)

8 (8, 8) = (2, 3)

11 (11, 11) = (2, 1)

13 (13, 13) = (1, 3)

14 (14, 14) = (2, 4)

There are 2 units modulo 3 and 4 units modulo 5, leading to 8 ordered pairs of units modulo 3 and units modulo 5: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), and (2,4). All these pairs show up (and just once) in the second column of the table.
We return to the general situation and show f: Umn → Um × Un is a bijection.
To see that f is one-to-one, suppose f(k mod m) = f(l mod n) Then k ≡ l mod m and k ≡ l mod n, so since (m,n) = 1 (aha!), we have k ≡ l mod mn. That means k = l in Umn, so f is one-to-one.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License