3.4: Cuantificadores
( \newcommand{\kernel}{\mathrm{null}\,}\)
DejarP(x) ser una fórmula en una variable. Si sustituimos una constantea∈U,,x pues llegamos a un comunicadoP(a). No obstante, supongamos que nos interesaP(x) con respecto a algún conjuntoX⊆U, más que a un elemento particular deU. En particular, preguntamos siP(a) es una verdadera declaración para todosa∈X. Recordemos que uno de los roles de una fórmula es definir conjuntos. Para cualquier fórmulaP(x), universoU yX⊆U,P(x) particionesX en dos conjuntos - aquellos elementos deX para los cualesP es cierto, y aquellos para los queP es falso. En este sentido, preguntar si seP sostiene para todosx∈X, o si se sostiene para algunosx∈X (lo que es complementario a preguntar si se¬P mantiene para todosx∈X) es preguntar siP define una nuevo o interesante subconjunto deX.
Así como se introdujeron los conectivos proposicionales para formalizar el comportamiento lingüístico de ciertos conectivos de lenguaje natural ampliamente empleados (y, o, implica, no), también formalizaremos la “cuantificación” sobre conjuntos.
Definición. Cuantificador universal,(∀x∈X)P(x) LetP(x) be una fórmula en una variable, con universoU. VamosX⊆U. QSea el enunciado(∀x∈X)P(x) EntoncesQ es cierto si por cadaa∈X,P(a) es cierto. De lo contrarioQ es falso.
La notación(∀x∈X)P(x) es una taquigrafía para(∀x)([x∈X]⇒[P(x)]) La declaración "(∀x∈X)P(x)"se lee “para todosx enX,P(x)". Tenemos(∀x∈X)P(x)⟺X⊆χP DEFINICIÓN. Cuantificador existencial,(∃x∈X)P(x) LetP(x) Ser una fórmula en una variable con universoU. LetX⊆U,X≠∅. QSea el enunciado(∃x∈X)P(x). EntoncesQ es cierto si hay algunoa∈X, para lo cualP(a) es cierto. De lo contrarioQ es falso.
La expresión(∃x∈X)P(x) es una taquigrafía para(∃x)[(x∈X)∧P(x)]. La declaración(∃x∈X)P(x) "" se lee “existex enX, tal queP(x)”. El cuantificador "∇" es el equivalente formal de la expresión del lenguaje natural “para todos” o “cada”. El cuantificador "∃" es el equivalente formal de “para algunos” o “existe... tal que...”.
Siempre que el universo de una variable sea claro, o no relevante para la discusión, es común suprimir el universo en la expresión del enunciado. Por ejemplo, siP(x) es una fórmula con universoU, podemos escribir(∀x)P(x) en lugar de(∀x∈U)P(x).
3.4.1. Cuantificadores Múltiples.
DejarP(x1,…,xn) ser una fórmula enn≥2 variables. Entonces la fórmula(∀x1)P(x1,…,xn) es una fórmula en lasn−1 variablesx2,…,xn. De igual manera, la fórmula(∃x1)P(x1,…,xn) es una fórmula enn−1 variables.
EJEMPLO 3.10. Considera la fórmula en cinco variablesP(x,x0,L,ε,δ):=(0<|x−x0|<δ)⇒(|sin(x)−L|<ε) con todas las variables teniendo universoR. Entonces(∀x0)P(x,x0,L,ε,δ) es una fórmula en cuatro variables,(∀x0)(∃L)P(x,x0,L,ε,δ) es una fórmula en tres variables, y(∀x0)(∃L)(∀ε)P(x,x0,L,ε,δ) es una fórmula en dos variables.
Definición. Variable abierta, Variable enlazada En la fórmulaP(x),x es una variable abierta. En las fórmulas(∀x)P(x),(∃x)P(x),(∀x)Q(x,y),(∃x)Q(x,y)x hay una variable enlazada o cuantificada, y en las dos últimas,y es una variable abierta.
3.4.2. Orden del cuantificador.
En la discusión a continuación, necesitamos discutir los cuantificadores genéricamente, es decir, sin tener en cuenta si el cuantificador en discusión es universal o existencial. Por lo que vamos a introducir alguna notación conveniente sólo para esta sección.
Notación. (Qx)P(x)Utilizamos la notación (Q Qx)P(x) para representar genéricamente(∀x)P(x) y(∃x)P(x). LetQ1,…,Qn be cuantificadores lógicos yP(x1,…,xn) ser una fórmula con variables abiertasx1,…,xn. Entonces(Q1x1)(Q2x2)(…)(Qnxn)P(x1,…,xn) es una declaración.
EJEMPLO 3.11. Considerar una declaraciónS en la formaS=(∀x∈X)(∃y∈Y)P(x,y).S es verdadera si para cada unoa∈X,(∃y∈Y)P(a,y) es verdad. Esto se satisface siempre que para cada unoa∈X, haya un elemento deY (llamémosloba para recordarnos que este elemento particular deY está asociado con la elección anterior, a) tal queP(a,ba) es cierto. Asíba se selecciona teniendoa en mente. Las declaraciones en esta forma son especialmente importantes en matemáticas porque la definición del límite en el cálculo es una declaración en la forma de este ejemplo.
Volvamos al enunciado(Q1x1)(…)(Qnxn)P(x1,…,xn) El orden de los cuantificadores es significativo. Si1≤i<j≤n,xi se comporta como un parámetro desde el punto de vista dexj (es decir,xi se fija desde el punto de vista dexj). Dicho de otra manera,xj se elige con respecto a las sustituciones dex1,…,xj−1, pero sin consideración paraxj+1,…,xn.
Siempre se lee desde la izquierda. El enunciado(∀x1)(Q2x2)(…)(Qnxn)P(x1,…,xn) es el mismo que(∀x1)[(Q2x2)(…)(Qnxn)P(x1,…,xn)], o, en otras palabras, para cada elección dex1, la afirmación(Q2x2)(…)(Qnxn)P(x1,…,xn) es cierta. De igual manera, la afirmación(∃x1)(Q2x2)(…)(Qnxn)P(x1,…,xn) es la misma que(∃x1)[(Q2x2)(…)(Qnxn)P(x1,…,xn)], o en otras palabras que hay alguna elección dex1 para la cual la afirmación(Q2x2)(…)(Qnxn)P(x1,…,xn) sobre lasn−1 variablesx2,…,xn es verdadera.
EJEMPLO 3.12. El orden de los cuantificadores es importante, como se puede ver en lo siguiente: no(∀x∈X)(∃y∈Y)P(x,y) es equivalente a(∃y∈Y)(∀x∈X)P(x,y). Por ejemplo, la afirmación(∀x∈R)(∃y∈R)(y=x2) es verdadera. Pero(∃y∈R)(∀x∈R)(y=x2) es falso. El enunciado[(∃y∈Y)(∀x∈X)P(x,y)]⇒[(∀x∈X)(∃y∈Y)P(x,y)] es cierto. Lo contrario claramente falla.
3.4.3. Negación de Cuantificadores.
En un sentido importante,∧ y∨ son complementarios. Por las identidades de Morgan (3.3) y (3.4), la negación de una simple conjunción es una disyunción de negaciones. De igual manera, la negación de una disyunción simple es una conjunción de negaciones. Los cuantificadores universales y existenciales también son complementarios. Observamos que[¬(∀x)P(x)]≡[(∃x)¬P(x)] para cualquier fórmula,P(x). Similarmente Por[¬(∃x)P(x)]≡[(∀x)¬P(x)]. supuesto,P(x) en sí misma puede ser una fórmula que tenga numerosos cuantificadores y variables enlazadas. Supongamos queP(x)=(∃y)Q(x,y). Entonces las siguientes declaraciones son equivalentes (para cualquier elecciónP yQ satisfacción de la identidad (3.13)):¬(∀x)P(x)(∃x)¬P(x)¬(∀x)(∃y)Q(x,y)(∃x)¬(∃y)Q(x,y)(∃x)(∀y)¬Q(x,y). Este ejemplo sugiere que es permisible permutar una negación y un cuantificador por cambiando el tipo de cuantificador, y de hecho esto es así.
DejarQi ser un cuantificador, para1≤i≤n. Para cada unoQi, dejaQ∗i ser el cuantificador complementario. Es decir, siQi=∀, entonces vamosQ∗i=∃; siQi=∃, entonces vamosQ∗i=∀. Entonces,¬(Q1x1)(…)(Qnxn)P(ˉx)≡(Q∗1x1)(…)(Q∗nxn)¬P(ˉx).