Limits of Logic #4: Recursion Theorem

From: Limits of Logic (Jeffrey Sanford Russell)

Definition

Let $F$ be a set of operations on a set $A$.

• A subset $X⊆A$ is $F−$ closed iff for each $n−$ place function $f∈F$, and for any elements $x1,x2,...xn∈X$ we also have that $f(x1,x2,...xn)∈X$
• A subset $X⊆A$ has the $F−$ inductive property iff for any $F−$ closed set $Y$, $X⊆Y$.
• A subset $X⊆A$ is $F−$ recursive iff $X$ is both $F−$ closed and $F−$ inductive.

That is to say, the $F−$ recursive set is the smallest $F−$ closed set.

This definition formalizes recursive definitions which are "a way of defining an infinite set or relation, or a function with an infinite domain."

An example of a recursive definition of a set is the set of even numbers:

• $0$ is even
• $n$ is even $⟹$ $n+2$ is even.

Here, we have recursively defined the property of "evenness" $E$. Ultimately, a property really just is a set of all and only those elements which have that property. So the property $E$ really is the set of all even numbers.

In putting our recurvise definition of $E$ in context with the formal definition of $F−$ recursiveness, we see that $F$ here contains two functions $f0$ and $fn$:

1. A zero place function that outputs $f0=0$.
2. A one place function $fn:n→n+2$.

What does an $F−$ closed set look like? The even numbers $E$ are not the only $F−$ closed set. Note how the set of all natural numbers $ℕ$ is also $F−$ closed; $0∈ℕ$ and $n∈ℕ⟹n+2∈ℕ$.

Along with the closure property (that $E$ is $F−$ closed), $E$ also has the inductive property. Intuitively, the inductive proeprty tells us that if for any $X$:

• $0∈X$
• For any $n∈X$ we have that $n+2∈X$

Then really, alll even numbers are in $X$.

In other words, if any $X$ is $F−$ closed, then $E⊆X$. Note how $X$ can represent any property (e.g. "nice") and since we know that $X$ is $F−$ closed, we can prove by induction that every even number is "nice".

Now see that $E$ is the smallest $F−$ closed set -- which we define as being $F−$ recursive. Intuitively, $f0$ tells us that $0$ is necessarily in an $F−$ closed set, and $fn$ takes $0$ to $2$,whichtakesusto$ 4$,... and eventually all and only even numbers.

Exercise 2.3.2

For any set of operations $F$ on a set $A$, there is exactly one $F−$ recursive set.

Proof:

Let $X,Y⊆A$ be arbitrary $F−$ recursive sets.

Both $X$ and $Y$ are $F−$ closed. But then, by definition, $X$ is $F−$ inductive which means that $X⊆Y$. Similarly, we have that $Y⊆X$. Therefore, $X=Y$ i.e. there is exactly one $F−$ recursive set. $∎$

Definition

The relation $m$ is less than or equal to $n$ is recursively defined as follows:

• $n≤n$
• $m≤n⟹m≤suc(n)$

Note that this definition of a relation defines a set of ordered pairs $(m,n)$.

In the context of the formal definition recursive definitions, here $F$ contains a one place function $f1:ℕ→ℕ×ℕ$ that takes $n→(n,n)$, and a two place function $f2:ℕ×ℕ→ℕ×ℕ$ that takes $(m,n)→(m,suc(n))$. Therefore, the $≤$ relation is the $F−$ recursive set on these operations.

Example 2.2.6

Prove that for any numbers $m$ and $n$ such that $m≤n$, either $m=n$ or $m≤suc(n)$.

Proof:

Call $(m,n)$ nice iff either $m=n$ or $m≤suc(n)$.

We are trying to prove that for every $(m,n)$ such that $≤$ holds, $(m,n)$ is nice.

We shall prove this by induction on the $≤$ relation.

Base Case $n≤n$.

By the first rule of the $≤$ recursive definition, $(n,n)$ is a $≤$ -pair. Clearly, $(n,n)$ is nice since $n=n$.

Inductive Case $m≤n⟹m≤suc(n)$.

By the second rule of our recursive definition of $≤$, we have that if $(m,n)$ is a $≤$ -pair, then so is $(m,suc(n))$.

So, we'll assume that $(m,n)$ is nice and show that it follows that $(m,suc(n))$ is also nice.

