12/11/2019, 03:36:04 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1] 2   Ir Abajo
  Imprimir  
Autor Tema: C. Sists. Numéricos. --- Sección 1: Números Naturales  (Leído 8459 veces)
0 Usuarios y 1 Visitante están viendo este tema.
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« : 21/07/2010, 12:13:03 am »

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 [texx]N, 1, S,[/texx] sujetos a los siguientes axiomas:

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

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 [texx]X[/texx] un conjunto no vacío, y
sea [texx]G:N\times X\to X[/texx] una función dada.
Sea además [texx]\alpha[/texx] un elemento dado de [texx]X[/texx].
Bajo tales condiciones, existe una, y sólo una función [texx]f:N\to X[/texx]
que satisface las siguientes relaciones de recurrencia:

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

En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #1 : 21/07/2010, 12:15:34 am »

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 [texx]f(n)[/texx], para [texx]n =1[/texx].
Luego se usa una función [texx]G[/texx] de [texx]N\times X[/texx] en [texx]X[/texx]
para asignar valores a los sucesivos [texx]n=2,3,...[/texx], etcétera,
mediante una regla tal que, si se conoce el valor de [texx]f(n)[/texx],
entonces el valor de [texx]f(S(n))[/texx] queda automáticamente establecido.
Esto es [texx]G(n,f(n))[/texx], lo cual significa que
el valor de la función [texx]f[/texx] asignado al "siguiente" de [texx]n[/texx]
está dado por una "fórmula" [texx]G[/texx],
que depende ahora tanto del mismo valor [texx]n[/texx] como del valor de [texx]f[/texx] en [texx]n[/texx].

El Principio de recurrencia nos asegura que
al dar especificaciones de recurrencia de esta manera,
podemos estar seguros de que la función [texx]f[/texx] así dada de verdad "existe",
y está bien definida, vale decir, no hay ambigüedad,
por cuanto hay una única [texx]f[/texx] 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.
En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #2 : 21/07/2010, 12:20:50 am »

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:




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

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

  • Postulado 1. La terna [texx](N, 1, S)[/texx] satisface los Axiomas de Peano.

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


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

    Spoiler: Sistema totalmente ordenado (click para mostrar u ocultar)

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

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

    • [texx]\forall{a,b,c\in N}a \leq b\Longleftrightarrow{}{a+c \leq b+c}[/texx]
    • [texx]\forall{a,b,c\in N}a \leq b\Longleftrightarrow{}{a\cdot c \leq b\cdot c}[/texx]

    (Notar el uso de [texx]\Longleftrightarrow{}[/texx]).

  • Postulado 6. La operación de "sucesor" [texx]S[/texx] está relacionada
    con la suma, el producto y la relación de orden mediante:

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

En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #3 : 21/07/2010, 12:26:10 am »

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 [texx](N,1,S)[/texx] satisface los Axiomas de Peano (Postulado 1), entonces existen operaciones de suma y producto, y una relación de orden en [texx]N[/texx], 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 [texx]N[/texx] por recurrencia, así:
[texx]m+1=S(m)[/texx]
[texx]m+S(n)= S(m+n)[/texx]

[texx]m\cdot 1= m[/texx]
[texx]m\cdot S(n)=m\cdot n+m[/texx]

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:

En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #4 : 21/07/2010, 12:26:46 am »

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 [texx]S[/texx] se llama sucesor. ¿Es sobreyectiva en [texx]N\setminus\{1\}[/texx]?
De hecho, sí que lo es, como se muestre en el siguiente desplegable:


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

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #5 : 21/07/2010, 12:26:56 am »

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 [texx]N[/texx]?
Respuesta: AÚN NO

En ninguna parte he definido un orden en [texx]N[/texx].
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 [texx]N[/texx] es el primero de entre unos cuantos".

Defino que [texx]m  < n[/texx] si existe algún [texx]k \in N[/texx] tal que [texx]m+k=n[/texx].
Defino que [texx]m   \leq n[/texx] si [texx]m < n[/texx] o si [texx]m = n[/texx].

Eso me define, claramente, una relación entre elementos de [texx]N[/texx].
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:


Para construir la noción de orden [texx]<[/texx] en [texx]N[/texx], 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:
[texx]1<S(1)<S(S(1))<...[/texx].

¿El orden  [texx]\leq[/texx] es total?
Esto quiere decir que cualquier par de elementos [texx]m,n\in N[/texx] es comparable, o sea, o bien [texx]m \leq n[/texx], o bien [texx]n \leq m[/texx].
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.  :¿eh?:  :guiño:

En el siguiente desplegable probamos la totalidad del orden [texx] \leq[/texx]:

Spoiler: El orden < es total. Demostración. (click para mostrar u ocultar)

En todo esto hemos de notar que el orden de [texx]N[/texx] ha sido construido.

El conjunto [texx]N[/texx] 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 [texx] \leq[/texx] 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 [texx]N[/texx]. Queda como ejercicio demostrar esto.
O sea, se puede probar que la relación [texx] \leq[/texx] que habíamos construido, satisface el Postulado 5.



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

Spoiler: El orden de N es un "buen orden". (click para mostrar u ocultar)

