Autor Tema: [Dem][texx]\sum_{}^{n}[/texx] es el conjunto de todas las cadenas de longitud n

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

01 Julio, 2017, 12:56 am
Leído 1283 veces

dresuer

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 119
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Prueba que para todo [texx]n \in \mathbb{N}, \sum_{}^{n}{}[/texx] es el conjunto de todas las cadenas sobre [texx]\sum_{}{}{}[/texx] de longitud [texx]n[/texx].

Ya sé que tengo que hacerlo por inducción pero tengo muchas dudas de como plantear la proposición.

Yo sé que:
[texx]\sum_{}^{n}{} = \left\{xp \mid x \in \sum_{}^{}{}, p \in  \sum_{}^{n-1}{} \right\}[/texx]

Pero lo que yo quiero probar es que cada cadena del alfabeto [texx]\sum_{}^{n}{}[/texx]  tiene longitud [texx]n[/texx]

Es decir [texx]\sum_{}^{n}{} = \left\{ a_1,a_2,...,a_n  \mid a_i \in \sum_{}{}{} \right\}[/texx], donde [texx]||a_1|| = ||a_2|| = ... = ||a_n|| = n.[/texx]

Mmm no lo sé tengo muchas dudas, ¿cómo debería plantear la proposición para probarlo por inducción?

03 Julio, 2017, 11:32 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Prueba que para todo [texx]n \in \mathbb{N}, \sum_{}^{n}{}[/texx] es el conjunto de todas las cadenas sobre [texx]\sum_{}{}{}[/texx] de longitud [texx]n[/texx].

Ya sé que tengo que hacerlo por inducción pero tengo muchas dudas de como plantear la proposición.

Yo sé que:
[texx]\sum_{}^{n}{} = \left\{xp \mid x \in \sum_{}^{}{}, p \in  \sum_{}^{n-1}{} \right\}[/texx]

Pero lo que yo quiero probar es que cada cadena del alfabeto [texx]\sum_{}^{n}{}[/texx]  tiene longitud [texx]n[/texx]

Es decir [texx]\sum_{}^{n}{} = \left\{ a_1,a_2,...,a_n  \mid a_i \in \sum_{}{}{} \right\}[/texx], donde [texx]||a_1|| = ||a_2|| = ... = ||a_n|| = n.[/texx]

Mmm no lo sé tengo muchas dudas, ¿cómo debería plantear la proposición para probarlo por inducción?

Me resulta confusa la notación que usas.

En principio el resultado me parece directo por definición.

Una cadena sobre \( \sigma \) de longitud \( n \) es un conjunto ordenado de \( n  \) símbolos de \( \sigma \) y por definición eso es un elemento \( (a_1,a_2,\ldots,a_n) \) del producto carterisano:

\( \sigma^n=\underbrace{\sigma\times \sigma\times \ldots\times \sigma}_{n\textsf{ veces}} \)

Saludos.

03 Julio, 2017, 11:39 pm
Respuesta #2

dresuer

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 119
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

A mi también me resulta confusa porque en el apunte define

Citar
[texx]\sum_{}^{n} := \left\{ xp \mid x \in \sum_{}, p \in \sum_{}^{n-1} \right\}[/texx]

donde xp es la yuxtaposición del carácter x con la cadena p.

Veamos, a traves del siguiente ejemplo que [texx]\sum_{}^{n}[/texx] está constituido por todas las cadenas sobre [texx]\sum_{}[/texx] con n caracteres.

Luego muestra un ejemplo donde define un alfabeto [texx]\sum_{} = \left\{ a,b \right\}[/texx]

Y define [texx]\sum_{}^{2} \sum_{}^{3} ... [/texx]

Para mi con la definición: [texx]\sum_{}^{n} := \left\{ xp \mid x \in \sum_{}, p \in \sum_{}^{n-1} \right\}[/texx] es obvio que tienen n carácteres.

No sé, no lo entiendo muy bien, un compañero lo hizo así:

[texx]P(n): \sum_{}^{n} = \left\{ a_1,...,a_n \mid a_i \in \sum_{}, \forall i=1,...,n \right\}
\\
P(1): \sum_{}^{1}= \left\{a_1 \mid a_1 \in \sum_{} \right\} = \sum_{}[/texx]

