4
$\begingroup$

In the book that I read there is a exercise where we need to prove the recursion principle that is written in the next fashion.

Proposition: Let $f: \mathbb{N} \times \mathbb{N}\rightarrow \mathbb{N}$ be a function and $c \in \mathbb{N}$. Then, there exist a unique function $ a: \mathbb{N} \rightarrow \mathbb{N}$ such that: $a(0):=c\: $ and $\:a(n^{+}):=f(n,a(n))$; (where $n^{+}:=n \cup \left\{n \right\} $).

The book give us a hint: Show that for each natural number there exist a n-function $ a_{n}: n^{+}\rightarrow \mathbb{N} $ such that $a_{n}(0):=c\: $ and for each $ i \in n$, $\:a_{n}(i^{+}):=f(i,a(i))$.

And here is what I have at this moment:

Claim 1: For each natural number there exist a n-function.

Proof of Claim 1: Let "$\varphi (x)$" be the following:

$ \forall x \forall y \forall y' ( \langle x,y\rangle \in a_{n} \wedge \langle x,y'\rangle \in a_{n} \rightarrow y=y' ) \wedge Dom(a_{n}) = n^{+} \wedge a_{n} (0)= c \,\wedge \, \forall i (i \in n \rightarrow a_{n} (i^{+}) = f(\,i,a_{n} (i))\,). $

Now we can apply the separation axiom and form a set which we define as: $ S : = \left\{n \in \mathbb{N}: \exists a_{n} \varphi (x) \right\} $

For n=0, we require a function with domain $ 0^{+} $. And as the only element of the domain is $ 0 $, we can form the ordered pair $ a_0 = \left\{ \langle 0, c\rangle \right\}. $ Which is a function, its domain is in fact $n^{+}$ and the last statement of the formula is vacously true. Then $ 0 \in S$.

Suppose $ n\in S $ that means $ a_{n} $ exist. Then, we define $ a_{n^{+}} $ as follows:

$ a_{n^{+}}: = a_{n} \cup \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$.

So, only we need to show that $ a_{n^{+}} $ is a n+1- function.

i) $ \langle x,y \rangle \in a_{n^{+}} \leftrightarrow \langle x,y \rangle \in a_{n} \vee \langle x,y \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$

As $ a_{n}$ is a function by our inductive hypothesis, only we need to show that $ \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} $ is a functional relation:

$\langle x,y \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} \wedge \langle x,y' \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} \rightarrow y = f(n,a_{n} (n) = y'$. It follows because f is indeed a function.

ii) $ Dom (a_{n^{+}}) = Dom(a_{n}) \cup \left\{ n^{+} \right\} $. By hypothesis we know that $ Dom(a_{n}) = n^{+} $. Hence $ n^{+} \cup \left\{ n^{+} \right\} = n^{++}$.

iii) As $a_{n}\subset a_{n ^ {+}} $, and by hypothesis we know that $\langle 0,c \rangle \in a_{n} $. Then $\langle 0,c \rangle \in a_{n ^ {+}} $.

iv) $\forall i \in n^{+}. \langle i^{+},c \rangle \in a_{n ^ {+}} \leftrightarrow \langle i^{+},c \rangle \in a_{n} \vee \langle i^{+},c \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} $.

If $ \langle i^{+},c \rangle \in a_{n} $ by hypothesis we know that $ c = f(i, a_{n}(i)) $ as desired. On the other hand if $\langle i^{+},c \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$ it follows by construction.

Then $ n^{+} \in S $, and we conclude by induction that, there exist a n-function for every natural number.

Claim 2: For each natural number this function is unique.

Proof of claim 2: For n = 0, the only 0-function is $ a_0 = \left\{ \langle 0, c\rangle \right\} $. If we assume that holds for n, we need to show that also holds for $ n^{+} $.

Let $ a_n = a'_n $, for construction of n-functions we know that:

$ a_{n^{+}} = a_{n} \cup \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} =a'_{n} \cup \left\{ \langle n^{+}, f(n,a'_{n} (n)) \rangle \right\} =a'_{n^{+}} $. Therefore all the n-functions are uniques.

At this point I'm not sure how could I derive exactly the function a, I think that maybe using the union of all the families $ a_{n} $. But I'm not really sure, somebody knows?


I'm not sure here, but if we use the replacement axiom for each n-function we have:

Let "$\varphi (x,y)$" be the formula:

$ ( x \in \mathbb{N} \wedge y = \,x-function ) \vee (\neg x \in \mathbb{N} \wedge y = 0 ) $.

For the claim 2 there exist a unique n-function for each n, therefore "$\varphi (x,y)$" is functional. And we can apply replacement to derive: $\left\{a_{n}: n\in \mathbb{N} \right\}$.

And (maybe) define the function $a$ to be: $a: = \bigcup \left\{a_{n}: n\in \mathbb{N} \right\}$

Here is my attempt: By the union axiom and the replacement schema axiom $a$ defined as above is a set. So, only we need to show that indeed is a function and that all property that we wish really holds.

Claim 3: The relation a is a functional relation.

Proof of Claim 3: To $a$ be a functional relation we need to show $ \langle x,y \rangle \in a \wedge \langle x,y' \rangle \in a \rightarrow y = y'.$

if $\langle x,y \rangle \in a \leftrightarrow \exists n \in \mathbb{N}. \langle x,y \rangle \in a_{n} $ at the same way $\langle x,y' \rangle \in a \leftrightarrow \exists m \in \mathbb{N}. \langle x,y' \rangle \in a_{m}. $ And as $ m \in n \vee n\in m \vee n = m$.

