Universal Quantifier

first-order-logic

Definition

Universal Quantifier

The universal quantifier $\forall x\phi$ is true under an interpretation $(\mathcal{M},\ell )$ if $\phi$ holds for every re-assignment of $x$:

$$(\mathcal{M},\ell )\models \forall x\phi ⟺(\mathcal{M},\ell [d/x])\models \phi \text{for all }d\in \mathcal{D}$$

Semantics

Formally, the semantics are defined using an interpretation $I$ and a variable assignment $\sigma$. The valuation function ${\mathrm{val}}_{I,\sigma }$ for a universally quantified formula is:

$${\mathrm{val}}_{I,\sigma }(\forall xF)=\{\begin{array}{ll}1& \text{if for all }{\sigma }^{\prime }\stackrel{x}{\sim }\sigma \text{ it holds that }{\mathrm{val}}_{I,{\sigma }^{\prime }}(F)=1\\ 0& \text{otherwise}\end{array}$$

where ${\sigma }^{\prime }\stackrel{x}{\sim }\sigma$ denotes a variable assignment that is identical to $\sigma$ except possibly for the value assigned to $x$.

Relation to Existential Quantifier

The universal quantifier is the dual of the existential quantifier ($\exists$). They are related by De Morgan’s laws for quantifiers:

$$\begin{array}{rl}\forall xF& \equiv \neg \exists x\neg F\\ \neg \forall xF& \equiv \exists x\neg F\end{array}$$

Empty Domains

In a universe that is empty, any universally quantified statement is vacuously true, while any existentially quantified statement is false. However, in standard first-order logic, the domain of discourse is usually assumed to be non-empty.