Logic, Sets and Proofs: How Mathematicians Think

Part 1 was mostly about getting answers: fractions, algebra, calculus, matrices. University mathematics asks a different question. Not "what is the answer?" but "how do you know it is true for every case, and not only the ones you tried?"

That needs a small amount of vocabulary (logic, sets, functions) and four proof methods. This post covers both. Everything later in the series, linear algebra, analysis and abstract algebra, is written in this language.

How to use this post

The layout is the same as part 1: the idea, how to do it, worked examples, the usual mistake, then practice. Proofs are learned by writing them, so work every example on paper before reading the steps, and attempt every practice question before opening the answer.

1. Statements and logic

A statement is a sentence that is either true or false. "7 is prime" is a statement. "Close the door" and "what time is it?" are not. A sentence with a variable, such as "x > 3", becomes a statement once you choose x.

The pieces

1. and: true only when both parts are true.
2. or: true when at least one part is true. Mathematicians use the inclusive "or", so "2 is even or 2 is prime" is true.
3. not: flips true and false.
4. if P then Q, written P ⇒ Q: the one that causes trouble. It is false in exactly one case: P true and Q false.

Think of it as a promise. "If you pass, I will buy you lunch" is broken only if you pass and I do not buy lunch. If you fail, the promise says nothing, so it cannot be broken. That is why a false P makes the whole statement true. Mathematicians call this "vacuously true".

Three relatives of "if P then Q"

1. The converse swaps the parts: if Q then P. It is not equivalent.
2. The contrapositive swaps and negates: if not Q then not P. It is equivalent.
3. The negation is "P and not Q". To show an "if" statement is false, find one case where P holds and Q fails. That case is a counterexample.

Example 1: "If n is divisible by 4, then n is even."

• True. Anything divisible by 4 is 2 times something.
• Converse: "If n is even, then n is divisible by 4." False. Take n = 2.
• Contrapositive: "If n is odd, then n is not divisible by 4." True, and it says the same as the original.

Quantifiers. ∀ means "for all" and ∃ means "there exists". To negate a statement that starts with one, swap the quantifier and negate the rest.

Example 2: negate "every prime number is odd".

• Swap "every" for "some" and negate the rest: "some prime number is not odd".
• That is true: 2 is the counterexample.

The usual mistake: treating the converse as if it were the original. "If it rains the ground is wet" does not give "if the ground is wet it rained". A sprinkler also does it.

2. Sets

A set is a collection of distinct things. Order does not matter and repeats do not count, so {1, 2, 2, 3} and {3, 1, 2} are the same set.

The notation

1. x ∈ A means x is an element of A. x ∉ A means it is not.
2. A ⊆ B means every element of A is also in B (A is a subset of B).
3. ∅ is the empty set, with no elements. It is a subset of every set.
4. A ∪ B (union) is everything in A or B or both. A ∩ B (intersection) is everything in both.
5. A \ B (difference) is everything in A that is not in B.
6. The size of A, written |A|, is the number of elements.
7. Set-builder notation describes a set by a rule: {x ∈ ℤ : x is even} reads "the integers x such that x is even".

Example 1: A = {1, 2, 3, 4} and B = {3, 4, 5}

• A ∪ B = {1, 2, 3, 4, 5}.
• A ∩ B = {3, 4}.
• A \ B = {1, 2}.
• Size check: |A ∪ B| = |A| + |B| − |A ∩ B| = 4 + 3 − 2 = 5. Adding the sizes counts the shared elements twice, so subtract them once.

Example 2: a class of 30. 18 play football, 12 play chess, 5 play both. How many play neither?

1. Players of at least one sport: 18 + 12 − 5 = 25.
2. Neither: 30 − 25 = 5.

Example 3: how many subsets does {a, b, c} have?

• For each element, choose in or out: 2 × 2 × 2 = 8.
• They are ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c} and {a, b, c}.
• In general a set with n elements has 2ⁿ subsets.

