2  Proofs

In this chapter we revise the process of producing correct proofs.

In the process of producing a valid/correct proof there are usually two phases:

A logician friend of mine once told me that for him “all proofs are eventually wrong, we just didn’t find an error yet”. This is a very pessimistic point of view (and he was joking) but it illustrates the point on the pessimist point of view.
CautionTo AI or not to AI?

Try to not delegate the process of producing correct proofs to AI tools. For several reasons:

  1. in the exam you’ll not have access to AI tools;
  2. using AI tools is mostly delegating to them the “optimistic phase”, which is the most fun;
  3. AI generated arguments on non-trivial exercises might be wrong, but the tone used might be very convincing, so you really need to have a very strong “pessimistic hat” in order to find errors.

The goal of the exercises it not to produce correct proofs, but to learn how to produce correct proofs. If you delegate the process to AI tools, you are not learning how to produce correct proofs, but how to use AI tools, which is not the point of the exercises.

On the other hand, AI tools might be useful for brainstorming. If you are really lost they might orient you in a generic direction that might be correct (or not).

2.1 Tools for the pessimistic phase

More often than not candidate proofs are neither correct nor wrong, they simply don’t contain enough details to be correct or wrong.

TipHow to detect if a proof contains enough details?

Put on your “pessimistic hat” and try to fill the gaps in your supposed proof as adversariarly as you can. If you can fill the gaps in such a way that your argument becomes wrong, then it is wrong (or maybe you just forgot to write down something important, so go back to the optimistic phase and write it down).

Look for corner cases, or whether you used all assumptions or not. Look for anything that smells suspicious.

Example 2.1 A common (and very powerful) strategy to detect errors is the following. Suppose you want to prove that statement A is true and you have a candidate proof \pi of A. It is always very useful to have (or to look for) statements very similar to A (say B) but false. If you try to use your candidate proof \pi on B then for \pi to be correct it must fail on B. If in the proof \pi it is not written explicitly something that makes \pi fail on B then it is also wrong (or not written with enough details). Even if your proof \pi fails on B it still might be wrong, but at least it passed a basic sanity check.

Example 2.2 A very simple example of errors that can be found using the strategy above. Suppose that you are arguing about the correcteness of some C++ code that you wrote. If you never mention anything of your code then the argument is wrong. I (the reader, with the pessimistic hat) can change the code to whatever I want, some completely unrelated one, and your argument does not detect the difference, hence it is wrong.

Exercise 2.1 To exercise the pessimistic point of view, try to find the error(s) in the following proofs (the statements are all false, so the proofs must be wrong).

  1. Dodgy Theorem 1. 1 is the largest integer.
    Proof. By contradiction suppose the conclusion is false. Then let n>1 be the largest integer. Multiplying both sides of this inequality by n, yields n^2>n. This is a contradiction, because n^2 is another integer larger than n. Therefore, 1 is the largest integer. \blacksquare

  2. Dodgy Theorem 2. All natural numbers are even.
    Proof. By induction on n. The base case is 0, which is even. For the inductive step, assume that n is even, we want to show that n+1 is even. Since n is even, there exists k\in \mathbb{N} such that n=2k. Then n+1=2k+1, which is odd, and this is a contradiction. Therefore, n+1 is even. \blacksquare

  3. Dodgy Theorem 3. All horses are black.
    Proof. We prove by induction on n that in every set of horses of size n, all n horses are the same color.
    Base Case (n=1): One horse is the same color as itself. This is true by inspection.
    Induction Step: Assume that the statement holds for n=k and we prove it holds for n=k+1. Since \{H_1, H_2, \ldots, H_k\} is a set of k horses, the induction hypothesis applies to this set. Thus, all the horses in this set are the same color.
    Since \{H_2, H_3, \ldots, H_{k+1}\} is also a set of k horses, the induction step likewise holds for this set. Thus, all the horses in this set are the same color too.

    Therefore, all n+1 horses in \{H_1, H_2, H_3, \ldots, H_n, H_{n+1}\} are the same color. \blacksquare

2.2 Tools for the optimistic phase

You should have already seen several tools to prove theorems, for example proofs by induction, by contradiction, by cases, etc.

Tip

Suppose that you want to prove that “A implies B” but you really don’t know where to start. As a general rule, the following are two good strategies:

  • proceed by contradiction: assume also that B is false and try to obtain a contradiction. Now you have two assumptions (A true and B false), or
  • proceed by cases: try to find a property P such that A\land P implies B and then try to show that A\land \lnot P also imply B.

One of the two strategies above might get you started!

Example 2.3 Suppose you are tasked to prove that there exists two numbers r,s\in \mathbb{R}\setminus \mathbb{Q} s.t. r^s\in \mathbb{Q}. Try r=s=\sqrt{2}. If \sqrt{2}^{\sqrt{2}}\in \mathbb{Q} we are done, otherwise try r=\sqrt{2}^{\sqrt{2}} and s=\sqrt{2}, then r^s=2 is rational and we are also done. This is a very nice example of how to use the “proceed by cases” strategy.

Exercise 2.2 Let f: {\mathbb N} \rightarrow \mathbb N be a function such that f(x+y) = f(x)+f(y) for any x, y \in \mathbb N. Prove that for any x \in \mathbb N, f(x) = f(1) \cdot x.

2.2.1 The Pigeonhole Principle

A very powerful tool (that you possibly didn’t see before) is the Pigeonhole Principle. This essentially is a “fancy” way of saying that for each natural number n, n\neq n+1:

there is no injective function from a set of size n+1 to a set of size n.

The elements of the set of size n+1 are usually called pigeons and the elements of the set of size n are called holes. The principle can then be stated pictorially saying that if you put n+1 pigeons in n holes, at least one hole will contain more than one pigeon.

This principle is very useful to prove the existence of some object without explicitly constructing it.

Exercise 2.3  

  1. Every graph with two or more vertices has two vertices with the same degree.1
  2. Given five points on a sphere, there is a closed hemisphere containing at least four of them.

Exercise 2.4 (🔥) Prove that any set of n+1 positive integers less than or equal to 2n, where n \ge 1, contains two distinct elements a and b such that a divides b.

A possibility is to use the pigeonhole principle: the pigeons are the n+1 numbers and the holes are the odd numbers between 1 and 2n. A pigeon of the form 2^k d with d odd flies to hole d.

Another option is to consider an induction proof on n and distinguish two cases in the inductive step: at least one of the elements 2n+1 and 2n+2 is not in the set or both are.

There is also a finite-vs-infinite version of the Pigeonhole Principle, which states that if you put infinitely many pigeons in m<\infty holes, at least one hole will contain infinitely many pigeons.

Exercise 2.5 For every real number r and every positive integer n, there exists a sequence of consecutive n digits that appears infinitely often in the decimal expansion of r.

  1. Recall that the degree of a vertex is the number of edges incident to it.↩︎