Logic for Computer Scientists/Induction

Induction

Induction plays a crucial role at least in two aspect throughout this book. Firstly, it is one of main proof principles in mathematics and of course in logics. In particular it can be used to investigate properties of infinite sets. Very often it is used as natural induction, namely over the natural numbers. We will introduce it as a more general principle over well founded partial orders, which is called structural induction. The second aspect is, that it can be used as well to define infinite structures, as the set of well formed formulae in a particular logic or the set of binary trees.

We start with a very general structure over arbitrary sets, namely partial orders. A relation $R$ over $A$ is a partial order iff $R$ is reflexive, transitive and anti-symmetric (i.e. $((x,y)\in R \land (y,x)\in R \Rightarrow x=y)$) . Partial ordered sets (p.o. sets) $A$ are usually written as $(A, \leq)$.

Definition 1

The necessary structure for our induction principle is a partial order, such that there exist minimal elements. Given a p.o. set $(A, \leq)$, we define:

• $x < y$ iff $x \leq y$ and $x\neq y$.
• $(A, \leq)$ is called well-founded iff there is no infinite sequence $(x_i)_{i\in N}$ and $x_{i+1} < x_i, \forall i \geq 0$.
• $X\subseteq A$ is called a chain iff $\forall x,y \in X : x\leq y$ or $y\leq x$
• $(A, \leq)$ is a total ordering iff $A$ is a chain.

Lemma 1

$(A, \leq)$ is well-founded, if every non-empty subset of $A$ has a minimal Element. Proof can be done by contradiction and will be given as an exercise.

We finally have the machinery to introduce the principle of complete induction:

Definition 2 (Complete (structural) induction)

Given a well-founded p.o. set $(A, \leq)$ and a predicate $P$, i.e. $P : A \to \{true, false \}$. The principle of induction is given by the following (second order) formula
$\forall x \in A\; ( \forall y \in A\; ( y <x \Rightarrow P(y)) \Rightarrow P(x)) \Rightarrow \forall z \in A\; P(z)$

Lemma 2

The induction principle holds for every well-founded set.

Proof: The proof is given by contradiction: Assume the principle is wrong; i.e. the implication is wrong, which means, that we have to assume the premise as true:

$\begin{matrix} \forall x \in A\; ( \forall y \in A\; ( y <x \Rightarrow P(y)) \Rightarrow P(x)) \equiv{true} (premise) \end{matrix}$

and the conclusion as wrong:

$\begin{matrix} \forall z \in A\; (P(z)) \equiv =false= (conclusion) \end{matrix}$

Hence we can assume that the set $X = \{ x \in A \mid P(x) = false\}$ is not empty.

Since $X$ is a subset of a well-founded set, it has a minimal element, say $b$. From assumption (premise) we conclude

$\begin{matrix} (\forall y \in A\; ( y < b \Rightarrow P(y)) \Rightarrow P(b)) \equiv{true} (inst) \end{matrix}$

Now we can distinguish two cases:

• $b$ is minimal in $A$: Hence there is no $y \in A$, such that $y < b$. Hence the premise $\forall y \in A\; ( y < b \Rightarrow P(y))$ of the implication in (inst) is true, which implies that the conclusion $P(b)$ is true. This is a contradiction to the assumption that
  $b \in X$!
• $b$ is not minimal in $A$: $\forall y \in A\; (y <b)$ holds and it must be that $P(y)$ is true, because otherwise it would be that $y\in X$ and $b$ not minimal in $X$. Hence, again the premise $\forall y \in A\; ( y < b \Rightarrow P(y))$ of the implication in (inst) is true, which implies that the conclusion $P(b)$ is true. This is a contradiction to the assumption that $b \in X$!

An Example

In this subsection we will carry out a proof with induction in detail. For this we need the extension of p.O. sets:

Definition 3 (Lexicographic Ordering)

A p.O. set $(A,\leq)$ induces an ordering $\ll$ over $A\times A$: $\forall x,y,x\prime,y\prime \in A : (x, y) \ll (x\prime, y\prime)$ iff

• $x= x\prime$ and $y = y \prime$ or
• $x < x\prime$ or
• $x= x\prime$ and $y<y\prime$

Lemma 3

If $(A,\leq)$ is a well-founded set, then $(A\times A, \ll)$ is well-founded as well.

Theorem 1

The Ackermann-function $ACK$ defined by the following recursion is a total function over $N \times N$

  ACK(x,y) = 
    if x=0  then y+1 else
                     if y=0 then ACK(x-1,1) 
                            else ACK(x-1,ACK(x, y-1))