The usual mistake: mixing up ∈ and ⊆. The number 2 is in {1, 2, 3}, so 2 ∈ {1, 2, 3}. The set {2} is a subset of it, so {2} ⊆ {1, 2, 3}. Also, ∅ (nothing) and {∅} (a set holding one thing, the empty set) are different.

3. Functions, stated carefully

A function f from a set X to a set Y gives each input in X exactly one output in Y. X is the domain and Y is the codomain. The range is the set of outputs actually reached, which can be smaller than the codomain.

Two properties decide whether a function can be undone:

1. Injective (one-to-one): different inputs always give different outputs.
2. Surjective (onto): every element of the codomain is hit by some input.
3. Bijective: both. Each output comes from exactly one input, so the function has an inverse.

Example 1: f(x) = x² from the reals to the reals.

• Not injective: f(2) = f(−2) = 4.
• Not surjective: no real x gives −1.
• On the graph from part 1, a horizontal line hits it twice (not injective) or not at all (not surjective).

Example 2: f(x) = 2x + 1 from the integers to the integers.

• Injective: if 2a + 1 = 2b + 1 then a = b.
• Not surjective: the output is always odd, so 4 is never hit.

Example 3: f(x) = x³ from the reals to the reals.

• Injective and surjective, so bijective. The inverse is the cube root.

The usual mistake: forgetting that the codomain is part of the question. The same rule x² is surjective if you change the codomain to the non-negative reals. "Is it onto?" has no answer until you say onto what.

4. What a proof is, and the direct proof

A proof is a chain of steps. Each step follows from a definition, an earlier proven fact, or the step before it, and the chain ends at the claim. A proof covers every case at once, which testing examples cannot do.

Here is why examples are not enough. The expression n² + n + 41 gives a prime number for every n from 0 to 39. At n = 40 it gives 40² + 40 + 41 = 1681, which is 41 × 41. Forty successes, then a failure. Nothing short of a proof settles a claim about all n.

The direct proof, step by step

1. Write down what you are given, using definitions. An even number is 2k for some integer k. An odd number is 2k + 1.
2. Write down what you must reach, also as a definition.
3. Calculate from the first to the second, one justified step at a time.
4. Use a fresh letter each time you say "some integer".

Example 1: the sum of two even numbers is even.

• Let the numbers be 2a and 2b, where a and b are integers.
• Their sum is 2a + 2b = 2(a + b).
• a + b is an integer, so the sum is 2 times an integer. It is even.

Example 2: the product of two odd numbers is odd.

