Autor Tema: Duda Teorema 1.13 en el libro "Lógica matemática" de Carlos Ivorra

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

19 Agosto, 2021, 05:59 pm
Leído 2490 veces

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, en el Teorema 1.13 del libro Lógica matemática (página 35) se establece que todos los apartados se prueban igual, supongo que se refiere a que se prueban por inducción, pero no consigo demostrar un caso del apartado e).

Concretamente, no consigo demostrar es lo siguiente:

Si \( x_i \) es una variable cualquiera, \( \alpha \) una fórmula que satisfaga el apartado e) y \( \theta=\forall x_i \alpha \), entonces \( \theta \) también satisface el apartado e).

Atendiendo a los distintos casos que se dan en la definición de sustitución he conseguido demostrarlo si supongo que \( x \) no está libre en \( \theta \), o bien que \( x \) está libre en \( \theta \) pero \( x_i \) no lo está en \( t \). Sin embargo, llevo horas intentando demostrar el último caso, es decir, \( x \) está libre en \( \theta \) y \( x_i \) lo está en \( t \), pero no llego a nada.

¿Alguna ayuda sobre como se prueba este último caso?

Un saludo y muchas gracias por las respuestas.

19 Agosto, 2021, 08:53 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Este tipo de pruebas son bastante tediosas pero no deberían ser difíciles. No lo he pensado con detalle, pero quizás te sean útiles unas observaciones para desencallarte.

Lo primero es que bajo el supuesto que manejas, \[ S_x^t \theta = \forall x_j S_x^t S_{x_i}^{x_j} \alpha \], donde \[ x_j \] es la variable con menor índice que no aparece ni en \[ \theta \] ni en \[ t \]. Entonces, \[ y \] está libre en \[ S_x^t \theta = \forall x_j S_x^t S_{x_i}^{x_j} \alpha \] si y solo si \[ y\neq x_j \] e \[ y \] está libre en \( S_x^t S_{x_i}^{x_j} \alpha \). Para seguir tienes que aplicar la hipótesis de inducción, pero no a \[ \alpha \] sino a \( S_{x_i}^{x_j} \alpha \). Esto está justificado porque la inducción es sobre la longitud de \[ \theta \],  y \[ S_{x_i}^{x_j}\alpha \] tiene la misma longitud que \( \alpha \) (y por tanto, menor que \[ \theta \]). A partir de aquí debería ser tedioso pero no difícil.

Si con esto no te saliera, y si no te responde Carlos antes, vuelve a preguntar e intento hacerlo con más detalle.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

19 Agosto, 2021, 09:55 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Continuando donde lo ha dejado geómetracat:

\( y \) está libre en \( S_x^t \theta = \forall x_j S_x^t S_{x_i}^{x_j} \alpha \) si y sólo si está libre en \( S_x^t S_{x_i}^{x_j} \alpha \) y no es \( x_j \).

Por hipótesis de inducción, esto sucede si y sólo si \( y \) está libre en \( S_{x_i}^{x_j} \alpha \) e \( y\not\equiv x \) o bien \( x \) está libre en \( S_{x_i}^{x_j} \alpha \) e \( y \) está libre en \( t \) (y además \( y\not\equiv x_j \)).

Volvemos a aplicar la hipótesis de inducción para concluir que \( y \) está libre en \( S_{x_i}^{x_j} \alpha \) si y sólo si \( y \) está libre en \( \alpha \) e \( y\not\equiv x_i \)  (ya que no puede ser que \( y \) esté libre en \( x_j \), pues \( y\not\equiv x_j \), por lo que la segunda alternativa no puede darse).

Otra vez por la hipótesis de inducción, \( x \) está libre en \( S_{x_i}^{x_j} \alpha \) si y sólo si \( x \) está libre en \( \alpha \) y \( x\not\equiv x_i \) (pues de nuevo el segundo caso es imposible, pues \( x \) no puede estar libre en \( x_j \), ya que \( x \) está libre en \( \theta \), pero \( x_j \) no).

En total, tenemos que \( y \) está libre en \( S_x^t \theta \) si y sólo si \( y \) está libre en \( \alpha \) e \( y\not\equiv x, x_i, x_j \), o bien \( x \) está libre en \( \alpha \), \( x\not\equiv x_i, x_j \) e \( y \) está libre en \( t \).

