3.4: Cuantificadores

Dejar\(P(x)\) ser una fórmula en una variable. Si sustituimos una constante\(a \in U\),,\(x\) pues llegamos a un comunicado\(P(a)\). No obstante, supongamos que nos interesa\(P(x)\) con respecto a algún conjunto\(X \subseteq U\), más que a un elemento particular de\(U\). En particular, preguntamos si\(P(a)\) es una verdadera declaración para todos\(a \in X\). Recordemos que uno de los roles de una fórmula es definir conjuntos. Para cualquier fórmula\(P(x)\), universo\(U\) y\(X \subseteq U, P(x)\) particiones\(X\) en dos conjuntos - aquellos elementos de\(X\) para los cuales\(P\) es cierto, y aquellos para los que\(P\) es falso. En este sentido, preguntar si se\(P\) sostiene para todos\(x \in X\), o si se sostiene para algunos\(x \in X\) (lo que es complementario a preguntar si se\(\neg P\) mantiene para todos\(x \in X)\) es preguntar si\(P\) define una nuevo o interesante subconjunto de\(X\).

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,\((\forall x \in X) P(x)\) Let\(P(x)\) be una fórmula en una variable, con universo\(U\). Vamos\(X \subseteq U\). \(Q\)Sea el enunciado\[(\forall x \in X) P(x)\] Entonces\(Q\) es cierto si por cada\(a \in X, P(a)\) es cierto. De lo contrario\(Q\) es falso.

