Existential Quantifier

first-order-logic

Definition

Existential Quantifier

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

$$(\mathcal{M},\ell )\models \exists x\phi ⟺(\mathcal{M},\ell [d/x])\models \phi \text{for some }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 an existentially quantified formula is:

$${\mathrm{val}}_{I,\sigma }(\exists xF)=\{\begin{array}{ll}1& \text{if there exists }{\sigma }^{\prime }\stackrel{x}{\sim }\sigma \text{ such 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 Universal Quantifier

The existential quantifier is the dual of the universal quantifier ($\forall$). In classical logic, they are related by De Morgan’s laws for quantifiers:

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

Multiplicity

The statement $\exists xF$ does not specify how many elements satisfy $F$, only that the set of such elements is non-empty. For “exactly one”, the unique existential quantifier $\exists !$ is used.