Supongo que es cierta para [texx]P(n)[/texx] pruebo para [texx]P(n+1)[/texx]
Tesis: [texx]P(n+1): \sum_{}^{n+1} = \left\{a_1,a_2,...,a_n,a_{n+1} \mid a_i \in \sum_{}, \forall i = 1,...,n+1 \right\}[/texx]

Prueba:
[texx]\sum_{}^{n+1} \stackrel{Def.}{=}  \left\{ xp \mid x \in  \sum_{} , p \in \sum_{}^{n} \right\} \stackrel{HIP.}{=} [/texx]

[texx]
p \in \sum_{}^{n} = \left\{ a_1, ..., a_n \right\}[/texx]
 donde [texx]p = a_1,...,a_n[/texx],  [texx]a_i \in \sum_{}[/texx]

[texx]
= \left\{ xp \mid x \in \sum_{} , p = a_1, ..., a_n ; a_i \in \sum_{} \forall i = 1,..., n \right\} = \\
= \left\{ x a_1 a_2 ... a_n \mid x,a_i \in \sum_{} \forall i = 1,...,n \right\}
\\[/texx]

[texx]
\therefore P(n+1)[/texx] es verdadero.
[texx]
\therefore P(n)[/texx] es verdadero [texx]\forall n \in \mathbb{N}[/texx]

Pero esta demostración no me cerraba bien, ahora la voy a volver a pensar porque estaba haciendo otros ejercicios y te comento lo que pienso.

Saludos.

04 Julio, 2017, 09:51 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 La clave es saber exactamente (cono total rigurosidad):

i) cómo te han definido \( \displaystyle\Sigma^n. \)
ii) cómo te han definido las cadenas de longitud \( n \) sobre \( \displaystyle\Sigma. \)

 Aparentemente (i) según lo que escribes te lo ha definido de manera recursiva:

[texx]\sum_{}^{n+1} \stackrel{Def.}{=}  \left\{ xp \mid x \in  \sum_{} , p \in \sum_{}^{n} \right\} \stackrel{HIP.}{=} [/texx]


 Pero no me queda clara la diferencia entre la propia definición de  \( \displaystyle\Sigma^n \) y la de  cadenas de longitud \( n \) sobre \( \displaystyle\Sigma. \)

 Es esencial que entiendas que para construir una demostración es necesario saber de que hablamos, dicho de otra manera, partir de unas definiciones sólidas, precisas.

Saludos.

04 Julio, 2017, 05:53 pm
Respuesta #4

dresuer

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 119
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
https://dcc.fceia.unr.edu.ar/sites/default/files/uploads/materias/Unidad_1.pdf

A partir de la página 5 habla de cadenas y no definió nada de cadenas de longitud n, creo que todavía me hace confundir más y eso que leí todo el apunte. De todos modos este ejercicio no es tan importante como los que siguen.

A mi también me hace confundir y sólo esa demostración las demás las hice y las entiendo.

08 Julio, 2017, 09:45 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

https://dcc.fceia.unr.edu.ar/sites/default/files/uploads/materias/Unidad_1.pdf

A partir de la página 5 habla de cadenas y no definió nada de cadenas de longitud n, creo que todavía me hace confundir más y eso que leí todo el apunte. De todos modos este ejercicio no es tan importante como los que siguen.

A mi también me hace confundir y sólo esa demostración las demás las hice y las entiendo.

Después de leer el documento me reafirmo en que no hay nada que demostrar.

Te están definiendo cadena de longitud \( n \) sobre \( \Sigma \) como una yuxtaposición de caracteres \( a_1a_2\ldots a_n \) donde cada \( a_i\in \Sigma \). Pero precisamente te aclaran en la discusión previa que eso no es más que una notación abreviada para la función:

\( f:\{1,2,\ldots,n\}\longrightarrow{}\Sigma,\qquad f(i)=a_i \)

y por definición de producto cartesiano, el conjunto de funciones de \( \{1,2,\ldots,n\} \) a \( \Sigma \) es precisamente \( \Sigma^n \).

Saludos.