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.

La implicación, la deducción y la completitud

Considérese las fórmulas siguientes:

(1) ¬ ( p₁ ∧ ... ∧ p_n → ¬ q)     →     (p₁ ∧ ... ∧ p_n → q)

(2)        K₁, ..., K_n ⊬ ¬X,   entonces:    K₁, ..., K_n ⊢ X

Lo que se asevera en la primera de ellas es una implicación cuyo antecedente es la negación de otra implicación que afirma que una conjunción de n proposiciones 'p' implican '¬q'; y cuyo consecuente que esa misma conjunción de proposiciones implica 'q'.

Dicho de otro modo: si no se da el caso de que la clase de proposiciones p implica la negación de q, entonces implica q. Esto es un esquema válido, es decir, verdadero para cualesquiera interpretaciones de las proposiciones p y de q. Veámoslo:

Si la conjunción "p₁ ∧ ... ∧ p_n" tiene algún miembro cuyo calor de verdad sea lo falso, toda la conjunción lo tiene, por lo tanto el antecedente de (1) es falso, y así, (1) es necesariamente (lógicamente) verdadero, sea cual sea la valuación de q.

Si la conjunción denota lo verdadero, (1) equivale a:

   ¬(¬q) → q

que a su vez puede, en virtud de la ley de la doble negación, transformase en

(3)   q → q

cuya validez puede parecer manifiesta. Para el lector a quien no le parezca así, hay una demostración de (3) a partir de los axiomas:

p → (q → p)

y

[p → (q → r)] → [(p → q) → (p → r)]

en el libro de Ivorra Castillo* (por el enfoque de las tablas de verdad llegar a su validez puede parecer más simple).

La fórmula (2) tiene alguna semejanza, quizá, con (1). En ella se afirma que si no se deduce de la clase de enunciados K el enunciado ¬X, entonces se deduce de ellos X. Sin embargo hay quedecir que no se trata de algo tan similar.

Ahora bien, es preciso distinguir '→' de '⊢'  y '¬(... →...)' de '... ⊬ ...'.

Por ejemplo, si → conecta dos proposiciones, lo que tenemos es una nueva proposición, del mismo nivel que las dos primeras, la cual será verdadera siempre que no lo sea también la primera de aquellas a la vez que falsa la segunda. Este símbolo → también puede vincular dos proposiiones variables, en cuyo caso ocurre de la misma manera.

En cambio, si ⊢ vincula dos fórmulas, lo que afirma es que hay una derivación de la segunda, llamada entonces concusión, a partir de la primera, que se llama premisa. Tal relación es posible en virtud de la reglas de inferencia. Veamos por ejemplo una demostración de 'p ⊢ p':

1. p    premisa
2. p    Rep., 1

Lo que esto significa es que en dos pasos es posible demostrar 'p ⊢ p'. En 1 tenemos expresada la premisa de nuestro argumento y en 2 tenemos expresada la conclusión en virtud de la regla de repetición que nos permite repetir cualquier línea de la derivación (siempre y cuando, como es evidente, no se trate de un supuesto cancelado).

Ahora veamos lo siguiente:

(4) (p → q) ∨ (p → ¬q)

tenemos aquí una fórmula válida universalmente. Siempre es verdadero que se da alguno de los dos casos: una proposición arbitraria implica otra proposición arbitraria o implica su negación.

En cambio:

(5) 'p ⊢ q' o 'p ⊢ ¬q'

¿es una fórmula válida? Lo que (5) afirma es que de una premisa puede demostrarse una fórmula y si no su negación.

El lector seguramente haya pensado que eso dependerá sin duda de las posibilidades que ofrezca el sistema deductivo a que refiera ⊢. Esto lleva a otra pregunta. A saber: ¿existe uno en el cual (5) pueda ser considerado una verdad lógica?

_______
*nota: Ivorra Castillo, C. Lógica y teoría de  conjuntos.

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

Deducción e interpretación en una pequeña teoría

Consideremos una relación cualquiera, llamémosla 'R'. Otorguémosle dos propiedades. La primera de ellas es la reflexividad. Esto significa que cualquier cosa (del dominio del modelo) mantiene consigo misma esa relación. Un ejemplo de ello puede ser, para el dominio de padres, "llevar el mismo nombre que". Así, para cualquier padre, es obvio que siempe "lleva el mismo nombre" que si mismo. Sin duda que si un padre cambiara un nombre el modelo ya no sería adecuado. Podemos pensar entonces otros. La igualdad matemática puede ser un ejemplo de relación con esta propiedad de la reflexividad, tal vez más frecuente. Para todos los números se cumple que son iguales a si mismos. Pero no osn lo mismo la relación de igualdad matemática que la reflexividad, que es una propiedad suya, y que también tienen otras relaciones.

Ahora pensemos otra propiedad para atribuir a 'R', la relación de la que estamos hablando. Sería esta: si dos cosas mantiene cada una esta relación con una tercera, entonces la mantienen entre sí. Un ejemplo: ser "hermano o hermana de", de manera que si alguien, cualquiera sea, es hermano o hermana de alguien y hay otra persona que también lo es, entonces ésta y aquél son hermanos.

