Universal Quantifier

The universal quantifier $\forall$ is used in predicate logic to ensure a predicate is true for all elements in a set. It can be thought of as a generalised conjunction.

For example, the statement “All natural numbers are greater or equal to 0 can be written as: $(\forall n\in \mathbb{N}),n\ge 0$

Definition §

Universal Quantifier

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

$$\forall xP(x)\equiv P(x_1)\wedge P(x_2)\wedge P(x_3)\dots$$

Which means for all elements in $\mathcal{U}$, the predicate $P$ must hold.

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

$$\forall x\in D(P(x))\equiv \forall x(x\in D\to P(x))$$

Truth (Universal Quantifier) ^definition-truth

The universal quantifier is true if negation is false (woah.):

$$\forall xP(x)\text{ is true iff }\neg (\exists x(\neg P(x)))$$

Its truth is usually expressed through the existential quantifier

The universal quantifier is always true for an empty set, i.e. $\forall x\in \varnothing ,P(x)$ is true.

Universal Quantifier Couples With Implication §

The universal quantifier couples well with implication ($\to$).

$$\forall t(P(t)\to M(t))$$

• $t$ means all things
• $P(t)$ means $t$ is a person
• $M(t)$ means $t$ is mortal

The statement above means ‘all people are mortal’. More specifically, if a thing is a person, it must be mortal.

Compare with conjunction ($\wedge$):

$$\forall t(P(t)\wedge M(t))$$

means everything is a mortal person, (obviously a very different, and usually less-desired meaning)!

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

Examples §

• Every program produces input: $\forall p\in P,I(p)$ where
  • $I(x)$ means $x$ produces input.
  • $P$ is the set of all programs