[pierrot]

Hola. Voy a plantear mi duda mediante un ejemplo. Es un ejercicio, dice así:

Considere el alfabeto \( \Sigma=\{a,b,c\} \) y el lenguaje \( \Gamma\subset{}\Sigma^* \) definido como:

\( \begin{array}{ll} \mbox{ i } & \epsilon\in \Gamma \\ \mbox{ ii }& a\in \Gamma\\ \mbox{ iii }& \mbox{Si $\alpha\in \Gamma$ y $\beta\in \Gamma$, entonces $b \alpha c\beta b\in \Gamma$} \end{array} \)

Aclaración

Respecto a la notación, \( \epsilon \) representa la palabra vacía, y \( \Sigma^* \) es el conjunto de todas las palabras que se pueden formar a partir del alfabeto \( \Sigma \).
Además cuando se da un conjunto definido por reglas, ha de interpretarse como el menor conjunto que satisface dichas reglas. Volveré sobre ese punto al final.
Otra cosa que creo oportuno aclarar, es que en la definición dada \( \alpha \) y \( \beta \) son metavariables que representan cualquier palabra de \( \Gamma \). No son elementos del alfabeto.

[cerrar]

Demuestre, usando el principio de inducción que corresponda, que:

[1] todas las palabras de \( \Sigma \) tienen una cantidad par de ocurrencias de la letra \( b \).
[2] en \( \Gamma \) no hay palabras de largo 2.
[3] en \( \Gamma \) hay palabras de cualquier largo, salvo 2.

Entonces lo que hago es enunciar el principio de inducción primitva para \( \Gamma \) (por cada conjunto inductivo, tendré un principio de inducción primitiva distinto):

Sea \( P \) una propiedad sobre los elementos de \( \Gamma \) tal que se cumple:

1. \( P(\epsilon) \)
2. \( P(a) \)
3. Si \( P(\alpha) \) y \( P(\beta) \) para \( \alpha,\beta\in \Gamma \), entonces \( P(b \alpha c\beta b) \)

En las hipótesis anteriores, se cumple \( P(\alpha) \) para todo \( \alpha\in \Gamma \).

En [1] la propiedad a probar es \( \textrm{$P_1(\alpha)$ := $\alpha$ tiene una cantidad par de ocurrencias de la letra $b$} \) y en [2] \( \textrm{$P_2(\alpha)$ := $\alpha$ no tiene largo $2$} \). Ambas se pueden demostrar usando el teorema enunciado anteriormente. En cambio, [3] no es una propiedad referida sobre los elementos de \( \Gamma \) (creo yo) sino sobre los números naturales. Es decir, la propiedad sería \( \textrm{$P_3(n)$ := existe una palabra $\alpha\in \Gamma$ tal que el largo de $\alpha$ es $n$} \), y habría que probar que se cumple \( P_3(0) \), \( P_3(1) \) y \( P_3(n) \) para todo \( n\geq 3 \).

Creo que la demostración que ellos buscan serían algo así. Definimos el conjunto \( S \) como:

\( \begin{array}{ll} \mbox{ i) } & 0\in S \\ \mbox{ ii) }& 1\in S\\ \mbox{ iii) }& \mbox{Si $n\in S$ y $m \in S$, entonces $(3+n+m) \in S$} \end{array} \)

Ahora enunciamos el correspondiente principio de inducción primitiva para \( S \):

Sea \( P \) una propiedad sobre los elementos de \( S \) tal que se cumple:

1. \( P(0) \)
2. \( P(1) \)
3. Si \( P(n) \) y \( P(m) \) para \( n,m\in S \), entonces \( P(3+n+m) \)

En las hipótesis anteriores, se cumple \( P(n) \) para todo \( n\in S \).

Usando este principio podemos estructurar la demostración así:

Demostración del apartado 3

Alcanza con probar:

Paso base 1: ¿Se cumple \( \textrm{$P_3(0)$ := existe una palabra $\alpha\in \Gamma$ tal que el largo de $\alpha$ es $0$} \)? Sí, tomamos \( \alpha\equiv{}\epsilon \) (la palabra vacía tiene largo 0 y pertenece a \( \Gamma \) por \( \textrm{i} \)).

