Equivalencia entre cuantificaciones

Hemos visto aquí que podía, una vez introducido el cuantificador universal, intruducirse 'por definición' el existencial con la siguiente fórmula: (∃a)A ≡df ~(a)~A.

Esto significa que el universar está implicitamente definido en los axiomas mientras que el otro a partir de él. Facil resulta probar, dada la definición, que ~(∃a)A ≡ (a)~A, que (∃a)~A ≡ ~(a)A y que y ~(∃a)~A ≡ (a)A; y en todo caso lo dejaremos para el lector.

Por otra parte, en la deducciónnatural, no se introduce un por defición y otro en los axiomas. De hecho, no hay axiomas sino reglas en los cuales está implícita su definición sintáctica. Por su puesto que no se debe ni al azar ni a ninguna armonía prestablecida que las equivalencias se cumplan en este sistema, pues al elaborárselo eran condición suya. Pero veamos cómo probarlas en él.

Primero: (x)A ≡ ~(∃x)~A

1 (x)A                     sup

2 (∃x)~A                 sup

3 ~A                       sup

4 A                         E∀, 1

5 ⊥                        3 y 4

6 ~A → ⊥                T.D. (3 a 5)

7 ⊥                         E∃ (2 y 6)

8 ~(∃x)~A                 RAA (2 - 7)

9 (x)A → ~(∃x)~A      T.D. (1 a 8)

1 ~(∃x)~A             sup

2 ~A                     sup

3 (∃x)~A               I∃ 2

4 ⊥                      1 y 3

5 ~~A                    RAA (2-4)

6 A                       Dneg

7 (x)A                    I ∀

8 ~(∃x)~A → (x) A   T.D. (1 a 7)

Ahora: ~(a)~A ≡ (∃a)A

1 ~(x)~A                     sup

2 ~(∃x) A                    sup

3 A                             sup

4 (∃x) A                     I∃, 3

5 ⊥                            2 y 4

6 ~A                           RAA (3-5)

7 (x)~A                        I∀, 6

8 ⊥                            1 y 7

9 ~~(∃x) A                   RAA(2-8)

10 (∃x) A                    D.Neg

11 ~(x)~A → (∃x) A      T.D. (1 a 10)

Y los restantes pueden ser tarea del lector.

Sustitutividad de la equivalencia, segunda parte.

Ahora consideremos, siguiendo con el post anterior sobre la sustitutividad de la equivalencia, que se realiza la sustitución y hay alguna ocurrencia en A de algún →, ~ o ∀. 

Existen tres casos: 

1) A es A₁ → A₂, 

2)A es ~A₁ y 

3) A es ∀xA₁. 

Primer caso: A es A₁ → A₂

Aquí (salvo en el caso a, ver post anterior) B es B₁ → B₂ donde B₁ y B₂ resultan por sustitución de M por N en A₁ y A₂. Por hipótesis de inducción:

*1) ∀x₁x₂...nₙ[M ≡ N] →. A₁ ≡ B₁ y

*2) ∀x₁x₂...nₙ[M ≡ N] →. A₂ ≡ B₂

Necesitamos probar, entonces, que de (*1) y (*2) se sigue el teorema.

Primero probemos T₁:

p → q →. r → s →. q → r →. s → t

Cuando figuren dos letras proposicionales una al lado de la otra así: pq, significará [p → q].

a) pq →. qr →. ps

transitividad de →

b) ps →. st →. pt

transitividad de →

c) [ps →. st → pt] →. qr → ps →. qr →. st → pt

transitividad de →

d) qr → ps →. qr →. st → pt

modus ponens (c y b)

e) pq →. qs →. st → pt

Regla de transitividad, (a y d)

f) p → qr →. q → pr

ley de conmutación

g) [qs →. st → pt] →. st →. qs → pt

R2, (f)

h) pq →. st →. qs → pt

Regla de transitividad (e y g)

Ahora probemos T₂: 

[p →. q → rs] →. pq →. pr → ps

a) [p →. r → s] →. pr → ps

Axioma 2

b) [p →. q → rs] →. pq →. p → rs

Axioma 2

c) [p → rs →. pr → ps] →. [pq →. p → rs] →. pq →. pr → ps

ley de transitividad de → 2

d) [pq →. p → rs] →. pq →. pr → ps

modus ponens (c y a)

e) [p →. q → rs] →. pq →. pr → rs

Regla de transitividd, (b y d)

Ahora escojamos cinco fórmulas cuales quiera A₁, A₂, B₁, B₂ y C tales que sea

*11) ⊢ C →. A₁ → B₁, ⊢ C →. A₂ → B₂

