Cuantificación universal

En lógica matemática , una cuantificación universal es un tipo de cuantificador , una constante lógica que se interpreta como " para cualquier ", " para todo ", " para cada " o " para un elemento arbitrario ". Expresa que un predicado puede ser satisfecho por cada miembro de un dominio de discurso . En otras palabras, es la predicación de una propiedad o relación a cada miembro del dominio. Afirma que un predicado dentro del alcance de un cuantificador universal es verdadero para cada valor de una variable de predicado .

Generalmente se denota mediante el símbolo del operador lógico A (∀) , que, cuando se usa junto con una variable predicativa, se denomina cuantificador universal (" $\forall$ $x$ ", " $\forall($ $x$ $)$ ", o a veces simplemente " $($ $x$ $)$ "). La cuantificación universal se distingue de la cuantificación existencial ("existe"), que solo afirma que la propiedad o relación se cumple para al menos un miembro del dominio.

La cuantificación en general se trata en el artículo sobre cuantificación (lógica) . El cuantificador universal se codifica como U+2200 ∀ FOR ALL en Unicode , y como en LaTeX y editores de fórmulas relacionados.\forall

Lo esencial

Supongamos que se da que

2·0 = 0 + 0, y 2·1 = 1 + 1, y 2·2 = 2 + 2 , ..., y 2 · 100 = 100 + 100, y ..., etc.

Esto parecería ser una conjunción lógica infinita debido al uso repetido de "y". Sin embargo, el "etc." no puede interpretarse como una conjunción en lógica formal . En cambio, la afirmación debe reformularse:

Para todos los números naturales n , se tiene 2· n = n + n .

Se trata de una única afirmación que utiliza cuantificación universal.

Esta afirmación puede considerarse más precisa que la original. Si bien el "etc." incluye informalmente los números naturales y nada más, esto no se especificó rigurosamente. En cambio, en la cuantificación universal, los números naturales se mencionan explícitamente.

Este ejemplo en particular es cierto , porque cualquier número natural podría sustituirse por n y la afirmación "2· n = n + n " sería verdadera. En cambio,

Para todos los números naturales n , se tiene 2· n > 2 + n

es falso , porque si se sustituye n por, por ejemplo, 1, la afirmación "2·1 > 2 + 1" es falsa. Es irrelevante que "2· n > 2 + n " sea verdadera para la mayoría de los números naturales n : incluso la existencia de un solo contraejemplo es suficiente para demostrar que la cuantificación universal es falsa.

Por otro lado, para todos los números compuestos n , se tiene que 2· n > 2 + n es verdadero, porque ninguno de los contraejemplos son números compuestos. Esto indica la importancia del dominio del discurso , que especifica qué valores puede tomar n . ^{[ nota 1 ]} En particular, observe que si el dominio del discurso se restringe a consistir solo en aquellos objetos que satisfacen un cierto predicado, entonces para la cuantificación universal esto requiere una condición lógica . Por ejemplo,

Para todos los números compuestos n , se tiene 2· n > 2 + n

es lógicamente equivalente a

Para todos los números naturales n , si n es compuesto, entonces 2· n > 2 + n .

Aquí, la construcción "si... entonces" indica la condición lógica.

Notación

En lógica simbólica , el símbolo cuantificador universal $\forall$ (una " A " girada en una fuente sans-serif , Unicode U+2200) se utiliza para indicar cuantificación universal. Fue utilizada por primera vez de esta manera por Gerhard Gentzen en 1935, por analogía con la de Giuseppe Peano . $\exists$ (convertida en E) notación para cuantificación existencial y el uso posterior de la notación de Peano por Bertrand Russell . ^{[ 1 ]}

Por ejemplo, si P ( n ) es el predicado "2· n > 2 + n " y N es el conjunto de los números naturales, entonces

\forall n\!\in \!\mathbb {N} \;P(n)

es la afirmación (falsa)

"Para todos los números naturales n , se tiene 2· n > 2 + n ".

De manera similar, si Q ( n ) es el predicado " n es compuesto", entonces

\forall n\!\in \!\mathbb {N} \;{\bigl (}Q(n)\rightarrow P(n){\bigr )}

es la afirmación (verdadera)

"Para todos los números naturales n , si n es compuesto, entonces 2· n > 2 + n ".