So, assume that $(m,n)$ is nice, that is, $m=n∨suc(m)≤n$.

Case $m=n$:

$m=n⟹suc(m)=suc(n)$. Therefore, $suc(m)≤suc(n)$ based on the first rule of the $≤$ definition, and so, $(m,suc(n))$ is nice.

Case $suc(m)≤n$:

$suc(m)≤n⟹suc(m)≤suc(n)$ based on the second rule of the $≤$ definition, and so, $(m,suc(n))$ is nice.

In either case, $(m,suc(n))$ is nice.

Hence, we have proved that for any numbers $m$ and $n$ such that $m≤n$, either $m=n$ or $m≤suc(n)$. $∎$

Exercise 2.2.7

Prove by induction that for all numbers $m,n,k$ if $m≤n$ and $n≤k$ then $m≤k$.

Proof:

Let $m$ be any number and $(n,k)$ be a $≤$ -pair.

We want to show by induction on the $≤$ relation that for any $≤$ -pair $(n,k)$, we have $m≤n⟹m≤k$.

Base Case $≤$ -pair $(n,n)$

By the first rule of the $≤$ recursive definition, $(n,n)$ is a $≤$ -pair. Clearly, $m≤n⟹m≤n$. The base case is satisfied.

Inductive case $n≤k⟹n≤suc(k)$

By the second rule of our recursive definition of $≤$, we have that if $(n,k)$ is a $≤$ -pair, then so is $(n,suc(k))$.

So, we'll assume that $m≤n⟹m≤k$ holds, and show that it follows that $m≤n⟹m≤suc(k)$.

So, let $m≤n$. But then it follows from our assumption that $m≤k$ and by the the second rule of the recursive definition of $≤$, we have that $m≤suc(k)$.

Therefore, $m≤n⟹m≤suc(k)$.

2.3.4 The Recursion Theorem

Let $A$ be a set. Let $z$ be an element of $A$, and let $s:A→A$ be a function. Then there is a unique function $f:ℕ→A$ with these two properties:

• $f(0)=z$
• $f(n+1)=s(f(n))$

Call these Recursive Properties.

We prove this theorem in parts. Particularly we prove that following relation " selects " is functional:

For a number $n$ and an element $a∈A$ we define the relation $n$ selects $a$ recusrively as follows:

• $0$ selects $z$.
• $n$ selects $a⟹suc(n)$ selects $s(a)$.

We want to show that each number selects exactly value. Once we have done this, we will check the function for Recursive properties.

2.3.5 Exercise

Prove each of the following by induction on the definition of selects:

1. If $0$ selects $a$ then $a=z$.
2. If $suc(n)$ selects $a$ then there is some $b∈A$ such that $n$ selects $b$ and $s(b)=a$.

Proof of 1:

By induction on the selects relation, we want to show that for every selects-pair $(n,a)$, it holds that $n=0⟹a=z$.

Base case: $(0,z)$ is a selects-pair

Here, $(n,a)=(0,z)⟹n=0∧a=z$. Therefore, it holds that If $0$ selects $a$ then $a=z$.

Inductive case: $n$ selects $a⟹suc(n)$ selects $s(a)$.

Here, we assume that for $(n,a)$ it holds that $n=0⟹a=z$.

We now show that it follows that for $(suc(n),s(a))$, it holds that $suc(n)=0⟹s(a)=z$.

Note how $suc(n)=0$ is always false. Therefore, $suc(n)=0⟹s(a)=z$ trivially holds.

Therefore, we have shown by induction on the selects relation that if $0$ selects $a$, then $a=z$. $∎$

Proof of 2:

We want to show that for every selects pair $(p∈ℕ,a)$, it holds that $p=suc(n)⟹s(b)=a∧(n,b)∈selects$.

Base case: $(0,z)$ is a selects-pair

Here, $(p∈ℕ,a)=(0,z)⟹p=0$. Note how $suc(n)=0$ is always false.

Therefore, $p=suc(n)⟹s(b)=a∧(n,b)∈selects$ holds trivially.

Inductive case: $p$ selects $a⟹suc(p)$ selects $s(a)$.

We assume that for $(p,a)$, it holds that $p=suc(n)⟹s(b)=a∧(n,b)∈selects$.

