Autor Tema: Regla de eliminación del particularizador (Lógica matemática de Carlos Ivorra)

0 Usuarios y 2 Visitantes están viendo este tema.

02 Septiembre, 2021, 12:15 pm
Leído 3141 veces

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, tengo algunas dudas respecto a la regla de eliminación del particularizador descrita en la página 68 del libro Lógica matemática de Carlos Ivorra.

Mi primera duda es si la línea m+1 es una hipótesis que introducimos tal como en el teorema de deducción, o que realmente se puede deducir a partir de las líneas anteriores.

Por otra parte, respecto al uso de la regla tengo también dudas. Lo que dice el metateorema es que si a partir de la línea m+1 no se generaliza respecto a variables libres en \( S_x^y \alpha \), entonces cualquier línea posterior \( \beta \) que no tenga libre la variable \( y \) es consecuencia de las premisas iniciales. Pero, por lo que veo en la demostración, da igual que para llegar a \( \beta \) si hayan líneas intermedias donde la variable y no esté libre, ¿no?

Un saludo y gracias por las respuestas.

02 Septiembre, 2021, 12:35 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Mi primera duda es si la línea m+1 es una hipótesis que introducimos tal como en el teorema de deducción, o que realmente se puede deducir a partir de las líneas anteriores.

No, en general, la línea \( m+1 \) no se puede deducir de las anteriores. Por simplicidad, considera el caso en que \( y\equiv x \). Si a partir de \( \exists x\alpha \) se pudiera deducir \( \alpha \) (sin necesidad de la regla de eliminación del particularizador y, por consiguiente, sin necesidad de cumplir sus condiciones), a continuación podríamos usar el generalizador y deducir \( \forall x\alpha \), pero, en general, no puedes deducir que todo \( x \) cumple \( \alpha \) a partir de una premisa que dice que existe un \( x \) que cumple \( \alpha \).

Puedes equipararlo a lo que se hace al usar el teorema de deducción, pero no es exactamente una "hipótesis". No es algo que "supongas". Lo que estás haciendo ahí es lo que hace cualquier matemático cotidianamente cuando en una demostración ha probado que existe un \( x \) que cumple algo y dice: "tomemos un \( x_0 \) en concreto que cumpla ese algo".

No está "suponiendo" nada, sino que está "tomando un ejemplo". La versión formal de eso de "tomar un ejemplo" es lo que dice la regla de eliminación del particularizador, que es que puedes tomar un \( x \) que cumpla \( \alpha \) con dos restricciones:

1) que la variable \( x \) sea "nueva", es decir, que no estés llamando ya \( x \) a otra cosa. Si no es así, tienes que cambiar la variable \( x \) por otra \( y \) para no llamar con el mismo nombre a dos cosas distintas.

2) a partir de ese momento te tienes que comprometer a no generalizar respecto de \( x \) ni las demás variables libres en \( \alpha \), porque, por defecto, una variable \( x \) significa "un \( x \) cualquiera", y por eso puedes generalizar cuando quieras, pero aquí la variable \( x \) pasa a ser "un ejemplo en particular" y no puedes generalizar (ni tampoco respecto de otras variables libres, podemos ver ejemplos que muestren por qué tiene que ser así, pero mejor si primero resuelves esta duda).

Pero todo esto son explicaciones añadidas. Si nos ceñimos al enunciado de la regla, lo único que estamos diciendo es que si en una demostración añades sin justificación alguna (sin que se deduzca de ninguna regla de inferencia) una línea \( S_x^y\alpha \) en las condiciones indicadas y luego cumples ciertos compromisos, aunque aparentemente nada de lo que digas tiene valor porque has añadido una línea "por la cara", resulta que no, que las líneas a las que llegues que no tengan libre la variable introducida pueden deducirse "honradamente" de las premisas.

Por otra parte, respecto al uso de la regla tengo también dudas. Lo que dice el metateorema es que si a partir de la línea m+1 no se generaliza respecto a variables libres en \( S_x^y \alpha \), entonces cualquier línea posterior \( \beta \) que no tenga libre la variable \( y \) es consecuencia de las premisas iniciales. Pero, por lo que veo en la demostración, da igual que para llegar a \( \beta \) si hayan líneas intermedias donde la variable y no esté libre, ¿no?

No me cuadra lo que dices. ¿No querrás decir "da igual que para llegar a \( \beta \) sí haya líneas intermedias donde la variable \( y \) sí esté libre"?

En tal caso, la respuesta es afirmativa, y no puede ser de otro modo, porque en la línea (m+1) está libre la variable \( y \), y lo seguirá estando en las líneas que deduzcas de ella mientras no se acabe eliminando de un modo u otro o bien la ligues mediante un particularizador.

