Autor Tema: Libro Lógica de Ivorra: No entiendo qué es "por hipótesis de inducción..."

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

18 Marzo, 2023, 03:45 am
Leído 1078 veces

Kortainnn

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino
  • uwu
Buenos días, tardes o noches, espero que te encuentres de la mejor manera.
El motivo de esta publicación es para buscar ayuda en el entendimiento de una forma de deducción (creo yo) llamada "por hipótesis de inducción". Si me permiten, ubicaré el siguiente ejemplo (en el cual yo me confundo):
Cita de: pagina 26 del libro "Lógica matemática" de Carlos Ivorra Castillo
Si \( \theta \equiv \alpha \to \beta \), por hipótesis de inducción \( M \vdash \alpha [v] \) syss \( M \vdash \alpha [w] \) y \( M \vdash \beta [v] \) syss \( M \vdash \beta [w] \). Entonces \( M \vdash (\alpha \to \beta)[v] \) syss no \( M \vdash \alpha [v] \) o \( M \vdash \beta [v] \) syss no \( M \vdash \alpha [w] \) o \( M \vdash \beta [w] \) syss \( M \vdash (\alpha \to \beta)[w] \)

Ahora bien, donde está las negritas marcadas en la cita, es donde me empiezo a confundir, en vista de que: ¿Cómo se puede llegar a afirmar algo así? es decir, cómo debo interpretar qué es "\( \alpha \)" en base a la inducción matemática para llegar a la conclusión de que "\( M \vdash \alpha [v]  \) syss \( M \vdash \alpha [w]  \)". Esta duda me lleva atormentando por más de 3 días...
Agradecería profundamente que me dieran respuesta a esta incógnita, pues, me gustaría interpretar lo mejor posible este libro.
- - -
En el siguiente apartado está la respuesta que he venido formando a lo largo de tres días pero, no me convence (pues, no sé si he usado correctamente los conceptos propuestos en el libro, o bien que, quizás haya sido muy redundante innecesariamente. :banghead:)
Mi respuesta:
Hay que demostrar que: \( M \vdash \alpha [v]\ \ syss \ \ M \vdash \alpha [v]\ \)
En vista de que \( \alpha \) es una fórmula, es claro que \( \theta_1,...,\theta_m \) tal que \( \theta_m \equiv \alpha \). Ahora bien, tengo una conjetura:
C.1: Si \( \phi_1, ···,\phi_m \) son cadenas de símbolos de un lenguaje \( L \) y \( \phi_1 ···\phi_m \) es una expresión, entonces, ¿Necesariamente, \( \phi_1 \) debe ser una variable o constante?
Lo anterior es importante para la exhibición de lo que entiendo por hipótesis de inducción.
Ahora, por inducción en \( \alpha \) entiendo yo (disculpen, quizás, la siguiente barbaridad sintáctica):

\(
\theta_1[v] \equiv \theta_1[w]
\\
\theta_2[v] \equiv \theta_2[w]
\\
...
\\
\theta_m[v] \equiv \theta_m[w]
 \)
Entonces, en mi interpretación, si probamos lo anterior se verifica que \( M \vdash \alpha [v] \) syss \( M \vdash \alpha [w] \)
Ahora, suponiendo que C.1 es cierta y si se aplica inducción fuerte, se hace trivial la demostración. ¿Es acaso este método el correcto para probar esta proposición? ¿Es acaso esta la correcta interpretación de "por hipótesis de inducción"? o ¿He mal interpretado conceptos clave del libro?
Muchas gracias por leer. Si he cometido un error de escritura matemática, por favor, háganmelo saber (soy nuevo)

Saludos.
Es evidente que, nada es evidente.

18 Marzo, 2023, 11:48 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El motivo de esta publicación es para buscar ayuda en el entendimiento de una forma de deducción (creo yo) llamada "por hipótesis de inducción". Si me permiten, ubicaré el siguiente ejemplo (en el cual yo me confundo):
Cita de: pagina 26 del libro "Lógica matemática" de Carlos Ivorra Castillo
Si \( \theta \equiv \alpha \to \beta \), por hipótesis de inducción \( M {\color{red}\vDash} \alpha [v] \) syss \( M {\color{red}\vDash} \alpha [w] \) y \( M {\color{red}\vDash} \beta [v] \) syss \( M {\color{red}\vDash} \beta [w] \). Entonces \( M {\color{red}\vDash} (\alpha \to \beta)[v] \) syss no \( M {\color{red}\vDash} \alpha [v] \) o \( M {\color{red}\vDash} \beta [v] \) syss no \( M {\color{red}\vDash} \alpha [w] \) o \( M {\color{red}\vDash} \beta [w] \) syss \( M {\color{red}\vDash} (\alpha \to \beta)[w] \)