• Let the numbers be 2a + 1 and 2b + 1.
• Multiply: (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1.
• 2ab + a + b is an integer, so the product has the form 2k + 1. It is odd.

Example 3: n² + n is even for every integer n.

• Factor: n² + n = n(n + 1).
• Of two consecutive integers, one is even.
• So the product has an even factor, which makes it even.

The usual mistake: reusing one letter for two different numbers. Writing the two evens as 2k and 2k is a proof about equal numbers only. Use 2a and 2b.

5. Contrapositive and contradiction

Two more methods, both built on the logic in section 1.

Proof by contrapositive. To prove "if P then Q", prove the equivalent "if not Q then not P". Use it when "not Q" is easier to work with than P.

Example 1: if n² is even, then n is even.

• Contrapositive: if n is odd, then n² is odd.
• Let n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd.
• That proves the contrapositive, so the original is true.

Proof by contradiction. To prove a claim, assume it is false and follow the consequences until something impossible appears. Then the assumption must have been wrong.

Example 2: √2 is irrational.

1. Suppose √2 = a ÷ b, a fraction in lowest terms (a and b share no common factor).
2. Square both sides: 2 = a² ÷ b², so a² = 2b².
3. So a² is even, and by Example 1, a is even. Write a = 2c.
4. Then 4c² = 2b², so b² = 2c². So b² is even, and b is even.
5. Now a and b are both even, so they share the factor 2. That contradicts "lowest terms".
6. The assumption fails, so √2 cannot be written as a fraction.

Example 3: there are infinitely many primes.

1. Suppose the list of all primes is finite: p₁, p₂, ..., pₙ.
2. Let N = p₁ × p₂ × ... × pₙ + 1.
3. Dividing N by any pᵢ leaves remainder 1, so no prime on the list divides N.
4. But every number above 1 has a prime factor. That factor is a prime not on the list, which contradicts step 1.

N itself need not be prime. With the first six primes, 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509. The proof only needs a prime factor of N outside the list, and 59 is one.

The usual mistake: calling something a proof by contradiction without reaching a contradiction. Finishing with "this seems unlikely" is not enough. You must arrive at a statement that is false, such as "a and b share no factor and also share the factor 2".

6. Induction

Induction proves a statement for every whole number n = 1, 2, 3, ... with two checks, like a row of dominoes. If the first falls, and each falling domino knocks over the next, they all fall.

How to do it

1. State the claim P(n) for a general n.
2. Base case: check P(1) directly.
3. Induction step: assume P(k) is true for some k (the induction hypothesis). Prove that P(k + 1) is true, and use the assumption somewhere in the proof.
4. Conclude that P(n) holds for all n.

Example 1: 1 + 2 + ... + n = n(n + 1) ÷ 2.

• Base case, n = 1: the left side is 1 and the right side is 1 × 2 ÷ 2 = 1. Equal.
• Step: assume 1 + 2 + ... + k = k(k + 1) ÷ 2.
• Then 1 + 2 + ... + k + (k + 1) = k(k + 1) ÷ 2 + (k + 1).
• Factor out k + 1: (k + 1)(k ÷ 2 + 1) = (k + 1)(k + 2) ÷ 2.
• That is the formula with n = k + 1, so the claim holds for all n.

Example 2: the sum of the first n odd numbers is n².

• Base case: 1 = 1².
• Step: assume 1 + 3 + ... + (2k − 1) = k². Add the next odd number, 2k + 1: k² + 2k + 1 = (k + 1)².
• It matches n = k + 1, so the claim holds for all n.

Example 3: 2ⁿ > n for every n ≥ 1.

• Base case: 2¹ = 2 > 1.
• Step: assume 2ᵏ > k. Then 2^(k+1) = 2 × 2ᵏ > 2k.
• And 2k ≥ k + 1 whenever k ≥ 1. So 2^(k+1) > k + 1.

The usual mistake: skipping the base case. Take the false claim "n = n + 1 for every n". The step works: if k = k + 1, add 1 to both sides to get k + 1 = k + 2. But there is no true first domino, so nothing falls. The base case is not a formality.

Getting unstuck

When a proof will not start, try these in order:

1. Rewrite every word in the claim as its definition. "Even" becomes 2k. "Rational" becomes a ÷ b.
2. Try small cases (n = 1, 2, 3) and look for the pattern you can then prove.
3. Work backwards from the conclusion and ask what would make it true.
4. If direct steps stall, try the contrapositive, then contradiction.

George Pólya's How to Solve It, listed in part 1, is the classic book on this habit.

The mistakes in one table

Where to go next

The next post in the series puts this to use in linear algebra and differential equations. If you want more practice with proofs first, two books written for exactly this stage are Daniel Velleman's How to Prove It and Ethan Bloch's Proofs and Fundamentals.

Sources and further reading

• Daniel J. Velleman, How to Prove It: A Structured Approach.
• Ethan D. Bloch, Proofs and Fundamentals: A First Course in Abstract Mathematics.
• George Pólya, How to Solve It (1945).
• The proof that √2 is irrational and the proof that there are infinitely many primes are classical results (the second is in Euclid's Elements). Both appear in most proof textbooks.