En el artículo sobre cuantificadores se pueden encontrar varias variaciones en la notación para la cuantificación (que se aplican a todas las formas) .

Propiedades

Negación

La negación de una función cuantificada universalmente se obtiene cambiando el cuantificador universal por un cuantificador existencial y negando la fórmula cuantificada. Es decir,

\lnot \forall x\;P(x)\quad {\text{is equivalent to}}\quad \exists x\;\lnot P(x)

dónde $\lnot$ denota negación .

Por ejemplo, si $P (x)$ es la función proposicional " $x$ está casado", entonces, para el conjunto $X$ de todos los seres humanos vivos, la cuantificación universal

Dado cualquier individuo vivo $x$ , ese individuo está casado.

está escrito

\forall x\in X\,P(x)

Esta afirmación es falsa. En realidad, se afirma que

No es cierto que, dado cualquier persona viva $x$ , esa persona esté casada.

o, simbólicamente:

\lnot \ \forall x\in X\,P(x)

.

Si la función $P (x)$ no es verdadera para cada elemento de $X$ , entonces debe haber al menos un elemento para el cual la afirmación sea falsa. Es decir, la negación de $\forall x\in X\,P(x)$ es lógicamente equivalente a "Existe una persona viva $x$ que no está casada", o:

\exists x\in X\,\lnot P(x)

Es erróneo confundir "no todas las personas están casadas" (es decir, "no existe ninguna persona que esté casada") con "no todas las personas están casadas" (es decir, "existe una persona que no está casada"):

\lnot \ \exists x\in X\,P(x)\equiv \ \forall x\in X\,\lnot P(x)\not \equiv \ \lnot \ \forall x\in X\,P(x)\equiv \ \exists x\in X\,\lnot P(x)

Otros conectores

El cuantificador universal (y existencial) se mueve sin cambios a través de los conectores lógicos ∧ , ∨ , → , y ↚ , siempre que el otro operando no se vea afectado; ^{[ 2 ]} es decir:

{\begin{aligned}P(x)\land (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\land Q(y))\\P(x)\lor (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\to (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\to Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\nleftarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y))\\P(x)\land (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\land Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\lor (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y))\\P(x)\to (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\to Q(y))\\P(x)\nleftarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \end{aligned}}

Por el contrario, para los conectores lógicos ↑ , ↓ , ↛ , y ← , los cuantificadores se invierten:

{\begin{aligned}P(x)\uparrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y))\\P(x)\downarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\nrightarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\gets (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y))\\P(x)\uparrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\downarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y))\\P(x)\nrightarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y))\\P(x)\gets (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\\end{aligned}}

Reglas de inferencia

Una regla de inferencia es una regla que justifica un paso lógico desde la hipótesis hasta la conclusión. Existen varias reglas de inferencia que utilizan el cuantificador universal.

La instanciación universal concluye que, si se sabe que la función proposicional es universalmente verdadera, entonces debe ser verdadera para cualquier elemento arbitrario del universo del discurso. Simbólicamente, esto se representa como

\forall {x}{\in }\mathbf {X} \,P(x)\to P(c)

donde c es un elemento completamente arbitrario del universo del discurso.

La generalización universal concluye que la función proposicional debe ser universalmente verdadera si es verdadera para cualquier elemento arbitrario del universo del discurso. Simbólicamente, para un c arbitrario ,

P(c)\to \ \forall {x}{\in }\mathbf {X} \,P(x).

El elemento c debe ser completamente arbitrario; de lo contrario, la lógica no se sigue: si c no es arbitrario, y en cambio es un elemento específico del universo del discurso, entonces P( c ) solo implica una cuantificación existencial de la función proposicional.

El conjunto vacío

Por convención, la fórmula $\forall {x}{\in }\emptyset \,P(x)$ siempre es cierto, independientemente de la fórmula P ( x ); véase verdad vacía .

Cierre universal

El cierre universal de una fórmula φ es la fórmula sin variables libres que se obtiene al agregar un cuantificador universal para cada variable libre en φ. Por ejemplo, el cierre universal de

P(y)\land \exists xQ(x,z)

es

\forall y\forall z(P(y)\land \exists xQ(x,z))

.

Como adjunto

