¿Cómo funcionan los cuantificadores en la lógica de predicados?

Cuantificadores en conexión con AND y OR

En las formas más comunes de lógica de predicados, ∀ y ∃ actúan como una especie de conjunción lógica (AND) en todos los objetos y una disyunción lógica (OR) en todos los objetos , respectivamente.

Conexión entre ∀ y 'Y'

Considere un argumento en el que los únicos 'objetos' son los escoceses, y sea EPP( x ) = " x come su papilla". Después

∀x : PPE(x)

se traduce (con algo menos de gracia social que la que se podría usar en el habla diaria) como

Por cada [persona escocesa] x: x come su papilla sola

que podríamos representar mejor como

Todos los escoceses comen sus gachas de avena .

Si suponemos que uno es un 'escocés' si y solo si uno nació en Escocia, o es un ciudadano británico que vive en Escocia durante al menos el 90% de su vida, entonces solo hay un número finito de escoceses; por lo que también podríamos imaginar producir una lista de todos los escoceses ("Angus", "Maeve", "Bruce", "Caroline", ...), en cuyo caso es equivalente a

(Angus come su avena normal) Y (Maeve come su avena normal) Y ...

que no es una forma muy conveniente de expresar lo mismo, pero sigue siendo equivalente siempre que enumeremos a todos los escoceses, y ninguna persona (o cosa) que no sea escocesa. El símbolo ∀ es más poderoso en este sentido: nos permite expresar una noción

• sin tener que referirse a cada objeto que cumple algún criterio;
• sin siquiera tener que comprometerse con una lista definitiva de todos los objetos en el universo del discurso; y
• en otros contextos, como cuando el universo del discurso son objetos matemáticos como los números, sin siquiera comentar si existe una lista finita de objetos bajo consideración.

Especialmente en el último caso, ∀ nos permite expresar potencialmente algo que es cierto sobre una colección que es infinita, o cuya extensión aún no conocemos. Pero aun así, la forma en que se comporta es muy parecida a un 'Y' lógico de la misma propiedad, en todos los objetos en el "dominio del discurso".

Conexión entre ∃ y 'OR'

De la misma manera que ∀ expresa algo como un 'Y' en todos los objetos que se están considerando, ∃ expresa algo como un 'O'. Supongamos que el dominio del discurso son las personas en una habitación específica (a la que me referiré como 'esta' habitación; puedes imaginar que el hablante está en la habitación), y M( x ) = " x es un asesino". Después

∃x : M(x)

se traduce como

Existe una [persona en esta habitación] x: x es un asesino

que podríamos representar mejor como

Alguna persona en esta habitación es un asesino .

En cambio, a veces decimos algo como 'Hay un asesino en esta habitación', pero sin querer afirmar definitivamente que hay exactamente una de esas personas. Nuevamente, si suponemos que solo hay un número finito de personas en la sala ("Coronel Mustard", "Sra. Peacock", "Professor Plum", ...) entonces esta afirmación es equivalente a

O (el Coronel Mustard es un asesino) O (la Sra. Peacock es una asesina) O ...

lo que nuevamente es inconveniente pero en principio es equivalente a la declaración con ∃ siempre que la lista contenga a todas las personas en la habitación y solo a las personas en la habitación.

Cuantificación restringida

Sería bueno poder hablar de todos los escoceses que beben whisky en su lugar, pero sin cambiar el universo del discurso; o, de hecho, para hablar de algo más que de los escoceses todo el tiempo. La forma en que hacemos esto es introduciendo formas de restringir la cuantificación.

Para el cuantificador existencial, esto es fácil y obvio. Por ejemplo, supongamos que dejamos que el universo del discurso sea todo en la Tierra, incluidos los escoceses, los chinos, la miel, la melaza, las hormigas, etc. Podemos recuperar enunciados sobre escoceses usando un predicado S( x ) = " x es una persona escocesa"; para que podamos representar

Hay un escocés que come sus gachas de avena

como "hay [algo] que es a la vez una persona escocesa y que come su papilla simple"; o

∃x: S(x) y PPE(x) .

Podemos hacer algo similar para la cuantificación universal. Por ejemplo, si queremos hablar de cosas que son verdaderas para todos los escoceses, podemos hacerlo haciendo un enunciado que sea verdadero para cualquier objeto x, si x es escocés. Por ejemplo,

Todos los escoceses comen sus gachas de avena

puede describirse como "cualquier [cosa] que sea una persona escocesa come su avena sola", o "para cualquier [cosa] x: si x es una persona escocesa, entonces x come su avena sola", lo que podemos traducir como