02 Septiembre, 2021, 12:52 pm
Respuesta #2

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, gracias por responder tan rápido  ;D


No, en general, la línea \( m+1 \) no se puede deducir de las anteriores. Por simplicidad, considera el caso en que \( y\equiv x \). Si a partir de \( \exists x\alpha \) se pudiera deducir \( \alpha \) (sin necesidad de la regla de eliminación del particularizador y, por consiguiente, sin necesidad de cumplir sus condiciones), a continuación podríamos usar el generalizador y deducir \( \forall x\alpha \), pero, en general, no puedes deducir que todo \( x \) cumple \( \alpha \) a partir de una premisa que dice que existe un \( x \) que cumple \( \alpha \).

Puedes equipararlo a lo que se hace al usar el teorema de deducción, pero no es exactamente una "hipótesis". No es algo que "supongas". Lo que estás haciendo ahí es lo que hace cualquier matemático cotidianamente cuando en una demostración ha probado que existe un \( x \) que cumple algo y dice: "tomemos un \( x_0 \) en concreto que cumpla ese algo".

No está "suponiendo" nada, sino que está "tomando un ejemplo". La versión formal de eso de "tomar un ejemplo" es lo que dice la regla de eliminación del particularizador, que es que puedes tomar un \( x \) que cumpla \( \alpha \) con dos restricciones:

1) que la variable \( x \) sea "nueva", es decir, que no estés llamando ya \( x \) a otra cosa. Si no es así, tienes que cambiar la variable \( x \) por otra \( y \) para no llamar con el mismo nombre a dos cosas distintas.

2) a partir de ese momento te tienes que comprometer a no generalizar respecto de \( x \) ni las demás variables libres en \( \alpha \), porque, por defecto, una variable \( x \) significa "un \( x \) cualquiera", y por eso puedes generalizar cuando quieras, pero aquí la variable \( x \) pasa a ser "un ejemplo en particular" y no puedes generalizar (ni tampoco respecto de otras variables libres, podemos ver ejemplos que muestren por qué tiene que ser así, pero mejor si primero resuelves esta duda).

Pero todo esto son explicaciones añadidas. Si nos ceñimos al enunciado de la regla, lo único que estamos diciendo es que si en una demostración añades sin justificación alguna (sin que se deduzca de ninguna regla de inferencia) una línea \( S_x^y\alpha \) en las condiciones indicadas y luego cumples ciertos compromisos, aunque aparentemente nada de lo que digas tiene valor porque has añadido una línea "por la cara", resulta que no, que las líneas a las que llegues que no tengan libre la variable introducida pueden deducirse "honradamente" de las premisas.

Vale, creo ya lo entiendo.

Formalmente si estamos haciendo lo mismo que con el teorema de deducción, pues añadimos una línea que no se deduce de nada anterior ni de las premisas, y utilizándola (y teniendo en cuenta ciertas cosas que no podemos hacer en la deducción desde ese punto, que son las mismas cosas que en el teorema de deducción) llegamos a que, la conclusión que obtengamos de todo ello será deducible "honradamente" a partir de únicamente las premisas.

Pero, por otra parte, a nivel semántico no es exactamente lo mismo pues como dices, lo que aquí hacemos es explicitar un ejemplo que "nos garantiza" el cuantificador.

¿Lo he entendido bien?

No me cuadra lo que dices. ¿No querrás decir "da igual que para llegar a \( \beta \) sí haya líneas intermedias donde la variable \( y \) sí esté libre"?

En tal caso, la respuesta es afirmativa, y no puede ser de otro modo, porque en la línea (m+1) está libre la variable \( y \), y lo seguirá estando en las líneas que deduzcas de ella mientras no se acabe eliminando de un modo u otro o bien la ligues mediante un particularizador.

Si, aquí quería decir esto. Metí un "no" donde no debía  ::)

Un saludo y gracias de nuevo.

02 Septiembre, 2021, 01:06 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Lo he entendido bien?

Perfectamente. Te pongo un ejemplo de por qué no se puede generalizar respecto de ninguna variable libre en la fórmula que dejas cuando eliminas el particularizador. Pon que hablamos de números naturales y partimos de aquí:

\( \forall m\exists n\, m<n \)   (por encima de un número natural hay siempre otro).

De ahí podemos quitar el generalizador. Un matemático diría: sea \( m \) un número natural arbitrario, de modo que

\( \exists n\, m<n \).

Ahora podemos eliminar el particularizador. Un matemático diría: tomemos un número natural \( n \) tal que:

\( m<n \).