Si tuvieramos que dar un ejemplo de una relación que las reúna a las dos propiedades mencionadas, podríamos citar la congruencia. Vista así, desde un punto de vista semántico, muy fácil es llegar a la conclusión, evidente, de que la relación es simétrica. Esto significa que si algo es semejante a otra cosa, esta otra cosa lo es de algo. Tal cosa no ocurre, por ejemplo, con la relación "está a la derecha de". Si alguien está a la derecha de su padre, su padre no está a la derecha de él, al menos si no cambiemos entre tanto nuestro punto de vista. Si vovlemos a tomar un ejemplo de la matemática podemos pensar en "ser mayor que".

Pero el tema es que la conclusión de que 'R' es simétrico porque es reflexiva y porque cualesquiera dos cosa que mantengal la relación con cualquier otra la mantienen entre sí basada en el ejemplo de la congruencia podría no ser suficientemente general. Mejor dicho, hay una maner ade demostrar que si 'R' cumple las dos propiedades mencionadas en primer lugar, cumple la otra que dijimos. Llamemos axiomas a las dos primeras:

Axioma I:  Rxx
Axioma II: Rxz ∧ Ryz → Rxy

Teorema I: Ryz → Rzy

Quedará para el lector la demostración del teorema I*. Por el momento, sólo nos ocuparemos de otro teorema de esta teoría:

Teorema II: Rxy ∧ Ryz → Rxz

Veamos como se podría probar si tuvieramos demostrado el otro teorema:


|1  Rxy ∧ Ryz              supuesto
|2  Ryz                         Eliminación de ∧: 1
|3  Ryz → Rzy              por teorema I: 2
|4  Rzy                         Modus Ponens: 2, 3
|5  Rxy                         Eliminación de ∧: 1
|6  Rxy ∧ Rzy               Introducción ∧: 4, 5
|7  Rxy ∧ Rzy → Rxz    por Axioma II: 6
|8  Rxz                          Modus ponens: 6, 7
 9  Rxy ∧ Ryz → Rxz     I→

______
*Nota: Un esquema de tal demostración (en realidad bastante sencilla como para que el lector de con ella por sus medios) y una mención a esta teoría pueden encontrarse en Tarski Introducción a la lógica y a la metodología de las ciencias deductivas.

Un condicional de corolario

Sea la siguiente función veritativa:

(i) ¬ ( p → ¬ q)

¿Puede probarse que (i) implica «p → q»?

¿Ejemplos?

El uso de los puntos en las expresiones del Principia Mathematica

La convención de los puntos (dots) que utiliza el Principia Mathematica de Russell y Whitehead parece menos pragmática que el habitual uso de los paréntesis, corchetes y llaves. Veamos cómo en la Introducción ellos son introducidos:

Hay tres grupos de ocurrencias de puntos, I, II y III.

Grupo I: puntos junto a '⊃', '≡', '∨' o '=Df'.
Grupo II: subsiguientes a paréntesis indicadores de "variables aparentes" -es decir ligadas- tales como (x), (x,y), (∃x), (∃x,y), [(ɿx)(φx)], etc.
Grupo III: puntos entre proposiciones que indican un "producto lógico" (o sea la conjunción de ambas).

El Grupo I tiene mayor "fuerza" que el II y éste que el III.

"El alcance de los paréntesis indicados por cualquier grupo de puntos se extiende hacia atrás o hacia adelante más allá de cualquier número menor de puntos, o cualquier número igual de un grupo de menor fuerza, hata llegar ya sea el fin de la proposición asertada o a un número mayor de puntos o a uno igual perteneciente a un grupo de fuerza igual o superior."

He aquí lo ejemplos que siguen, que pueden aclarar:

⊢:. p ⊃ q .⊃: q ⊃ r .⊃. p ⊃ r.
o sea:
⊢ (p ⊃ q) ⊃ (q ⊃ r) ⊃ (p ⊃ r)


p ⊃ q .⊃. q ⊃ r :⊃. q ⊃ r.
o sea:
[(p ⊃ q) ⊃ (q ⊃ r)] ⊃ (q ⊃ r)


p ⊃ q . q ⊃ r .⊃. p ⊃ r
o sea:
(p ⊃ q) . (q ⊃ r) ⊃ (p ⊃ r)

Acá, el primer punto indica un producto lógico, así que el alcance del segundo se extiende más allá de él hasta el principio.


p ⊃ q : q ⊃ r .⊃. p ⊃ r
o sea:
(p ⊃ q) . [(q ⊃ r) ⊃ (p ⊃ r)]

En éste, los dos puntos indican u producto lógico y como no hay otros dos puntos en ningún otra parte del esquema su alcance va tanto hasta su principio como hasta su fin.

p ∨ q .⊃:. p .∨. q ⊃ r :⊃. p ∨ r
o sea:
p ∨ q ⊃ {[ p ∨ (q ⊃ r)] ⊃ p ∨ r)}

Para asertar lo cual debemos escribir:

⊢::p ∨ q .⊃:. p .∨. q ⊃ r :⊃. p ∨ r


⊢:. p ∨ q : p .∨. q ⊃ r :⊃. p ∨ r.
o sea:
⊢ (p ∨ q) . [p ∨ (q ⊃ r)] ⊃ p ∨ r

En este caso, el primer par de puntos indica una conjunción y el segundo no, asíque es este de mayor fuerza.

______________
Como ejercicio:

Diga si las fórmulas son esquemas válidos o si, muy por el contrario, no lo son.