Ahora usamos que una variable está libre en \( \theta \) si y sólo si está libre en \( \alpha \) y no es \( x_i \), con lo que lo anterior equivale a que \( y \) está libre en \( \theta \) e \( y\not\equiv x, x_j \) o bien \( x \) está libre en \( \theta \), \( x\not\equiv x_j \) e \( y \) no está libre en \( t \).

Ahora sólo falta observar que podemos eliminar las referencias a \( x_j \), pues si \( y \) está libre en \( \theta \) eso ya implica que \( y\not\equiv x_j \) y si \( x \) está libre en \( \theta \) eso ya implica que \( x\not\equiv x_j \).

20 Agosto, 2021, 12:26 pm
Respuesta #3

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a ambos, muchas gracias por las respuestas.

Únicamente me faltaba considerar que podía aplicar la hipótesis de inducción a \( S_{x_i}^{x_j}\alpha \), pues estaba siendo muy cabezón e intentado probarlo suponiendo únicamente que el resultado era cierto para \( \alpha \) y no para cualquier expresión con longitud menor a \( \theta \).

Vamos, estaba siendo cabezón en utilizar una inducción más "débil" porque me parecía más "justificable", pero después de darle varias vueltas más veo que la inducción fuerte es igual de "justificable"  ;D

Solo una par de pequeñas dudas.

Ahora sólo falta observar que podemos eliminar las referencias a \( x_j \), pues si \( y \) está libre en \( \theta \) eso ya implica que \( y\not\equiv x_j \) y si \( x \) está libre en \( \theta \) eso ya implica que \( x\not\equiv x_j \).

Yo no he probado la doble implicación de golpe, si no que he probado primero un sentido de la implicación, y luego el otro, con lo que esto último que comentas no aparece en el tipo de prueba que yo he hecho, ¿verdad?

Quiero decir, yo he razonado como sigue:

Si \( y \) está libre en \( S_x^t \theta \) entonces \( y \not \equiv x_j \) e \( y \) está libre en \( S_x^tS_{x_i}^{x_j} \alpha \).
Por tanto, por hipótesis de inducción aplicada a \( S_{x_i}^{x_j} \alpha \) tenemos que, o bien \( y \) está libre en \( S_{x_i}^{x_j} \alpha \) e \( y \not \equiv x \), o bien \( x \) está libre en \( S_{x_i}^{x_j} \alpha \) e \( y \) está libre en \( t \).

En el primer caso, aplicando ahora la hipótesis de inducción a \( \alpha \), tenemos que (al ser \( y \not \equiv x_j \)) \( y \) está libre en \( \alpha \) e \( y \not \equiv x_i \), lo que implica que \( y \) está libre en \( \theta \). Por tanto, en este caso obtenemos que \( y \) está libre en \( \theta \) y que \( y \not \equiv x \) por lo que se cumple la disyunción.

En el segundo caso, puesto que ya sabemos que \( x \) está libre en \( \theta \), obtenemos directamente que \( x \) está libre en \( \theta \) e \( y \) está libre en \( t \), cumpliéndose también la disyunción.

Recíprocamente, si \( y \) está libre en \( \theta \) e \( y \not \equiv x \), entonces \( y \) está libre en \( \alpha \) e \( y \not \equiv x_i, x \).
Por tanto, por hipótesis de inducción aplicada a \( \alpha \), tenemos que \( y \) está libre en \( S_{x_i}^{x_j} \alpha \) siendo además \( y \not \equiv x \), y aplicando ahora la hipótesis de inducción a \( S_{x_i}^{x_j} \alpha \), obtenemos que \( y \) está libre en \( S_x^tS_{x_i}^{x_j} \alpha \).
Como además \( y \not \equiv x_j \) (pues \( y \) está libre en \( \theta \) pero \( x_j \) no está en \( \theta \)) concluimos que \( y \) está libre en \( S_x^t \theta \).

Por otro lado, supongamos ahora que \( y \) está libre en \( t \) (por el  caso en el que estamos ya es cierto que \( x \) está libre en \( \theta \)).
Entonces, por estar \( x \) libre en \( \theta \), tenemos que lo está en \( \alpha \) y al ser \( x \not \equiv x_i \) (pues \( x \) está libre en \( \theta \)), por hipótesis de inducción tenemos que \( x \) está libre en \( S_{x_i}^{x_j} \alpha \). Aplicando ahora la hipótesis de inducción a \( S_{x_i}^{x_j} \alpha \), teniendo en cuenta que hemos supuesto que \( y \) está libre en \( t \), obtenemos que \( y \) está libre en \( S_x^tS_{x_i}^{x_j} \alpha \).
Como \( y \not \equiv x_j \) (pues \( y \) está libre en \( t \) y \( x_j \) no está en \( t \)) concluimos que \( y \) está libre en \( S_x^t \theta \).