En la teoría de categorías y la teoría de topoi elementales , el cuantificador universal puede entenderse como el adjunto derecho de un functor entre conjuntos potencia , el functor imagen inversa de una función entre conjuntos; asimismo, el cuantificador existencial es el adjunto izquierdo . ^{[ 3 ]}

Para un conjunto $X$ , dejar ${\mathcal {P}}X$ denotemos su conjunto potencia . Para cualquier función $f:X\to Y$ entre conjuntos $X$ y $Y$ , existe un functor de imagen inversa $f^{*}:{\mathcal {P}}Y\to {\mathcal {P}}X$ entre conjuntos potencia, que transforma subconjuntos del codominio de f en subconjuntos de su dominio. El adjunto izquierdo de este functor es el cuantificador existencial. $\exists _{f}$ y el adjunto derecho es el cuantificador universal $\forall _{f}$ .

Eso es, $\exists _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ es un funtor que, para cada subconjunto $S\subset X$ , da el subconjunto $\exists _{f}S\subset Y$ dado por

\exists _{f}S=\{y\in Y\;|\;\exists x\in X.\ f(x)=y\quad \land \quad x\in S\},

aquellos $y$ en la imagen de $S$ bajo $f$ . De manera similar, el cuantificador universal $\forall _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ es un funtor que, para cada subconjunto $S\subset X$ , da el subconjunto $\forall _{f}S\subset Y$ dado por

\forall _{f}S=\{y\in Y\;|\;\forall x\in X.\ f(x)=y\quad \implies \quad x\in S\},

aquellos $y$ cuya preimagen bajo $f$ está contenido en $S$ .

La forma más familiar de los cuantificadores tal como se utilizan en la lógica de primer orden se obtiene tomando la función f como la única función ${\displaystyle$ para que ${\mathcal {P}}(1)=\{T,F\}$ es el conjunto de dos elementos que contiene los valores verdadero y falso, un subconjunto S es aquel subconjunto para el cual el predicado $S(x)$ sostiene y

{\begin{array}{rl}{\mathcal {P}}(!)\colon {\mathcal {P}}(1)&\to {\mathcal {P}}(X)\\T&\mapsto X\\F&\mapsto \{\}\end{array}}

\exists _{!}S=\exists x.S(x),

lo cual es cierto si $S$ no está vacío, y

\forall _{!}S=\forall x.S(x),

lo cual es falso si S no es X.

Los cuantificadores universales y existenciales dados anteriormente se generalizan a la categoría de prehaz .

Véase también

cuantificación existencial
Lógica de primer orden
Lista de símbolos lógicos —para el símbolo Unicode ∀

Notas

↑ Puede encontrar más información sobre el uso de dominios de discurso con enunciados cuantificados en elartículo Cuantificación (lógica) .

Referencias

↑ Miller, Jeff. "Primeros usos de los símbolos de la teoría de conjuntos y la lógica" . Primeros usos de varios símbolos matemáticos .
↑ es decir, si la variable $y$ no aparece libre en la fórmula $P(x)$ en las equivalencias a continuación
↑ Saunders Mac Lane , Ieke Moerdijk , (1992) Haz en geometría y lógica Springer-Verlag. ISBN 0-387-97710-4Ver página 58

Hinman, P. (2005). Fundamentos de lógica matemática . AK Peters . ISBN 1-56881-262-0.
Franklin, J. y Daoud, A. (2011). Demostración en matemáticas: Una introducción . Kew Books. ISBN 978-0-646-54509-7.{{cite book}}: CS1 maint: nombres múltiples: lista de autores ( enlace ) (cap. 2)

Enlaces externos

La definición de diccionario de cada uno en Wikcionario

[1] Puede encontrar más información sobre el uso de dominios de discurso con enunciados cuantificados en elartículo Cuantificación (lógica) .

[2] Miller, Jeff. "Primeros usos de los símbolos de la teoría de conjuntos y la lógica" . Primeros usos de varios símbolos matemáticos .

[3] s decir, si la variable $y$ no aparece libre en la fórmula $P(x)$ en las equivalencias a continuación

[4] Saunders Mac Lane , Ieke Moerdijk , (1992) Haz en geometría y lógica Springer-Verlag. ISBN 0-387-97710-4Ver página 58

[ nota 1 ]

[ 1 ]

[ 2 ]

[ 3 ]