∀x: S(x) ⇒ PPE(x) .

Esto tiende a ser una forma tan útil de describir cosas que definimos una notación para ello, tal vez de la siguiente manera:

∃x∈S: PAG   ≡   ∃x: [ S(x) & PAG ]

∀x∈S: PAG   ≡   ∀x: [ S(x) ⇒ PAG ]

donde lo que he escrito a la izquierda trata básicamente a S como la descripción de un conjunto, por ejemplo, el conjunto de todos los escoceses. (Las notaciones variarán en diferentes comunidades.) Estas dos cuantificaciones 'limitadas' actúan exactamente como si fueran cuantificadores normales ∀ y ∃, excepto que se extienden sobre aquellos objetos x que satisfacen S( x ).

Conexión entre ∀ y ∃ usando las Leyes de Morgan

Te preguntarás por qué, con la cuantificación restringida sobre S, usamos S(x) & Ppara la cuantificación existencial sobre S, y S(x) ⇒ Ppara la cuantificación universal sobre S. La respuesta está oculta en la conexión entre los cuantificadores y los conectores AND y OR: hay una conexión entre ∀ y ∃ a través de las leyes de Morgan en lógica clásica. Esto es cierto ya sea que usemos cuantificadores restringidos o cuantificadores no restringidos.

Por ejemplo, considérese el caso en que los escoceses vuelven a ser el universo del discurso. Supongamos que interpretamos ¬EPP(x) en el sentido de " x agrega algo a su papilla cuando la comen". Entonces las siguientes afirmaciones son equivalentes:

∀x: EPP(x) — Todos los escoceses comen sus gachas
solas ¬∃x: [¬EPP(x)] — Ningún escocés agrega nada a sus gachas

(¿Por qué cambiamos la palabra 'algo' a 'cualquier cosa' en la oración anterior? Básicamente porque lo opuesto de "algunos" en inglés es "no cualquiera".) Podemos ver esto usando la descripción en términos de AND y OR:

¬ ∃x: [¬EPP(x)] — Ningún escocés agrega nada a su papilla cuando la come

puede interpretarse, utilizando nuestra lista de escoceses, como

¬[ (Angus come su papilla con algo añadido) O (Maeve come su papilla con algo añadido) O... ]

que es equivalente a

¬(Angus come su avena con algo agregado) Y ¬(Maeve come su avena con algo agregado) Y...

≡ (Angus come su avena sola) Y (Maeve come su avena sola) Y...

que es lo mismo ∀x: EPP(x)que antes. Por el contrario, si hay algún escocés que come sus gachas con algo añadido, tenemos

∃x: [¬EPP(x)] — Algunos escoceses agregan algo a su papilla cuando la comen

que con nuestra lista de escoceses se convierte en

(Angus come su papilla con algo agregado) O (Maeve come su papilla simple) O ...

≡ ¬ (Angus come su papilla simple) O ¬ (Maeve come su papilla simple) O ...

que, usando la Ley de Morgan, nos da

¬[ (Angus come su papilla) Y (Maeve come su papilla) Y... ]

que es justo ¬∀x:EPP(x), o

No todos los escoceses comen sus gachas de avena .

En resumen, para cualquier propiedad P, tenemos las siguientes equivalencias:

Ningún objeto x es P — Todos los objetos x son no-P ; o
¬∃x: P(x)   ≡   ∀x: ¬P(x) .

Algún objeto x no es-P — No todos los objetos x son P ; o
∃x: ¬P(x)   ≡   ¬∀x: P(x) .

Lo mismo es cierto si usamos la cuantificación restringida. Para cualquier propiedad S, y cualquier proposición P, tenemos las siguientes equivalencias:

¬∀x∈S: PAG
≡ ¬∀x: [ S(x) ⇒ PAG ]
≡ ¬∀x: [ ¬S(x) ∨ PAG ]
≡ ∃x: ¬[ ¬S(x) ∨ PAG ]
≡ ∃ x: [ S(x) & ¬P ]
≡   ∃x∈S: ¬P

y también

¬∃x∈S: P
≡ ¬∃x: [ S(x) & P ]
≡ ∀x: ¬[ S(x) & P ]
≡ ∀x: [ ¬S(x) ∨ ¬P ]
≡ ∀x : [ S(x) ⇒ ¬P ]
≡   ∀x∈S: ¬P .

La razón de los diferentes conectivos, al definir las cuantificaciones restringidas, es esencialmente que esto es lo que necesitamos para permitir que las cuantificaciones restringidas se comporten como si fueran cuantificaciones 'normales' en el dominio más pequeño.