Paso base 2: ¿Se cumple \( \textrm{$P_3(1)$ := existe una palabra $\alpha\in \Gamma$ tal que el largo de $\alpha$ es $1$} \)? Sí, tomamos \( \alpha\equiv{}a \) (la palabra \( a \) tiene largo 1 y pertenece a \( \Gamma \) por \( \texrm{ii} \)). Hay que aclarar en este punto que se está tomando \( a \) como palabra y no como elemento (o letra) del alfabeto.

Paso inductivo: Asumimos \( P_3(n) \) y \( P_3(m) \) para ciertos \( n,m\in S \) (podría ser eventualmente \( n=m \), no importa) y hay que probar \( P_3(3+m+n) \). La demostración es simpe. Por hipótesis inductiva sabemos que existe una palabra \( \alpha_1\in \Gamma \) tal que el largo de \( \alpha_1 \) es \( n \) y que existe otra palabra \( \alpha_2\in \Gamma \) tal que el largo de \( \alpha_2 \) es \( m \). Por la regla \( \textrm{iii} \) de construcción de \( \Gamma \) sabemos que \( b\alpha_1 c \alpha_2 b\in \Gamma \) y el largo de esta palabra es el largo de \( \alpha_1 \) más el largo de \( \alpha_2 \) más tres, ya que esta nueva palabra tiene, además de las letras que conforman a \( \alpha_1 \) y \( \alpha_2 \), a las letras \( b,c,b \). En consecuencia, tenemos que la palabra \( b\alpha_1 c \alpha_2 b \) (que sabemos que pertenece al lenguaje \( \Gamma \) por \( \textrm{iii} \)) tiene \( 3+n+m \) letras, por lo tanto es cierto \( P_3(3+n+m) \) que es lo que se quería probar.

[cerrar]

Ahora bien, por el principio de inducción primitiva para \( S \) sabemos que la propiedad se cumple para todo \( n\in S \). Pero nosotros queríamos probar que la propiedad se cumplía para todos los naturales menos el 2. ¿No habría que demostrar formalmente que \( S=\mathbb{N}-\{2\} \)? ¿Cómo sería tal demostración?

En el teórico nos dijeron: "Se puede definir el conjunto de los números naturales \( \mathbb{N} \) mediante las siguientes reglas:"

\( \begin{array}{ll} \mbox{ I } & 0\in \mathbb{N} \\ \mbox{ II } & \mbox{Si $n\in \mathbb{N}$, entonces $n+1\in \mathbb{N}$} \end{array} \)

Ahora bien, \( \mathbb{N} \) no es el único conjunto que satisface \( \textrm{I} \) y \( \textrm{II} \), pues por ejemplo \( \mathbb{Z} \) o \( \mathbb{Q} \) también las satisfacen. Me han constestado que en realidad, cada vez que se da un conjunto inductivo por reglas, ha de interpretarse como el menor conjunto que satisface dichas reglas. ¿Pero menor en qué sentido? Intuyo que debe referirse a que sólo lo integran los elementos comunes a todos los conjuntos que cumplen con las reglas. O dicho de otra manera, si \( \mathcal{A} \) representa la familia de todos los conjuntos que cumplen simultáneamente con \( \textrm{I} \) y \( \textrm{II} \), se estaría definiendo \( \mathbb{N}=\bigcap_{A\in \mathcal{A}}A \). ¿Es ésto correcto? En caso de serlo, ¿cómo se corrobora ese hecho? Hmmm aunque si se toma por definición, es así y punto. No hay nada que demostrar. En tal caso, ¿es ésa es una definición válida de los naturales? ¿Coincide con la idea intuitiva que nosotros tenemos de los números \( 0,1,2,\dots \)? Parece tan simple enumerarlos...

¿Y si se traslada a \( \Gamma \)? ¿Cómo sé que \( \Gamma=\{\epsilon,\ a,\ bcb,\ bacb,\ bcab,\ bacab,\dots\} \)? ¿Qué me asegura que \( \Gamma \) es exactamente ese conjunto?

