2 Induction and Relations

2.1 Induction

Induction is a proof technique used to show statements \(P(n)\) for all natural numbers, i.e. for all \(n\in\mathbb{N}.\) The idea is to exploit the structure of the natural numbers revealed by the Peano axioms: there is a starting number \(0,\) from which we can reach all other natural numbers by repeatedly applying the successor function, i.e. by adding \(1\) as follows \[0\rightarrow S(0) = 1 \rightarrow S(1) = 2 \rightarrow \cdots \rightarrow n \rightarrow S(n)=n+1 \rightarrow \cdots\]

The idea of induction is strongly connected to Axiom Number 5 in 1.5. We assume that a property \(P(a)\) is true for some \(a\in\mathbb{N}.\) If we can show that, if \(P(n)\) holds for arbitrary \(n\in\mathbb{N}\) it also holds for the successor \(S(n)=n+1,\) i.e. if we show that \(P(n+1)\) holds, then it follows that \(P(m)\) holds for all \(a\leq m\in\mathbb{N}.\)

Induction is carried out as follows:

1. Base Case: Show that P(a) is true for some \(0\leq a\in\mathbb{N}.\)

2. Induction Hypothesis: Assume that \(P(n)\) is true for an arbitrary but fixed \(n\geq a.\)

3. Induction Step: Prove that \(P(n)\Rightarrow P(n+1)\) for all \(n\geq a\)

Then, we can conclude that \(P(n)\) holds for all \(n\geq a.\) The process can be visualized as follows \[P(a)\rightarrow P(S(a)) = P(a+1) \rightarrow P(S(S(a)) = P((a+1)+1) = P(a+2) \rightarrow \cdots\]

We illustrate this with the following example. We would like to prove the formula \[1+2+\ldots +n = \sum\limits_{k=1}^n k = \frac{n(n+1)}{2}\] for the sum of the first \(n\) natural numbers. We proceed as follows

1. Base Case: We choose \(a=1\) and see that \[1 = \sum\limits_{k=1}^1 k = 1\] holds true.

2. Induction Step. We assume that for arbitrary \(n\geq 1\) the formula \(\sum_{k=1}^n k = \frac{n(n+1)}{2}\) holds. Then we see that \[\begin{aligned} \sum\limits_{k=1}^{n+1} k &= n+1 + \sum\limits_{k=1}^{n} k\\ &= n+1+\frac{n(n+1)}{2}\\ &= (n+1)(1+\frac{n}{2})\\ &= (n+1)\frac{2+n}{2}\\ &= \frac{(n+1)(n+2)}{2}\\ &= \sum\limits_{k=1}^{n+1} k \end{aligned}\] holds, which finishes the induction.

Here you can find the video explanation on induction.

2.2 Relations and Orderings

We now will define relations, equivalence relations, and orderings. These will not only provide the necessary formal background for the relations \(<,\leq,>,\geq\) and \(=,\) which we already know, but will also turn out to be quite useful in different contexts.

Of particular interest are the so-called equivalence relations. The most common example is the relation \(=,\) but we will also use equivalence relations to construct the integers from the natural numbers.

From the above definition, we see that if \(xRx',\) we have \([x]_R=[x']_R.\) The equivalence relation partitions the set \(A\) into the equivalence classes. Generally speaking, equivalence relations allow us to remove all information which, for the current considerations, is not relevant. As an example, consider the number \(2,\) which can be written as \(2=\frac{4}{2} = \frac{34}{17}= \frac{2\pi}{\pi}.\) All of these expressions are equivalent, and we usually use the most convenient representing element, i.e. \(2,\) for our calculations. Whereas equivalence classes formalize our idea of equality, ordering relations are connected to the idea of inequality.