Hemos usado la variable \( n \) para ejemplificar el particularizador, pero \( m \) también está libre en la fórmula resultante. Si generalizamos respecto de \( m \), estamos haciendo lo que un matemático borracho explicaría así:

Como \( m \) es un número natural arbitrario, podemos concluir que

\( \forall m\, m<n \),

y como \( n \) era un número natural en concreto, podemos introducir el particularizador y concluir que

\( \exists n\forall m\, m<n \).

En suma, hemos "demostrado" que hay un número natural mayor que todos los números naturales. Incluso mayor que sí mismo.

03 Septiembre, 2021, 07:14 pm
Respuesta #4

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, muchas gracias por este último ejemplo. Así queda todo muy, muy claro  ;D

Ya que estaba, por no abrir otro hilo ya que lo que quiero preguntar está muy relacionado con esto, lo pregunto por aquí si os parece bien.

Mi duda es respecto a la demostración de c) en el Teorema 2.9.

Entiendo que es aplicar "de forma sucesiva" b), pero al querer hacerlo bien he tenido ciertas dificultades y quería exponer aquí mi prueba para saber si lo que he hecho es en primer lugar correcto, pero también para saber si realmente es innecesario, pues es más sencillo que todo eso.

Expongo pues la demostración, donde en rojo escribo las razones por las que he tomado este camino.

Demostración:

Por definición tenemos que

\( \exists! x_1 \cdots x_n \alpha \equiv \exists z_1 \cdots z_n \forall x_1 \cdots x_n \left( \alpha \leftrightarrow x_1=z_1 \wedge \cdots \wedge x_n=z_n \right) \)

donde \( z_1, \cdots, z_n \) son las variables de menor índice que no están en \( \forall x_1 \cdots x_n \alpha \).

Consideremos pues \( w_1, \cdots, w_n \) variables que no estén en \( \forall x_1 \cdots x_n \alpha \) y distintas de \( z_1, \cdots, z_n, y_1, \cdots, y_n \). Esto lo he hecho, pues en primer lugar intenté probarlo directamente para \( y_1, \cdots, y_n \) pero encontraba ciertas dificultades si, por ejemplo, \( y_n \equiv z_{n-1} \).

Entonces, si denominamos

\( \beta \equiv \forall x_1 \cdots x_n \left( \alpha \leftrightarrow x_1=z_1 \wedge \cdots \wedge x_n=z_n \right) \)

como \( w_n \) no está en \( \beta \), por b) se tiene que

\( \vdash \exists z_n \beta \leftrightarrow \exists w_n S_{z_n}^{w_n} \beta \hspace{4mm} (*_1) \)

Ahora, supongamos que para cada \( j \leq i \) se cumple que

\( \vdash \exists z_{n-(j-1)} \cdots z_n \beta \leftrightarrow \exists w_{n-(j-1)} \cdots w_n S_{z_{n-(j-1)}}^{w_{n-(j-1)}} \cdots S_{z_n}^{w_n} \beta \hspace{4mm} (*_j) \)

entonces, como \( w_{n-i} \) no está en \( \exists w_{n-(j-1)} \cdots w_n S_{z_{n-(j-1)}}^{w_{n-(j-1)}} \cdots S_{z_n}^{w_n} \beta \) se tiene que

\(
\begin{array}{cll}
(1) & \exists z_{n-(i-1)} \cdots z_n \beta \leftrightarrow \exists w_{n-(i-1)} \cdots w_n S_{z_{n-(i-1)}}^{w_{n-(i-1)}} \cdots S_{z_n}^{w_n} \beta & \text{Tma. logico }(*_i)\\
(2) & \exists z_{n-i} \exists z_{n-(i-1)} \cdots z_n \beta \leftrightarrow \exists z_{n-i} \exists w_{n-(i-1)} \cdots w_n S_{z_{n-(i-1)}}^{w_{n-(i-1)}} \cdots S_{z_n}^{w_n} \beta & \text{PB }1\\
(3) & \exists z_{n-i} \exists w_{n-(i-1)} \cdots w_n S_{z_{n-(i-1)}}^{w_{n-(i-1)}} \cdots S_{z_n}^{w_n} \beta \leftrightarrow \exists w_{n-i} S_{z_{n-i}}^{w_{n-i}} \exists w_{n-(i-1)} \cdots w_n S_{z_{n-(i-1)}}^{w_{n-(i-1)}} \cdots S_{z_n}^{w_n} \beta & \text{Tma. logico (b)}\\
(4) & \exists z_{n-i} \exists w_{n-(i-1)} \cdots w_n S_{z_{n-(i-1)}}^{w_{n-(i-1)}} \cdots S_{z_n}^{w_n} \beta \leftrightarrow \exists w_{n-i} w_{n-(i-1)} \cdots w_n S_{z_{n-i}}^{w_{n-i}} S_{z_{n-(i-1)}}^{w_{n-(i-1)}} \cdots S_{z_n}^{w_n} \beta & \text{R }3\\
(5) & \exists z_{n-i} \cdots z_n \beta \leftrightarrow \exists w_{n-i} \cdots w_n S_{z_{n-i}}^{w_{n-i}} \cdots S_{z_n}^{w_n} \beta & \text{MBB }2, 4
\end{array}
 \)