*12) ⊢ C →. A₂ → B₂ y ⊢ C →. A₂ → B₂

(es decir ⊢ C →. A₁ ≡ B₁ y ⊢ C →. A₂ ≡ B₂)

Tenemos:

a) B₁ → A₁ →. A₂ → B₂ →. A₁ → A₂ →. B₁ → B₂ y

b) A₁ → B₁ →. B₂ → A₂ →. B₁ → B₂ →. A₁ → A₂

ambos por regla 2, T₁.

Sustituyendo en T₂, obtenemos (c) y (d):

c) [C →. B₁A₁ →. A₂B₂ →. A₁A₂ → B₁B₂] →. C → B₁A₁ →. C → A₂B₂ →. C →. A₁A₂ → B₁B₂

d) [C →. A₁B₁ →. B₂A₂ →. B₁B₂ → A₁A₂] →. C → A₁B₁ →. C → B₂A₂ →. C →. B₁B₂ → A₁A₂

Luego:

e) C →. B₁A₁ →. A₂B₂ →. A₁A₂ → B₁B₂

Lema 1, (a)

f) C →. A₁B₁ →. B₂A₂ →. B₁B₂ → A₁A₂

Lema 1, (b)

Y entonces

h) C → B₁A₁ →. C → A₂B₂ →. C →. A₁A₂ → B₁B₂

i) C → A₁B₁ →. C → B₂A₂ →. C →. B₁B₂ → A₁A₂

ambos por modus ponens (c y e) y (d y f). Esto se cumple para cualesquiera fórmulas (bf) C, A₁, A₂, B₁ y B₂.

Ahora sustituímos C por ∀x₁x₂...nₙ[M ≡ N] (regla de sust.), con lo cual obtenemos:

h') [∀x₁x₂...nₙ[M ≡ N] →. B₁ → A₁] →. [∀x₁x₂...nₙ[M ≡ N] →. A₂ → B₂] →. ∀x₁x₂...nₙ[M ≡ N] →. A₁ → A₂ →. B₁ → B₂

i') [∀x₁x₂...nₙ[M ≡ N] →. A₁ → B₁] →. [∀x₁x₂...nₙ[M ≡ N] →. B₂ → A₂] →. ∀x₁x₂...nₙ[M ≡ N] →. B₁ → B₂ → A₁ → A₂

Entonces (recuérdense las hipótesis de la inducción *1 y *2):

j) [∀x₁x₂...nₙ[M ≡ N] →. A₂ → B₂] →. ∀x₁x₂...nₙ[M ≡ N] →. A₁ → A₂ →. B₁ → B₂

modus ponens, (h' y *1)

k) ∀x₁x₂...nₙ[M ≡ N] →. A₁ → A₂ →. B₁ → B₂

modus ponens, (j y *2)

l) [∀x₁x₂...nₙ[M ≡ N] →. B₂ → A₂] →. ∀x₁x₂...nₙ[M ≡ N] →. B₁ → B₂ → A₁ → A₂

modus ponens, (i' y *1)

m) ∀x₁x₂...nₙ[M ≡ N] →. B₁ → B₂ → A₁ → A₂

modus ponens (l y *2)

Y como A es A₁ → A₂ y B es B₁ → B₂, luego hemos probado:

n) ∀x₁x₂...nₙ[M ≡ N] →. A ≡. B

Ahora el segundo caso: A es ~A₁

Así, B es ~B₁ y nuestra hipótesis de inducción establece que

*) ∀x₁x₂...nₙ[M ≡ N] →. A₁ ≡ B₁

Debemos probar

[C →. q ≡ r] →. C → ~q ≡ ~r

y sustutuir C por la hipótesis, q por A₁ y r por B₁ para obtener por modus ponens lo que queremos, de modo similar al primer caso.

Sabemos por el axioma 3 y por modus tolens que:

a) q ≡ r →. ~q ≡ ~r

Por otra parte:

b) p → q →. C →. p → q

Axioma 1

c) [C →. p → q] →. C → p →. C → q

Axioma 2

d) [C →. q ≡ r →. ~q ≡ ~r] →. C → q ≡ r →. C →. ~q ≡ ~r

Sustituyendo en (b)

e) C →. q ≡ r →. ~q ≡ ~r

lema 1, (a)

f) C → q ≡ r →. C →. ~q ≡ ~r

modus ponens (d y e)

Finalmente, nos queda el tercer caso: A es ∀xA₁

Aquí, B es ∀xB₁. hay que probar:

A ≡ₓ B →. (x)A ≡ (x)B

Y con eso obtenemos la prueba utilizando la transitivida de →.

