Hola. Voy a plantear mi duda mediante un ejemplo. Es un ejercicio, dice así:
Considere el alfabeto
y el lenguaje
definido como:
Respecto a la notación,
representa la palabra vacía, y
es el conjunto de todas las palabras que se pueden formar a partir del alfabeto
.
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
y
son metavariables que representan cualquier palabra de
. No son elementos del alfabeto.
Demuestre, usando el principio de inducción que corresponda, que:
[1] todas las palabras de
tienen una cantidad par de ocurrencias de la letra
.
[2] en
no hay palabras de largo 2.
[3] en
hay palabras de cualquier largo, salvo 2.
Entonces lo que hago es enunciar el
principio de inducción primitva para
(por cada conjunto inductivo, tendré un principio de inducción primitiva distinto):
Sea 
una propiedad sobre los elementos de tal que se cumple:
1. 
2. 
3. Si 
y 
para 
, entonces 
En las hipótesis anteriores, se cumple para todo 
.
En [1] la propiedad a probar es
y en [2]
. Ambas se pueden demostrar usando el teorema enunciado anteriormente. En cambio, [3] no es una propiedad referida sobre los elementos de
(creo yo) sino sobre los números naturales. Es decir, la propiedad sería
, y habría que probar que se cumple
,
y
para todo
.
Creo que la demostración que ellos buscan serían algo así. Definimos el conjunto
como:
Ahora enunciamos el correspondiente principio de inducción primitiva para
:
Sea una propiedad sobre los elementos de tal que se cumple:
1. 
2. 
3. Si 
y 
para 
, entonces 
En las hipótesis anteriores, se cumple para todo 
.
Usando este principio podemos estructurar la demostración así:
Alcanza con probar:
Paso base 1: ¿Se cumple
? Sí, tomamos
(la palabra vacía tiene largo 0 y pertenece a
por
).
Paso base 2: ¿Se cumple
? Sí, tomamos
(la palabra
tiene largo 1 y pertenece a
por
). Hay que aclarar en este punto que se está tomando
como palabra y no como elemento (o letra) del alfabeto.
Paso inductivo: Asumimos
y
para ciertos
(podría ser eventualmente
, no importa) y hay que probar
. La demostración es simpe. Por hipótesis inductiva sabemos que existe una palabra
tal que el largo de
es
y que existe otra palabra
tal que el largo de
es
. Por la regla
de construcción de
sabemos que
y el largo de esta palabra es el largo de
más el largo de
más tres, ya que esta nueva palabra tiene, además de las letras que conforman a
y
, a las letras
. En consecuencia, tenemos que la palabra
(que sabemos que pertenece al lenguaje
por
) tiene
letras, por lo tanto es cierto
que es lo que se quería probar.
Ahora bien, por el principio de inducción primitiva para
sabemos que la propiedad se cumple para todo
. 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
? ¿Cómo sería tal demostración?
En el teórico nos dijeron: "Se puede definir el conjunto de los números naturales
mediante las siguientes reglas:"
Ahora bien,
no es el único conjunto que satisface
y
, pues por ejemplo
o
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
representa la familia de todos los conjuntos que cumplen simultáneamente con
y
, se estaría definiendo
. ¿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
? Parece tan simple enumerarlos...
¿Y si se traslada a
? ¿Cómo sé que
? ¿Qué me asegura que
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