Por lo tanto, nuestra relación de orden [texx] \leq[/texx] 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 [texx](N,1,S)[/texx] 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 [texx](N,1,S,+,\cdot, \leq)[/texx] tales que [texx](N,1,S)[/texx] satisface los Axiomas de Peano, tales que se cumplen las relaciones de recurrencia antes dadas para la suma y el producto, y tal que [texx]a \leq b[/texx] significa [texx]a=b[/texx] ó existe [texx]x\in N[/texx] con [texx]a+x=b[/texx], entonces [texx](N,1,S,+,\cdot, \leq)[/texx] 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.
En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #6 : 21/07/2010, 12:29:43 am »

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 [texx]N,1,S[/texx] que cumpla los axiomas de Peano induce una estructura como la de "números naturales".
Para ilustrarlo, consideremos un "ejemplo" de [texx]N,1,S[/texx], 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):


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.

* 20100721-argentinator-cuadrados-recurrentes.png (5.13 KB - descargado 1251 veces.)
En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #7 : 21/07/2010, 12:31:18 am »

Principal * N Z Q R C +


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

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

Spoiler: Demostración (click para mostrar u ocultar)
En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #8 : 21/07/2010, 12:33:03 am »

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 [texx]N[/texx].

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

Queda como ejercicio probar que [texx]\curlyeqprec[/texx] 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 [texx]2= S(1), 3 = S(S(1))[/texx], 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:    [texx]X = \{0, 1, 2, 3, 4\}[/texx]
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 [texx]X[/texx], tenemos que:

[texx]0+1 = 1, \quad 1+1=2, \quad 2+1 = 3, \quad 3+1 = 4,\quad 4+1= 0.[/texx]

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 [texx]X[/texx].
La razón es que resultaría un orden demasiado trivial: todo elemento de [texx]X[/texx] es menor que todo otro elemento de [texx]X[/texx].
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 [texx]N[/texx] vale el principio de inducción.
Al combinar la función "siguiente" con el principio de inducción, la secuencia definida en [texx]N[/texx] 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 [texx]N[/texx].
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 [texx]m[/texx] y su siguiente [texx]S(m)[/texx] no hay elementos de [texx]N[/texx] intermedios, o sea, no hay [texx]n\in N[/texx] tal que: [texx]m <n < S(m)[/texx].

Si lo hubiera, tendríamos algún [texx]k[/texx] tal que [texx]m + k = n < S(m) = m + 1[/texx].
Por cancelación, resultaria que [texx]k < 1[/texx], que es absurdo.
En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #9 : 21/07/2010, 12:37:04 am »

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:


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.
En línea

Marcos Castillo
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.712


Ver Perfil
« Respuesta #10 : 13/09/2012, 08:07:02 pm »

Hola, argentinator. Estoy leyendo un libro que habla de los números naturales, y para definir con rigor la suma en [texx]\mathbb{N}[/texx], 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 [texx]f(n)[/texx], para [texx]n =1[/texx].
Luego se usa una función [texx]G[/texx] de [texx]N\times X[/texx] en [texx]X[/texx]
para asignar valores a los sucesivos [texx]n=2,3,...[/texx], etcétera,
mediante una regla tal que, si se conoce el valor de [texx]f(n)[/texx],
entonces el valor de [texx]f(S(n))[/texx] queda automáticamente establecido.
Esto es [texx]G(n,f(n))[/texx], lo cual significa que
el valor de la función [texx]f[/texx] asignado al "siguiente" de [texx]n[/texx]
está dado por una "fórmula" [texx]G[/texx],
que depende ahora tanto del mismo valor [texx]n[/texx] como del valor de [texx]f[/texx] en [texx]n[/texx]."

La pregunta es: ¿podría definir la suma en [texx]\mathbb{N}[/texx], aplicando paso a paso lo que dice en el párrafo citado?; ¿ en qué momento se echa mano de [texx]G[/texx] y de qué forma?; ¿por qué hace falta [texx]G[/texx]?; ¿cuál es la naturaleza de [texx]G[/texx]?; ¿es una función que a un par de números asigna un único número?.
Un saludo. :cara_de_queso:
En línea

No man is an island (John Donne)
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #11 : 13/09/2012, 10:27:34 pm »

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

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 [texx]\mathbb{N}[/texx],
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í:

[texx]a^0=1, a^{n+1}=a^n\cdot a[/texx].

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 [texx]G[/texx] 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  [texx]G[/texx] 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 [texx]f [/texx] que se desea definir, es [texx]f:\mathbb{N}\to X[/texx], para un conjunto dado [texx]X[/texx], la regla de recurrencia [texx]G[/texx] "haría" más o menos esto:

[texx]f(n+1)=G(...algo....)[/texx]

