Existential Quantifier

The existential quantifier $\exists$ is used in predicate logic to ensure a predicate is true for at least one element in a set. It can be thought of as a generalised disjunction

$$\exists x\in S,P(x)$$

where $p$ is the predicate for $x$. Which means there exists (there is at least one) element in $S$ that the predicate holds for.

Definition §

Existential Quantifier ^definition

Let $P$ be a predicate and let $\mathcal{U}$ be a universe (universal set) consisting of $\{x_1,x_2,\dots \}$. Then the existential quantifier is applied as:

$$\exists xP(x)\equiv P(x_1)\vee P(x_2)\vee P(x_3)\dots$$

Which means for at least element in $\mathcal{U}$, the predicate $P$ must hold.

A convention when having a proper subset $D\subset \mathcal{U}$, is:

$$\exists x\in D(P(x))\equiv \exists x(x\in D\wedge P(x))$$

Truth (Existential Quantifier) ^definition-truth

The truth of the existential quantifier requires a model $M$ (having universe, $\mathcal{U}$ and interpretation, $\mathcal{I}$) with a variable assignment, $v$:

$$\exists xP(x)\text{ is true iff there exists at least one u∈U such that P is true under vx↦u}$$

• $P\text{ is true}$ : Refers to truth of the predicate, $P$
• $v_{x\mapsto u}$ : Refers to on-the-fly variable assignment

The existential quantifier is always false for an empty set, i.e. $\exists x\in \varnothing ,P(x)$ is unsatisfiable

Properties §

Let $x,y$ be variables, and let $P,F,G$ be predicates

Self-Commutative §

$$\exists x(\exists yP(x,y))\equiv \exists y(\exists xP(x,y))$$

Not commutative with Universal Quantifier §

Distributive over disjunction §

$$\exists x(F(x)\vee G(x))\equiv (\exists xF(x))\vee (\exists xG(x))$$

Existential Quantifier Couples With Conjunction §

The universal quantifier couples well with conjunction ($\wedge$):

$$\exists m(C(m)\wedge E(m))$$

• $m$ means all students studying a major
• $C(m)$ means $m$ is a CS major
• $E(m)$ means $m$ is employed

The statement above means ‘there exists an employed CS major’. It means there is at least one such person (not me).

Compare with implication:

$$\exists m(C(m)\to E(m))$$

means ‘there exists a college major, who, if they are studying CS, is employed’. At first glance both statements seem to mean the same thing. However, the problem is that this chosen person could very well be an unemployed person who does not study CS, because implication is always true if the premise is false. Meaning, if I were to pick a random college major, and I know that they are not a CS major, the premise of my implication is false, so the implication is vacuously true. Hence, it does not matter if they are employed or not, they could be ‘chosen’ if they do not study CS.

Obviously this is very different than using $\wedge$ and far more undesirable.

%%🖋 Edit in Excalidraw, and the dark exported image%%