Existential Quantifier

logic

Definition

Existential Quantifier

The existential quantifier, denoted by the symbol $\exists$, is a quantifier used in logic to express that there exists at least one element in the domain of discourse that satisfies a given predicate.

A formula $\exists xF$ is true if and only if there is some value in the universe that, when assigned to $x$, makes $F$ true.

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.