Autor Tema: C. Sists. Numéricos. --- Sección 1: Números Naturales

0 Usuarios y 1 Visitante están viendo este tema.

21 Julio, 2010, 05:13 am
Leído 9215 veces

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Nota: Este thread forma parte del tema





Construcción de los Sistemas Numéricos.

Sección 1. Números Naturales.


El sistema axiomático de los números naturales que suele darse es el de G. Peano.
Por eso, comenzaremos listando esos axiomas.

Se consideran tres objetos primitivos \( N, 1, S, \) sujetos a los siguientes axiomas:

  • \( N \) es un conjunto no vacío.
  • 1 es un elemento de \( N \).
  • \( S \) es una función con dominio \( N \), e imagen \( N\setminus\{1\} \)
  • La función \( S \) es inyectiva: \( S(x)=S(y)\Rightarrow{x=y} \)
  • Si \( A \) es un subconjunto no vacío de \( N \), definido de tal forma que \( 1\in A \), y tal que para todo \( n\in N \) vale la implicación \( n\in A\Rightarrow{S(n)\in A} \), entonces \( A=N. \)

La última propiedad es el famoso Principio de Inducción.

Ante todo, este principio está asociado directamente a la posibilidad de
definir funciones a través de relaciones por recurrencia.
Hay dos maneras de definir funciones de recurrencia,
que si bien son similares, necesitan herramientas algo diferentes.
A partir de los meros Axiomas de Peano,
sólo podemos dar el enunciado de la primera de ellas.

  • Subsección 1.1.
    Primer Principio de Definición de funciones por recurrencia.

Sea \( X \) un conjunto no vacío, y
sea \( G:N\times X\to X \) una función dada.
Sea además \( \alpha \) un elemento dado de \( X \).
Bajo tales condiciones, existe una, y sólo una función \( f:N\to X \)
que satisface las siguientes relaciones de recurrencia:

  • \( f(1)=\alpha, \)
  • \( f(S(n))=G(n,f(n)). \) para todo \( n\in N. \)

Demostración del Primer Principio de Definición por Recurrencia