Comprender ∀ y ∃ en inglés simple

Usando todo lo anterior, podemos entender cómo las oraciones en el lenguaje cotidiano se pueden describir en términos de cuantificadores. Al final, se reduce a entender las cosas en términos de "algunas" o "todas", y luego traducirlas formalmente.

• "No X" o "Ninguno de X" son declaraciones universales.
  
  ¿Por qué? Porque "ninguno" es la negación de "algunos". Entonces, si decimos "Ningún X es P", en realidad estamos diciendo

  No existe una X que sea P

  o equivalente

  ¬∃x∈X: P(x)
  ≡   ∀x∈X: ¬P(x)

  que es una afirmación universal.

• Las declaraciones "Algunas X" son declaraciones existenciales.
  
  Esto es cierto ya sea que estemos hablando o no de que algún X tenga una propiedad, o que algún X carezca de una propiedad. ¿Por qué? En este caso, está ahí mismo en el idioma. Si decimos "algunos X son P", estamos diciendo

  Existe una X que es P

  o equivalente

  ∃x∈X: P(x) .

  De manera similar, si decimos "algunos X no son P", estamos diciendo

  Existe un X que no es-P

  o equivalente

  ∃x∈X: ¬P(x) .

  Así que ambos son obviamente existenciales.

• Las declaraciones "All X" y "every X" son declaraciones universales.
  
  Esto vuelve a ser cierto ya sea que hablemos o no de que algún X tenga una propiedad, o que algún X carezca de una propiedad, y como en el caso de las declaraciones "algunas", está ahí mismo en el lenguaje: una declaración "todos" hervirá hasta algo de la forma

  ∀x∈X: P(x)   o   ∀x∈X: ¬P(x) ,

  dependiendo de si se trata de si todos los objetos son P o todos los objetos no son P.

• Las declaraciones "Cualquier X" son declaraciones universales.
  
  Debe tener cuidado al pensar en cómo se usa la palabra 'cualquiera'. A menudo preguntamos en inglés: are there any of [some object] ? Esta pregunta podría ser sobre la cuantificación existencial, pero ciertamente no es una proposición existencial , ni una proposición de ningún tipo.

  Si piensa en cualquier declaración (en oposición a la pregunta) de la forma "cualquier X", debe quedar bastante claro que tiene que ver con algo que se dice que es verdadero para todos los objetos. "Cualquiera que haya nacido en Escocia es escocés" es una declaración sobre todas las personas que han nacido en Escocia; "El cuadrado de cualquier número entero es otro número entero" es una declaración sobre algo que se cumple para cada número entero. Entonces, una declaración "Cualquier X es P" se traduce como

  ∀x∈X: PAG .

  Esto también es cierto para las declaraciones "no hay ninguna X", del tipo relacionado con la pregunta "¿hay alguna?" Si decimos que no los hay, afirmamos que no los hay de X ; entonces, como observamos anteriormente, estamos afirmando

  ¬∃x∈X: PAG   ≡   ∀x∈X: ¬P .

De esta manera, al considerar cuidadosamente lo que se afirma, podemos convertirlo en una afirmación sobre la existencia, la inexistencia o algo que es cierto para todos los objetos, y luego transformarlo en algo que es obviamente existencial (∃) u obviamente universales (∀).

En el orden de los cuantificadores

Es importante recordar que el orden de los cuantificadores es importante; a menudo, no es posible reordenarlos sin cambiar el significado.

• Puede cambiar el orden de dos cuantificadores existenciales adyacentes, básicamente porque OR es conmutativo y asociativo: recuerde que esa v b v c lo mismo que c v a v b, y así sucesivamente. Entonces, si c = "comer queso", y si A( x,t,a ) significa que " x es un lugar y t es un momento en el que hacer a es apropiado", entonces

  ∃x ∃t: A(x,t,c)   y   ∃t ∃x: A(x,t,c)

  ambos significan esencialmente que hay un tiempo y un lugar para comer queso ; la diferencia consiste en si la disyunción itera primero a través de lugares posibles y luego (para cada lugar) considera tiempos posibles para encontrar si hay un tiempo apropiado en ese lugar; o si, por el contrario, la disyunción itera primero a través de tiempos posibles y luego, para cada tiempo, considera lugares posibles para averiguar si hay un lugar apropiado en ese momento.

