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.

Properties §

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

Self-Commutative §

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

Not commutative with Existential Quantifier §

Distributive over conjunction §

$$\forall x(F(x)\wedge G(x))\equiv (\forall xF(x))\wedge (\forall xG(x))$$

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%%

Universally Quantifiable Variables §

Any free variable (i.e. not bound by an explicit quantifier) conventionally is considered a universally quantifiable variable. Meaning it contains a implicit (hidden) universal quantifier

Let $P,Q$ be predicates. Take the formulas

$$[P(x)\to \exists yQ(y)]\wedge [Q(z)]$$

$y$ is a bound variable, but $x$ and $z$ are free so they are considered to be universally quantifiable variables. Hence, we have an implicit quantifier:

$$\underline{\forall x}(P(x)\to \exists y(Q(y))),\underline{\forall z}(Q(z))$$

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