Ante todo, recordemos que una función
es una colección de pares ordenados \( (x,y) \)
con la propiedad de unicidad de la imagen, esto es:

  • Si \( (x,y), (x,y') \) son dos pares correspondientes a la función,
    entonces \( y = y' \).

Notacionalmente, se conviene en escribir que \( y= f(x) \) es lo mismo que afirmar
que el par ordenado \( (x,y) \) pertenece al conjunto \( f \).

Por lo tanto, la función \( f \) que estamos buscando,
cuyo dominio es \( N \) y cuya imagen está en \( X \),
será cierto conjunto de pares ordenados \( (n,y) \), con \( n\in N, y\in X \),
y de tal suerte que se cumpla la propiedad de unicidad de la imagen.

Lo que se hace en esta situación es
  • construir un conjunto de pares ordenados \( f \),
  • posteriormente demostrar que \( f \) es, en efecto, una función, y
  • que además cumple las relaciones de recurrencia.
  • Finalmente, se debe probar que sólo hay una función \( f \) posible que satisface dicha recurrencia.
    Este hecho es más sencillo de demostrar.

Así que vayamos a los detalles.



Vamos a dar algunas definiciones para limpiar un poco el lenguaje.

Sea \( D \) un subconjunto de \( N \).
Diremos que \( h \) es una función \( G \)-recursiva
con dominio \( D \) y valor inicial \( \alpha\in X \)
,
si \( h \) es una función de \( D \) en \( X \), tal que:
  • \( 1\in D \),
  • \( h(1)=\alpha \), y además,
  • para todo \( n\in N \), si \( S(n)\in D \), entonces también \( n\in D \) y \( h(S(n))=G(n,h(n)) \).

Tomemos \( \alpha\in X \) fijo,
y definamos un gran conjunto \( K_\alpha \) que contenga a todos los subconjuntos \( h \) de \( N\times X \)
(o sea, cada \( h \) es un conjunto formado por pares ordenados \( (n,y) \), con \( n\in N, y\in X \)),
con la propiedad de que existe un conjunto \( D\subset N  \)
tal que \( h \) es una función \( G \)-recursiva con dominio \( D \)
y valor inicial \( \alpha \).

Formalmente, esto sería así:

\( K_\alpha=\{h: D\to X| D\subset N, h(1)=\alpha, \forall{n\in N}:(S(n)\in D \Rightarrow{n\in D \wedge h(S(n))=G(n,h(n))})\}. \)

Ahora definimos \( f \) como la unión de todos los elementos \( h \) del conjunto \( K_\alpha \):

\( \displaystyle f=\bigcup_{h\in K_\alpha} h. \)

¿Esta unión de apariencia enorme y caótica va a comportarse como la función \( f \) que esperamos obtener?

Asombrosamente, .
O sea, la enormidad y el caos de esa unión así tomada son sólo aparentes.
Veamos.

En primer lugar,
notemos que \( f \) es un conjunto de pares ordenados \( (n,y) \),
con \( n\in N \), \( y\in Y \).
Lo primero que deseamos probar es que,
para cada \( n\in N \), hay al menos un par \( (n,y) \) en \( f \).

Esto es necesario demostrarlo,
porque si pretendemos que \( f \) sea una función con dominio \( N \),
para cada \( n \) debe corresponder algún valor \( y \) por la aplicación \( f \).
Así que sea \( A \) el conjunto de las "primeras componentes" de los pares que están en \( f \), esto es:

\( A=\{n\in N| \exists{y\in X:(n,y)\in f}\}. \)

Deseamos demostrar que \( A = N \),
y eso lo haremos usando el Principio de Inducción.


Ciertamente, el elemento \( 1 \) está en \( A \), porque \( (1,\alpha)\in f \).

Para un \( n\in N \) arbitrario, supongamos que \( n\in A \).
Por definición de \( A \), existe \( y\in X \) tal que el par ordenado \( (n,y) \in f \).
Como \( f \) es la unión de los elementos de \( K_\alpha \),
ha de existir un elemento \( h\in K_\alpha \) tal que \( (n,y)\in h. \)
Denotemos \( D \) al dominio de una tal \( h \).

Ocurren dos casos posibles: o bien \( S(n) \) está en \( D \), o bien no está.

Si \( S(n)\in D \),
entonces
existe\(  z\in X \) tal que \( (S(n),z)\in h \),
pero como \( h\subset f \), tenemos que \( (S(n),z)\in f \)

Supongamos ahora el caso en que \( S(n) \) no pertenece a \( D \).
En tal situación, construiremos una función \( h_1 \) de la siguiente manera:
Definimos \( D_1 = D\cup\{S(n)\} \),
y hacemos que \( h_1 \) sea una función con dominio \( D_1 \), dada por:

\( h_1(k)=\begin{Bmatrix} h(k) & \mbox{ si }& k\in D\\G(n,h(n)) & \mbox{si}& k=S(n)\end{matrix} \).

Mostremos que \( h_1 \in K_\alpha. \)

En efecto, sea \( k\in N \) tal que \( S(k)\in D_1 \).
Si \( k\neq n \), entonces necesariamente \( S(k)\in D \), el dominio de \( h \),
y esto significa que \( k\in D \),
y además \( h(S(k))=G(k,h(k)) \).
Pero también, como \( k,S(k)\in D \), la definición de \( h_1 \) nos da
que \( h_1(S(k))=h(S(k))=G(k,h(k))=G(k,h_1(k)) \).

Por otra parte, si \( k=n \), recordemos que
teníamos al principio de todo que \( n \) es un elemento de \( D \) (pues \( (n,y)\in h\subset f \)),
luego \( h_1(n)=h(n) \), y por definición: \( h_1(S(n))=G(n,h(n))=G(n,h_1(n)). \)
Esto prueba que \( h_1 \in K_\alpha. \)
Por lo tanto, \(  h_1 \subset f \), y esto quiere decir que existe \( z\in X \) tal que \( (S(n),z)\in f. \)

En cualquier caso, hemos probado que existe \( z\in X \) tal que \( (S(n),z)\in f. \)
Esto indica que \( S(n)\in A \).

En resumen, tenemos que \( 1\in A \) y \( n\in A\Rightarrow{S(n)\in A} \).
Aplicando Principio de Inducción, obtenemos que \( A=N \).
Por lo tanto, para todo \( n\in N \),
existe algún \( z\in X \) tal que \( (n,z)\in f. \)


Ahora nos falta probar que \( f \) es una función,
o sea, que tiene la propiedad de unicidad de la imagen.
Veamos.

Consideremos el conjunto \( B \) formado por todos los \( n\in N \)
para los que se cumple la propiedad de unicidad de la imagen para \( f \),
o sea, tales que si \( (n,y),(n,z)\in f \), entonces \( y=z \). Formalmente:

\( B=\{n\in N: (n,y),(n,z)\in f \Rightarrow{ y=z}\}. \)

Sea \( n= 1 \). Para todo \( h\in K_\alpha \),
tenemos que \( (1,\alpha)\in h \subset f \),
por lo tanto \( (1,\alpha)\in f \).
Supongamos que para cierto \( z\in X \) se cumple que \( (1,z)\in f \).
Esto quiere decir que existe \( h\in K_\alpha \) tal que \( (1,z)\in h \).
Como \( h \) es una función, debemos tener que \( z=\alpha \).
Así que hemos probado que \( 1\in B \).

Supongamos que para cierto \( n\in N \) vale \( n\in B \).
Deseamos probar que esto implica que \( S(n)\in B \).

Sean \( y, z \in X \) tales que \( (S(n),y),(S(n),z)\in f \).
Existe alguna función \( h\in K_\alpha \) tal que  \( (S(n),y)\in h \).
Esto quiere decir que existe \( v\in X \) tal que \( (n,v)\in h\subset f \),
y además \( y=h(S(n))=G(n,h(n))=G(n,v) \).
De modo similar, se puede encontrar una función \( \tilde h\in K_\alpha \) y un \( w\in X \)
tal que \( (n,w)\in \tilde h\subset f \),
y además \( z=\tilde h(S(n))=G(n,\tilde h(n))=G(n,w) \).

Como \( (n,v),(n,w)\in f \),
la hipótesis de inducción en \( n \) nos dice que \( v=w \).
Por lo tanto \( y=G(n,v)=G(n,w)=z \), como se deseaba probar.

Aplicando el Principio de Inducción, hallamos que \( B= N \),
y entonces \( f \) tiene la propiedad de unicidad de la imagen.


En resumen, \( f \) es una función, con dominio \( N \) e imagen en \( X \).
A su vez, vale que \( f(1)=\alpha \), y dado \( n\in N \),
existen \( h\in K_\alpha, y\in X, \) tal que \( (S(n),y)\in h\subset f \), \( (n,h(n))\in h\subset f \),
con lo cual \( f(S(n))=h(S(n))=G(n,h(n))=G(n,f(n)) \).

Hemos demostrado que existe una función \( f \) que cumple con las condiciones de recurrencia.
Resta demostrar que hay sólo una tal \( f \).

Sea \( \tilde f \) otra posible función de \( N \) en \( X \)
que cumple con las relaciones de recurrencia\(  \tilde f(1)=\alpha, \tilde f(S(n))=G(n,\tilde f(n)) \).
Sea \( C \) el conjunto donde las imágenes de ambas funciones \( f, \tilde f  \) coinciden, o sea:
\( C=\{n\in N: f(n)=\tilde f(n)\}. \)

Claramente \( 1\in C \), porque \( f(1)=\alpha=\tilde f(1). \)
Supongamos que \( n\in C \).
En ese caso, tenemos que \( f(n)=\tilde f(n) \),
luego \( f(S(n)) = G(n,f(n))=G(n,\tilde f(n))= \tilde f(S(n)). \)
Por lo tanto también \( S(n)\in C. \)
Por el Principio de Inducción, resulta que \( C=N \).
Así que \( f=\tilde f \), como se deseaba demostrar.

[cerrar]

21 Julio, 2010, 05:15 am
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.2.
Explicación y aplicación del Primer Principio de Definición por Recurrencia.


Básicamente, el modo de aplicar este Principio consiste en dos pasos:
Primero, se le asigna un valor cualquiera a la función \( f(n) \), para \( n =1 \).
Luego se usa una función \( G \) de \( N\times X \) en \( X \)
para asignar valores a los sucesivos \( n=2,3,... \), etcétera,
mediante una regla tal que, si se conoce el valor de \( f(n) \),
entonces el valor de \( f(S(n)) \) queda automáticamente establecido.
Esto es \( G(n,f(n)) \), lo cual significa que
el valor de la función \( f \) asignado al "siguiente" de \( n \)
está dado por una "fórmula" \( G \),
que depende ahora tanto del mismo valor \( n \) como del valor de \( f \) en \( n \).

El Principio de recurrencia nos asegura que
al dar especificaciones de recurrencia de esta manera,
podemos estar seguros de que la función \( f \) así dada de verdad "existe",
y está bien definida, vale decir, no hay ambigüedad,
por cuanto hay una única \( f \) posible.

ETERNA CANCIÓN DE LA EXISTENCIA Y UNICIDAD:

En matemática, siempre que vayamos a dar una definición,
antes debemos estar seguros de que el objeto a definir existe y es único.

21 Julio, 2010, 05:20 am
Respuesta #2

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.3.
Sobre la "correcta" definición de "Sistema de Números Naturales".


Ahora voy a dar mi propia definición de lo que considero que debe ser
un sistema de números naturales, a través de una lista de Postulados.
Para aquellos que deseen comprender los motivos filosóficos
detrás de los Postulados que listaré a continuación,
enseguida colocamos la discusión pertinente.

¿Son los Axiomas de Peano lo que "define" un Sistema de Números Naturales?

En el siguiente Spoiler me pongo a divagar y discutir este asunto:

¿Qué es lo que "define" los Números Naturales?

Muchos argüirán que lo único que se necesita para desarrollar
la teoría de los números naturales son los Axiomas de Peano.

Estos Axiomas podrían llamarse también sistema de números naturales.
Pues bien, eso es cierto, como veremos en breve.

Pero uno bien puede dar una lista diferente de Axiomas de los números naturales,
y llegar a las mismas propiedades de la suma, el producto, etc. Así que,
¿cuáles son esas propiedades que todo sistema de números naturales
debiera cumplir, independientemente de cómo esté definido?


Primero adelantaré algunos hechos.
A partir de los Axiomas de Peano
y con la ayuda del Primer Principio de Definición por Recurrencia,
es posible "construir"
las operaciones "usuales" de suma y producto de números naturales,
con las propiedades a las que todos estamos acostumbrados,
y además se puede "construir" la relación de orden usual de los números naturales.

Esto quiere decir que los Axiomas de Peano permiten
"construir y demostrar"
todas las cuestiones que interesan de los números naturales,
y por lo tanto, todas estas propiedades que deseamos que se cumplan
no haría falta que figuren como "axiomas" de la teoría de numeros naturales,
ya que podemos obtenerlos más bien como Teoremas.
Si las pusiéramos como axiomas, habría redundancia,
un exceso de axiomas en la lista, que matemáticamente no parece deseable.


Pero hay otra verdad dando vueltas en el aire, y es que
no estamos obligados a iniciar nuestro trabajo con los Axiomas de Peano.
Si comenzáramos con otras propiedades,
podríamos llegar a los Axiomas de Peano vía una demostración,
o sea, el Principio de Inducción, por dar un ejemplo,
se convertiría en un Teorema, y cosas así.

Las propiedades que "nos gustan" de los números naturales,
son propiedades que debieran cumplirse siempre,
sin importar qué usemos como fundamento una lista más pequeña de Axiomas o no.

Lo que ocurre es que el "concepto" de número natural
no es lo mismo que algún sistema axiomático que tomemos por ahí.
El "concepto" de número natural consta de
todas aquellas propiedades de los números naturales que "nos gustan",
y que deben formar parte de la teoría,
sin importar otros detalles demasiado técnicos,
como la independencia de los axiomas utilizados,
que es una propiedad deseable, pero no es matemáticamente necesaria.

[cerrar]



Así que, para nosotros, y en lo que sigue, diremos que:

Una lista \( (N,1,S,+,\cdot, \leq) \) es un sistema de números naturales
si satisface los siguientes postulados:

  • Postulado 1. La terna \( (N, 1, S) \) satisface los Axiomas de Peano.

  • Postulado 2. La cuarteta \( (N,+,\cdot,1) \) satisface
    los Axiomas de un Semianillo ordenado con identidad 1 para el producto.
    Los detalles de lo que esto significa, abriendo el siguiente desplegable:

    Semianillo Ordenado con Identidad 1 para el producto

    La suma y el producto son asociativas:

    \( a,b,c\in N \Rightarrow{}\quad (a+b)+c=a+(b+c),\quad(a\cdot b)\cdot c=a\cdot (b\cdot c). \)

    La suma y el producto son conmutativos:

    \( a,b\in N \Rightarrow{}\quad a+b=b+a,\quad a\cdot b=b\cdot a. \)

    La suma no tiene elemento neutro, o sea,
    no existe \( \omega\in N \) tal que \( a+\omega=\omega \) (todo \( a\in N \)).

    El 1 es neutro para el producto:

    \( \forall{a\in N}:a\cdot1=a. \)

    La suma es una operación cancelativa.

    \( \forall{}a,b,c\in N:\quad a+b=a+c \Rightarrow{} b=c. \)

    El producto es una operación cancelativa.

    \( \forall{}a,b,c\in N:\quad a\cdot b=a \cdot c \Rightarrow{} b=c. \)

    El producto distribuye a la suma:

    \( \forall{}a,b,c\in N:\quad (a+b)\cdot c=a\cdot c+b\cdot c. \)


    En forma más resumida, tenemos que:

    • La dupla \( (N,+) \) es un semigrupo cancelativo sin elemento identidad.
    • La terna \( (N,\cdot,1) \) es un semigrupo cancelativo con identidad 1.
    • El producto distribuye a la suma.
    [cerrar]

  • Postulado 3. La dupla \( (N, \leq) \) es un sistema totalmente ordenado.
    Los detalles de lo que esto significa, abriendo el desplegable:

    Sistema totalmente ordenado

    • Reflexividad: Para todo \( a\in N: a \leq a \).
    • Antisimetría: Para todo \( a,b\in N: a \leq b,b \leq a \Rightarrow{a= b} \).
    • Transitividad: Para todo \( a,b,c\in N: a \leq b,b \leq c\Rightarrow{a \leq c} \).
    • Linealidad: Para todo \( a,b\in N: a\neq b\Rightarrow{a \leq b} \) ó \( b \leq a \).
    [cerrar]

  • Postulado 4. La relación \(  \leq \) es un buen orden en \( N \).
    Esto quiere decir que, para cualquier subconjunto no vacío \( A \) de \( N \),
    existe un elemento \( m\in A \) que es menor que todos los demás, o sea, \( a\in A \Rightarrow{m \leq a} \).

  • Postulado 5. La suma y el producto son monótonas respecto la relación de orden \(  \leq \).
    Esto quiere decir lo siguiente:

    • \( \forall{a,b,c\in N}a \leq b\Longleftrightarrow{}{a+c \leq b+c} \)
    • \( \forall{a,b,c\in N}a \leq b\Longleftrightarrow{}{a\cdot c \leq b\cdot c} \)

    (Notar el uso de \( \Longleftrightarrow{} \)).

  • Postulado 6. La operación de "sucesor" \( S \) está relacionada
    con la suma, el producto y la relación de orden mediante:

    • \( \forall{a\in N}:a+1=S(a) \)
    • \( \forall{a,b\in N}:a+S(b)=S(a+b) \)
    • \( \forall{a\in N}:a\cdot1=a \)
    • \( \forall{a,b\in N}:a\cdot S(b)=a\cdot b+a \)
    • \( \forall{a\in N}:a\neq S(a), a \leq S(a) \)
    • \( \forall{a,b\in N}:a\leq b \Rightarrow{} a\neq S(b),a \leq S(b) \)


21 Julio, 2010, 05:26 am
Respuesta #3

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Listar propiedades agradables mediante postulados o axiomas no nos asegura que lo que estamos definiendo existe realmente. Podría ser que estamos imaginando una estructura que matemáticamente podría carecer de sentido.

Así que, lo que haremos a continuación será demostrar que si la terna \( (N,1,S) \) satisface los Axiomas de Peano (Postulado 1), entonces existen operaciones de suma y producto, y una relación de orden en \( N \), de tal suerte que se cumplen las propiedades listadas en los Postulados 2, 3, 4, 5 y 6.

Subsección 1.4. Construcción de Suma, Producto para un Sistema de Números Naturales.

Se definen la suma y el producto en \( N \) por recurrencia, así:
\( m+1=S(m) \)
\( m+S(n)= S(m+n) \)

\( m\cdot 1= m \)
\( m\cdot S(n)=m\cdot n+m \)

El Primer Principio de Definición por Recurrencia nos asegura que esas operaciones están bien definidas, y están unívocamente determinadas. Dejamos al lector reflexionar sobre posibles detalles.

Con estas definiciones se pueden demostrar ahora todas las propiedades del Postulado 2.
La técnica para demostrar cada una de esas propiedades requiere usar el Principio de Inducción.
Probarlas a todas puede ser demasiado tedioso, porque se usan argumentos rutinarios y directos.

Mas, como un ejemplo del uso del principio de inducción, veamos cómo se prueba la ley cancelativa de la suma, abriendo el desplegable:

Prueba de que la suma es cancelativa en N.

Sea \( A \) el conjunto de todos aquellos \( a \in N \) tales que para cualesquiera \( m,n\in N \), vale la implicación:

\( m+a=n+a\Rightarrow{m=n} \)

O sea, \( a \) es un elemento que puede ser cancelado en una igualdad de sumas.
¿Hay alguno, varios, muchos, todos?
Veamos en primer lugar, como requiere el principio de inducción, que el elemento 1 está en \( A \):
Por hipótesis: \( m+1=n+1. \)
Por definición de suma: \( m+1=S(m),\quad n+1=S(n). \)
Luego: \( S(m)=S(n) \).
Como \( S \) es inyectiva, resulta \( m=n \).
Por lo tanto: \( 1\in A \).

Ahora aplicamos el paso inductivo, y supongamos que sabemos que un cierto elemento \( a \) está en \( A \).
Entonces, esto quiere decir que es cancelable en la suma, vale decir, para cualesquiera \( m,n\in N \), vale que:

\( m+a=n+a\Rightarrow{m=n} \)

Ahora analicemos el elemento \( S(a) \), y verifiquemos si también ha de estar en \( A \).
Para ello, partimos de la igualdad \( m+S(a)=n+S(a) \), con \( m,n\in N \) cualesquiera.
Por definición de suma, se tiene que:

\(  S(m+a)=m+S(a)=n+S(a)=S(n+a). \)

Como \( S \) es inyectiva, sigue necesariamente que \( m+a=n+a \).
Pero sabemos por hipótesis de inducción que \( a \) es cancelativo, así que \( m=n \).
Hemos probado pues que si \( a\in A \) entonces también \( S(a)\in A \).

Ahora aplicamos principio de inducción y se obtiene que \( A =N \), pero esto quiere decir que todos los elementos de \( N \) son cancelativos para la suma.

[cerrar]

21 Julio, 2010, 05:26 am
Respuesta #4

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.5. Función Sucesor e infinitud de un Sistema de Números Naturales.

La función \( S \) se llama sucesor. ¿Es sobreyectiva en \( N\setminus\{1\} \)?
De hecho, sí que lo es, como se muestre en el siguiente desplegable:

Prueba de la sobreyectividad de la función "sucesor".

Analicemos el asunto más despacio.
Si \( m \in N\setminus\{1\} \), ¿existe algún \( k \in N \) tal que \( S(k)=m \)?
Definamos el conjunto A mediante la siguiente propiedad:
"Un elemento \( m \) están en \( A \) si y sólo si \( m = 1 \) o bien existe \( k\in N \) tal que \( S(k)=m \)".
Obviamente, por mera definición, hemos impuesto que \( 1\in A \).
Ahora, supongamos que \( m \in N \) es tal que pertenece a \( A \). Analicemos si \( S(m) \) está en \( A \).
Es totalmente trivial, porque tomando \( k= m \) obtenemos que existe \( k\in N \) tal que \( S(k)= S(m) \).
Por lo tanto \( S(m)\in A \) y por principio de inducción \( A = N \).
Por definición de \( A \), todo elemento \( n \) de \( N \) distinto de 1 tiene un antecesor \( k \) tal que \( S(k)=m \).

Esto prueba que la función sucesor \( S \) es sobreyectiva.

[cerrar]

O sea que \( S \) es una biyección (porque ya era inyectiva) entre \( N \) y \( N\setminus\{1\} \), que es un subconjunto propio.
En particular, \( N \) resulta ser un conjunto infinito.

21 Julio, 2010, 05:26 am
Respuesta #5

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.6. Construcción de un Orden Total para los Números Naturales. Buen Orden.

Ahora bien, ¿están ordenados los elementos de \( N \)?
Respuesta: AÚN NO

En ninguna parte he definido un orden en \( N \).
Tengo que definir una noción de orden, si no, decir que "un elemento es menor que otro" es algo que no tiene sentido.
Así como tampoco lo tiene el decir que "cierto elemento de \( N \) es el primero de entre unos cuantos".

Defino que \( m  < n \) si existe algún \( k \in N \) tal que \( m+k=n \).
Defino que \( m   \leq n \) si \( m < n \) o si \( m = n \).

Eso me define, claramente, una relación entre elementos de \( N \).
Pero, ¿es realmente una relación de orden?
Para ello debe cumplir las propiedades reflexiva, antisimétrica y transitiva, las cuales se prueban en el desplegable que sigue:

Prueba de que < es efectivamente un orden en N.
  • Reflexiva: \( m \leq m \).
    La cumple trivialmente, por definición de  \( \leq \).

  • Antisimétrica: \( m \leq n, n \leq m\Rightarrow{ m=n} \).
    Esta propiedad la cumple, pues si \( m \leq n \), o bien existe \( k\in N \) tal que \( m+k=n \), o bien \( m=n \). Si \( m=n \), no hay nada más que probar, así que supongamos que \( m+k=n \).
    Además, como \( n \leq m \), se tiene que existe \( h\in N \) tal que \( n+h=m \) o bien \( n=m \).
    De nuevo, si \( m=n \), no hay nada más que probar, así que supongamos que \( n+h=m \).
    Tenemos ahora que \( n=m+k=(n+h)+k= n+(h+k) \) (por ley asociativa de la suma).
    Sumo 1 a ambos miembros, y obtengo: \( n+1 = n+(h+k+1) \) (propiedad uniforme y asociativa).
    Por lo tanto: \( 1 = h+k+1= S(h+k) \), por definición de suma.
    Pero el elemento 1 no está en la imagen de la función sucesor \( S \).
    Este absurdo muestra que habíamos partido de algo falso, o sea que necesariamente \( m=n \).

  • Transitiva: \( m \leq n,n \leq p\Rightarrow{m \leq p} \).
    Hay que separar en varios casos, según que haya o no igualdad.
    Voy a probar sólo el caso más complicado, en que hay desigualdad estricta, y los demás casos quedan como ejercicio.
    Estamos pues en la situación \( m<n \) y \( n<p \).
    Por definición de <, existen \( k,h\in N \) tales que \( m+k=n \) y \( n+h=p \).
    Defino \( j = k+h \).
    Ahora vemos que \( m+j=m+(k+h)=(m+k)+h=n+h=p \).
    Así que existe \( j\in N \) tal que \( m+j=p \).
    Por definición, esto es lo mismo que decir que \( m<p \).
    Luego \( m \leq p \).

[cerrar]

Para construir la noción de orden \( < \) en \( N \), hemos tenido que usar la noción de suma y sus propiedades (asociativa, cancelativa, conmutativa).
O sea que la noción de orden en N "no es trivial".

Una cosa que podemos decir ahora con más "relax" es lo que todos imaginamos:
\( 1<S(1)<S(S(1))<... \).

¿El orden  \( \leq \) es total?
Esto quiere decir que cualquier par de elementos \( m,n\in N \) es comparable, o sea, o bien \( m \leq n \), o bien \( n \leq m \).
Esto no es algo trivial. Debe usarse el principio de inducción para poder demostrarlo.
¿Qué significaría que el orden no es total? Pensarlo.  ???  ;)

En el siguiente desplegable probamos la totalidad del orden \(  \leq \):

El orden < es total. Demostración.

De manera trivial se prueba que \( 1 \leq m \) para todo \( m\in N \).
En efecto, si \( m \) no es 1, entonces, por ser S sobreyectiva, existe k tal \( S(k)=m \).
Luego \( m= S(k)=1+k \), por definición. Esto quiere decir que \( 1<m \), por definición de <.

Sea \( A \) el conjunto de todos los \( m\in N  \)tales que para todo \( n\in N \), o bien \( m \leq n \) o bien \( n \leq m \).
Por lo dicho antes, \( 1\in A \).
Ahora aplicamos hipótesis de inducción, suponiendo que \( m \) está en \( A \), y analizamos si también \( S(m)  \) está en \( A \).
Sea \( n\in A \) arbitrario. Por hipótesis inductiva, o bien \( n \leq m \) o bien \( m \leq n \).
Si \( n \leq m \), entonces, como \(  m  \leq S(m) \), por transitividad, resulta que \(  n \leq S(m) \), por lo tanto \( n \) y \( S(m) \) son comparables.
Si \( m \leq n \), podemos suponer que la desigualdad es estricta \( m<n \), pues el caso \( m=n \) está contemplado en el paso anterior.
Así, existe un \( k\in N \) tal que \( m+k=n \).
Si \( k=1 \), esto diría que \( S(m)=m+1=n \), con lo cual \( S(m) \) y \( n \) son trivialmente comparables.
Así que supongamos el caso en que \( k \) no es 1.
Sabemos que existe un antecesor para \( k \), digamos \( h\in N \), y escribimos \( S(h)=k \).
Se sigue que \( n=m+k=m+S(h)=S(m+h)=S(h+m)=h+S(m) \).
Hemos probado que existe \( h\in N \) tal que \( S(m)+ h = n \), y esto significa que \( S(m) < k \).

Así que, en cualquier caso, \( S(m) \) y \( n \) son comparables, y esto prueba que \( S(m) \) está en \( A \).

Por inducción, \( A = N \), lo cual significa que todos los elementos de \( N \) son comparables mediante la relación <.

O sea que < es un orden total.

[cerrar]

En todo esto hemos de notar que el orden de \( N \) ha sido construido.

El conjunto \( N \) no venía de fábrica con un orden total, sino que hay que definirlo, construirlo, y luego probar sus propiedades.

La relación de orden \(  \leq \) que hemos construido cumple, pues, con el Postulado 3.



A partir de aquí, mediante el uso del Principio de Inducción, se puede probar que el orden es monótono y cancelativo, tanto para la suma como para el producto en \( N \). Queda como ejercicio demostrar esto.
O sea, se puede probar que la relación \(  \leq \) que habíamos construido, satisface el Postulado 5.



Se puede probar que el orden de \( N \) es un buen orden.
Esto quiere decir que cualquier subconjunto \( A \) de \( N \), no vacío, tiene un elemento mínimo.
La prueba en el desplegable siguiente:

El orden de N es un "buen orden".
Para probarlo, un modo posible es suponer que no hay tal elemento mínimo y razonar por el absurdo.
Fijamos un elemento \( b \) de \( A \).
Se puede construir una sucesión estrictamente decreciente \( a_m \) de elementos de \( A \), menores estrictos que \( b \), con \( m \in N \).
Tenemos que \( a_b < ... < a_{2} < a_1 < b \).
Existen pues números \( x_m \in N \) de modo que \( a_{S(m)}+x_{S(m)} =a_m  \), para todo \( m\in N \).
Tenemos luego que \( b = a_1+x_1 = a_2 + x_2+x_1 = ...= a_b + x_b + ... + x_2 +x_1. \)
Como \( x_1,...,x_m \) son números naturales, son todos mayores o iguales que 1.
Resulta que \(  b +1 = (1+...+1)+1 \leq x_b + ... + x_2 +x_1 +a_b= ... = a_1+x_1 = b. \)
En resumen, \( b+1<b \), que es absurdo.

Así que ha de haber un elemento mínimo en \( A \): vale el buen orden de < en \( N \).

[cerrar]

Por lo tanto, nuestra relación de orden \(  \leq \) satisface el Postulado 4.



Mirando un poco las definiciones y hechos probados, encontraremos que la lista de propiedades listadas en el Postulado 6 también se cumplen.



Podemos resumir lo dicho en esta sección y las precedentes, diciendo:

A partir de los Axiomas de Peano puede construirse sobre el sistema \( (N,1,S) \) mismo, una estructura de números naturales.
O sea: el Postulado 1 implica los demás Postulados del 2 al 6.

Una moraleja que podemos extraer de aquí es la siguiente:
Si tenemos una lista de objetos \( (N,1,S,+,\cdot, \leq) \) tales que \( (N,1,S) \) satisface los Axiomas de Peano, tales que se cumplen las relaciones de recurrencia antes dadas para la suma y el producto, y tal que \( a \leq b \) significa \( a=b \) ó existe \( x\in N \) con \( a+x=b \), entonces \( (N,1,S,+,\cdot, \leq) \) es un sistema de números naturales.

O sea, no hace falta comprobar uno a uno todos los Postulados del 1 al 6, sino sólo las propiedades que hemos indicado.

21 Julio, 2010, 05:29 am
Respuesta #6

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.7. Existencia de varios Sistemas de Números Naturales.

¿Por qué he dicho "UN" sistema y no "EL" sistema?

Bueno, ocurre que cualquier terna \( N,1,S \) que cumpla los axiomas de Peano induce una estructura como la de "números naturales".
Para ilustrarlo, consideremos un "ejemplo" de \( N,1,S \), que en principio no tiene ninguna apariencia de ser un sistema de números naturales, y que sin embargo satisface todos los Axiomas (para detalles, abrir desplegable):

Un ejemplo contraintuitivo de sistema de "números naturales"

Tomamos un cuadrado \( X \) en el plano, lo dividimos en 4 partes iguales en forma "natural",
formando cuatro cuadrados iguales dentro de él, y nos quedamos con la esquina superior izquierda.
Definimos como \( S(X) \) (el siguiente del cuadrado \( X \)) a este cuadrado más pequeño de la esquina.
Queda definida una función \( S \) en la familia de todos los cuadrados del plano.

Fijamos uno de esos cuadrados, y lo llamamos "1" (elijamos uno que nos guste, y dejémoslo fijo de aqué en adelante).
Decimos que una familia de cuadrados \( \mathcal F \) es recurrente, si satisface estas dos condiciones:
  • El cuadrado prefijado, "1", está en la familia \( \mathcal F \).
  • Para todo cuadrado \( X \in \mathcal F \), el slguiente \( S(X) \) también está en \( \mathcal F \).


Existe al menos una familia recurrente de cuadrados no vacía, que es trivial. ¿cuál?: La familia de todos los cuadrados del plano, claro.
Ahora, consideremos la familia \( \mathcal R \) formada por todas las familias recurrentes \( \mathcal F \) de cuadrados. Como hay al menos una tal \( \mathcal F \), resulta que \( \mathcal R \) es no vacía.
Luego, tiene sentido hablar de la intersección de todos los elementos de la familia \( \mathcal R \), pues la intersección de una familia no vacía tiene sentido.
Llamemos \( N \) a esa intersección:
\( \displaystyle N=\bigcap_{\mathcal F\in\mathcal R} \mathcal F \)

Se puede probar que la intersección \( N \) es también un elemento de \( \mathcal R \), o sea, \( N \) es una familia recurrente de cuadrados. Demostración: Ejercicio.

Más aún, \( N \) es no vacío, porque contiene al elemento "1".
También \( N \) es minimal: si \( A \) es una familia recurrente de cuadrados contenida en \( N \), entonces \( A = N \).
El conjunto \( A \) de todos los elementos de \( N \) que son subconjuntos del cuadrado "1" es también una familia recurrente de cuadrados, y está contenida en \( N \), o sea que \( A = N \).
Esto quiere decir que no hay en \( N \) cuadrados que contengan estrictamente al "1".

Ahora, "1" no puede estar en la imagen de \( N \).
Si lo estuviera, habría un cuadrado \( c\in N \) tal que \( S(c) \) = "1".
Pero un tal cuadrado \( c \) contendría estrictamente al "1", y hemos dicho que cuadrados como estos no pueden estar en \( N \).

Claramente, la función \( S \) es inyectiva, y además, para todo elemento \( q \) de \( N \), vale que \( S(q)\in N \).
Pero también sabemos que "1" no está en la imagen de \( S \).


Así que tenemos:
  • La familia de cuadrados "N" es un conjunto no vacío.
  • El cuadrado "1" está en N.
  • La función \( S \) que transforma un cuadrado en su "siguiente", está definida de \( N \) en \( N\setminus\{\textsf{"1"}\} \).
  • La función \( S \) es inyectiva.
  • Si \( A \) es un subconjunto no vacío de \( N \), que es familia recurrente de cuadrados, entonces \( A = N \).
La última propiedad es el principio de inducción en la familia de cuadrados.
En efecto: Como \( A \) es familia recurrente de cuadrados, "1" ha de estar en \( A \).
Además, si \( c \) es un cuadrado que está en \( A \), entonces su "siguiente" \( S(c) \) también está en \( A \), por definición de familia recurrente.
Pero entonces, como \( N \) es minimal, y \( A\subset N \), necesariamente ocurre que \( A = N \).
En resumen:
  • Si \( A \) es subconjunto de \( N \), "1" está en \( A \), y si cada vez que \( c \) está en \( A \) implica que \( S(c) \) está en \( A \), entonces \( A = N \).

Así que estos cuadrados satisfacen los Axiomas de Peano de los números naturales.
[cerrar]

Con ideas similares pueden definirse infinidad de sistemas que sean "sistemas de números naturales".



Sin embargo, no hay peligro de confusión.
Se puede considerar que todos los sistemas de números naturles son, en esencia, el mismo.
Esto lo probaremos en el siguiente post.

21 Julio, 2010, 05:31 am
Respuesta #7

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.8. Unicidad Algebraica del Sistema de Números Naturales.

Si \( (N,1,S,+_N,\cdot_N, \leq_N) \) y \( (N',1',S',+_{N'},\cdot_{N'}, \leq_{N'}) \) son sistemas de números naturales, entonces:
  • \( N \) y \( N' \) tienen el mismo cardinal.
  • Existe un isomorfismo que transforma \( N \) en \( N' \) de manera que se conservan las operaciones de suma y producto, y también se conserva el orden \( < \). Es un isomorfismo algebraico y ordinal.

Demostración

Sea \( f:N\to N' \) una función definida por recurrencia de la siguiente manera:
\( f(1) = 1' \).
\( f(S(n)) = S'(f(n)), n\in N. \)
Hay que usar inducción en \( N \) para probar que \( f \) es inyectiva.
Luego se usa la inducción en \( N' \) para probar que \( f \) es sobreyectiva.
Esta construcción es válida por el Principio de definición por recurrencia, el cual es consecuencia del principio de inducción.

Esta función además sirve como "isomorfismo algebraico", pues se puede probar, otra vez por inducción, que:
\( f(a+_N b) =f(a)+_{N'}f(b) \)
\( f(a\cdot_N b) =f(a)\cdot_{N'}f(b) \)
\( f^{-1}(\alpha +_{N'} \beta ) =f^{-1}(\alpha )+_{N}f^{-1}(\beta ) \)
\( f^{-1}(\alpha \cdot_{N'} \beta ) =f^{-1}(\alpha )\cdot_{N}f^{-1}(\beta ) \)

También es un isomorfismo ordinal, pues:
\( a<_N b\Rightarrow{f(a)<_{N'}f(b)}. \)
\( \alpha <_{N'} \beta \Rightarrow{f^{-1}(\alpha )<_{N}f^{-1}(\beta )}. \)

[cerrar]

21 Julio, 2010, 05:33 am
Respuesta #8

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.9. Otros comentarios sobre los Números Naturales.

Por último, mostremos otro orden que se usa en \( N \).

Así como hemos definido \( m < n \) en términos de la suma, se puede definir un orden en términos del producto.
Decimos que \( m  \curlyeqprec n \) si existe \( k\in N \) tal que \( m\cdot k=n \) (o sea, \( m \) divide a \( n \)).

Queda como ejercicio probar que \( \curlyeqprec \) es un orden: es reflexiva, antisimétrica y transitiva.

Sin embargo, no es un orden total, pues hay pares de números no comparables con esa relación:
Por ejemplo 3 y 5 no son comparables, pues ninguno de ellos divide al otro.

En este caso, se dice que el orden es parcial.



Un último comentario, que puede ser importante.

Tenemos que \( 2= S(1), 3 = S(S(1)) \), etc.
O sea, esa sería la definición de los signos 2, 3, 4, 5, etc.

Estamos acostumbrados a pensar que esta "secuencia" de los números es lo que "define el orden de los números naturales".

Pero entonces debemos tener claro que una "secuencia" no necesariamente define un orden en un conjunto dado.

Supongamos el conjunto de restos módulo 5:    \( X = \{0, 1, 2, 3, 4\} \)
Debido a las propiedades de los restos, se tiene que 4+1 es congruente con 0 módulo 5.
O sea, que si usamos la suma módulo 5 como operación en \( X \), tenemos que:

\( 0+1 = 1, \quad 1+1=2, \quad 2+1 = 3, \quad 3+1 = 4,\quad 4+1= 0. \)

Claramente, tenemos la secuencia 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, etc., que se vuelve a repetir indefinidamente.
Pero ahora, no puedo usar esa secuencia como "base" para definir un orden en \( X \).
La razón es que resultaría un orden demasiado trivial: todo elemento de \( X \) es menor que todo otro elemento de \( X \).
Por ejemplo, 3 sería menor que 1, pues 3 es menor que 4, 4 menor que 0 (pues 0 es el "siguiente" de 4 en la secuencia), y 0 es menor que 1. Por transitividad: 3 < 1.
Esto ocurre porque la secuencia es "circular", claro.

Así que no podemos "confiarnos" de la "enumeración secuencial" o del "orden secuencial".

El hecho de que el "orden secuencial" de los números naturales sirva de base para una relación de orden con "pleno sentido", radica en que en \( N \) vale el principio de inducción.
Al combinar la función "siguiente" con el principio de inducción, la secuencia definida en \( N \) da lugar a un orden correcto, que no es "circular".

A su vez, dicho principio de inducción es equivalente al Principio de buena ordenación de \( N \).
Estas relaciones son más o menos fáciles de probar, pero su significado es no trivial.
Conviene reflexionar un poco sobre todo ello.



Otra propiedad del orden es que entre un número \( m \) y su siguiente \( S(m) \) no hay elementos de \( N \) intermedios, o sea, no hay \( n\in N \) tal que: \( m <n < S(m) \).

Si lo hubiera, tendríamos algún \( k \) tal que \( m + k = n < S(m) = m + 1 \).
Por cancelación, resultaria que \( k < 1 \), que es absurdo.

21 Julio, 2010, 05:37 am
Respuesta #9

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Principal * N Z Q R C +


Subsección 1.10. Construcción de un ejemplo de Sistema de Números Naturales.

Hasta ahora hemos discutido varias propiedades de los Sistemas de Números Naturales, pero no hemos probado que existe al menos un "objeto" matemático que cumpla dichas propiedades.
O sea, hasta ahora no hemos demostrado que de verdad "existe" un Sistema de Números Naturales.

Esta cuestión conlleva profundos problemas filosóficos, sin embargo nosotros podemos "patear el problema debajo de la alfombra", ya que nos conformaremos con "construir" un sistema de números naturales "asumiendo" que la Teoría de Conjuntos estándar es válida (se conoce como Teoría de Zermelo-Fraenkel).
Así que no nos preocupemos aquí de cuestiones demasiado profundas.



Hemos probado que los Postulados del 2 al 6 son consecuentes con (por ser consecuencia de) los Axiomas de Peano.
Así que podemos reducir ciertas discusiones de fundamento de la teoria de números naturales al mero estudio de los Áxiomas de Peano. Por ejemplo, nos preguntamos si existe algún ejemplo de sistema matemático que cumpla los Postulados de un Sistema de Números Naturales. Esto se reduce a preguntar si existe algún sistema matemático que satisfaga los Axiomas de Peano.

Vamos a dar varios ejemplos, pero el primero de todos será el que se obtiene directamente a partir de los Axiomas de la Teoría de Conjuntos. En el desplegable van los detalles:

Modelo de N basado directamente en la Teoría de Conjuntos

El objeto más básico de esta teoría es el conjunto vacío \( \emptyset \), es decir, aquel conjunto que no contiene elemento alguno.
Dada una lista finita \( a, b, c, d,  \), etc., de objetos de la teoría de conjuntos, se puede construir un conjunto que tenga a esos objetos como elementos, y se lo denota \( \{a,b,c,d,...\} \).
Dado un objeto \( x \) cualquiera, podemos formar el conjunto unitario que contiene sólo a \( x \), y se denota \( \{x\} \).
Podemos formar, a partir del conjunto vacío, ciertos conjuntos que contengan al vacío como elemento, y luego otros que contengan al vacío y al conjunto recién definido, etc.
O sea, podemos ir construyendo sucesivamente estos conjuntos:

\( \{\emptyset\} \)
\( \{\emptyset,\{\emptyset\}\} \)
\( \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \)
...

y así continuamos iterativamente.

Lo que se puede hacer en este momento es "bautizar" a esos conjuntos con los signos que solemos usar para los números naturales.
Así, tendríamos:

\( 1=\{\emptyset\} \)
\( 2=\{\emptyset,\{\emptyset\}\} \)
\( 3=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \)
etcétera.

Este acto de "bautizar" no ofrece ninguna ventaja matemática, o sea, no demuestra nada.
En todo caso, lo importante es haber elegido a uno de esos conjuntos como el objeto que va a tener significado de "1" en el futuro modelo de números naturales.
O sea, lo importante es que hemos identificado el signo 1 con el conjunto \( 1=\{\emptyset\} \).
Definimos la operación "sucesor" para todo conjunto \( x \), mediante la siguiente fórmula:

\( S(x)=x\cup \{x\}. \)

Es decir, formamos el conjunto unitario que contiene a \( x \), y lo unimos al mismo \( x \).
Así que el nuevo conjunto \( S(x) \) contiene a todos los elementos que contenía \( x \), y además el mismo \( x \) se vuelve un elemento de \( S(x) \).

Es claro que podemos ir formando los sucesivos conjuntos \( \{\emptyset\}, S(\{\emptyset\}), S(S(\{\emptyset\})),  \) etc. Mas, como hemos identificado \( 1=\{\emptyset\} \), escribimos la lista como \( 1, S(1), S(S(1)) \).

Muy bien, parece que somos capaces de "generar" todos los números naturales con esta idea, usando sólo conjuntos.
Pero hay un problema, y es que desearíamos estar seguros de que hay un conjunto \( N \) que contiene a todos los números naturales.
¿Existe un conjunto que contenga como elementos a \( 1, S(1), S(S(1)) \), etc.?
Eso no puede asegurarse así nada más, y entonces se apela al Axioma del Infinito, que dice lo siguiente:

Existe un conjunto \( X \) que contiene como elementos a \( \{\emptyset\} \), y además, para todo elemento \( n \) que está en \( X \), también contiene a \( S(n) \).

Ahora bien, tomando la intersección de todos los conjuntos que cumplen con esas propiedades, se obtiene el "mínimo" conjunto posible \( X \) tal que \( \{\emptyset\}\in X \), y además, para todo elemento \( n \) que estuviera en \( X \), también \( S(n) \) estará en \( X \).
Si llamamos \( N \) a ese conjunto \( X \) "mínimo", la terna \( (N,1,S) \) satisfará los Axiomas de Peano.
Los detalles de la demostración los dejamos a cuidado del lector interesado.
Nos llevaría demasiado tiempo desarrollar esto aquí.

[cerrar]

Con al menos un modelo en mano de los números naturales, estamos ahora seguros de que el sistema de Axiomas de Peano, así como la lista de Postulados de los números naturales, tienen sentido matemático, pues la teoría no es vacía.

14 Septiembre, 2012, 01:07 am
Respuesta #10

Marcos Castillo

  • Héroe
  • Mensajes: 1,831
  • País: sd
  • Karma: +0/-0
  • Sexo: Masculino
Hola, argentinator. Estoy leyendo un libro que habla de los números naturales, y para definir con rigor la suma en \( \mathbb{N} \), necesito primero entender la Demostración del Primer Principio de Definición por Recurrencia que usted explica en este thread. Ha sido Carlos Ivorra, quien también participa en este foro, el que me ha aconsejado que lea lo que escribió.
El caso es que me han surgido unas dudas, porque soy un principiante (estoy estudiando por mi cuenta, al tiempo que trabajo, el grado en matemáticas de la Universidad Nacional de Educación a Distancia, y estoy en el primer curso).
Me gustaría contar con usted para, en unos pocos mensajes, terminar entendiendo la Demostración del Primer Principio de Definición por Recurrencia.
Para empezar voy a citarle en unas líneas que escribió, posteriores a la citada Demostración:

"Explicación y aplicación del Primer Principio de Definición por Recurrencia.

Básicamente, el modo de aplicar este Principio consiste en dos pasos:
Primero, se le asigna un valor cualquiera a la función \( f(n) \), para \( n =1 \).
Luego se usa una función \( G \) de \( N\times X \) en \( X \)
para asignar valores a los sucesivos \( n=2,3,... \), etcétera,
mediante una regla tal que, si se conoce el valor de \( f(n) \),
entonces el valor de \( f(S(n)) \) queda automáticamente establecido.
Esto es \( G(n,f(n)) \), lo cual significa que
el valor de la función \( f \) asignado al "siguiente" de \( n \)
está dado por una "fórmula" \( G \),
que depende ahora tanto del mismo valor \( n \) como del valor de \( f \) en \( n \)."

La pregunta es: ¿podría definir la suma en \( \mathbb{N} \), aplicando paso a paso lo que dice en el párrafo citado?; ¿ en qué momento se echa mano de \( G \) y de qué forma?; ¿por qué hace falta \( G \)?; ¿cuál es la naturaleza de \( G \)?; ¿es una función que a un par de números asigna un único número?.
Un saludo. :D
No man is an island (John Donne)

14 Septiembre, 2012, 03:27 am
Respuesta #11

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
La pregunta es: ¿podría definir la suma en \( \mathbb{N} \), aplicando paso a paso lo que dice en el párrafo citado?; ¿ en qué momento se echa mano de \( G \) y de qué forma?; ¿por qué hace falta \( G \)?; ¿cuál es la naturaleza de \( G \)?; ¿es una función que a un par de números asigna un único número?.
Un saludo. :D

Hola Marcos.

Estos son temas que me gustan bastante, así que siempre me hago un tiempo para esto.
Intentaré ayudarte lo más que pueda.

Tu pregunta sobre la función G es importante.

Por un lado, expliquemos la "idea" de la definición por recurrencia.
La "idea" es que uno quiere definir una función con dominio \( \mathbb{N} \),
a partir de una regla de recurrencia.

Esa regla se suele colocar en los textos matemáticos de un modo informal.

Por ejemplo, para definir la potenciación con exponente natural, se hace así:

\( a^0=1, a^{n+1}=a^n\cdot a \).

Ahí, la regla de recurrencia indica que uno "ya supone definida" la potencia de exponente n, y la aprovecha para definir la de exponente n+1.

Ahora bien, en matemática uno necesita ser preciso, utilizando correctamente el formato de la lógica y la teoría de conjuntos. Esto es lo que entendemos por formalización.
La formalización, o escritura formal, se requiere para evitar ambigüedades, imprecisiones, circularidades, y toda serie de "pecados matemáticos".

Así que lo que se requiere es "formalizar" la regla de recurrencia de un modo que sea "preciso", usando la teoría de conjuntos estándar, por ejemplo.

Hay dos posibilidades para definir formalmente una "regla": usar una relación o usar una función.
Lo adecuado en este caso es usar una función, porque las funciones asignan valores de forma unívoca, y esto nos aseguraría que la regla de recurrencia está dada de forma también unívoca, vale decir, sin ambigüedades.

Así que \( G \) será nuestra regla de recurrencia que, formalizada, tomará forma de una cierta función.

El inconveniente acá es que, ya que hablamos de funciones, la  \( G \) tiene que estar bien definida como tal.
Para ello debemos respetar el aspecto formal de toda función: una función bien definida tiene un dominio y un codominio, que son ciertos conjuntos previamente especificados.

Es decir que, para definir la regla de recurrencia, necesitamos que previamente haya estos conjuntos bien concretos y previamente establecidos con los cuales definir la regla.

____________

¿Cuáles serían ese dominio y ese codominio?

En general, si la función de recurrencia \( f  \) que se desea definir, es \( f:\mathbb{N}\to X \), para un conjunto dado \( X \), la regla de recurrencia \( G \) "haría" más o menos esto:

\( f(n+1)=G(...algo....) \)

(aún no he explicado qué es el "algo" que va en el argumento de la G).

Si te fijás con cuidado, sin importar qué hace la \( G \), ni qué es el "algo" a lo cual se aplica,
es claro que el valor que se obtiene ha de asignarse a \( f(n+1) \), que a su vez es una función con valores en \( X \).

Eso muestra claramente que lo "sensato" es que \( G \) sea una función con codominio \( X \), ya que allí han de "caer" sus valores.

_________

En cuanto al "algo", lo que vemos en toda regla de recurrencia (sencilla) es que al valor \( f(n+1) \) se lo hace depender del número natural \( n \), y también del valor que \( f \) toma en \( n \), es decir \( f(n) \). Pero \( f(n) \) es elemento de \( X \).

Así que el "algo" tiene que tener en cuenta números naturales \( n \) así como valores de \( X \).

Por otra parte, no hay manera de que la regla de recurrencia sea capaz de predecir la relación entre \( n \) y \( f(n) \) antes de definir la función de recurrencia \( f \).

Por lo tanto, la regla \( G \) tiene que depender "libremente" tanto de \( n\in\mathbb N \) como de \( x\in X \).
Así, \( G(n,x) \) tiene que estar definida con claridad para todo \( n\in\mathbb N \) y todo \( x\in X \).

Por ello, el dominio de \( G \) termina siendo \( \mathbb{N}\times X \).

O sea que \( G \) es ahora una función \( G:\mathbb N\times X\to X \).

____________

La regla \( G \) ha de ser independiente en su declaración de la "futura" función de recurrencia \( f \).
Es decir, por una lado se indica la regla, y por otro lado se hace la definición por recurrencia a través del uso de la regla indicada.

_______________


Con respecto a la suma de números naturales, como el resultado será de nuevo un número natural, tenemos que el conjunto \( X \) coincide ahora con el mismo \( \mathbb N \).

Además, yo no usaría una sola recurrencia, sino muchas, para definir la suma.
Veamos.

Supongamos que \( m\in\mathbb N \) es un número natural prefijado.
Voy a definir una función \( f_m:\mathbb{N}\to\mathbb{N} \) por recurrencia, de la siguiente manera:

La regla de recurrencia \( G \) sería:

\( G:\mathbb{N}\times{\mathbb{N}}\to\mathbb{N},\qquad G(n,x)=S(x). \)

\( f_m(1)=S(m) \), es decir, el siguiente de \( m \).
\( f_m(n+1)=G(n,f_m(n))=S(f_m(n)) \)

Como se ve, la regla de recurrencia \( G \) es sencilla en este caso, ya que no aparece una dependencia explícita de \( n \).

Ahora, para cada \( m \) fijo hemos definido una función \( f_m \).

La suma de números naturales puede definirse ahora así:

\( m+n=f_m(n). \)

__________

De manera algo más formal, lo que hemos hecho es definir una sucesión de funciones
\( \{f_m\}_{m\in\mathbb{N}} \), con dominio y codominio \( \mathbb{N} \)
cada una con su propia relación de recurrencia.

En realidad la regla de recurrencia usada para todas ellas es la misma (\( G(n,x)= S(x) \)), y sólo ha cambiado el valor inicial dado a cada una. (\( f_m(1) \)).


14 Septiembre, 2012, 11:07 pm
Respuesta #12

Marcos Castillo

  • Héroe
  • Mensajes: 1,831
  • País: sd
  • Karma: +0/-0
  • Sexo: Masculino
Hola, argentinator
Muchas gracias por tu respuesta a mi duda. He entendido todo lo que has dicho. Pero todavía tengo dudas respecto a la Demostración del Primer Principio de Definición por Recurrencia. He avanzado un poco y me he encontrado con la siguiente duda. Primero te cito:


Supongamos ahora el caso en que \( S(n) \) no pertenece a \( D \).
En tal situación, construiremos una función \( h_1 \) de la siguiente manera:
Definimos \( D_1 = D\cup\{S(n)\} \),
y hacemos que \( h_1 \) sea una función con dominio \( D_1 \), dada por:

\( h_1(k)=\begin{Bmatrix} h(k) & \mbox{ si }& k\in D\\G(n,h(n)) & \mbox{si}& k=S(n)\end{matrix} \).

Mostremos que \( h_1 \in K_\alpha. \)

En efecto, sea \( k\in N \) tal que \( S(k)\in D_1 \).
Si \( k\neq n \), entonces necesariamente \( S(k)\in D \), el dominio de \( h \),
y esto significa que \( k\in D \),
y además \( h(S(k))=G(k,h(k)) \).
Pero también, como \( k,S(k)\in D \), la definición de \( h_1 \) nos da
que \( h_1(S(k))=h(S(k))=G(k,h(k))=G(k,h_1(k)) \).

Por otra parte, si \( k=n \), recordemos que
teníamos al principio de todo que \( n \) es un elemento de \( D \) (pues \( (n,y)\in h\subset f \)),
luego \( h_1(n)=h(n) \), y por definición: \( h_1(S(n))=G(n,h(n))=G(n,h_1(n)). \)
Esto prueba que \( h_1 \in K_\alpha. \)
Por lo tanto, \(  h_1 \subset f \), y esto quiere decir que existe \( z\in X \) tal que \( (S(n),z)\in f. \)

En cualquier caso, hemos probado que existe \( z\in X \) tal que \( (S(n),z)\in f. \)
Esto indica que \( S(n)\in A \).

En resumen, tenemos que \( 1\in A \) y \( n\in A\Rightarrow{S(n)\in A} \).
Aplicando Principio de Inducción, obtenemos que \( A=N \).
Por lo tanto, para todo \( n\in N \),
existe algún \( z\in X \) tal que \( (n,z)\in f. \)

Dices que si \( k\neq{n} \), entonces necesariamente \( S(k)\in{D} \). ¿Cuál es en este caso \( n \) y \( k \)?; ¿cómo es que \( S(k)\in{D} \)?. Además, ¿cómo es \( h_1 \)?. Muchas gracias de antemano. Ya ves que estoy un poco pez; es el primer obstáculo consistente con el que me he encontrado.
No man is an island (John Donne)

14 Septiembre, 2012, 11:26 pm
Respuesta #13

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

Dices que si \( k\neq{n} \), entonces necesariamente \( S(k)\in{D} \). ¿Cuál es en este caso \( n \) y \( k \)?; ¿cómo es que \( S(k)\in{D} \)?. Además, ¿cómo es \( h_1 \)?. Muchas gracias de antemano. Ya ves que estoy un poco pez; es el primer obstáculo consistente con el que me he encontrado.

Lo que ocurre es que ahí se tenía además la condición \( S(k)\in D_1 \).
Como \( D_1=D\cup \{S(n)\} \), tenemos que \( S(k)\in D \) o bien \( S(k)\in \{S(n)\} \).
Si se diera el último caso, necesariamente sería \( S(k)= S(n) \).
Por ser \( S \) una función inyectiva, se obtiene que \( k=n \).
Pero esto contradice la hipótesis de que \( k\neq n \).

Por lo tanto el caso \( S(k)=S(n) \) no es posible, y sólo puede suceder que \( S(k)\in D \).

Los valores de \( k,n \) vienen tomados unos párrafos arriba.

La función \( h_1 \) lo que hace es tomar "la" función \( h \), que tiene como dominio un cierto conjunto \( D \), y le agrega un elemento al dominio, y también un elemento al codominio.
Fijate que además la función \( h_1 \) coincide con \( h \) para los valores \( k\in D \). Y luego se usa la regla de recurrencia para definir el valor de \( h_1 \) en el nuevo elemento agregado al dominio.

Lo que interesa de \( h_1 \) es demostrar que es, al igual que \( h \), una función que pertenece a la familia \( K_\alpha \).

Hay aspectos de la demostración que son muy técnicos,
es decir que resulta difícil visualizarlos, o construirlos.

Me parece que la clave del asunto es tratar de entender por qué se exigen a la familia \( K_\alpha \) las propiedades que se le han pedido.
Es decir, si uno quisiera demostrar el Teorema de Recurrencia sin usar las funciones recursivas h de la clase \( K_\alpha \), ¿podría?

La cosa se complica, y tiene esto que ver conque, al parecer, hace falta un juego previo entre el valor de \( h \) en cada \( n \) y el valor de \( h \) en el siguiente de \( n \).
No se sabe si existen funciones de recurrencia \( h \), y si existen, tampoco se conoce su dominio completo  \( D \).
Así que se define un conjunto que sea la unión de todas las \( h \) que se comportan como uno desea, y luego uno intenta probar que esa unión no es un conjunto cualquiera, sino que sigue siendo una función, y que su dominio es todo N.


14 Septiembre, 2012, 11:35 pm
Respuesta #14

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Voy a leer con más detenimiento este hilo, me parece extremadamente interesante. Curiosamente la idea de la demostración del principio de definición por recurrencia es la misma que aquí.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

14 Septiembre, 2012, 11:49 pm
Respuesta #15

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Hola Pablo. Voy a leer el enlace que has puesto.

Tan sólo creo conveniente aclarar que las demostraciones que yo pongo en este hilo, si bien no se las he copiado a nadie, y me salen "naturalmente" (por viejo que soy), en realidad no son originales mías, sino que se sabe que el modo de trabajar es "así".
Si se buscan libros donde esté demostrado el Teorema de Recurrencia, se verá que las demostraciones siguen las mismas líneas que yo (por ejemplo, ver Topología General, Kelley, Capítulo 0).

15 Septiembre, 2012, 11:17 pm
Respuesta #16

Marcos Castillo

  • Héroe
  • Mensajes: 1,831
  • País: sd
  • Karma: +0/-0
  • Sexo: Masculino
Hola, argentinator:
Ya he entendido el Primer Principio de Definición por Recurrencia. Me ha costado cuatro días, pero ya estoy en condiciones de definir por recurrencia cosas como por ejemplo la suma de números naturales. En el libro que estoy leyendo (y del que ahora me fío un poco menos), decía literalmente:
Citar
Suma en \( \mathbb{N} \)
La suma de números naturales se define por recurrencia utilizando el axioma \( A_5 \) (aquí se refiere al Principio de Inducción).
Definición 5.1. Se define por recurrencia sobre \( n \) la suma \( m+n \) mediante:
1. \( m+0=m \) para todo \( m\in{\mathbb{N}} \).
2. \( m +s(n)=s(m+n) \) para todo \( m,n\in{\mathbb{N}} \).
.
Para definir por recurrencia, sin embargo, hace falta un teorema de recursión, para el que a su vez, y en este caso, hacen falta los axiomas de Peano (y no solo el Principio de Inducción, como menciona el libro).
En resumen, que muchas gracias, argentinator!
No man is an island (John Donne)

15 Septiembre, 2012, 11:52 pm
Respuesta #17

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
El Teorema de Recursión se deduce del Principio de Inducción... aunque los otros axiomas de Peano también participan.

Todos los axiomas son importantes, pero el Principio de Inducción es el más importante de todos, y es interesante notar que no se necesitan axiomas extra para deducir el de Recursión.

Bueno, suerte con tus estudios.
Nos estamos viendo.

P.D.: Hay un Segundo Teorema de Recurrencia, que tiene una forma algo más complicada, y que puede deducirse una vez que ya se han demostrado varios hechos acerca de los números naturales.
Este Segundo Teorema no lo he enunciado aún en este hilo, y me queda como una tarea pendiente.
Sirve para definiciones por recurrencia más interesantes.


15 Marzo, 2016, 08:23 pm
Respuesta #18

dcarballor

  • Nuevo Usuario
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
Buenas tardes.
Me gustaría preguntar lo siguiente:
En la subsección 1.4 se define la suma empleando la función S. La función S está en los axiomas. ¿Por qué necesito el principio de definición por recurrencia para concluir que la suma existe y está definida? ¿No es suficiente con que lo esté S (y lo está pues me lo creo a partir de los axiomas)?
Gracias de antemano si alguien responde.
Un saludo.

15 Marzo, 2016, 08:35 pm
Respuesta #19

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
La respuesta es sí y no a la vez.

El Principio de Definición por Recurrencia se deduce lógicamente como un Teorema a partir de los Axiomas, por lo tanto no es un supuesto adicional, sino que es los Axiomas son suficientes para justificar ese Principio.

Y luego se usa Recurrencia para definir la Suma por una cuestión de comodidad,
y porque resulta más natural hacerlo así.

Como el Principio de Recurrencia se deduce de los Axiomas, no haría falta mencionarlo explícitamente, pero en el medio habría que hacer algo parecido.

La cuestión aquí es que la Suma se define como "la única función de 2 variables en N que satisface las relaciones de recurrencia" que se muestran en la Sección 1.4.

Ahora hay que preguntarse dos cosas: cuando decimos "la única", ¿existe al menos alguna cosa que satisfaga eso?, y si existe, ¿de verdad es la única?

Esta existencia y unicidad viene garantizado por el Principio de Recurrencia,
y por eso se lo usa.
Si no lo quieres usar, tendrás que garantizar la existencia y unicidad de la suma por algún camino similar, pero a fin de cuentas tendrás implícitamente la misma deducción que se hace para probar el Principio de Recurrencia.

----------------

Si no, lo único que podrías hacer es definir la suma para un conjunto finito de casos,
uno a uno, usando la función S, y sería complicado saltar al caso de los infinitos números naturales.

------------

No sé si esto te aclara algo tu pregunta.