Donde (PB): \( \alpha \leftrightarrow \beta \vdash \exists x \alpha \leftrightarrow \exists x \beta \) y (MBB): \( \alpha \leftrightarrow \beta, \beta \leftrightarrow \gamma \vdash \alpha \leftrightarrow \gamma \). (MBB) es simplemente aplicar (MB) junto a (IB) y (EB), pero me parecía más conveniente tener una regla propia para este hecho, y respecto a (PB) la he demostrado porque no veía otra forma de como realizar la deducción anterior en base a las reglas anteriores en el libro. Pongo en spoiler la demostración por si acaso fuera erronea.

Spoiler
(GC): \( \alpha \rightarrow \beta \vdash \forall x \alpha \rightarrow \forall x \beta \)

\(
\begin{array}{cll}
(1) & \alpha \rightarrow \beta & \text{Premisa}\\
(2) &  \forall x \alpha & \text{Hipotesis}\\
(3) & \alpha & \text{EG }2 \\
(4) & \beta & \text{MP }1, 3 \\
(5) & \forall x \beta & \text{IG } 4  \\
(6) & \forall x \alpha \rightarrow \forall x \beta & \text{Tma. deduccion}         
\end{array}
 \)

(Debería haber una raya vertical desde (2) a (5) pero no se como ponerla usando latex en el foro)
El uso de IG en 5 es válido porque \( x \) no está libre en \( \forall x \alpha \).

(GB): \( \alpha \leftrightarrow \beta \vdash \forall x \alpha \leftrightarrow \forall x \beta \)

La prueba es directa a partir de lo anterior, EB e IB.

(PC): \( \alpha \rightarrow \beta \vdash \exists x \alpha \rightarrow \exists x \beta \)

\(
\begin{array}{cll}
(1) & \alpha \rightarrow \beta & \text{Premisa}\\
(2) &  \neg \beta \rightarrow \neg \alpha & \text{NI }1\\
(3) & \forall x\neg \beta \rightarrow \forall x \neg \alpha & \text{GC }2 \\
(4) & \neg \forall x \neg \alpha \rightarrow \neg \forall x \neg \beta & \text{NI }3 \\
(5) & \exists x \alpha \rightarrow \exists x \beta & \text{R }4       
\end{array}
 \)

(PB): \( \alpha \leftrightarrow \beta \vdash \exists x \alpha \leftrightarrow \exists x \beta \)

De nuevo, la prueba es directa a partir de PC, EB e IB.
[cerrar]

Por lo que

\( \vdash \exists z_{n-i} \cdots z_n \beta \leftrightarrow \exists w_{n-i} \cdots w_n S_{z_{n-i}}^{w_{n-i}} \cdots S_{z_n}^{w_n} \beta \hspace{4mm} (*_{i+1}) \)

Con todo, por inducción tenemos que

\( \vdash \exists z_1 \cdots z_n \beta \leftrightarrow \exists w_1 \cdots w_n S_{z_1}^{w_1} \cdots S_{z_n}^{w_n} \beta \)

y como

