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 "dada cualquier" o "para todos". 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.

Por lo general, se denota con el símbolo del operador lógico A girado (∀), que, cuando se usa junto con una variable de predicado, se denomina cuantificador universal ("∀x", "∀(x)&# 34;, o a veces por "(x)" solo). La cuantificación universal es distinta 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 ∀ PARA TODOS en Unicode, y como forall en LaTeX y editores de fórmulas relacionados.

Conceptos básicos

Supongamos que se da que

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

Parecería ser una conjunción lógica debido al uso repetido de "y". Sin embargo, el "etc." no puede interpretarse como una conjunción en lógica formal. En su lugar, la declaración debe ser reformulada:

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

Esta es una declaración única que utiliza la cuantificación universal.

Se puede decir que esta afirmación es más precisa que la original. Mientras que el "etc." informalmente incluye números naturales, y nada más, esto no se dio con rigor. En la cuantificación universal, en cambio, los números naturales se mencionan explícitamente.

Este ejemplo en particular es verdadero, porque cualquier número natural podría sustituirse por n y la afirmación "2·n = n + n" seria verdad A diferencia de,

Para todos los números naturales n, uno tiene 2·n ■ 2 + n

es falso, porque si n se sustituye por, por ejemplo, 1, la sentencia "2·1 > 2 + 1" Es falso. Es irrelevante que "2·n > 2 + n" es cierto 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, uno tiene 2·n > 2 + n es cierto, porque ninguno de los contraejemplos son números compuestos. Esto indica la importancia del dominio del discurso, que especifica qué valores puede tomar n. En particular, tenga en cuenta que si el dominio del discurso está restringido a consistir solo en aquellos objetos que satisfacen un cierto predicado, entonces para la cuantificación universal esto requiere un condicional lógico. Por ejemplo,

Para todos los números compuestos n, uno 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í el "si... entonces" la construcción indica el condicional lógico.

Notación

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

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

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

es la declaración (falsa)

"para todos los números naturales n, uno tiene 2·n ■ 2 + n".

Del mismo modo, si Q(n) es el predicado "n es compuesto", entonces

${displaystyle 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 composite, entonces 2·n ■ 2 + n".

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

Propiedades

Negación

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

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

Donde ${displaystyle 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

Given any living person x, esa persona está casada

está escrito

${displaystyle forall xin X,P(x)}$

Esta afirmación es falsa. A decir verdad, se afirma que

No es el caso que, dado cualquier persona viva x, esa persona está casada

o, simbólicamente:

${displaystyle lnot \forall xin X,P(x)}$.

Si la función P()x) no es verdad cada uno elemento X, entonces debe haber al menos un elemento para el cual la declaración es falsa. Es decir, la negación de ${displaystyle forall xin X,P(x)}$ es lógicamente equivalente a "Existe una persona viviente x que no está casado", o:

${displaystyle exists xin X,lnot P(x)}$

Es erróneo confundir "todas las personas no 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"):

${displaystyle lnot exists xin X,P(x)equiv forall xin X,lnot P(x)not equiv lnot paraall xin X,P(x)equiv exists xin 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; es decir:

${fnMicrosoft Sans Serif}$

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

${fnMicrosoft Sans Serif}$

Reglas de inferencia

Una regla de inferencia es una regla que justifica un paso lógico de la hipótesis a la conclusión. Hay 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

${displaystyle 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 una c arbitraria,

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

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

El conjunto vacío

Por convención, la fórmula ${displaystyle forall {x}{in }emptyset ,P(x)}$ es siempre verdad, independientemente de la fórmula P()x); ver la verdad vacua.

Cierre universal

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

${displaystyle P(y)land exists xQ(x,z)}$

es

${displaystyle forall yforall z(P(y)land exists xQ(x,z)}$.

Como adjunto

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

Para un set ${displaystyle X}$, vamos ${displaystyle {Mathcal {}X}$ denota su potencia. Para cualquier función ${displaystyle f:Xto Sí.$ entre grupos ${displaystyle X}$ y ${displaystyle Sí.$, hay un functor de imagen inversa ${displaystyle f^{}:{mthcal {}Yto {fnMithcal}X}$ entre poderes, que toma subconjuntos del codominio f volver a subconjuntos de su dominio. La unión izquierda de este functor es el cuantificador existencial ${displaystyle exists _{f}$ y la unión derecha es el cuantificador universal ${displaystyle forall _{f}$.

Eso es, ${displaystyle exists _{f}colon {fnMitcal {}Xto {fnMitcal} Sí.$ es un functor que, para cada subconjunto ${displaystyle Ssubset X}$, da el subconjunto ${displaystyle exists _{f} Ssubset Sí.$ dado por

${displaystyle exists _{f}S={yin Y; paciencia;exists xin X. f(x)=yquad land quad xin S},}$

esos ${displaystyle y}$ en la imagen de ${displaystyle S.$ menores ${displaystyle f}$. Del mismo modo, el cuantificador universal ${displaystyle forall _{f}colon {fnMitcal {}Xto {fnMitcal} Sí.$ es un functor que, para cada subconjunto ${displaystyle Ssubset X}$, da el subconjunto ${displaystyle forall _{f} Ssubset Sí.$ dado por

${displaystyle forall _{f}S={yin Y; paciencia;forall xin X. f(x)=yquad implies quad xin S},}$

esos ${displaystyle y}$ cuyo preimage ${displaystyle f}$ figura en ${displaystyle S.$.

La forma más familiar de los cuantificadores utilizados en la lógica de primer orden se obtiene tomando la función f ser la función única ${displaystyle !:Xto 1}$ así ${displaystyle {mathcal {}(1)={T,F}$ es el conjunto de dos elementos que sostienen los valores verdaderos y falsos, un subconjunto S es ese subconjunto para el cual el predicado ${displaystyle S(x)}$ y

${displaystyle {begin{rl}{mathcal {P}(!)colon {mathcal {}(1) limitto {mathcal {}(X)\T simultáneamentemapsto X\\fnMicrosoft\\fnMicrosoft Sans Serif} {fnK}}$

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

que es verdad si ${displaystyle S.$ no está vacío, y

${displaystyle 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 pregavilla.