Ante todo, debes usar \vDash en lugar de \vdash, pues \( \vDash \) tiene un significado muy distinto a \( \vdash \)

Ahora bien, donde está las negritas marcadas en la cita, es donde me empiezo a confundir, en vista de que: ¿Cómo se puede llegar a afirmar algo así? es decir, cómo debo interpretar qué es "\( \alpha \)" en base a la inducción matemática para llegar a la conclusión de que "\( M \vdash \alpha [v]  \) syss \( M \vdash \alpha [w]  \)". Esta duda me lleva atormentando por más de 3 días...

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.

En el siguiente apartado está la respuesta que he venido formando a lo largo de tres días pero, no me convence (pues, no sé si he usado correctamente los conceptos propuestos en el libro, o bien que, quizás haya sido muy redundante innecesariamente. :banghead:)
Mi respuesta:
Hay que demostrar que: \( M {\color{red}\vDash} \alpha [v]\ \ syss \ \ M {\color{red}\vDash} \alpha [{\color{red} w}]\ \)

Bueno, eso es la mitad de lo que hay que demostrar, el caso en que la expresión es una fórmula. La otra mitad es el caso en que es un término, y no se pueden separar en dos teoremas independientes debido a que los relatores transforman términos en fórmulas y los descriptores fórmulas en términos.

En vista de que \( \alpha \) es una fórmula, es claro que \( \theta_1,...,\theta_m \) tal que \( \theta_m \equiv \alpha \).

Supongo que quieres decir que existe una sucesión de expresiones según la definición de expresión que termina en \( \alpha \), pero, si es eso, deberías dejarlo más claro.

Ahora bien, tengo una conjetura:
C.1: Si \( \phi_1, ···,\phi_m \) son cadenas de símbolos de un lenguaje \( L \) y \( \phi_1 ···\phi_m \) es una expresión, entonces, ¿Necesariamente, \( \phi_1 \) debe ser una variable o constante?

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).

Lo anterior es importante para la exhibición de lo que entiendo por hipótesis de inducción.
Ahora, por inducción en \( \alpha \) entiendo yo (disculpen, quizás, la siguiente barbaridad sintáctica):

\(
\theta_1[v] \equiv \theta_1[w]
\\
\theta_2[v] \equiv \theta_2[w]
\\
...
\\
\theta_m[v] \equiv \theta_m[w]
 \)

Esto no lo entiendo. ¿Qué es \( \theta_1[v \)?

Entonces, en mi interpretación, si probamos lo anterior se verifica que \( M \vdash \alpha [v] \) syss \( M \vdash \alpha [w] \)

Ahora, suponiendo que C.1 es cierta y si se aplica inducción fuerte, se hace trivial la demostración.

No te sigo.

¿Es acaso este método el correcto para probar esta proposición? ¿Es acaso esta la correcta interpretación de "por hipótesis de inducción"? o ¿He mal interpretado conceptos clave del libro?

Pues no sé qué decirte, porque no entiendo el método ni la interpretación que planteas.

18 Marzo, 2023, 08:05 pm
Respuesta #2

Kortainnn

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino
  • uwu
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.
Es evidente que, nada es evidente.

19 Marzo, 2023, 01:01 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
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?

Sí, es 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?

Si quieres probar que todas las expresiones cumplen una determinada propiedad, una forma de hacerlo es por inducción en los términos siguientes:

Supones (por hipótesis de inducción) que todas las expresiones de longitud menor que \( n \) cumplen la propiedad considerada y demuestras que toda fórmula de longitud \( n \) la cumple también.

Ya está. No hay "caso base" ni falta que hace. ¿Por qué?

Podrías decir que hay que demostrar, como "caso base", que las expresiones de longitud 1 cumplen la propiedad deseada, pero no hace falta. Una expresión de longitud 1 es una variable o una constante. ¿Faltaría demostrar que las variables y las constantes cumplen la propiedad? ¡No! Eso ya lo habrás demostrado si realmente has probado lo que he puesto en azul.

En efecto, para demostrar la frase en azul habrás tenido que probar que si las expresiones de longitud menor que 1 cumplen la propiedad, también la cumplen las expresiones de longitud 1, pero, como no existen expresiones de longitud menor que 1, eso es lo mismo que demostrar que las expresiones de longitud 1 cumplen la propiedad. Eso es parte de lo que tienes que demostrar para probar lo que he puesto en azul antes.

Por ejemplo, en la prueba del teorema 1.9, que es el caso por el que has preguntado en este hilo, se razona por inducción sobre la longitud de \( \theta \) y se distinguen tantos casos como formas puede tener \( \theta \) y, si te fijas, los dos primeros casos (que \( \theta \) sea una variable o una constante) son todas las posibilidades para expresiones de longitud 1, y en ellos se demuestra que las variables y las constantes (las expresiones de longitud 1) cumplen la propiedad requerida. Eso es el caso base de la inducción, pero no es necesario distinguirlo como tal, sino que es parte de la prueba de que si las expresiones de longitud menor que la de \( \theta \) cumplen la propiedad, lo mismo vale para \( \theta \).

No sé si con esto lo verás claro. Si no, vuelve a preguntar.

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] \)

