Autor Tema: Definición recursiva de suma de cualquier sucesión finita de números naturales

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

26 Junio, 2020, 11:20 am
Leído 141 veces

Eparoh

  • Aprendiz
  • Mensajes: 242
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, estoy estudiando el libro "Introduction to set theory" (Third revised edition) de Karel Hrbacek and Thomas Jech y estoy atascado con el ejercicio 4.9 del capítulo 3.
El ejercicio dice:

Para cada sucesión finita \( \langle k_i: 0 \leq i < n \rangle \) de números naturales define \( \sum \langle k_i: 0 \leq i < n \rangle \) tal que:

 1. \( \sum\langle \rangle=0 \)
 2. \( \sum\langle k_0 \rangle=k_0 \)
 3. \( \sum\langle k_i: 0 \leq i <n \rangle = \sum\langle k_i: 0 \leq i <n-1 \rangle +k_n \) para cada \( n \geq 1 \)

Se que la idea es definir de forma recursiva una función tal que, para cualquier sucesión finita de números naturales devuelva su suma, con lo que he estado intentando encontrar alguna forma de utilizar el Teorema de Recursión, para a partir de este conseguir definir la función \( \sum: Seq(\mathbb{N}) \longrightarrow \mathbb{N} \) que satisfaga las condiciones 1 y 3 (pues de ellas se deriva la 2 creo), pero no he sido capaz de hacerlo.
¿Alguna idea de como encontrar esta aplicación \( \sum \)?

Dejo un enlace a google books, donde están los primeros capítulos del libro. De la página 46 a las 52 se habla sobre el teorema de recursión y se dan varias versiones de éste, y el ejercicio por el que pregunto en concreto está en la página 55.

Un saludo y muchas gracias por las respuestas.

Ps. \( Seq(\mathbb{N}) \) es el conjunto de todas las sucesiones finitas de números naturales que ya demostré previamente que existe.

26 Junio, 2020, 01:45 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 1,430
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Una idea: usa la versión paramétrica del teorema de recursión (Teorema 3.6) con \( P=Seq(\Bbb N) \), \( A= \Bbb N \), \( a:Seq(\Bbb N) \to \Bbb N \) dada por \( a(p)=0 \) y \( g:Seq(\Bbb N) \times \Bbb N \times \Bbb N \to \Bbb N \) dada por \( g(p,m,n)= m + p(n)  \) si \( n < len(p) \) y \( g(p,m,n)=0 \) en otro caso.
El teorema de recursión te da una aplicación \( f:Seq(\Bbb N) \times \Bbb N \to \Bbb N \) que cumple:
\( f(p,0)= 0 \)
\( f(p,n+1)=f(p,n) + p(n) \) (si \( n<len(p) \)).
Si ahora defines \( \Sigma: Seq(\Bbb N) \to \Bbb N \) como \( \Sigma(p) = f(p,len(p)) \), ya lo tienes.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

27 Junio, 2020, 11:49 am
Respuesta #2

Eparoh

  • Aprendiz
  • Mensajes: 242
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Una idea: usa la versión paramétrica del teorema de recursión (Teorema 3.6) con \( P=Seq(\Bbb N) \), \( A= \Bbb N \), \( a:Seq(\Bbb N) \to \Bbb N \) dada por \( a(p)=0 \) y \( g:Seq(\Bbb N) \times \Bbb N \times \Bbb N \to \Bbb N \) dada por \( g(p,m,n)= m + p(n)  \) si \( n < len(p) \) y \( g(p,m,n)=0 \) en otro caso.
El teorema de recursión te da una aplicación \( f:Seq(\Bbb N) \times \Bbb N \to \Bbb N \) que cumple:
\( f(p,0)= 0 \)
\( f(p,n+1)=f(p,n) + p(n) \) (si \( n<len(p) \)).
Si ahora defines \( \Sigma: Seq(\Bbb N) \to \Bbb N \) como \( \Sigma(p) = f(p,len(p)) \), ya lo tienes.

¡Muchas gracias!
Llevaba dandole vueltas unos días, y lo había intentado con una función \( g \) parecida, aunque no lograba llegar a ésta que propones.
Aun así, para demostrar lo que deseaba, he tenido que probar un pequeño resultado auxiliar, que es el siguiente:

Lema: Dados \( p, q \in Seq(\Bbb N) \) si \( n \leq len(q)<len(p) \) y \( p(k)=q(k) \) para cada \( k < n \) entonces \( f(p,n)=f(q,n) \)

Demostración:
Por inducción sobre \( n \), si \( n=0 \) es claro ya que f(p,0)=0=f(q,0), luego supongamos que el lema es cierto para \( n \) y veamos que también lo es para \( n+1 \).
Sin más, si son \( q,p \in Seq(\Bbb N) \) tales que \( n+1 \leq len(q)<len(p) \) y con \( p(k)=q(k) \) para cada \( k < n+1 \), entonces

\( f(p,n+1)=f(p,n)+p(n)\underset{HI}{=}f(q,n)+p(n)=f(q,n)+q(n)=f(q,n+1) \)
y concluimos la inducción.

Este lema lo he necesitado en la siguiente cadena de igualdades (en la cuarta igualdad en concreto)

\( \sum\langle k_0, \cdots, k_{n+1} \rangle = f\left(\langle k_0, \cdots, k_{n+1} \rangle, n+2 \right)=f\left(\langle k_0, \cdots, k_{n+1} \rangle, (n+1)+1 \right)=f\left(\langle k_0, \cdots, k_{n+1} \rangle, n+1 \right)+k_{n+1}=f\left(\langle k_0, \cdots, k_{n} \rangle, n+1 \right)+k_{n+1}=\sum \langle k_0, \cdots, k_{n} \rangle + k_{n+1} \)

No se si usar este lema es el camino más corto, pero si no me he equivocado en algo, creo que es correcta la demostración así.

Un saludo.

27 Junio, 2020, 12:59 pm
Respuesta #3

geómetracat

  • Moderador Global
  • Mensajes: 1,430
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sí, veo bien tanto el lema como la demostración. Sí que parece necesario demostrar un lema de ese estilo.
La ecuación más bonita de las matemáticas: \( d^2=0 \)