Bueno, espero haber sido lo suficientemente claro y que me puedan aclarar estos puntos. Esta parte introductoria se nos da para luego introducir el lenguaje de la lógica proposicional en forma inductiva. El libro que se sigue es Logic and Structure de Dirk van Dalen.

Muchas gracias por todo.

Saludos

[Carlos Ivorra]

Ahora bien, por el principio de inducción primitiva para \( S \) sabemos que la propiedad se cumple para todo \( n\in S \). Pero nosotros queríamos probar que la propiedad se cumplía para todos los naturales menos el 2. ¿No habría que demostrar formalmente que \( S=\mathbb{N}-\{2\} \)? ¿Cómo sería tal demostración?

En efecto, con tu prueba no has demostrado lo que te piden (me salto todo lo anterior porque es correcto). Creo que lo más sencilo sería definir el conjunto \( S \) de los números naturales \( n \) que cumplen la propiedad

\( n = 2\lor \text{existe $\alpha\in \Gamma$ de longitud $n$} \)

Y has de probar que \( S = \mathbb{N} \). Esto puedes probarlo con esta variante del principio de induccion: supones que todos los números menores que \( n \) están en \( S \) y pruebas que \( n\in S \).

Para ello distingues casos: si \( n=0, 1, 2 \) es obvio que \( n\in S \), si \( n=4,5 \) encuentras explícitamente un elemento de \( \Gamma \) de longitud \( n \) y si \( n>5 \) por hipótesis de inducción existe una palabra en \( \Gamma \) de longitud \( n-3 \), de donde obtienes otra de longitud \( n \).

En el teórico nos dijeron: "Se puede definir el conjunto de los números naturales \( \mathbb{N} \) mediante las siguientes reglas:"

\( \begin{array}{ll} \mbox{ I } & 0\in \mathbb{N} \\ \mbox{ II } & \mbox{Si $n\in \mathbb{N}$, entonces $n+1\in \mathbb{N}$} \end{array} \)

Ahora bien, \( \mathbb{N} \) no es el único conjunto que satisface \( \textrm{I} \) y \( \textrm{II} \), pues por ejemplo \( \mathbb{Z} \) o \( \mathbb{Q} \) también las satisfacen. Me han constestado que en realidad, cada vez que se da un conjunto inductivo por reglas, ha de interpretarse como el menor conjunto que satisface dichas reglas. ¿Pero menor en qué sentido? Intuyo que debe referirse a que sólo lo integran los elementos comunes a todos los conjuntos que cumplen con las reglas. O dicho de otra manera, si \( \mathcal{A} \) representa la familia de todos los conjuntos que cumplen simultáneamente con \( \textrm{I} \) y \( \textrm{II} \), se estaría definiendo \( \mathbb{N}=\bigcap_{A\in \mathcal{A}}A \). ¿Es ésto correcto?

Es correcto.

En caso de serlo, ¿cómo se corrobora ese hecho? Hmmm aunque si se toma por definición, es así y punto. No hay nada que demostrar.

¿A qué te refieres con "ese hecho"?, ¿a que se puede definir así los números naturales? O bien lo tomas como definición, o bien tendrás que comparar esa definición con otra para comprobar que obtienes el mismo conjunto o un conjunto "isomorfo". Naturalmente, tu "definición" supone definidos el cero, el uno y la suma. Puede servir como una forma de definir los números naturales si ya tienes definidos los números reales, por ejemplo, cosa un poco rara, pero si, por ejemplo, has introducido axiomáticamente los números reales como un cuerpo ordenado arquimediano completo,  entonces la definición que propones puede servir como definición de \( \mathbb{N} \) como subconjunto de \( \mathbb{R} \).

En tal caso, ¿es ésa es una definición válida de los naturales?

Si supones definido un conjunto mayor como \( \mathbb{R} \) o \( \mathbb{Z} \), sí. Si no, no.

¿Coincide con la idea intuitiva que nosotros tenemos de los números \( 0,1,2,\dots \)?

