Práctico 1

Buenas!

Estuve haciendo el ejercicio 9), y se me ocurrió una posible forma de demostrar el paso inductivo de la inclusión, que de ser correcta me parece mas intuitiva/mas directa que aplicar dos veces el PIP. Pero no sé si voy por buen camino o tiene sentido.

Queremos probar que $\Gamma = \Delta$ y para eso se prueba la doble inclusión. Supongamos que primero quiero probar que $\Gamma \subseteq \Delta$

Para aplicar el PIP, defino una propiedad $P(x) := x \in \Delta$. Y se quiere probar $P(x) \forall x \in \Gamma$. Utilizo el PIP en $\Gamma$.

El paso base es trivial, pues $\epsilon \in \Delta$ por def.

La idea viene para el paso inductivo, donde suponemos que $\forall x \in \Gamma , P(x)$, y queremos probar entonces $P(ax) = ax \in \Delta$. 

Ya que $P(x) \forall x \in \Delta \Rightarrow  \exists X$ conjunto de reglas que, aplicándolas en cierto orden, y usando la def. de $\Delta$ construyen a $x$. La idea es tomar ese conjunto de reglas, y añadir al principio de ellas las reglas para crear $a$. Y que al aplicar dichas reglas y luego $X$ en el orden correcto, la tira construida es $ax$, entonces quedaría demostrado $P(ax)$, pues $ax$ es construible usando las reglas de $\Delta$, si se da la HI.

También quiero notar que la intuición que tuve es que, para añadir a cualquier elemento $x \in \Delta$, se necesita "pasar" por la primera regla (la de la tira vacía) o tener algo ya en $\Delta$ , porque sino el antecedente de las otras reglas nunca se cumple, y por tanto no se pueden aplicar, pero simplemente se podría cambiar esa primera regla por las reglas que sirven para añadir a $a$ en $\Delta$

Sé que le falta formalidad, solo quería explicar la idea antes de intentar formalizar todo para ver si voy por buen camino.