Universal quantification

Properties

Negation

The negation of a universally quantified function is obtained by changing the universal quantifier into an existential quantifier and negating the quantified formula. That is,

${\displaystyle \mathrm{\neg }\mathrm{\forall }xP(x)\text{is equivalent to}\mathrm{\exists }x\mathrm{\neg }P(x)}$

where ${\displaystyle \mathrm{\neg }}$ denotes negation.

For example, if P(x) is the propositional function "x is married", then, for the set X of all living human beings, the universal quantification

Given any living person x, that person is married

is written

${\displaystyle \mathrm{\forall }x\in XP(x)}$

This statement is false. Truthfully, it is stated that

It is not the case that, given any living person x, that person is married

or, symbolically:

${\displaystyle \mathrm{\neg }\mathrm{\forall }x\in XP(x)}$.

If the function P(x) is not true for every element of X, then there must be at least one element for which the statement is false. That is, the negation of ${\displaystyle \mathrm{\forall }x\in XP(x)}$ is logically equivalent to "There exists a living person x who is not married", or:

${\displaystyle \mathrm{\exists }x\in X\mathrm{\neg }P(x)}$

It is erroneous to confuse "all persons are not married" (i.e. "there exists no person who is married") with "not all persons are married" (i.e. "there exists a person who is not married"):

${\displaystyle \mathrm{\neg }\mathrm{\exists }x\in XP(x)\equiv \mathrm{\forall }x\in X\mathrm{\neg }P(x)\not\equiv \mathrm{\neg }\mathrm{\forall }x\in XP(x)\equiv \mathrm{\exists }x\in X\mathrm{\neg }P(x)}$

Other connectives

The universal (and existential) quantifier moves unchanged across the logical connectives ∧, ∨, →, and ↚, as long as the other operand is not affected; that is:

${\displaystyle \begin{array}{cc}P(x)\wedge (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\wedge Q(y))\\ P(x)\vee (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\vee Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\\ P(x)\to (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\to Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\\ P(x)\nleftarrow (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\nleftarrow Q(y))\\ P(x)\wedge (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\wedge Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\\ P(x)\vee (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\vee Q(y))\\ P(x)\to (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\to Q(y))\\ P(x)\nleftarrow (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\nleftarrow Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\end{array}}$

Conversely, for the logical connectives ↑, ↓, ↛, and ←, the quantifiers flip:

${\displaystyle \begin{array}{cc}P(x)\uparrow (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\uparrow Q(y))\\ P(x)\downarrow (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\downarrow Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\\ P(x)\nrightarrow (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\nrightarrow Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\\ P(x)\leftarrow (\mathrm{\exists }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\forall }y\in \mathbf{Y}(P(x)\leftarrow Q(y))\\ P(x)\uparrow (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\uparrow Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\\ P(x)\downarrow (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\downarrow Q(y))\\ P(x)\nrightarrow (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\nrightarrow Q(y))\\ P(x)\leftarrow (\mathrm{\forall }y\in \mathbf{Y}Q(y))& \equiv \mathrm{\exists }y\in \mathbf{Y}(P(x)\leftarrow Q(y)),& \text{provided that }\mathbf{Y}\ne \mathrm{\varnothing }\end{array}}$

Rules of inference

A rule of inference is a rule justifying a logical step from hypothesis to conclusion. There are several rules of inference which utilize the universal quantifier.

Universal instantiation concludes that, if the propositional function is known to be universally true, then it must be true for any arbitrary element of the universe of discourse. Symbolically, this is represented as

${\displaystyle \mathrm{\forall }x\in \mathbf{X}P(x)\to P(c)}$

where c is a completely arbitrary element of the universe of discourse.

Universal generalization concludes the propositional function must be universally true if it is true for any arbitrary element of the universe of discourse. Symbolically, for an arbitrary c,

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

The element c must be completely arbitrary; else, the logic does not follow: if c is not arbitrary, and is instead a specific element of the universe of discourse, then P(c) only implies an existential quantification of the propositional function.

The empty set

By convention, the formula ${\displaystyle \mathrm{\forall }x\in \mathrm{\varnothing }P(x)}$ is always true, regardless of the formula P(x); see vacuous truth.

Universal closure

The universal closure of a formula φ is the formula with no free variables obtained by adding a universal quantifier for every free variable in φ. For example, the universal closure of

${\displaystyle P(y)\wedge \mathrm{\exists }xQ(x,z)}$

is

${\displaystyle \mathrm{\forall }y\mathrm{\forall }z(P(y)\wedge \mathrm{\exists }xQ(x,z))}$.

As adjoint

In category theory and the theory of elementary topoi, the universal quantifier can be understood as the right adjoint of a functor between power sets, the inverse image functor of a function between sets; likewise, the existential quantifier is the left adjoint.

For a set ${\displaystyle X}$, let ${\displaystyle \mathcal{P}X}$ denote its powerset. For any function ${\displaystyle f:X\to Y}$ between sets ${\displaystyle X}$ and ${\displaystyle Y}$, there is an inverse image functor ${\displaystyle f^{\ast }:\mathcal{P}Y\to \mathcal{P}X}$ between powersets, that takes subsets of the codomain of f back to subsets of its domain. The left adjoint of this functor is the existential quantifier ${\displaystyle {\mathrm{\exists }}_f}$ and the right adjoint is the universal quantifier ${\displaystyle {\mathrm{\forall }}_f}$.

That is, ${\displaystyle {\mathrm{\exists }}_f:\mathcal{P}X\to \mathcal{P}Y}$ is a functor that, for each subset ${\displaystyle S\subset X}$, gives the subset ${\displaystyle {\mathrm{\exists }}_{f}S\subset Y}$ given by

${\displaystyle {\mathrm{\exists }}_{f}S=\{y\in Y|\mathrm{\exists }x\in X.f(x)=y\wedge x\in S\},}$

those ${\displaystyle y}$ in the image of ${\displaystyle S}$ under ${\displaystyle f}$. Similarly, the universal quantifier ${\displaystyle {\mathrm{\forall }}_f:\mathcal{P}X\to \mathcal{P}Y}$ is a functor that, for each subset ${\displaystyle S\subset X}$, gives the subset ${\displaystyle {\mathrm{\forall }}_{f}S\subset Y}$ given by

${\displaystyle {\mathrm{\forall }}_{f}S=\{y\in Y|\mathrm{\forall }x\in X.f(x)=y⟹x\in S\},}$

those ${\displaystyle y}$ whose preimage under ${\displaystyle f}$ is contained in ${\displaystyle S}$.

The more familiar form of the quantifiers as used in first-order logic is obtained by taking the function f to be the unique function ${\displaystyle !:X\to 1}$ so that ${\displaystyle \mathcal{P}(1)=\{T,F\}}$ is the two-element set holding the values true and false, a subset S is that subset for which the predicate ${\displaystyle S(x)}$ holds, and

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

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

which is true if ${\displaystyle S}$ is not empty, and

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

which is false if S is not X.

The universal and existential quantifiers given above generalize to the presheaf category.