Buenos días, tardes o noches.
Primero que todo, me gustaría agradecerle por responder en tan poco tiempo (y, agradecerle, por muchas otras cosas también).
El teorema afirma que si \( v \) y \( w \) son valoraciones de un lenguaje formal en un modelo \( M \) que coinciden sobre las variables libres de una expresión \( \theta \), entonces, si \( \theta \) es un término, \( M(\theta)[v] \equiv M(\theta)[w] \) (el objeto denotado por \( \theta \) en \( M \) es el mismo si se calcula con cualquiera de las dos valoraciones) y, si \( \theta \) es una fórmula, entonces \( M\vDash \theta[v] \) si y sólo si \( M\vDash\theta[w] \) (\( \theta \) es satisfecha en \( M \) respecto de una valoración si y sólo si lo es respecto de la otra).
La demostración es por inducción sobre la longitud de \( \theta \), es decir, suponemos (hipótesis de inducción) que el teorema es cierto para expresiones de longitud menor que \( \theta \) y lo probamos para expresiones de longitud \( \theta \).
Aquí hay que entender que si \( \theta \) es, por ejemplo, una variable, que tiene longitud 1, no hay expresiones de longitud menor que \( 1 \), por lo que la hipótesis de inducción no dice nada, y hay que demostrar que las variables cumplen el teorema sin recurrir a ninguna hipótesis de inducción. Así, el "caso base" de la inducción está implícito en el planteamiento. No es que no haya "caso base", sino que el "caso base" es un caso particular de la inducción.
La prueba distingue todas las posibilidades que hay para \( \theta \), y tú estás preguntando por el caso en que \( \theta\equiv \alpha\rightarrow\beta \), donde \( \alpha \) y \( \beta \) son fórmulas que, necesariamente, tendrán longitud menor que \( \theta \), por lo que podemos aplicarles la hipótesis de inducción, que afirma precisamente que
\( M \vDash \alpha [v] \) syss \( M \vDash \alpha [w] \) y \( M \vDash \beta [v] \) syss \( M \vDash \beta [w] \).
No sé si esto resuelve tu duda. Si sigues sin entenderlo vuelve a preguntar.
Sí profesor, con ese apartado a resuelto casi en su totalidad la duda que tenía. Básicamente, había ignorado el concepto de "longitud" el cual significa, por así decirlo, la cantidad de símbolos que tiene una cadena de símbolos. ¿Es esto correcto?
Pero, el "caso base" de la inducción, no logro entenderlo. Lo que sé es que para que se cumpla la inducción, debe cumplirse un "caso base" pero, no logro discernir el significado de:
No es que no haya "caso base", sino que el "caso base" es un caso particular de la inducción.
¿Me podrías explicar esto más a fondo por favor?
Ahora con lo que respecta:
No sé si entiendo lo que planteas. Estás diciendo que coger una expresión y la partes en trocitos, y preguntas si el primer trocito será necesariamente una variable o constante. Si es eso, obviamente no. Para empezar, estás diciendo que cada trocito es una cadena de signos, luego si tu primer trocito tiene más de un signo, seguro que no es una variable o constante.
Más aún, el primer signo de una expresión no es necesariamente una variable o constante, puede ser cualquier signo. De hecho, con la sintaxis que uso en mi libro, el primer signo de una expresión es una variable o constante si y sólo si la expresión es toda ella una variable o constante (y tiene longitud 1).
Tienes toda la razón, no sé en que habré estado pensando cuando realicé esta explicación en mis escritos. Gracias por tomarte la molestia de aclarar eso también. Más aún, un contraejemplo claro sería que \( \theta_1 \equiv x|\alpha \)... no sé por qué algo tan obvio se me paso por alto...
Supongo que quieres decir que existe una sucesión de expresiones según la definición de expresión que termina en α, pero, si es eso, deberías dejarlo más claro.
Sí, es exactamente eso.
Esto no lo entiendo. ¿Qué es \( \theta [v] \)?
Voy a intentarlo explicar mejor (en base a las recomendaciones que me ha dado):
Sea \( \theta_1,···,\theta_m \) una sucesión de cadenas finita tal que \( \theta_m \equiv \alpha \) y, además, \( \alpha \) es una fórmula. Si se supone cierto que (hipótesis de inducción):
Si \( \theta_i \) es un término:
\( M(\theta_1)[v] \equiv M(\theta_1)[w] \)
···
\( M(\theta_{m-1})[v] \equiv M(\theta_{m-1})[w] \)
Si \( \theta_i \) es una fórmula:
\( M \vDash \theta_1[v] \ \ syss \ \ M \vDash \theta_1[w] \)
···
\( M \vDash \theta_{m-1}[v] \ \ syss \ \ M \vDash \theta_{m-1}[w] \)
Y, en base a la hipótesis de inducción, si se lograra demostrar que: \( M \vDash \alpha[v] \ \ syss \ \ M \vDash \alpha[w] \). Entonces, se logra demostrar que siempre \( M \vDash \alpha[v] \ \ syss \ \ M \vDash \alpha[w] \) cuando \( \alpha \) es una fórmula.
Ahora, por ejemplo, para mi el "caso base" aquí sería demostrar que:
\( M(\theta_{1})[v] \equiv M(\theta_{1})[w] \)
En base a mi conjetura (que me ha quedado claro que es obviamente falsa) se verificaría lo anterior.
Luego, por inducción fuerte, suponer que lo anterior se cumple para:
\( M \vDash \theta_{i}[v] \ \ syss \ \ M \vDash \theta_{i}[w] \) y \( M(\theta_{i})[v] \equiv M(\theta_{i})[w][i] \)
Con \( i \in (0,m) \) y con eso demostrar que \( M \vDash \alpha[v] \ \ syss \ \ M \vDash \alpha[w] \).
---
Ese fue mi pensamiento antiguo, ahora, tomando en cuenta el concepto de longitud de una expresión, se hace muy ameno demostrar que \( M \vDash \alpha[v] \ \ syss \ \ M \vDash \alpha[w] \). Pero, lo que no me queda claro (vuelvo a iterar), es ¿Cuál es el "caso base" en este caso?
Gracias por leer, espero tus respuestas.
Saludos.