Logic, sets and proof techniques – university Year 1 maths lesson to download as PDF

Example 1

Compare \(\forall x\,\exists y\,(x+y=0)\) and \(\exists y\,\forall x\,(x+y=0)\) over \(\mathbb R\).

The first is true: take \(y=-x\). The second is false: no single \(y\) works for every \(x\). The order of quantifiers matters. To disprove a "for all" claim, one counterexample is enough.

Example 2: direct proof

Prove that if \(n\) is odd then \(n^2\) is odd.

Write \(n=2k+1\). Then \(n^2=4k^2+4k+1=2(2k^2+2k)+1\), which is odd.

Example 3: contrapositive

Prove that if \(n^2\) is even then \(n\) is even.

The contrapositive is: if \(n\) is odd then \(n^2\) is odd, which was just shown.

Example 4: contradiction

Prove that \(\sqrt2\) is irrational.

Suppose \(\sqrt2=p/q\) in lowest terms. Then \(p^2=2q^2\), so \(p^2\) is even, hence \(p\) is even, \(p=2r\), so \(q^2=2r^2\) and \(q\) is even too, contradicting lowest terms.

Example 5: induction

Prove that \(1+2+\cdots+n=\tfrac{n(n+1)}2\).

Base: \(n=1\) gives \(1=1\). Step: assume it for \(k\); then \(1+\cdots+k+(k+1)=\tfrac{k(k+1)}2+(k+1)=\tfrac{(k+1)(k+2)}2\), the formula for \(k+1\).

Worked example 6: Negating nested quantifiers

Write the negation of "for every \(\varepsilon>0\) there exists \(\delta>0\) such that \(|x|\lt \delta\) implies \(|x^2|\lt \varepsilon\)".

To negate a statement, change every "for every" into "there exists" and every "there exists" into "for every", working from left to right, and then negate the final condition. The negation is: there exists \(\varepsilon>0\) such that for every \(\delta>0\) there is an \(x\) with \(|x|\lt \delta\) and \(|x^2|\ge\varepsilon\). Note that the negation of an implication \(A\Rightarrow B\) is "\(A\) and not \(B\)". The order of the quantifiers matters, and swapping them changes the meaning completely.

Worked example 7: De Morgan's laws for sets

Prove that \((A\cup B)^c=A^c\cap B^c\).

We show that the two sets have the same elements. Let \(x\in(A\cup B)^c\). Then \(x\) is not in \(A\cup B\), so \(x\) is in neither \(A\) nor \(B\). That is, \(x\in A^c\) and \(x\in B^c\), so \(x\in A^c\cap B^c\). Conversely, if \(x\in A^c\cap B^c\), then \(x\) is in neither \(A\) nor \(B\), so \(x\notin A\cup B\) and \(x\in(A\cup B)^c\). Since each set is contained in the other, they are equal. This "two inclusions" method is the standard way to prove set equalities.

Worked example 8: Injective, surjective and bijective

Let \(f:\mathbb R\to\mathbb R\) be defined by \(f(x)=x^3-x\). Decide whether \(f\) is injective or surjective.

We have \(f(0)=f(1)=f(-1)=0\), so three different inputs give the same output and \(f\) is not injective. For surjectivity, \(f\) is a cubic with positive leading coefficient: it tends to \(-\infty\) as \(x\to-\infty\) and to \(+\infty\) as \(x\to\infty\), and it is continuous, so by the intermediate value theorem every real number is a value. So \(f\) is surjective but not injective. If we defined \(g(x)=x^3\) instead, we would have a bijection.

Worked example 9: A contrapositive proof

Prove that if \(n^2\) is divisible by 3 then \(n\) is divisible by 3.

We prove the contrapositive: if \(n\) is not divisible by 3 then \(n^2\) is not divisible by 3. If \(n\) is not divisible by 3, then \(n=3k+1\) or \(n=3k+2\). In the first case \(n^2=9k^2+6k+1=3(3k^2+2k)+1\), which leaves remainder 1. In the second case \(n^2=9k^2+12k+4=3(3k^2+4k+1)+1\), which also leaves remainder 1. In both cases \(n^2\) is not divisible by 3, which proves the contrapositive and therefore the original statement.

Worked example 10: A proof by contradiction with an infinite set

Prove that there are infinitely many primes.

Suppose that there are only finitely many primes, \(p_1,p_2,\dots,p_k\). Form the number \(N=p_1p_2\cdots p_k+1\). Dividing \(N\) by any \(p_i\) leaves remainder 1, so no prime on the list divides \(N\). But every integer greater than 1 has a prime factor, so \(N\) has a prime factor that is not on the list. This contradicts our assumption that the list contained all the primes. This argument is more than 2 000 years old and appears in Euclid's Elements.

Worked example 11: Induction with an inequality

Prove that \(n!>2^n\) for all integers \(n\ge4\).

Base case \(n=4\): \(4!=24>16=2^4\). For the inductive step assume \(k!>2^k\) for some \(k\ge4\). Then \((k+1)!=(k+1)\cdot k!>(k+1)\cdot2^k\ge2\cdot2^k=2^{k+1}\), because \(k+1\ge5>2\). Hence the statement holds for \(k+1\). Notice that the base case starts at 4, not 1: the statement is false for \(n=2\) and \(n=3\), and an induction proof always starts where the statement first becomes true.