(1) If $n = m$, by claim 2 we have that $ a_{n} = a_{m}$ and as $ a_{n} $ is functional. We're done, that means $ y = y'$ because $\langle x,y \rangle \in a_{n} \wedge \langle x,y' \rangle \in a_{n} \rightarrow y = y'$.

(2) If $ m \in n\, (m < n)$ by construction we know that $ a_{m} \subset a_{n}$. Then $\langle x,y' \rangle \in a_{m} \rightarrow \langle x,y' \rangle \in a_{n} $. As $ \langle x,y \rangle \in a_{n} \wedge \langle x,y' \rangle \in a_{n} $ and as $a_{n}$ is functional. Then $ y = y' $ as desired.

(3) At the same way if $ n \in m\, (n < m),\, a_{n} \subset a_{m}$. Then $\langle x,y \rangle \in a_{n} \rightarrow \langle x,y \rangle \in a_{m} $. As $ \langle x,y \rangle \in a_{m} \wedge \langle x,y' \rangle \in a_{m} $ and as $a_{m}$ is functional. Then $ y = y' $ as desired.

Then $a$ is a functional relation.

Claim 4: The functional relation a, is a function such that $ a(0) = c \wedge a (i^{+}) = f(i, a(i))$.

Proof of claim 4:

(1) As definition all the n-function evaluated at 0 are c, therefore the union of all of them is c, $ \langle 0,c \rangle \in a $ as desired.

(2) If $i^{+} \in \mathbb{N}. \langle i^{+},y \rangle \in a \leftrightarrow \exists n\in \mathbb{N}. \langle i^{+},y \rangle \in a_{n}. $ By construction of all the n-function that means $ y = f(i, a_{n} (i))$. So, only we need to show that $ a_{n} (i) = a (i) $. But since $ a_{n} $ is the restriction of $a$ at n, that follows inmediately.

What do you think? Is it correct?


The other exercise the book says this:

Show using the last proposition there exist only one version of the natural numbers in set theory.

My attempt: Let $ \mathbb{N'}$ be a set such that the Peano's axioms hold. Let f be a function, $f : \mathbb{N} \times \mathbb{N'} \rightarrow \mathbb{N'} $, such that $ \langle n,n' \rangle \mapsto n'^{+}$. And, $ a: \mathbb{N}\rightarrow \mathbb{N'}$ such that, $a(0) = 0'$ and $ a(n^{+}) = f(n, a(n)) = n'^{+} =(a(n))^{+} $. By the last proposition the function exist and it is unique.

Injective part:

For $n = 0$ we have $ a (0) = a(0^{*}) = 0'$, so we need to show that $0 = 0^{*}$. By the sake of the contradiction suppose $0 \neq 0^{*}$. Therefore $ 0^{*} = k^{+} $ for some $k \in \mathbb{N},\, a(0^{*})=a(k^{+}) = k'^{+}$. And as the Peano's Axiom hold in $\mathbb{N'}, k'^{+} \neq 0'$, a contradiction. Then, $ 0=0^{*} $.

Suppose that our assumption holds for n, we need to show that also holds for $ n^{+} $. If $ n'^{+}=a (n^{+}) = a (n^{*+})=n'^{*+}$. By the Peano's axioms we have $ n'^{+} = n'^{*+} \rightarrow n'= n'^{*}$. As $a(n)=n' = a(n^{*})=n'^{*},\; a(n) = a(n^{*}) \rightarrow n = n^{*} $ (by the inductive hypothesis). Hence $ n^{+} = n^{*+}$. That closed the induction.

Surjective part:

By definition we know that $0' = a (0)$, so there exist a $0 \in \mathbb{N}$. Suppose that our assumption holds for n', that means $ n' = a(n)$ there exist a $n \in \mathbb{N}$. So, $ n' ^{+}=(n')^{+} = (a(n))^{+} = a(n^{+})$. That closed the induction.

Hence exist a bijection between them.

Any suggestion about all of these exercises....

$\endgroup$
  • $\begingroup$ I don't know what an $n$-function is but if you're allowed to use the usual principle of recursive definition then you should. $\endgroup$ – dfeuer Jul 15 '13 at 20:18
  • $\begingroup$ @PeterTamaroff This is a specific application of that principle. I see that he's going through all the steps to prove the principle for this special case, which looks like overkill. $\endgroup$ – dfeuer Jul 15 '13 at 20:20
  • $\begingroup$ @dfeuer Heh, true. I read all this too quickly. $\endgroup$ – Pedro Tamaroff Jul 15 '13 at 20:22
  • $\begingroup$ @dfeuer An $n$ function seems to be a function with domain $n^{+}$ mapping to the naturals. $\endgroup$ – Pedro Tamaroff Jul 15 '13 at 20:23
  • $\begingroup$ @PeterTamaroff Exactly that is what the book define them. Any function with domain $ n^{+}$ such that $\varphi (x)$ is true. $\endgroup$ – Jose Antonio Jul 15 '13 at 20:29
1
$\begingroup$

Your proof of the recursion theorem for $\Bbb N$ looks spot-on. Good job, this proof is nontrivial to write correctly :).


In the second exercise, you take an overly long route, as well as glance over the proof that $a(n) = n'$.

If you first prove by induction on $\Bbb N$ that $a(n) = n'$, then injectivity is immediate.

Subsequently take $S = \{n' \in \Bbb N': \exists m: a(m) = n'\}$ and conclude surjectivity by induction on $\Bbb N'$. (This is actually more or less identical to what you wrote.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.