An example of an ordering relation is the relation \(\leq\) on the set of real numbers \(\mathbb{R}.\) Another example is the power set \({\mathcal P}(A)\) for a non-empty set \(A,\) which can be ordered by means of the inclusion \(\subset.\) As we know, for two real numbers \(x,y,\) we always have \(x\leq y\) or \(y\leq x.\) In the case that \(x\leq y\) and \(y\leq x\) hold, we even know that \(x=y.\) For the power set, however, the situation is different. If we look at the set \(A=\{a,b\},\) then we have \({\mathcal P}(A)=\{\emptyset, \{a\}, \{b\}, A\}.\) Clearly, \(\{a\}\subset A\) and \(\{b\}\subset A,\) but \(\{a\}\not\subset\{b\}\) and \(\{b\}\not\subset\{a\}.\) This observation motivates the following definition

As discussed above, \(\mathbb{R}\) w.r.t. \(\leq\) is totally ordered. The power set \({\mathcal P}(A)\) w.r.t. \(\subset\) is only partially ordered.

Here you can find the video explanation on relations and ordering.

2.3 Countable and Uncountable

An obvious property of the natural numbers is that they can be indexed, i.e. we simply take each natural number to be its own index. We generalize this observation with the following

Loosely speaking, this means that every element \(a\in A\) can get an index \(i(a),\) e.g. \(A=\{a_1,a_2,a_3,\ldots\}.\) Clearly, finite sets are countable, as \(i\) does not need to be surjective. We can also see that the set of all square numbers \(S=\{0,1,4,9,16,25,\ldots\}\) is countable. The mapping \(i\colon S\longrightarrow \mathbb{N}\) is even a bijection! This illustrates that the strict subset \(S\subsetneq \mathbb{N}\) has the same number of elements as its superset \(\mathbb{N}.\) For infinite sets, our usual ideas on size, therefore, do not apply.

We can easily see that the integers are countable by constructing a map that alternates between positive and negative numbers. The construction of \(i\) for this case is left as an exercise to the reader–do not forget \(0.\)

Also, the rational numbers \(\mathbb{Q}\) are countable, which can be seen by means of an enumeration scheme, which goes back to Georg Cantor.

We are now left with the question: are there (infinite) sets which are uncountable?

As it turns out, the answer is yes. An example of an uncountable set is the set \(\mathbb{R}\) of real numbers. The fact that \(\mathbb{R}\) is uncountable can be seen by means of an as elegant as an elementary argument, the so-called diagonal argument of Cantor.

Here you can find the video explaining Cantor’s proof.

2.3.1 Infimum and Supremum

For totally ordered sets \(A,\) we can ask the question of whether we can find lower and upper bounds for a subset \(E\subset A.\) For example, let \(A=\mathbb{R}\) and let \(E=[0,1]\) be the unit interval. Then, we have \(0\leq x\leq 1\) for all \(x\in E\) and can say that \(E\) is bounded from below by \(0\) and bounded from above by \(1,\) which motivates us to consider \(0\) as a lower bound for \(E\) and \(1\) as an upper bound for \(E.\)

In general, \(\alpha\) and \(\beta\) are not unique. For example, if \(E\subset\mathbb{R}\) and if \(\beta\) is an upper bound of \(E,\) then all \(\gamma\geq \beta\) are also upper bounds of \(E.\)

In our above example, we could have taken \(-1\) or \(-123.45\) as lower bound and \(5\) or \(42.24\) as upper bound, as clearly \(-123.45\leq -1\leq 0\leq x \leq 1 \leq 5 \leq 42.24\) for all \(x\) in \(E.\)

We, therefore, will pay particular attention to the least upper bound, which we will call supremum, and the greatest lower bound, which we will call infimum.

If \(\sup E\) exists, it may or may not be a member of \(E.\) For example, consider the set \(E=\{x\in R\colon x<1\}.\) Then, \(\sup E=1,\) but \(1\not\in E.\) Accordingly, for the infimum.

That means we can use the terms minimum (maximum) only if the infimum (supremum) is a member of the set \(E,\) respectively. In general, it is therefore preferable to use the terms infimum and supremum.

The following theorem is very useful. We do not prove it here and leave the proof to the Calculus 1 course.

Here you can find the video explanation on Infimum and Supremum.

See also the book of Rudin, “Principles of Mathematical Analysis”.

Home

Chapters

Contents

✕