We show that it follows for $(suc(p),s(a))$ that $p=suc(n)⟹s(b)=a∧(n,b)∈selects$.

Note that clearly $suc(p)$ is a successor of some $n∈ℕ$, particularly it is the successor of $p$, and $a∈ℕ$ is such that $s(a)=s(a)∧(p,a)∈selects$.

Therefore, $(suc(p),s(a))$ that $p=suc(n)⟹s(b)=a∧(n,b)∈selects$ holds trivially.

We have shown by induction on the selects relation that If $suc(n)$ selects $a$ then there is some $b∈A$ such that $n$ selects $b$ and $s(b)=a$. $∎$

2.3.6 Exercise

Prove the following:

1. For each number $n∈ℕ$ there is at least one $a∈A$ such that $n$ selects $a$.
2. For each number $n∈ℕ$ there is at most one $a∈A$ such that $n$ selects $a$.

Proof for 1:

We prove by induction on the natural numbers that For each number $n∈ℕ$ there is at least one $a∈A$ such that $n$ selects $a$.

Base case: $n=0$

By definition of the selects relation, we have that $n=0$ selects $z∈A$. Therefore, the base case is satisfied.

Inductive case: Assume there is some $a∈A$ such that $n$ selects $a$.

We show that there is some $b∈A$ such that $suc(n)$ selects $b$. Note by definition of the selects relation, $suc(n)$ selects $b=s(a)∈A$. Therefore the inductive case is satisfied.

We have shown by induction that for each number $n∈ℕ$ there is at least one $a∈A$ such that $n$ selects $a$. $∎$

Proof for 2:

We prove by induction on the natural numbers that For each number $n∈ℕ$ there is at most one $a∈A$ such that $n$ selects $a$.

Base case: $n=0$

By the result of 2.3.5 - 1, we have shown that if $0$ selects some $a∈A$, then $a=z$. Therefore, $0$ selects at most one value. The base case is satisfied.

Inductive case: Assume there is at most one $a∈A$ such that $n$ selects $a$.

We show that there is at most one b \in A$such that$suc(n)$selects$b$.

Note by definition of the selects relation, $suc(n)$ selects $s(a)∈A$.

Now let's say that $suc(n)$ selects some $b∈A$. Then by the result in 2.3.5-2, there is some $x∈A$ such that $n$ selects $x$ and $b=s(x)$.

But by our assumption, $n$ selects at most one $a∈A$. Therefore, $x=a$ and $s(x)=s(a)=b$ where $suc(n)$ selects $b=s(a)$.

Therefore, $suc(n)$ selects at most one value, that is, $s(a)$.

We have proved by induction that for each number $n∈ℕ$ there is at most one $a∈A$ such that $n$ selects $a$. $∎$

Completing the proof of Recursion theorem

Based on our results in 2.3.5 and 2.3.6 we can pick out a unique function $f:ℕ→A$ such that:

$f(n)=a$ iff $n$ selects $a$ for every $n∈ℕ$ and $a∈A$.

We now prove that:

1. For each $a∈A$, $f(0)=a$ iff $a=z$.
2. For each $a∈A$, $f(suc(n))=a$ iff $a=s(f(n))$.

Proof for 1:

Let $f(0)=a$ for some $a∈A$. Then, by the definition of $f$, we have that $0$ selects $a$. But $0$ exclusively selects $z∈A$. This implies that $a=z$.

For the other direction, let $a=z$. We know $0$ selects $z$. Therefore, by definition of $f$, we have that $f(0)=z=a$.

Therefore, we have proved that for each $a∈A$, $f(0)=a$ iff $a=z$. $∎$

Proof for 2:

Let $f(suc(n))=a$. But then, we know that there is some $b∈A$ such that $n$ selects $b$ and $a=s(b)$. By the definition of $f$, $f(n)=b$.

Therefore, $f(suc(n))=a=s(f(n))$.

For the other direction, assume $a=s(f(n))$. By definition of $f$, we have that $n$ selects $f(n)$. By the definition of the selects relation, we have that $suc(n)$ selects $s(f(n))$. But again by definition of $f$, we have that $f(suc(n))=s(f(n))$.

Therefore, $f(suc(n))=a=s(f(n))$.

We have proved that for each $a∈A$, $f(suc(n))=a$ iff $a=s(f(n))$.

This completes the proof of the recursion theorem. $∎$