• De manera similar, puede cambiar el orden de cualquier cuantificador universal adyacente. Si eres un entusiasta extremo del queso, es posible que desees afirmar lo siguiente (ambos son equivalentes):

  ∀x ∀t: A(x,t,c)   y   ∀t ∀x: A(x,t,c)

  ambos significan que cada momento y cada lugar es un buen momento y lugar para comer queso; no importa qué momento consideres, cada lugar es bueno; y no importa en qué lugar estés, cualquier momento es bueno.

• SIN EMBARGO , no puede cambiar el orden de los cuantificadores universales y los cuantificadores existenciales sin cambiar el significado. En lugar de limitarnos a comer queso, consideremos todos los tipos posibles de actividad. Después

  ∀ a ∃x ∃t: A(x,t,a)

  significa que para cada actividad, hay un tiempo y un lugar cuando es apropiado; dicho a menudo en voz alta como "hay un tiempo y un lugar para todo". Esto no es , sin embargo, lo mismo que

  ∃x ∃t ∀ a: A(x,t,a)

  lo que significa que hay un tiempo y un lugar donde todo simultáneamente es apropiado. (Esto es algo que también podría describir como " hay un momento y un lugar , para todo "; esto solo demuestra que el habla cotidiana es ambigua y que debe ejercer su juicio sobre cómo interpretarla). ejemplo conmovedor, si L( x,y,t ) significa " x ama a y en el tiempo t ", entonces la proposición

  ∀x ∃y ∃t: L(x,y,t)

  podría interpretarse como " todos aman a alguien alguna vez "; mientras

  ∃y ∀x ∃t: L(x,y,t)

  significa que hay una sola persona a la que todos aman en algún momento de sus vidas;

  ∃t ∀x ∃y: L(x,y,t)

  significa que hay un momento en que todos están enamorados de otra persona; y

  ∃y ∃t ∀x: L(x,y,t)

  significa que hay una sola persona que, al menos en un momento dado, fue amada por todos a la vez, lo que significa cosas muy diferentes.

existencia única

Finalmente, usando la teoría de las descripciones definidas, podemos caracterizar la existencia única usando una combinación de cuantificación existencial, cuantificación universal e igualdad. Por ejemplo, si E( x ) = " x es Elvis Presley" e i = yo mismo, podría representar que soy el único Elvis Presley por

E(i) & ∀y: [ (y ≠ i) ⇒ ¬E(y) ]

o "Soy Elvis Presley, y cualquiera que no sea yo no es Elvis Presley". Podemos simplificar esto lógicamente (aunque a costa de convertirlo en una frase ligeramente perversa en el habla normal) tomando la contrapositiva en la segunda parte:

E(i) & ∀y: [ E(y) ⇒ (y = i) ]

o "Soy Elvis Presley, y cualquiera que sea Elvis Presley no es otro que yo mismo". Si quisiera decir que hay uno y sólo un Elvis Presley, sin afirmar que yo mismo soy Elvis, podría escribir en su lugar

∃x: [ E(x) & ∀y: [ E(y) ⇒ (x = y) ]]

lo que podríamos interpretar como "hay alguien que es Elvis Presley, y [él es único, es decir] cualquiera que sea Elvis Presley no es otro que Elvis Presley". (Usando las definiciones de las cuantificaciones restringidas, incluso podríamos escribir esto como ∃x∈E ∀y∈E: (x=y): "hay un Elvis Presley, y todos los Elvis Presley son la misma persona".)

Si quisiéramos decir que hay al menos dos Elvises Presley, podríamos negar solo la parte de la proposición anterior donde reclamamos la unicidad:

∃x: [ E(x) & ¬∀y: [ E(y) ⇒ (x = y) ]]

o equivalente

∃x: [ E(x) & ∃y: [ E(y) & (x ≠ y) ]]

(La versión de cuantificación restringida se escribiría como ∃x∈E ∃y∈E: (x≠y), o "Hay dos [diferentes] Elvises Presley".) Podemos llevar el cuantificador interno al frente, que está poniendo la fórmula en forma normal prenex :

∃x ∃y: E(x) & E(y) & (x ≠ y) .

Si quisiéramos decir que hay exactamente dos Elvis Presley, entonces podríamos afirmar que cualquiera que sea Elvis Presley debe ser uno de los dos que hemos identificado, es decir

∃x ∃y: E(x) & E(y) & (x ≠ y) & (∀z: [ E(z) ⇒ (z=x ∨ z=y) ]) .

o de nuevo, trayendo el cuantificador interno hacia afuera para poner la fórmula en la forma normal prenex , podemos escribir

∃x ∃y ∀z: E(x) & E(y) & (x ≠ y) & [ E(z) ⇒ (z=x ∨ z=y) ] .