Sabemos, desde luego, que:

a) A ≡ B →. A → B y

b) A ≡ B →. B → A , por la definición de ≡.

c) ∀x[A ≡ B] →. A → B

regla 5 y reflexividad de →

d) ∀x[A ≡ B] →. ∀x[A → B]

Lema 4

e) (x)A → A

regla 5

f) [p →. q → r] →. s → q →. p → s → r

ver prueba

g) [A ≡ₓ B →. A → B] →. (x)A → A →. [A ≡ₓ B →. (x)A → B]

sust, (f)

h) (x)A → A →. [A ≡ₓ B →. (x)A → B]

modus ponens, (g y c)

i) A ≡ₓ B →. (x)A → B

modus ponens, (h y e)

j) A ≡ₓ B →. (x)A →ₓ B

lema 4, i

k) (x)A →ₓ B →. (x)A → (x)B

Axioma 4

l) A ≡ₓ B →.(x)A → (x)B

Regla de transitividad

Sustitutividad de la equivalencia

El sistema axiomático de Nicod-Lukasievicz se caracteriza por bastar para abarcar a la lógica proposicional en su conjunto, quiero decir, para probar cada uno de sus teoremas, y no contar más que con un solo teorema y dos reglas de inferencia. Su nombre tiene el de dos personas pues la primera de ellas no dió su versión definitiva sino que su versión del axioma difería en el número de variables proposicionales del de la segunda según quien, por otra parte, había omitido explicitar que el sistema incluía la regla de sustitución −además de faltarle un paso en la demostración de la reflexividad de → al publicarlo−, (ver).

Tal regla de sustitución, que puede encontrarse como conformando este sistema axiomático de lógica de primer orden, afirma que una variable proposicional puede ser sustituída por una fórmula cualquiera constituyendo un paso válido de prueba.

Algunos sistemas axiomáticos prescinden de ella. Por ejemplo, si el citado es reemplazado por uno en que en lugar de los axiomas presentara "esquemas de axiomas" de la misma forma pero que en lugra de p → [q → p], etc., sea A → [B → A], etc., donde A y B no son variables proposicionales sino lugares a ser ocupados por fórmulas cualesquiera; entonces la regla de sustitución podría ser una regla derivada (omitimos la prueba en este post).

Pero cuando hablamos de "sustitutividad de la equivalencia" nos referimos a una cosa completamente distinta. Con ello mentamos que si dos fórmulas son equivalentes y una de ella es una parte de una tercera, entonces la resultante de sustituir en esta última tal fórmula por la otra (su equivalente), es equivalente con ella. Por si resulta más claro, en símbolos:

Si M ≡ N, y si B resulta de sustituir N por M en A en cero o más lugares, entonces A ≡ B.

Es decir que B es S[N/M]A|, y que si ⊢ M ≡ N, luego ⊢ A ≡ B.

Una muy útil regla de inferencia que se sigue de ella es que si B es S[N/M]A|, si ⊢ M ≡ N y si ⊢ A, luego ⊢ B. Una muestra suficiente de su utilidad está en que con ella, en conjunto con algunos teoremas del cálculo restringido de predicados, puede probarse que cualquier fórmula tiene una equivalente en forma normal prenexa. Lo cual es un paso para una de las demostraciones de la completitud semántica de dicho cálculo. Probemosla, pues por inducción, según el número de ocurrencias de los signos →, ~ y ∀. Formulemos el teorema para la lógica de primer orden:

Si B resulta de A por sustitución de N por M en cero o más lugares de A (no necesariamente todas las ocurrencias de M en A), y si x₁, x₂, ..., xₙ es una lista de variables individuales que incluye al menos todas aquellas variables libres en M y en N que ocurren también como variables ligadas en A, entonces: ⊢ ∀x₁x₂...nₙ[M ≡ N] →. A ≡ B

Primero veamos los casos a) la sustitución de N por M tiene lugar en cero lugares en A, y b) M coincide con A y se sustituye una ocurrencia de M en A.

a) En este caso B es lo mismo que A por que se obtiene de A sin cambiar nada en ella. Luego,

∀x₁x₂...xₙ[M ≡ N] →. A ≡ B

es lo mismo que

∀x₁x₂...xₙ[M ≡ N] →. A ≡ A

Sustituyendo en el axioma 1 (ver post citado):

A ≡ A →. ∀x₁x₂...xₙ[M ≡ N] →. A ≡ A

Como A ≡ A (por reflexividad de la implicación material), luego, por modus ponens:

∀x₁x₂...xₙ[M ≡ N] →. A ≡ A

b) En este caso A es lo mismo que M y B lo mismo que N. De modo que:

∀x₁x₂...xₙ[M ≡ N] →. A ≡ B

en nada difiere de

∀x₁x₂...xₙ[A ≡ B] →. A ≡ B

Pero dicha fórmula se obtiene por medio del axioma 5 aplicado n veces y la regla de transitividad.

Debemos considerar ahora que se realiza la sustitución y hay alguna ocurrencia en A de algún →, ~ o ∀. 

Existen tres casos: 

1) A es A₁ → A₂,

2)A es ~A₁ y 

3) A es ∀xA₁. 

Lo que resta puede leerse en el siguiente post.

Un método para el cálculo restringido de predicados

El método de la cuarta edición de Hilbert-Ackerman (Grundzüge der theoretischen Logic) para demostrar las fórmulas válidas proposicionales fue presentado en este post.

Sobre dicha base se formula en el mismo libro un sistema axiomático para la expresiones universalmente válidas del cálculo restringido de predicados (la lógica de primer orden).

Se reformula el concepto de fórmula elemental¹. Serán elementales las fórmulas que consistan en una disyunción «α₁ ∨ ... ∨ α₂» donde:

1) α_i será una fórmula primaria, una fórmula primaria negada o será de la forma: «∃x β» o «∃y β» o «∃z β», etc.
2) han de existir una α_i y uan α_j tales que α_i sea una fórmula primaria y α_j sea «¬α_i».

Las reglas de deducción son:

(a)


   θ ∨ α ∨ γ 
θ ∨ ¬¬α ∨ γ

No es necesario que θ y γ estén presentes en la deducción. Si lo hace γ, ninguno de sus miembros disyuntivos tendrá la forma «¬¬β», «¬(β ∨ δ)» o «¬∃x β» (ni tener una forma así).

(b)

θ ∨ ¬α ∨ γ             θ ∨ ¬β ∨ γ
        θ ∨ ¬(α ∨ β) ∨ γ

Aquí se cumplen para θ y γ las mismas reglas que en (a). En cuanto a β, ésta no puede ser una disyunción.

la siguiente regla no tenía lugar en el cálculo proposicional:

(c)

  θ ∨ ¬α(y) ∨ γ 
θ ∨ ¬∃x α(x) ∨ γ

La expresión «α(y)» contiene una variable libre y. θ y γ (que están sujetas a idénticas condiciones que en (a)) pueden no estar presentes y si lo están en ellas no aparecerá dicha variable, ni tampoco la variable x (pueden tener otras variables).

La última regla es la siguiente:

(d)

θ ∨ ∃x α(x) ∨ α(y) ∨ γ
   θ ∨   ∃x α(x)   ∨   γ

θ y γ deben cumplir con las mismas condiciones que en (a) se exigen para θ. «α(y)» no debe aparecer como miembro disyuntivo una segunda en la fórmula superior.

La equivalencia entre las fórmulas de cada uno de los pisos de (c) se vé así: «¬α(y)» significa que esta fórmula si es verdadero, lo es de cualquier y, pues es una variable libre. Esto equivale a decir que lo es de todo «y», es decir «∀y ¬α(y)». Es cierto además que decir que para todo «x» se cumple que no es α es lo mismo que decir que no existe «x» alguno para el que se cumpla α. O sea: «¬∃y α(y)».

La equivalencia entre los pisos de (d) se sigue de la equivalencia siguiente:

∃x α(x) ∨ α(x)   ≡eq   ∃x α(x)

Esto es así porque:

Primero: ∃x α(x) ∨ α(x)  →   ∃x α(x)

1) ∃x α(x) implica   ∃x α(x) por motivos obvios.
2) Si α(x), esto significa que α es verdadero de cualquier x, asi dado que el dominio de la función no es vacío, existe en él al menos un x que es α

Segundo: ∃x α(x)   →    ∃x α(x) ∨ α(x)

Basta con que el antecedente implique cualquiera de los miembros disyuntivos del consecuente, que es el caso de 1).

___________
1. Se agregan las fórmulas con letras de predicados y cuantificadores a las variables proposicionales.

Orden de los cuantificadores. Esquemas poliádicos.

Hablamos ya de prenexitud y pureza de esquemas cuantificacionames monádicos. Veamos los dos siguientes:

1. ∀x∃y(Fx → Gx ∨ Fy)
2. ∃y∀x(Fx → Gx ∨ Fy)

Puede verse en ellos que en todo son iguales, excepto por el lugar que tienen los cuantificadores. Trasformemos (1):

∀x(Fx → Gx ∨ ∃yFy)
∀x[¬Fx v (Gx ∨ ∃yFy)]
∀x(¬Fx v Gx) ∨ ∃yFy