Pero eso no está bien, porque ahí estás suponiendo que, o bien todos los \( \theta_i \) son términos, o bien todos son fórmulas, y en general unos serán términos y otros fórmulas, y para cada \( \theta_i \) tienes que aplicar la parte del enunciado correspondiente a términos o a fórmulas según lo que sea dicho \( \theta_i \) en concreto.

19 Marzo, 2023, 08:55 pm
Respuesta #4

Kortainnn

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino
  • uwu
Si quieres probar que todas las expresiones cumplen una determinada propiedad, una forma de hacerlo es por inducción en los términos siguientes:

Supones (por hipótesis de inducción) que todas las expresiones de longitud menor que \( n \) cumplen la propiedad considerada y demuestras que toda fórmula de longitud \( n \) la cumple también.

Ya está. No hay "caso base" ni falta que hace. ¿Por qué?

Podrías decir que hay que demostrar, como "caso base", que las expresiones de longitud 1 cumplen la propiedad deseada, pero no hace falta. Una expresión de longitud 1 es una variable o una constante. ¿Faltaría demostrar que las variables y las constantes cumplen la propiedad? ¡No! Eso ya lo habrás demostrado si realmente has probado lo que he puesto en azul.

En efecto, para demostrar la frase en azul habrás tenido que probar que si las expresiones de longitud menor que 1 cumplen la propiedad, también la cumplen las expresiones de longitud 1, pero, como no existen expresiones de longitud menor que 1, eso es lo mismo que demostrar que las expresiones de longitud 1 cumplen la propiedad. Eso es parte de lo que tienes que demostrar para probar lo que he puesto en azul antes.

Por ejemplo, en la prueba del teorema 1.9, que es el caso por el que has preguntado en este hilo, se razona por inducción sobre la longitud de \( \theta \) y se distinguen tantos casos como formas puede tener \( \theta \) y, si te fijas, los dos primeros casos (que \( \theta \) sea una variable o una constante) son todas las posibilidades para expresiones de longitud 1, y en ellos se demuestra que las variables y las constantes (las expresiones de longitud 1) cumplen la propiedad requerida. Eso es el caso base de la inducción, pero no es necesario distinguirlo como tal, sino que es parte de la prueba de que si las expresiones de longitud menor que la de \( \theta \) cumplen la propiedad, lo mismo vale para \( \theta \).

No sé si con esto lo verás claro. Si no, vuelve a preguntar.

Ya veo, ahora entiendo mucho mejor esto, muchas gracias.

Pero eso no está bien, porque ahí estás suponiendo que, o bien todos los \( \theta_i \) son términos, o bien todos son fórmulas, y en general unos serán términos y otros fórmulas, y para cada \( \theta_i \) tienes que aplicar la parte del enunciado correspondiente a términos o a fórmulas según lo que sea dicho \( \theta_i \) en concreto.

Entendido, lo tomaré en cuenta. Gracias por aclarar eso también.

Saludos.
Es evidente que, nada es evidente.