\( S_{z_1}^{w_1} \cdots S_{z_n}^{w_n} \beta \equiv \underbrace{\forall x_1 \cdots x_n \left(  \alpha \leftrightarrow x_1=w_1 \wedge \cdots \wedge x_n=w_n \right)}_{\beta'} \)

obtenemos finalmente que

\( \vdash \exists z_1 \cdots z_n \beta \leftrightarrow \exists w_1 \cdots w_n \beta' \hspace{4mm} (*) \)

Por otra parte, observemos que \( y_1, \cdots, y_n \) no están en \( \forall x_1, \cdots, x_n \alpha \) y son distintos de \( w_1, \cdots, w_n \), con lo que realizando lo mismo que hemos hecho anteriormente podemos obtener que

\( \vdash \exists w_1 \cdots w_n \beta' \leftrightarrow \exists y_1 \cdots w_n \beta'' \hspace{4mm} (**) \)

siendo

\( \beta'' \equiv \forall x_1 \cdots x_n \left( \alpha \leftrightarrow x_1=y_1 \wedge \cdots \wedge x_n=y_n \right) \)

Con todo, aplicando MBB a (*) y (**) obtenemos el resultado deseado.

Un saludo y muchas gracias por vuestro tiempo.

04 Septiembre, 2021, 12:25 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Lo veo bien. Lo único que te diría es que complicas la notación al llenarlo todo de "eses" cuando puedes escribir explícitamente las sustituciones.

En efecto, conviene hacer esto:

Consideremos pues \( w_1, \cdots, w_n \) variables que no estén en \( \forall x_1 \cdots x_n \alpha \) y distintas de \( z_1, \cdots, z_n, y_1, \cdots, y_n \). Esto lo he hecho, pues en primer lugar intenté probarlo directamente para \( y_1, \cdots, y_n \) pero encontraba ciertas dificultades si, por ejemplo, \( y_n \equiv z_{n-1} \).

O, lo que es lo mismo, podemos decir que no perdemos generalidad si suponemos que las \( y_i \) son distintas de las \( z_j \), porque si hay coincidencias tomamos variables \( w_i \) distintas de todas, sustituimos primero las \( z_i \) por las \( w_i \) y luego sustituimos las \( w_i \) por las \( y_i \).

Entonces aplicamos b) a la fórmula

\( \beta \equiv \forall x_1 \cdots x_n \left( \alpha \leftrightarrow x_1=z_1 \wedge \cdots \wedge x_n=z_n \right) \)

y obtenemos:

\( \exists z_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_n=z_n)\leftrightarrow \exists w_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_{n-1}=z_{n-1}\land x_n=w_n) \).

De aquí, con la regla que has llamado (PB), podemos pasar a

\( \exists z_{n-1}z_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_n=z_n)\leftrightarrow \exists z_{n-1}w_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_{n-1}=z_{n-1}\land x_n=w_n) \).

Ahora aplicamos b) al miembro derecho, con lo que obtenemos:

\( \exists z_{n-1}w_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_{n-1}=z_{n-1}\land x_n=w_n)\leftrightarrow
 \)
\(
\exists w_{n-1}w_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_{n-2}=z_{n-2}\land x_{n-1}=w_{n-1}\land x_n=w_n) \)

y encadenando las dos coimplicaciones obtenemos:

\( \exists z_{n-1}z_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_n=z_n)\leftrightarrow \exists w_{n-1}w_n\forall x_1\cdots x_n(\alpha\leftrightarrow x_1=z_1\land \cdots \land x_{n-2}=z_{n-2}\land x_{n-1}=w_{n-1}\land x_n=w_n) \).

Y así podemos seguir hasta sustituir todas las variables.

Creo que esto es exactamente lo que has hecho.

04 Septiembre, 2021, 11:50 am
Respuesta #6

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Gracias Carlos por confirmármelo, justo lo que comentas es efectivamente lo que he hecho  ;D

Tengo una última duda respecto a lo que comentas en el libro después de la prueba de EP sobre la deducción en la página 54.

Comentas que si utilizamos EP para deducir cierta fórmula \( \beta \) a partir de unas premisas debemos llevar cuidado pues en la deducción irá de forma implícita una generalización respecto de la variable \( y \), y creo que te refieres a la que aparece en la línea (5) de la prueba, porque sabemos que al aplicar el teorema de deducción, se generaliza de exactamente las mismas variables que las que usamos en la deducción con la hipótesis adicional.

Ahora bien, ¿en la prueba no se generaliza también de forma implícita respecto de \( x \)?

Para tener \( \exists y S_x^y \alpha \) como premisa, una de las líneas de nuestra deducción deberá ser el teorema lógico dado en el resultado anterior \( \exists x \alpha \leftrightarrow \exists y S_x^y \alpha \). Realmente nos basta con \( \exists x \alpha \rightarrow \exists y S_x^y \alpha \).

Ahora, si no estoy equivocado la deducción de este teorema lógico es como sigue:

\(
\begin{array}{cll}
(1) & \forall y S_x^y \neg \alpha \rightarrow \forall x \neg \alpha & \text{Teo. logico}\\
(2) & \neg \forall x \neg \alpha \rightarrow \neg \forall y S_x^y \neg \alpha & \text{NI }1\\
(3) & \exists x \alpha \rightarrow \exists y S_x^y \alpha & \text{R }2
\end{array}
 \)

Pero, para obtener el teorema lógico en (1), \( \forall y S_x^y \alpha \rightarrow \forall x \alpha \) ,la deducción es la siguiente:

\(
\begin{array}{cll}
(1) & \forall y S_x^y \alpha & \text{Hipotesis}\\
(2) & S_y^x S_x^y \alpha & \text{EG }1\\
(3) & \alpha & \text{R }2\\
(4) & \forall x \alpha & \text{IG }3\\
(5) & \forall y S_x^y \alpha \rightarrow \forall x \alpha & \text{Teo. deduccion}
\end{array}
 \)

Nuevamente, debe aparecer una línea vertical de (1) a (4) que no se poner.
(3) es consecuencia del Teorema 1.13 pues por hipótesis \( y \) no está en \( \alpha \).
Podemos generalizar respecto de \( x \) en (4) porque \( x \) no está libre en \( \forall y S_x^y \alpha \), ya que de estarlo, de nuevo por el Teorema 1.13 tendríamos que \( x \equiv y \) siendo \( x \) libre en \( \alpha \), lo que contradice que \( y \) no está en \( \alpha \).

Así, la deducción anterior creo que es válida, y como se ve, se generaliza respecto de \( x \), por lo que en la deducción del teorema lógico que nos interesa \( \exists x \alpha \rightarrow \exists y S_x^y \alpha \) también se generaliza respecto de \( x \).

Ahora, si todo lo anterior es cierto y no he metido la pata en nada, al aplicar EP en una deducción generalizamos tanto respecto de \( x \) como de \( y \).

Por tanto, en la deducción de la página 54 en la línea 7, ¿no deberíamos haber utilizado una variable distinta de \( u \)?

Digo esto porque, como se dice en la página 69 desde la línea 5 tenemos prohibido generalizar respecto de \( x, y, z \) y \( u \), pero tal como está escrita la deducción, en la línea 7 aparece \( \exists u z=yu \), y al particularizar en la línea 8, aunque cambiemos de variable a \( v \), al aplicar EP vamos a generalizar tanto respecto de \( v \) como de \( u \), donde lo último no lo podemos hacer. ¿Es esto correcto?

En caso de que fuera correcto todo lo que he dicho, creo que la solución simplemente pasa por cambiar la línea 7 por directamente \( \exists v z=yv \), ¿no?

Un saludo y gracias por todo.

04 Septiembre, 2021, 01:04 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Empezando por el núcleo de la duda:

Por tanto, en la deducción de la página 54 en la línea 7, ¿no deberíamos haber utilizado una variable distinta de \( u \)?

La respuesta es no. Da igual usar \( u \) o cualquier otra variable. Y, si somos puntillosos y queremos respetar la definición de \( y\mid z \) y en ella hemos usado la variable \( u \), pues ésa es "la que toca" (aunque sabemos que podemos cambiarla por cualquier otra y obtenemos una fórmula equivalente).

Y antes de entrar en por qué no hay problema en usar la variable \( u \), conviene que entiendas por qué no tiene que haber problema. Imagina que un matemático que no sabe nada de lógica matemática ve la demostración de la página 54, por ejemplo en la versión "verbalizada" de la izquierda. ¿Crees que se le ocurriría poner cualquier objeción al uso de la variable \( u \) en la línea (7)? Pon que no sabe nada de lo que es EP, pero sabe razonar lógicamente. ¿Tendría algo que objetar al uso de esa variable?

Si en la línea (8) pusieras \( z=yu \) sí que se quejaría. Aun sin saber nada de EP o del teorema de deducción, te diría: "No puedes usar la letra \( u \) porque ya estás llamando \( u \) a otra cosa". Un matemático no tiene nada que objetar a que escribas \( \exists u a= bu \) y \( \exists u c= du \) siempre y cuando al eliminar los cuantificadores uses letras diferentes.

Pues bien: un principio fundamental es que si algo le parece bien a un matemático que sepa razonar sin saber lógica, eso está bien, y nada en la teoría que estás estudiando se opondrá a ello. O, dicho al revés: todas las restricciones que impone la teoría sobre cuándo se puede generalizar, o qué variables se pueden usar, etc. son exactamente las mismas que los matemáticos se imponen "instintivamente" cuando razonan sin saber nada de lógica formal. O dicho de forma más práctica: Si te molesta algo que a un matemático no le molestaría, es que algo estás entendiendo mal.

Este principio te puede ser muy útil para orientarte. Ahora vamos a ver por qué funciona en este caso concreto. Dices:

Ahora, si todo lo anterior es cierto y no he metido la pata en nada, al aplicar EP en una deducción generalizamos tanto respecto de \( x \) como de \( y \).

La respuesta es "sí, pero no", y lo más importante es que si la respuesta fuera "sí", sería una pesadilla, porque eso significaría que cada vez que usamos un teorema tenemos que "recordar" qué hemos hecho en su demostración, con lo cual no podríamos estar seguros nunca de qué variables podemos usar libremente, porque nunca podríamos saber qué hemos hecho para demostrar los resultados previos que usamos.