Entonces, al no haber estado llevando las equivalencias a lo largo de la prueba, sino simplemente implicaciones, me he dejado atrás la dependencia de los \( x_j \) cuando lo he necesitado. ¿Es mi prueba también correcta?

Por último, quería preguntaros si al decir que la longitud de \( S_{x_i}^{x_j} \alpha \) y \( \alpha \) son iguales estamos haciendo algo que es evidente por alguna razón que se me escapa o si, para ser del todo rigurosos, es algo que también deberíamos demostrar por inducción. Se que la prueba de que si \( \theta \) es una expresión y \( x, z \) dos variables, entonces la longitud de \( S_x^z \) y \( \theta \) es la misma es muy sencillita por inducción, pero lo que quiero saber es si es algo más evidente de lo que me lo parece por alguna razón que no veo.

Un saludo y muchas gracias por las respuestas.

20 Agosto, 2021, 01:09 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Entonces, al no haber estado llevando las equivalencias a lo largo de la prueba, sino simplemente implicaciones, me he dejado atrás la dependencia de los \( x_j \) cuando lo he necesitado. ¿Es mi prueba también correcta?

Yo la veo bien.

Por último, quería preguntaros si al decir que la longitud de \( S_{x_i}^{x_j} \alpha \) y \( \alpha \) son iguales estamos haciendo algo que es evidente por alguna razón que se me escapa o si, para ser del todo rigurosos, es algo que también deberíamos demostrar por inducción.

Lo que pasa en el fondo es que  \( S_{x_i}^{x_j} \alpha \) es, o bien, la propia fórmula \( \alpha \) (que tiene la misma longitud que \( \alpha \)), o bien la fórmula que resulta de cambiar cada \( x_i \) por \( x_j \) en \( \alpha \) (y al cambiar una variable por otra no alteras la longitud) o, en el peor de los casos, si al meter \( x_j \) va a quedar ligada, lo evitas cambiando las \( x_j \) que ya hubiera en la fórmula por otra variable distinta, pero eso tampoco altera la longitud.

En suma, que, en cualquier caso, \( S_{x_i}^{x_j} \alpha \) se diferencia de \( \alpha \) a lo sumo en que algunas variables han sido cambiadas por otras, pero no has añadido o quitado nada que pueda hacer la fórmula más larga o más corta. En general, por esta misma razón, cuando cambias una variable \( x \) por un término \( t \) de longitud  \( l \), la longitud de la expresión resultante será la de la expresión inicial más \( n(l-1) \), donde \( n \) es el número de veces que \( x \) aparece libre en la expresión inicial, porque lo que haces es cambiar unas variables por otras y cambiar cada una de las \( n \) variables \( x \) libres por el término \( t \), lo cual hace que la longitud aumente \( l-1 \) unidades por cada \( t \) insertado.

Se que la prueba de que si \( \theta \) es una expresión y \( x, z \) dos variables, entonces la longitud de \( S_x^z \) y \( \theta \) es la misma es muy sencillita por inducción, pero lo que quiero saber es si es algo más evidente de lo que me lo parece por alguna razón que no veo.

La razón que lo hace evidente es la que te digo. Si te convence, pues ya está, y si prefieres la inducción, pues bien está, pero aquí lo de "para ser del todo rigurosos" no tiene sentido. No hay normas de rigor: ante cualquier argumento, o bien te convence de que la conclusión es necesariamente cierta, y entonces ya está, o no te parece concluyente, y entonces no vale.

Todo esto se hace precisamente para poder dar un concepto preciso de lo que debemos entender por "rigor matemático". No puedes definir el "rigor matemático" con "rigor matemático" sin caer en un círculo vicioso.

20 Agosto, 2021, 01:30 pm
Respuesta #5

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, gracias por los comentarios.

Lo que pasa en el fondo es que  \( S_{x_i}^{x_j} \alpha \) es, o bien, la propia fórmula \( \alpha \) (que tiene la misma longitud que \( \alpha \)), o bien la fórmula que resulta de cambiar cada \( x_i \) por \( x_j \) en \( \alpha \) (y al cambiar una variable por otra no alteras la longitud) o, en el peor de los casos, si al meter \( x_j \) va a quedar ligada, lo evitas cambiando las \( x_j \) que ya hubiera en la fórmula por otra variable distinta, pero eso tampoco altera la longitud.