Proof: For the induction start we take the minimal element $(0,0)$ of the well-founded set,
$(N \times N , \ll)$, where $\ll$ is the lexicographic ordering induced by $(N, \leq )$. Hence, assume $x=0, y=0$. By definition of
$ACK$, we conclude $ACK(0,0)=1$ and hence defined. Assume for an an arbitrary $(m,n)$, that

$ACK(m', n')$ is defined for all $(m'. n') \ll (m,n)$, if $(m,n) \neq (m',n')$

We distinguish the following cases:

• $m=0$: i.e. $ACK(0,n) = n+1$ and hence defined.
• $m\neq0$ and $n=0$: We know that $(m-1,1) \ll (m,0)$ and $(m-1,1) \neq (m,0)$. From the induction hypothesis we know that $ACK(m-1,1)$ is defined, and hence $ACK(m,0) = ACK(m-1,1)$ as well.
• $m\neq0$ and $n\neq 0$: According to the definition of $ACK$ we have two cases to consider:
  • $(m,n-1) \ll (m,n)$ and $(m,n-1) \neq (m,n)$: From the induction hypothesis we conclude immediately that $ACK(m,n-1)$ is defined.
  • $(m-1,y) \ll (m,z)$ and $(m-1,y) \neq (m,z)$: Independent from the values of $x$ and $y$. If we assume
    $y 'ACK(m,n-1)$ and $z=n$, we again can conclude from the hypothesis, that $ACK(m-1, ACK(m, n-1))$ is defined and hence $ACK(m,n)$ as well

Altogether we proved, that $ACK(x,y)$ is defined for all $x,y \geq 0$.

Problems

Problem 1 (Induction)

Prove the following lemma: If $(A,\leq)$ is well founded also $(A \times A,\ll)$.

Note: The lexicographical Order $(A \times A,\ll)$ is defined as follows:

$(m,n) \ll (m',n') \iff \big( m<m' \lor (m=m' \land n \leq n') \big)$

Problem 2 (Induction)

How many points of intersection could $n$ straight lines have at most? Find a recursive and explicit formula and show

Problem 3 (Induction)

Prove that a number $x$ is even if and only if $x^2$ is even.

Problem 4 (Induction)

Point by an indirect proof that there is not any greatest prime number!

Problem 5 (Induction)

Which prerequisite do you need that the following order

$(\{A,\,B,\,C,\,0,\,1,\,2\},\leq)$ is

1. partial ordered
2. total ordered
3. well-founded?

Problem 6 (Induction)

An example of a well founded set is the power set $P(M)$ over a finite set $M$ which is comparable over the relation of the subset $\subseteq$. If $M=\{1,\, 2,\, 3\}$ then is e.g. ${1}\subseteq \{1,\, 2,\, 3\}$ but $\{1,\, 2\}$ and $\{2,\, 3\}$ are not comparable. Give a definition of a relation $B$ in this way that $( P(M),\, B )$ is total ordered and well founded.

Problem 7 (Induction)

Examine which of the following partial order are total and which are well founded!

1. $(2^{\N},\subseteq)$ with $2^{\N}$ is the power set for natural numbers.
2. $(\N,|)$ with $|$ marks the relation "`is factor of"'.
3. $(\N\times\N,\ll)$ with $(m,n) \ll (m',n')$ iff $m<m'$ or ($m=m'$ and $n \leq n'$).
4. $(\N^*,\preceq)$ with $\preceq$ is the lexicographical .
5. for $\N^*$, i.e. $1 \prec 1.1 \prec 3 \prec 3.3.8$

Problem 8 (Induction)

Give for the natural numbers $\N$ an order relation, that is

1. both well-founded and total,
2. total but not well-founded,
3. well-founded but not total and
4. neither well-founded nor total.

Problem 9 (Induction)

Prove, that a partial order $(A,\leq)$ is well-founded iff every non-empty partial set of $A$ (at least) contains a minimum element.

Problem 10 (Induction)

A root tree consists (a) of a single node or (b) of a node - that's the root of the tree - and at least one, but only at most finite many (part)trees, this one is bandaged over an edge with the root. Point formally by means of induction, that in every tree the number of the nodes $n$ around $1$ is taller than the number of the edges $e$, i.e. $e = n-1$.

Problem 11 (Induction)

Prove: If ε is a quality of the natural numbers $\N$ and it is valid

1. ε(0) and
2. $\forall n \in \N$ : [ε(n) $\Rightarrow$ ε(n+1)].

then $\forall n \in \N$ : ε(n) is valid.

Note: The proof can be done by the fact that the principle of the complete induction in $\N$ (which should be proved) can be reduced to the principle of the transfinite induction for well founded orders.