La notación\[(\forall x \in X) P(x)\] es una taquigrafía para\[(\forall x)([x \in X] \Rightarrow[P(x)])\] La declaración "\((\forall x \in X) P(x) "\)se lee “para todos\(x\) en\(X, P(x) "\). Tenemos\[(\forall x \in X) P(x) \Longleftrightarrow X \subseteq \chi_{P}\] DEFINICIÓN. Cuantificador existencial,\((\exists x \in X) P(x)\) Let\(P(x)\) Ser una fórmula en una variable con universo\(U .\) Let\(X \subseteq U, X \neq \emptyset\). \(Q\)Sea el enunciado\[(\exists x \in X) P(x) .\] Entonces\(Q\) es cierto si hay alguno\(a \in X\), para lo cual\(P(a)\) es cierto. De lo contrario\(Q\) es falso.

La expresión\[(\exists x \in X) P(x)\] es una taquigrafía para\[(\exists x)[(x \in X) \wedge P(x)] \text {. }\] La declaración\((\exists x \in X) P(x)\) "" se lee “existe\(x\) en\(X\), tal que\(P(x)\)”. El cuantificador "\(\nabla\)" es el equivalente formal de la expresión del lenguaje natural “para todos” o “cada”. El cuantificador "\(\exists\)" 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, si\(P(x)\) es una fórmula con universo\(U\), podemos escribir\[(\forall x) P(x)\] en lugar de\[(\forall x \in U) P(x) .\]

3.4.1. Cuantificadores Múltiples.

Dejar\(P\left(x_{1}, \ldots, x_{n}\right)\) ser una fórmula en\(n \geq 2\) variables. Entonces la fórmula\[\left(\forall x_{1}\right) P\left(x_{1}, \ldots, x_{n}\right)\] es una fórmula en las\(n-1\) variables\(x_{2}, \ldots, x_{n}\). De igual manera, la fórmula\[\left(\exists x_{1}\right) P\left(x_{1}, \ldots, x_{n}\right)\] es una fórmula en\(n-1\) variables.

EJEMPLO 3.10. Considera la fórmula en cinco variables\[P\left(x, x_{0}, L, \varepsilon, \delta\right):=\left(0<\left|x-x_{0}\right|<\delta\right) \Rightarrow(|\sin (x)-L|<\varepsilon)\] con todas las variables teniendo universo\(\mathbb{R}\). Entonces\(\left(\forall x_{0}\right) P\left(x, x_{0}, L, \varepsilon, \delta\right)\) es una fórmula en cuatro variables,\(\left(\forall x_{0}\right)(\exists L) P\left(x, x_{0}, L, \varepsilon, \delta\right)\) es una fórmula en tres variables, y\[\left(\forall x_{0}\right)(\exists L)(\forall \varepsilon) P\left(x, x_{0}, L, \varepsilon, \delta\right)\] es una fórmula en dos variables.

Definición. Variable abierta, Variable enlazada En la fórmula\(P(x)\),\(x\) es una variable abierta. En las fórmulas\[(\forall x) P(x), \quad(\exists x) P(x), \quad(\forall x) Q(x, y), \quad(\exists 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. \((\mathcal{Q} x) P(x)\)Utilizamos la notación\[\text { (Q } \mathcal{Q} x) P(x)\] para representar genéricamente\[(\forall x) P(x)\] y\[(\exists x) P(x) \text {. }\] Let\(\mathcal{Q}_{1}, \ldots, \mathcal{Q}_{n}\) be cuantificadores lógicos y\(P\left(x_{1}, \ldots, x_{n}\right)\) ser una fórmula con variables abiertas\(x_{1}, \ldots, x_{n}\). Entonces\[\left(\mathcal{Q}_{1} x_{1}\right)\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] es una declaración.

EJEMPLO 3.11. Considerar una declaración\(S\) en la forma\[S=(\forall x \in X)(\exists y \in Y) P(x, y) .\]\(S\) es verdadera si para cada uno\(a \in X\),\[(\exists y \in Y) P(a, y)\] es verdad. Esto se satisface siempre que para cada uno\(a \in X\), haya un elemento de\(Y\) (llamémoslo\(b_{a}\) para recordarnos que este elemento particular de\(Y\) está asociado con la elección anterior, a) tal que\[P\left(a, b_{a}\right)\] es cierto. Así\(b_{a}\) se selecciona teniendo\(a\) 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\[\left(\mathcal{Q}_{1} x_{1}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] El orden de los cuantificadores es significativo. Si\(1 \leq i<j \leq n, x_{i}\) se comporta como un parámetro desde el punto de vista de\(x_{j}\) (es decir,\(x_{i}\) se fija desde el punto de vista de\(x_{j}\)). Dicho de otra manera,\(x_{j}\) se elige con respecto a las sustituciones de\(x_{1}, \ldots, x_{j-1}\), pero sin consideración para\(x_{j+1}, \ldots, x_{n}\).

Siempre se lee desde la izquierda. El enunciado\[\left(\forall x_{1}\right)\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] es el mismo que\[\left(\forall x_{1}\right)\left[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\right] \text {, }\] o, en otras palabras, para cada elección de\(x_{1}\), la afirmación\[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] es cierta. De igual manera, la afirmación\[\left(\exists x_{1}\right)\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] es la misma que\[\left(\exists x_{1}\right)\left[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\right] \text {, }\] o en otras palabras que hay alguna elección de\(x_{1}\) para la cual la afirmación\[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] sobre las\(n-1\) variables\(x_{2}, \ldots, x_{n}\) es verdadera.

EJEMPLO 3.12. El orden de los cuantificadores es importante, como se puede ver en lo siguiente: no\[(\forall x \in X)(\exists y \in Y) P(x, y)\] es equivalente a\[(\exists y \in Y)(\forall x \in X) P(x, y) .\] Por ejemplo, la afirmación\[(\forall x \in \mathbb{R})(\exists y \in \mathbb{R})\left(y=x^{2}\right)\] es verdadera. Pero\[(\exists y \in \mathbb{R})(\forall x \in \mathbb{R})\left(y=x^{2}\right)\] es falso. El enunciado\[[(\exists y \in Y)(\forall x \in X) P(x, y)] \Rightarrow[(\forall x \in X)(\exists y \in Y) P(x, y)]\] es cierto. Lo contrario claramente falla.

3.4.3. Negación de Cuantificadores.

En un sentido importante,\(\wedge\) y\(\vee\) 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\[[\neg(\forall x) P(x)] \equiv[(\exists x) \neg P(x)]\] para cualquier fórmula,\(P(x)\). Similarmente Por\[[\neg(\exists x) P(x)] \equiv[(\forall x) \neg P(x)] .\] supuesto,\(P(x)\) en sí misma puede ser una fórmula que tenga numerosos cuantificadores y variables enlazadas. Supongamos que\[P(x)=(\exists y) Q(x, y) .\] Entonces las siguientes declaraciones son equivalentes (para cualquier elección\(P\) y\(Q\) satisfacción de la identidad (3.13)):\[\begin{gathered} \neg(\forall x) P(x) \\ (\exists x) \neg P(x) \\ \neg(\forall x)(\exists y) Q(x, y) \\ (\exists x) \neg(\exists y) Q(x, y) \\ (\exists x)(\forall y) \neg Q(x, y) . \end{gathered}\] 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í.

Dejar\(\mathcal{Q}_{i}\) ser un cuantificador, para\(1 \leq i \leq n\). Para cada uno\(\mathcal{Q}_{i}\), deja\(\mathcal{Q}_{i}^{*}\) ser el cuantificador complementario. Es decir, si\(\mathcal{Q}_{i}=\forall\), entonces vamos\(\mathcal{Q}_{i}^{*}=\exists\); si\(\mathcal{Q}_{i}=\exists\), entonces vamos\(\mathcal{Q}_{i}^{*}=\forall\). Entonces,\[\neg\left(\mathcal{Q}_{1} x_{1}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P(\bar{x}) \equiv\left(\mathcal{Q}_{1}^{*} x_{1}\right)(\ldots)\left(\mathcal{Q}_{n}^{*} x_{n}\right) \neg P(\bar{x}) .\]