A partir de (2) se llega al mismo resultado.

Cuando se introducen letras de predicados de más de una variable, ocurre lo siguiente:

3.  ∀x∃y Fxy
4.  ∃y∀x Fxy

Las fórmulas de arriba no afirman lo mismo. Interpretemos 'F' como que 'x' imita a 'y' en el dominio de personas y obtenemos que una fórmula afirma "todos imitan a alguien" mientras que la otra "hay alguien que es imitado por todos".

Para ver esta diferencia (que se la escucha directamente por otra parte) podemos transformar (3) y (4) de la forma siguiente:

Demos a nuestro universo de personas y cosas nombres, suponiendo que alcanza con las letras a, b, c, ..., n. Entonces, (3) puede expresrse así:

∃yFay ∧ ∃yFby ∧ ... ∧ ∃yFny

Lo cual significa que 'a imita a alguien', 'b imita a alguien', etc.

(Faa ∨ Fab ∨ ... ∨ Fan) ∧ (Fba ∨ Fbb ∨ ... ∨ Fbn) ∧ ... ∧ (Fna ∨ Fnb ∨ ... ∨ Fnn)

Esta última fórmula está compuesta de n conjunciones. La primera, a su vez, de n disyunciones que expresan que "a se imita a sí", "a imita a b", etc.; la segunda "b imita a a", "b se imita a sí", etc.

En cuanto a (4):

∀xFxa ∨ ∀xFxb ∨ ... ∨ ∀xFxn

Esto afirma: "todos imitan a a, o todos imitan a b, ..." etc. Luego:

Faa ∧ Fba ∧ ... Fna ∨ Fab ∧ Fbb ∧ ... Fnb ∨ ... ∨ Fan ∧ Fbn ∧ ... Fnn

O sea la disyunción de n conjunciones, cada una de las cuales afirma uno que es imitado por cada uno de los demás.

Cuantificaciones dentro de cuantificaciones. Esquemas cuantificacionales monádicos.

Siempre que se consideren fórmulas lógicas con predicados monádicos, es posible transformarlos de manera que los alcances de sus cuantificadores no incluyan otros cuantificadores.

Por el contrario, cuando todos sus cuantificadores se encuentran a la izquierda, la forma de una esquema recibe el adjetivo de prenexa. Ejemplo:

(i) ∃x∀y(Fx → Fx ∨ Fy).

Cuando el alcance de un cuantificacos sólo abarca estancias libres de la variable que cuantifica, se lo purifica. Ejemplo:

(ii) ∃xFx → (∀xGx → ∃xGx ∨ ∃xFx).

Veamos cómo purificar (i) y cómo darle forma prenexa a (ii).

i.1.   ∃x[Fx → ∀y(Fx ∨ Fy)]
i.2.   ∃x(Fx → Fx ∨ ∀yFy)

Ahora, antes de 'mover' el cuantificador existencial hay que trnsformar el esquema:

i.3.   ∃x[¬Fx v (Fx ∨ ∀yFy)]

lo cual es lícito debido a la definición de la implicación material.

i.4.   ∃x¬Fx v ∃x(Fx ∨ ∀yFy)

Esto último pues el cuantificador existencial se distribuye en la disyunción.

i.5.   ∃x¬Fx v ∃xFx ∨ ∀yFy

Ahora (ii). Primero cambiemos las variables para que no entren en conflicto:

ii.1   ∃xFx → [∀yGy → ∃z(Gz ∨ Fz)]

Tal y como dijimos antes, el cuantificador existencial se distribuye en la disyunción. Prestemos atención a lo que sigue. abstraigámosnos del consecuente de ii.1, llamémoslo en su conjunto 'p', entonces:

ii.2   ∃xFx → p
        ¬∃xFx v p       Def.→
        ∀x¬Fx v p      
        ∀x(¬Fx v p)   
        ∀x(Fx → p)   
Así:
ii.3   ∀x{Fx → [∀yGy → ∃z(Gz ∨ Fz)]}
ii.4   ∀x{Fx → ∃y[Gy → ∃z(Gz ∨ Fz)]}
ii.5   ∀x∃y{Fx → [Gy → ∃z(Gz ∨ Fz)]}
ii.6   ∀x∃y{Fx → ∃z[Gy → (Gz ∨ Fz)]}
ii.7   ∀x∃y∃z{Fx → [Gy → (Gz ∨ Fz)]}

Quedará ahora como ejercicio la purificación del siguiente esquema:

∀x∃y[Fx ∨ Gx → ∀z(Fz ∧ Gy ∨ Fz ∧ Gx)]