En el libro que he leído hay un ejercicio donde tenemos que demostrar el principio de recursividad que está escrito en el lado de la moda.
La proposición: Vamos a $f: \mathbb{N} \times \mathbb{N}\rightarrow \mathbb{N}$ ser una función y $c \in \mathbb{N}$. Entonces, existe una única función de $ a: \mathbb{N} \rightarrow \mathbb{N}$: $a(0):=c\: $$\:a(n^{+}):=f(n,a(n))$; (donde $n^{+}:=n \cup \left\{n \right\} $).
El libro nos da una sugerencia: Muestre que para cada número natural existe una n-función de $ a_{n}: n^{+}\rightarrow \mathbb{N} $ tal que $a_{n}(0):=c\: $, y para cada uno de los $ i \in n$, $\:a_{n}(i^{+}):=f(i,a(i))$.
Y aquí es lo que tengo en este momento:
Reivindicación 1: Para cada número natural existe una n-función.
Prueba de Reclamación 1: Vamos a "$\varphi (x)$" ser el siguiente:
$ \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))\,). $
Ahora podemos aplicar el axioma de separación y forma un conjunto que se define como: $ S : = \left\{n \in \mathbb{N}: \exists a_{n} \varphi (x) \right\} $
Para n=0, se necesita una función con dominio de $ 0^{+} $. Y como el único elemento del dominio es $ 0 $, podemos formar el par ordenado $ a_0 = \left\{ \langle 0, c\rangle \right\}. $ Que es una función, su dominio es, en realidad, $n^{+}$ y la última declaración de la fórmula es vacously verdadero. A continuación,$ 0 \in S$.
Supongamos $ n\in S $ esto quiere decir $ a_{n} $ existen. Entonces, definimos $ a_{n^{+}} $ como sigue:
$ a_{n^{+}}: = a_{n} \cup \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$.
Así, sólo tenemos que mostrar que $ a_{n^{+}} $ es un n+1 - función.
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\}$
Como $ a_{n}$ es una función de nuestra hipótesis inductiva, sólo tenemos que mostrar que $ \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} $ es una relación funcional:
$\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'$. De ello se deduce debido a que f es de hecho una función.
ii) $ Dom (a_{n^{+}}) = Dom(a_{n}) \cup \left\{ n^{+} \right\} $. Por hipótesis sabemos que $ Dom(a_{n}) = n^{+} $. Por lo tanto $ n^{+} \cup \left\{ n^{+} \right\} = n^{++}$.
iii) Como $a_{n}\subset a_{n ^ {+}} $, y por hipótesis sabemos que $\langle 0,c \rangle \in a_{n} $. A continuación,$\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\} $.
Si $ \langle i^{+},c \rangle \in a_{n} $ por hipótesis sabemos que $ c = f(i, a_{n}(i)) $ como se desee. Por otro lado, si $\langle i^{+},c \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$ sigue en construcción.
A continuación,$ n^{+} \in S $, y llegamos a la conclusión de que la inducción por eso, existe una n-función para cada número natural.
Reivindicación 2: Para cada número natural esta función es única.
La prueba de la reivindicación 2: Para n = 0, el 0 la función es $ a_0 = \left\{ \langle 0, c\rangle \right\} $. Si asumimos que se tiene para n, tenemos que mostrar que tiene también para $ n^{+} $.
Deje $ a_n = a'_n $, para la construcción de la n-funciones sabemos que:
$ 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^{+}} $. Por lo tanto, todas las n-funciones son únicas.
En este punto no estoy seguro de cómo podría derivar exactamente la función una, creo que tal vez mediante la unión de todas las familias $ a_{n} $. Pero realmente no estoy segura, alguien sabe?
No estoy seguro de que aquí, pero si usamos el axioma de reemplazo para cada uno de los n-función tenemos:
Vamos a "$\varphi (x,y)$" ser la fórmula:
$ ( x \in \mathbb{N} \wedge y = \,x-function ) \vee (\neg x \in \mathbb{N} \wedge y = 0 ) $.
Para la reivindicación 2 existe un único n-función para cada n, por lo tanto, "$\varphi (x,y)$ " es funcional. Y podemos aplicar la sustitución de derivar: $\left\{a_{n}: n\in \mathbb{N} \right\}$.
Y (tal vez) definir la función de $a$: $a: = \bigcup \left\{a_{n}: n\in \mathbb{N} \right\}$
Aquí está mi intento: Por el axioma de la unión y la sustitución del esquema de axioma $a$ se define como el anterior es un conjunto. Así, sólo tenemos que mostrar que, de hecho, es una función y que todos los bienes que deseamos realmente tiene.
Reivindicación 3: La relación es una relación funcional.
La prueba de la Reivindicación 3: $a$ ser una relación funcional que tenemos que mostrar $ \langle x,y \rangle \in a \wedge \langle x,y' \rangle \in a \rightarrow y = y'.$
si $\langle x,y \rangle \in a \leftrightarrow \exists n \in \mathbb{N}. \langle x,y \rangle \in a_{n} $ a de la misma manera $\langle x,y' \rangle \in a \leftrightarrow \exists m \in \mathbb{N}. \langle x,y' \rangle \in a_{m}. $ Y $ m \in n \vee n\in m \vee n = m$.
(1) Si $n = m$, por la reivindicación 2, tenemos que $ a_{n} = a_{m}$ y $ a_{n} $ es funcional. Hemos terminado, que significa $ y = y'$ porque $\langle x,y \rangle \in a_{n} \wedge \langle x,y' \rangle \in a_{n} \rightarrow y = y'$.
(2) Si $ m \in n\, (m < n)$ por la construcción sabemos que $ a_{m} \subset a_{n}$. A continuación,$\langle x,y' \rangle \in a_{m} \rightarrow \langle x,y' \rangle \in a_{n} $. Como $ \langle x,y \rangle \in a_{n} \wedge \langle x,y' \rangle \in a_{n} $ y $a_{n}$ es funcional. A continuación, $ y = y' $ como se desee.
(3) En la misma manera si $ n \in m\, (n < m),\, a_{n} \subset a_{m}$. A continuación,$\langle x,y \rangle \in a_{n} \rightarrow \langle x,y \rangle \in a_{m} $. Como $ \langle x,y \rangle \in a_{m} \wedge \langle x,y' \rangle \in a_{m} $ y $a_{m}$ es funcional. A continuación, $ y = y' $ como se desee.
A continuación, $a$ es una relación funcional.
Reivindicación 4: La relación funcional de una, es una función tal que $ a(0) = c \wedge a (i^{+}) = f(i, a(i))$.
La prueba de la reivindicación 4:
(1) Como la definición de todas las n-función evaluada en 0 son c, por lo tanto, la unión de todos ellos es la c, $ \langle 0,c \rangle \in a $ como se desee.
(2) Si $i^{+} \in \mathbb{N}. \langle i^{+},y \rangle \in a \leftrightarrow \exists n\in \mathbb{N}. \langle i^{+},y \rangle \in a_{n}. $ Por la construcción de todas las n-función que significa $ y = f(i, a_{n} (i))$. Así, sólo tenemos que mostrar que $ a_{n} (i) = a (i) $. Pero desde $ a_{n} $ es la restricción de $a$ n, que sigue inmediatamente.
¿Qué te parece? Es correcto?
El otro ejercicio que el libro dice esto:
Mostrar el uso de la última proposición no existe una sola versión de los números naturales en el conjunto de la teoría.
Mi intento: Vamos a $ \mathbb{N'}$ ser un conjunto tal que los axiomas de Peano espera. Sea f una función, $f : \mathbb{N} \times \mathbb{N'} \rightarrow \mathbb{N'} $, de tal manera que $ \langle n,n' \rangle \mapsto n'^{+}$. Y, $ a: \mathbb{N}\rightarrow \mathbb{N'}$ de manera tal que, $a(0) = 0'$$ a(n^{+}) = f(n, a(n)) = n'^{+} =(a(n))^{+} $. Por la última proposición de la función existe y es único.
Inyectiva parte:
Para $n = 0$ tenemos $ a (0) = a(0^{*}) = 0'$, por lo que tenemos que mostrar que $0 = 0^{*}$. Por el bien de la contradicción, supongamos $0 \neq 0^{*}$. Por lo tanto, $ 0^{*} = k^{+} $ algunos $k \in \mathbb{N},\, a(0^{*})=a(k^{+}) = k'^{+}$. Y como el Axioma de Peano mantenga en $\mathbb{N'}, k'^{+} \neq 0'$, una contradicción. A continuación, $ 0=0^{*} $.
Supongamos que nuestro presupuesto es cierto para n, tenemos que mostrar que tiene también para $ n^{+} $. Si $ n'^{+}=a (n^{+}) = a (n^{*+})=n'^{*+}$. Por los axiomas de Peano tenemos $ n'^{+} = n'^{*+} \rightarrow n'= n'^{*}$. Como $a(n)=n' = a(n^{*})=n'^{*},\; a(n) = a(n^{*}) \rightarrow n = n^{*} $ (por la hipótesis inductiva). Por lo tanto $ n^{+} = n^{*+}$. Que cerrada de la inducción.
Surjective parte:
Por definición sabemos que $0' = a (0)$, por lo que existe una $0 \in \mathbb{N}$. Supongamos que nuestro presupuesto es cierto para n', que significa $ n' = a(n)$ existe una $n \in \mathbb{N}$. Por eso, $ n' ^{+}=(n')^{+} = (a(n))^{+} = a(n^{+})$. Que cerrada de la inducción.
Por lo tanto existe un bijection entre ellos.
Cualquier sugerencia acerca de todos estos ejercicios....