En suma, que, en cualquier caso, \( S_{x_i}^{x_j} \alpha \) se diferencia de \( \alpha \) a lo sumo en que algunas variables han sido cambiadas por otras, pero no has añadido o quitado nada que pueda hacer la fórmula más larga o más corta. En general, por esta misma razón, cuando cambias una variable \( x \) por un término \( t \) de longitud  \( l \), la longitud de la expresión resultante será la de la expresión inicial más \( n(l-1) \), donde \( n \) es el número de veces que \( x \) aparece libre en la expresión inicial, porque lo que haces es cambiar unas variables por otras y cambiar cada una de las \( n \) variables \( x \) libres por el término \( t \), lo cual hace que la longitud aumente \( l-1 \) unidades por cada \( t \) insertado.

Ya, eso es lo que pensaba que realmente solo estás cambiando unos símbolos por otros, pero sin añadir ninguno extra.

La razón que lo hace evidente es la que te digo. Si te convence, pues ya está, y si prefieres la inducción, pues bien está, pero aquí lo de "para ser del todo rigurosos" no tiene sentido. No hay normas de rigor: ante cualquier argumento, o bien te convence de que la conclusión es necesariamente cierta, y entonces ya está, o no te parece concluyente, y entonces no vale.

Todo esto se hace precisamente para poder dar un concepto preciso de lo que debemos entender por "rigor matemático". No puedes definir el "rigor matemático" con "rigor matemático" sin caer en un círculo vicioso.

Cierto, fallo mío al expresarme. Lo que realmente quería decir es si había algún argumento a parte del inductivo para justificarlo.

Ya que estoy, tengo otra duda relacionada precisamente con esto último. Todos los teoremas que se prueban en los primeros capítulos de tu libro deberían llamarse realmente metateoremas, ¿no?.

Es que, no me queda del todo claro la distinción pero si entendí bien, al hacer metamatemática estás hablando sobre propiedades que pueden tener o no las expresiones o conjuntos de expresiones que se emplean en matemáticas. Y por tanto, hasta donde he podido leer y entender, todos los teoremas que se enuncian en estos términos son realmente metateoremas, no teoremas matemáticos en el sentido en el que estoy acostumbrado, ¿no?
Y, si esto es así, entonces todas estas demostraciones son, como dices, argumentos informales, con "informal" en el sentido que explicas en el libro, que si no entiendo mal, es que son argumentos precisos sobre definiciones precisas, pero que no se pueden formalizar en el sentido que se formalizan los razonamientos en el capítulo 2, pues entonces estaríamos en un círculo vicioso.

¿He entendido bien la cosas?

Un saludo y gracias.

20 Agosto, 2021, 02:19 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Lo que realmente quería decir es si había algún argumento a parte del inductivo para justificarlo.

Piénsalo en el caso general que te planteaba, que igual por ser más complicado hace que se vea todo más claro:

La longitud de \( S_x^t\theta \) es la longitud de \( \theta \) más \( n(l-1) \), donde \( l \) es la longitud de \( t \) y \( n \) es el número de veces que \( x \) aparece libre en \( \theta \).

Esto es así porque al sustituir \( x \) por \( t \) se sustuyen algunas variables ligadas de \( \theta \) por otras, lo cual no altera la longitud de la expresión resultante, y cada \( x \) que aparece libre se sustituye por \( t \), con lo cual sustituimos una variable \( x \) de longitud \( 1 \) por un término de longitud \( l \), lo que hace que la longitud total aumente en \( l-1 \) por cada sustitución, y eso hace que la longitud en total aumente \( n(l-1) \) unidades.

¿Te cabe alguna duda de que la conclusión es correcta? Podrías demostrar esto mismo por inducción, pero la prueba quedará un poco farragosa, y la cuestión es, ¿si te pones a escribir con todo detalle la inducción necesaria, al final estarás más convencido de que el resultado es cierto de lo que lo estás ahora que no te has puesto a hacerlo?

Si la respuesta es que no, eso significa que el "rigor" que proporciona la inducción en este caso es superfluo.

Ya que estoy, tengo otra duda relacionada precisamente con esto último. Todos los teoremas que se prueban en los primeros capítulos de tu libro deberían llamarse realmente metateoremas, ¿no?.

Sí. Pasando las páginas rápidamente, los primeros teoremas propiamente dichos que he encontrado están en la página 87, pero puedo haberme saltado algunos.