El problema que ves es éste:

Ahora bien, ¿en la prueba no se generaliza también de forma implícita respecto de \( x \)?

Para tener \( \exists y S_x^y \alpha \) como premisa, una de las líneas de nuestra deducción deberá ser el teorema lógico dado en el resultado anterior \( \exists x \alpha \leftrightarrow \exists y S_x^y \alpha \). Realmente nos basta con \( \exists x \alpha \rightarrow \exists y S_x^y \alpha \).

Así, la deducción anterior creo que es válida, y como se ve, se generaliza respecto de \( x \), por lo que en la deducción del teorema lógico que nos interesa \( \exists x \alpha \rightarrow \exists y S_x^y \alpha \) también se generaliza respecto de \( x \).

En efecto, se generaliza respecto de \( x \), pero eso no importa. En general, nunca tiene que preocuparte respecto de qué variables se generaliza en los teoremas que usas. Y la razón es que, cuando quieres usar un teorema en una demostración, si quieres que ésta sea autocontenida, siempre puedes empezar demostrando todos los teoremas que necesitas, y cuando ya los tienes demostrados todos, entonces puedes empezar con la demostración propiamente dicha. Y en ese momento en el que empiezas la demostración propiamente dicha, con todas las demostraciones previas terminadas, no estás sujeto a ninguna restricción que te impida generalizar respecto de nada, y dispones de todos los teoremas necesarios como líneas previas que puedes usar.

Piensa que todas las limitaciones sobre las variables que puedes usar o sobre las que puedes generalizar son "locales", en el sentido de que forman parte de metateoremas que te aseguran que ciertas fórmulas son demostrables, pero si ya sabes que \( \alpha \) es demostrable, entonces sabes que existe una demostración pura y dura de \( \alpha \) según la definición, es decir, una demostración que no es sino una sucesión de fórmulas que se obtienen de axiomas mediante las dos reglas de inferencia, sin ninguna condición adicional (ni mucho menos ningún compromiso sobre lo que puedes hacer luego si quieres usar ese teorema).

Más concretamente, si tienes una "pseudodemostración" que usa ED, es decir, que usa "por la cara" la premisa adicional \( S_x^y\alpha \), y quieres transformarla en otra que no use esta premisa, tienes que hacer la manipulación descrita en la prueba de ED y, como bien dices, así obtendremos otra demostración que tiene incrustada una demostración de \( \exists x\alpha\rightarrow \exists yS_x^y\alpha \), pero si todo esto quieres incrustarlo a su vez en una demostración en la que esté prohibido generalizar respecto de \( x \), lo único que tienes que hacer es colocar la demostración de \( \exists x\alpha\rightarrow \exists yS_x^y\alpha \) antes del punto de dicha demostración en el que empieza a estar prohibido generalizar respecto de \( x \), y asunto arreglado.

Por ejemplo, si quieres eliminar las eliminaciones del particularizador en la demostración de la página 54, necesitarás \( \exists u\, z = xu\rightarrow \exists v\,z = xv \), y sólo necesitas asegurarte de incluir la demostración de este teorema antes de la línea (5), cuando no hay ningún inconveniente en generalizar respecto de \( u \), y usarla luego cuando la necesites.

Este "truco" no te exime de la prohibición de generalizar respecto de las variables libres en \( S_x^y\alpha \), porque eso es necesario para aplicar el teorema de deducción en la prueba de ED.


04 Septiembre, 2021, 01:44 pm
Respuesta #8

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, una explicación excelente como siempre.

Pues bien: un principio fundamental es que si algo le parece bien a un matemático que sepa razonar sin saber lógica, eso está bien, y nada en la teoría que estás estudiando se opondrá a ello. O, dicho al revés: todas las restricciones que impone la teoría sobre cuándo se puede generalizar, o qué variables se pueden usar, etc. son exactamente las mismas que los matemáticos se imponen "instintivamente" cuando razonan sin saber nada de lógica formal. O dicho de forma más práctica: Si te molesta algo que a un matemático no le molestaría, es que algo estás entendiendo mal.

Tendré en cuenta este principio cuando me vuelvan a surgir una duda de este estilo y así igual podré solventarla yo solo  :laugh:

Ahora, si todo lo anterior es cierto y no he metido la pata en nada, al aplicar EP en una deducción generalizamos tanto respecto de \( x \) como de \( y \).