(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 [texx]G[/texx], ni qué es el "algo" a lo cual se aplica,
es claro que el valor que se obtiene ha de asignarse a [texx]f(n+1)[/texx], que a su vez es una función con valores en [texx]X[/texx].

Eso muestra claramente que lo "sensato" es que [texx]G[/texx] sea una función con codominio [texx]X[/texx], 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 [texx]f(n+1)[/texx] se lo hace depender del número natural [texx]n[/texx], y también del valor que [texx]f[/texx] toma en [texx]n[/texx], es decir [texx]f(n)[/texx]. Pero [texx]f(n)[/texx] es elemento de [texx]X[/texx].

Así que el "algo" tiene que tener en cuenta números naturales [texx]n[/texx] así como valores de [texx]X[/texx].

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

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

Por ello, el dominio de [texx]G[/texx] termina siendo [texx]\mathbb{N}\times X[/texx].

O sea que [texx]G[/texx] es ahora una función [texx]G:\mathbb N\times X\to X[/texx].

____________

La regla [texx]G[/texx] ha de ser independiente en su declaración de la "futura" función de recurrencia [texx]f[/texx].
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 [texx]X[/texx] coincide ahora con el mismo [texx]\mathbb N[/texx].

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

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

La regla de recurrencia [texx]G[/texx] sería:

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

[texx]f_m(1)=S(m)[/texx], es decir, el siguiente de [texx]m[/texx].
[texx]f_m(n+1)=G(n,f_m(n))=S(f_m(n))[/texx]

Como se ve, la regla de recurrencia [texx]G[/texx] es sencilla en este caso, ya que no aparece una dependencia explícita de [texx]n[/texx].

Ahora, para cada [texx]m[/texx] fijo hemos definido una función [texx]f_m[/texx].

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

[texx]m+n=f_m(n).[/texx]

__________

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

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

En línea

Marcos Castillo
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.712


Ver Perfil
« Respuesta #12 : 14/09/2012, 06:07:20 pm »

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 [texx]S(n)[/texx] no pertenece a [texx]D[/texx].
En tal situación, construiremos una función [texx]h_1[/texx] de la siguiente manera:
Definimos [texx]D_1 = D\cup\{S(n)\}[/texx],
y hacemos que [texx]h_1[/texx] sea una función con dominio [texx]D_1[/texx], dada por:

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

Mostremos que [texx]h_1 \in K_\alpha.[/texx]

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

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

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

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

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

No man is an island (John Donne)
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #13 : 14/09/2012, 06:26:25 pm »


Dices que si [texx]k\neq{n}[/texx], entonces necesariamente [texx]S(k)\in{D}[/texx]. ¿Cuál es en este caso [texx]n[/texx] y [texx]k[/texx]?; ¿cómo es que [texx]S(k)\in{D}[/texx]?. Además, ¿cómo es [texx]h_1[/texx]?. 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 [texx]S(k)\in D_1[/texx].
Como [texx]D_1=D\cup \{S(n)\}[/texx], tenemos que [texx]S(k)\in D[/texx] o bien [texx]S(k)\in \{S(n)\}[/texx].
Si se diera el último caso, necesariamente sería [texx]S(k)= S(n)[/texx].
Por ser [texx]S[/texx] una función inyectiva, se obtiene que [texx]k=n[/texx].
Pero esto contradice la hipótesis de que [texx]k\neq n[/texx].

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

Los valores de [texx]k,n[/texx] vienen tomados unos párrafos arriba.

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

Lo que interesa de [texx]h_1[/texx] es demostrar que es, al igual que [texx]h[/texx], una función que pertenece a la familia [texx]K_\alpha[/texx].

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 [texx]K_\alpha[/texx] 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 [texx]K_\alpha[/texx], ¿podría?

La cosa se complica, y tiene esto que ver conque, al parecer, hace falta un juego previo entre el valor de [texx]h[/texx] en cada [texx]n[/texx] y el valor de [texx]h[/texx] en el siguiente de [texx]n[/texx].
No se sabe si existen funciones de recurrencia [texx]h[/texx], y si existen, tampoco se conoce su dominio completo  [texx]D[/texx].
Así que se define un conjunto que sea la unión de todas las [texx]h[/texx] 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.

En línea

pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.353


Ver Perfil
« Respuesta #14 : 14/09/2012, 06:35:15 pm »

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í.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #15 : 14/09/2012, 06:49:42 pm »

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).
En línea

Marcos Castillo
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.712


Ver Perfil
« Respuesta #16 : 15/09/2012, 06:17:20 pm »

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:
Cita
Suma en [texx]\mathbb{N}[/texx]
La suma de números naturales se define por recurrencia utilizando el axioma [texx]A_5[/texx] (aquí se refiere al Principio de Inducción).
Definición 5.1. Se define por recurrencia sobre [texx]n[/texx] la suma [texx]m+n[/texx] mediante:
1. [texx]m+0=m[/texx] para todo [texx]m\in{\mathbb{N}}[/texx].
2. [texx]m +s(n)=s(m+n)[/texx] para todo [texx]m,n\in{\mathbb{N}}[/texx].
.
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!
En línea

No man is an island (John Donne)
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #17 : 15/09/2012, 06:52:13 pm »

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.

En línea

dcarballor
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 5


Ver Perfil
« Respuesta #18 : 15/03/2016, 04:23:50 pm »

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.
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.276

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #19 : 15/03/2016, 04:35:23 pm »

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.
En línea

Páginas: [1] 2   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!