Es que, no me queda del todo claro la distinción pero si entendí bien, al hacer metamatemática estás hablando sobre propiedades que pueden tener o no las expresiones o conjuntos de expresiones que se emplean en matemáticas. Y por tanto, hasta donde he podido leer y entender, todos los teoremas que se enuncian en estos términos son realmente metateoremas, no teoremas matemáticos en el sentido en el que estoy acostumbrado, ¿no?

En efecto, un teorema (en sentido "moderno") es una fórmula demostrable en un sistema deductivo formal. Para hablar de teoremas es necesario haber fijado unos axiomas y unas reglas de inferencia. He precisado lo de "en sentido moderno" porque, obviamente, cuando Fermat demostraba que \( x^4+y^4=z^4 \) no tiene soluciones enteras no sabría decirte qué axiomas o qué reglas de inferencia estaba usando, pero el caso es que su demostración es formalizable, es decir, que puede convertirse en un teorema en sentido moderno considerando los axiomas y reglas de inferencia de ZFC (y los de teorías mucho más débiles, para este caso en concreto).

En cambio, el hecho de que \( S_x^y\theta \) tiene la misma longitud que \( \theta \) no es un teorema en ese sentido. Es uno de los muchos resultados que usamos para estudiar los sistemas deductivos que usaremos para definir ZFC y justificar que cumple todo lo exigible (¡salvo tal vez la consistencia!) para que podamos afirmar que un teorema matemático en el sentido "tradicional" es lo mismo que un teorema demostrable en ZFC.

Y, si esto es así, entonces todas estas demostraciones son, como dices, argumentos informales, con "informal" en el sentido que explicas en el libro, que si no entiendo mal, es que son argumentos precisos sobre definiciones precisas, pero que no se pueden formalizar en el sentido que se formalizan los razonamientos en el capítulo 2, pues entonces estaríamos en un círculo vicioso.

Sí, salvo un pequeño matiz. No es que no se puedan formalizar. Se pueden formalizar, pero entonces obtenemos otra cosa no equivalente.

  • Partimos de nuestra convicción de que podemos hablar con seguridad de conceptos finitos como sucesiones finitas de signos y sucesiones finitas de sucesiones finitas de signos (y, cuando apuramos un poco y dependiendo de la filosofía de cada cual, también de ciertos conceptos infinitos sin tomamos precauciones).
  • A partir de ahí damos una serie de definiciones y demostramos algunos hechos hasta construir ZFC y otras teorías axiomáticas de interés.
  • Pero en ZFC, e incluso en otras teorías más débiles, es posible formalizar toda la metamatemática, es decir, podemos definir en ZFC lo que es un lenguaje formal, lo que son términos y fórmulas, lo que es un sistema deductivo formal, lo que es un teorema, etc. Y entonces todos los razonamientos metamatemáticos informales se pueden formalizar, es decir, se pueden demostrar con rigor matemático, es decir, se puede justificar que son teoremas de ZFC.
  • El círculo vicioso al que haces referencia surge si pretendes definir ZFC usando teoremas de ZFC, pero una vez construido ZFC (u otra teoría más débil capaz de formalizar la lógica) nada te impide estudiar la lógica trabajando en ZFC o incluso definir y estudiar ZFC mediante teoremas de ZFC.
  • Es precisamente cuando se estudia ZFC desde ZFC (o en general una teoría formalizada en ella misma)  cuando la distinción entre teoremas y metateoremas es más crucial que nunca, y es fundamental distinguir si en un momento dado hablamos de una fórmula "de verdad" o lo que dentro de la teoría se define como "fórmula", que es otra cosa. Si no se establece claramente la distinción caemos inmediatamente en paradojas y contradicciones.
¿He entendido bien la cosas?

Yo diría que sí.

20 Agosto, 2021, 03:12 pm
Respuesta #7

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por la respuesta y las aclaraciones ;D

El matiz que comentas en el mensaje anterior sobre la metamatemática, se expone en detalle más adelante en tu libro sobre lógica, ¿no?

Un saludo.

20 Agosto, 2021, 03:22 pm
Respuesta #8

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El matiz que comentas en el mensaje anterior sobre la metamatemática, se expone en detalle más adelante en tu libro sobre lógica, ¿no?

Sí, el hecho de que la lógica es formalizable en cualquier teoría lógica suficientemente potente (en cualquier teoría aritmética) se analiza en el capítulo VIII, y es algo esencial en la demostración de los teoremas de incompletitud.