La respuesta es "sí, pero no", y lo más importante es que si la respuesta fuera "sí", sería una pesadilla, porque eso significaría que cada vez que usamos un teorema tenemos que "recordar" qué hemos hecho en su demostración, con lo cual no podríamos estar seguros nunca de qué variables podemos usar libremente, porque nunca podríamos saber qué hemos hecho para demostrar los resultados previos que usamos.

Ciertamente, si la respuesta fuera únicamente "sí" deberías llevar una cuenta mental de sobre que se generaliza en cada teorema y la lógica sería infernal  >:D

En efecto, se generaliza respecto de \( x \), pero eso no importa. En general, nunca tiene que preocuparte respecto de qué variables se generaliza en los teoremas que usas. Y la razón es que, cuando quieres usar un teorema en una demostración, si quieres que ésta sea autocontenida, siempre puedes empezar demostrando todos los teoremas que necesitas, y cuando ya los tienes demostrados todos, entonces puedes empezar con la demostración propiamente dicha. Y en ese momento en el que empiezas la demostración propiamente dicha, con todas las demostraciones previas terminadas, no estás sujeto a ninguna restricción que te impida generalizar respecto de nada, y dispones de todos los teoremas necesarios como líneas previas que puedes usar.

Piensa que todas las limitaciones sobre las variables que puedes usar o sobre las que puedes generalizar son "locales", en el sentido de que forman parte de metateoremas que te aseguran que ciertas fórmulas son demostrables, pero si ya sabes que \( \alpha \) es demostrable, entonces sabes que existe una demostración pura y dura de \( \alpha \) según la definición, es decir, una demostración que no es sino una sucesión de fórmulas que se obtienen de axiomas mediante las dos reglas de inferencia, sin ninguna condición adicional (ni mucho menos ningún compromiso sobre lo que puedes hacer luego si quieres usar ese teorema).

Más concretamente, si tienes una "pseudodemostración" que usa ED, es decir, que usa "por la cara" la premisa adicional \( S_x^y\alpha \), y quieres transformarla en otra que no use esta premisa, tienes que hacer la manipulación descrita en la prueba de ED y, como bien dices, así obtendremos otra demostración que tiene incrustada una demostración de \( \exists x\alpha\rightarrow \exists yS_x^y\alpha \), pero si todo esto quieres incrustarlo a su vez en una demostración en la que esté prohibido generalizar respecto de \( x \), lo único que tienes que hacer es colocar la demostración de \( \exists x\alpha\rightarrow \exists yS_x^y\alpha \) antes del punto de dicha demostración en el que empieza a estar prohibido generalizar respecto de \( x \), y asunto arreglado.

Por ejemplo, si quieres eliminar las eliminaciones del particularizador en la demostración de la página 54, necesitarás \( \exists u\, z = xu\rightarrow \exists v\,z = xv \), y sólo necesitas asegurarte de incluir la demostración de este teorema antes de la línea (5), cuando no hay ningún inconveniente en generalizar respecto de \( u \), y usarla luego cuando la necesites.

Este "truco" no te exime de la prohibición de generalizar respecto de las variables libres en \( S_x^y\alpha \), porque eso es necesario para aplicar el teorema de deducción en la prueba de ED.

Creo que lo  he entendido. El punto es que, cuando usemos un teorema lógico en una demostración es completamente irrelevante sobre que variables se generaliza o no en su demostración pues, tras realizar una "pseudodemostración" donde utilicemos \( n \) teoremas lógicos dispuestos de la forma en la que hemos ido necesitándolos, podemos reescribirla de forma que las \( n \) primeras líneas de la "pseudodemostración" sean estos \( n \) teoremas lógicos, y como entonces ya son líneas anteriores de la demostración podemos utilizarlas sin problema aunque apliquemos el teorema de deducción o EP, o cualquier metateorema que nos prohíba en cierto momento generalizar respecto de ciertas variables.

¿Es esto lo que querías decirme?

Un saludo y muchas gracias por toda la ayuda. Sin todos estos comentarios entender ciertas cosas sería mucho más complicado.

04 Septiembre, 2021, 01:47 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Creo que lo  he entendido. El punto es que, cuando usemos un teorema lógico en una demostración es completamente irrelevante sobre que variables se generaliza o no en su demostración pues, tras realizar una "pseudodemostración" donde utilicemos \( n \) teoremas lógicos dispuestos de la forma en la que hemos ido necesitándolos, podemos reescribirla de forma que las \( n \) primeras líneas de la "pseudodemostración" sean estos \( n \) teoremas lógicos, y como entonces ya son líneas anteriores de la demostración podemos utilizarlas sin problema aunque apliquemos el teorema de deducción o EP, o cualquier metateorema que nos prohíba en cierto momento generalizar respecto de ciertas variables.

¿Es esto lo que querías decirme?

Exactamente.