Kripke–Platek set theory

If any set ${\displaystyle c}$ is postulated to exist, such as in the axiom of infinity, then the axiom of empty set is redundant because it is equal to the subset ${\displaystyle \{x\in c\mid x\neq x\}}$. Furthermore, the existence of a member in the universe of discourse, i.e., ∃x(x=x), is implied in certain formulations[1] of first-order logic, in which case the axiom of empty set follows from the axiom of Δ₀-separation, and is thus redundant.

As noted, the above are weaker than ZFC as they exclude the power set axiom, choice, and sometimes infinity. Also the axioms of separation and collection here are weaker than the corresponding axioms in ZFC because the formulas φ used in these are limited to bounded quantifiers only.

The axiom of induction in the context of KP is stronger than the usual axiom of regularity, which amounts to applying induction to the complement of a set (the class of all sets not in the given set).

The ordinal α is an admissible ordinal if and only if α is a limit ordinal and there does not exist a γ < α for which there is a Σ₁(L_α) mapping from γ onto α. If M is a standard model of KP, then the set of ordinals in M is an admissible ordinal.

Theorem: If A and B are sets, then there is a set A×B which consists of all ordered pairs (a, b) of elements a of A and b of B.

Proof:

The singleton set with member a, written {a}, is the same as the unordered pair {a, a}, by the axiom of extensionality.

The singleton, the set {a, b}, and then also the ordered pair

${\displaystyle (a,b):=\{\{a\},\{a,b\}\}}$

all exist by pairing. A possible Δ₀-formula ${\displaystyle \psi (a,b,p)}$ expressing that p stands for the pair (a, b) is given by the lengthy

${\displaystyle \exists r\in p\,{\big (}a\in r\,\land \,\forall x\in r\,(x=a){\big )}}$

${\displaystyle \land \,\exists s\in p\,{\big (}a\in s\,\land \,b\in s\,\land \,\forall x\in s\,(x=a\,\lor \,x=b){\big )}}$

${\displaystyle \land \,\forall t\in p\,{\Big (}{\big (}a\in t\,\land \,\forall x\in t\,(x=a){\big )}\,\lor \,{\big (}a\in t\land b\in t\land \forall x\in t\,(x=a\,\lor \,x=b){\big )}{\Big )}.}$

What follows are two steps of collection of sets, followed by a restriction through separation. All results are also expressed using set builder notation.

Firstly, given ${\displaystyle b}$ and collecting with respect to ${\displaystyle A}$, some superset of ${\displaystyle A\times \{b\}=\{(a,b)\mid a\in A\}}$ exists by collection.

The Δ₀-formula

${\displaystyle \exists a\in A\,\psi (a,b,p)}$

grants that just ${\displaystyle A\times \{b\}}$ itself exists by separation.

If ${\displaystyle P}$ ought to stand for this collection of pairs ${\displaystyle A\times \{b\}}$, then a Δ₀-formula characterizing it is

${\displaystyle \forall a\in A\,\exists p\in P\,\psi (a,b,p)\,\land \,\forall p\in P\,\exists a\in A\,\psi (a,b,p)\,.}$

Given ${\displaystyle A}$ and collecting with respect to ${\displaystyle B}$, some superset of ${\displaystyle \{A\times \{b\}\mid b\in B\}}$ exists by collection.

Putting ${\displaystyle \exists b\in B}$ in front of that last formula and one finds the set ${\displaystyle \{A\times \{b\}\mid b\in B\}}$ itself exists by separation.

Finally, the desired

${\displaystyle A\times B:=\bigcup \{A\times \{b\}\mid b\in B\}}$

exists by union. Q.E.D.