Coincide en la medida en que una definición formal puede coincidir. Sobre eso habría mucho que hablar. Ya ha aparecido en otros hilos el problema de hasta qué punto una teoría de primer orden puede capturar la idea intuitiva de los números naturales.

Parece tan simple enumerarlos...

Lo fácil es empezar a enumerarlos, pero...

¿Y si se traslada a \( \Gamma \)? ¿Cómo sé que \( \Gamma=\{\epsilon,\ a,\ bcb,\ bacb,\ bcab,\ bacab,\dots\} \)? ¿Qué me asegura que \( \Gamma \) es exactamente ese conjunto?

El problema es que

\( \Gamma=\{\epsilon,\ a,\ bcb,\ bacb,\ bcab,\ bacab,\dots\} \)

No es ningún conjunto. La definición de \( \Gamma \) es la definición de los puntos suspensivos. Tendrás que precisar tu pregunta, porque literalmente no significa nada. (Entiendo lo que quieres decir, claro, pero la única respuesta a tu pregunta es que estás comparando una definición con algo que no puede valer como definición, pues no especifica lo que sigue a los puntos suspensivos, y si tratas de especificarlo, acabarás repitiendo la definición de \( \Gamma \).)

[pierrot]

Muchas gracias Carlos. Respecto a ésto:

En efecto, con tu prueba no has demostrado lo que te piden (me salto todo lo anterior porque es correcto). Creo que lo más sencilo sería definir el conjunto \( S \) de los números naturales \( n \) que cumplen la propiedad

\( n = 2\lor \text{existe $\alpha\in \Gamma$ de longitud $n$} \)

Y has de probar que \( S = \mathbb{N} \). Esto puedes probarlo con esta variante del principio de induccion: supones que todos los números menores que \( n \) están en \( S \) y pruebas que \( n\in S \).

Para ello distingues casos: si \( n=0, 1, 2 \) es obvio que \( n\in S \), si \( n=4,5 \) encuentras explícitamente un elemento de \( \Gamma \) de longitud \( n \) y si \( n>5 \) por hipótesis de inducción existe una palabra en \( \Gamma \) de longitud \( n-3 \), de donde obtienes otra de longitud \( n \).

Hay un problema. Y es que en el curso en que estoy, no se nos permite hacer demostraciones por inducción fuerte. Sí nos dejaban hacer eso en un curso anterior que tuve de matemática discreta. De hecho, es lo mismo que uso acá, ¿no? Pues resulta que ahora en Lógica no nos dejan usar eso. Supuestamente es porque definen el lenguaje de la lógica proposicional de manera inductiva (le llaman PROP a ese lenguaje) y enuncian un principio de inducción primitiva para PROP y prueban propiedades a partir de ese principio. Siguen el enfoque del libro que cité antes. Por eso es que sólo les interesa la inducción primitiva. Disculpa, es algo que omití en el enunciado así que no tenías por qué saberlo. Por eso definí \( S \) de esa manera y demostré que la propiedad se cumple para todo \( n\in S \) usando el principio de inducción primitiva para \( S \). Intuitivamente está claro que \( 2\not\in S \) y que cualquier otro natural sí puede construirse con las reglas que lo definen, ¿no?. Pero ¿por qué no estoy probando lo que me piden?

Por lo demás, has sido muy conciso al responder mis dudas y me has aclarado cantidad de cosas. Gracias nuevamente.

Saludos

[Carlos Ivorra]

Intuitivamente está claro que \( 2\not\in S \) y que cualquier otro natural sí puede construirse con las reglas que lo definen, ¿no?. Pero ¿por qué no estoy probando lo que me piden?

Bueno, tú mismo preguntabas si no habría que demostrar que \( S = \mathbb{N}\setminus \{2\} \). Si lo aceptas como "intuitivamente evidente", entonces tienes la prueba completa, pero, aunque sea una afirmación más elemental, formalmente no veo gran diferencia en probar que \( S = \mathbb{N}\setminus \{2\} \) a partir de la definición inductiva que das de \( S \) o demostrar lo que te piden.