Kripke–Platek set theory

The Kripke–Platek set theory (KP), pronounced /ˈkrɪpki ˈplɑːtɛk/, is an axiomatic set theory developed by Saul Kripke and Richard Platek. The theory can be thought of as roughly the predicative part of ZFC and is considerably weaker than it.

Axioms

In its formulation, a Δ₀ formula is one all of whose quantifiers are bounded. This means any quantification is the form $\forall u\in v$ or $\exists u\in v.$ (See the Lévy hierarchy.)

Axiom of extensionality: Two sets are the same if and only if they have the same elements.
Axiom of induction: φ(a) being a formula, if for all sets x the assumption that φ(y) holds for all elements y of x entails that φ(x) holds, then φ(x) holds for all sets x.
Axiom of empty set: There exists a set with no members, called the empty set and denoted {}.
Axiom of pairing: If x, y are sets, then so is {x, y}, a set containing x and y as its only elements.
Axiom of union: For any set x, there is a set y such that the elements of y are precisely the elements of the elements of x.
Axiom of Δ₀-separation: Given any set and any Δ₀ formula φ(x), there is a subset of the original set containing precisely those elements x for which φ(x) holds. (This is an axiom schema.)
Axiom of Δ₀-collection: Given any Δ₀ formula φ(x, y), if for every set x there exists a set y such that φ(x, y) holds, then for all sets X there exists a set Y such that for every x in X there is a y in Y such that φ(x, y) holds.

Some but not all authors include an

Axiom of infinity

KP with infinity is denoted by KPω. These axioms lead to close connections between KP, generalized recursion theory, and the theory of admissible ordinals. KP can be studied as a constructive set theory by dropping the law of excluded middle, without changing any axioms.

Empty set

If any set $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 $\{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.

Comparison with Zermelo-Fraenkel set theory

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).

Related definitions

A set $A\,$ is called admissible if it is transitive and $\langle A,\in \rangle$ is a model of Kripke–Platek set theory.
An ordinal number $\alpha$ is called an admissible ordinal if $L_{\alpha }$ is an admissible set.
$L_{\alpha }$ is called an amenable set if it is a standard model of KP set theory without the axiom of Δ₀-collection.

Theorems

Admissible sets

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.

Cartesian products exist

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

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

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

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

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

\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 $b$ and collecting with respect to $A$ , some superset of $A\times \{b\}=\{(a,b)\mid a\in A\}$ exists by collection.

The Δ₀-formula

\exists a\in A\,\psi (a,b,p)

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

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

\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 $A$ and collecting with respect to $B$ , some superset of $\{A\times \{b\}\mid b\in B\}$ exists by collection.

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

Finally, the desired

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

exists by union. Q.E.D.

Metalogic

The proof-theoretic ordinal of KPω is the Bachmann–Howard ordinal. KP fails to prove some common theorems in set theory, such as the Mostowski collapse lemma. ^[2]

References

^ Poizat, Bruno (2000). A course in model theory: an introduction to contemporary mathematical logic. Springer. ISBN 0-387-98655-3., note at end of §2.3 on page 27: "Those who do not allow relations on an empty universe consider (∃x)x=x and its consequences as theses; we, however, do not share this abhorrence, with so little logical ground, of a vacuum."
^ P. Odifreddi, Classical Recursion Theory (1989) p.421. North-Holland, 0-444-87295-7

Bibliography

Devlin, Keith J. (1984). Constructibility. Berlin: Springer-Verlag. ISBN 0-387-13258-9.
Gostanian, Richard (1980). "Constructible Models of Subsystems of ZF". Journal of Symbolic Logic. 45 (2). Association for Symbolic Logic: 237. doi:10.2307/2273185. JSTOR 2273185.
Kripke, S. (1964), "Transfinite recursion on admissible ordinals", Journal of Symbolic Logic, 29: 161–162, doi:10.2307/2271646, JSTOR 2271646
Platek, Richard Alan (1966), Foundations of recursion theory, Thesis (Ph.D.)–Stanford University, MR 2615453

[1] Poizat, Bruno (2000). A course in model theory: an introduction to contemporary mathematical logic. Springer. ISBN 0-387-98655-3., note at end of §2.3 on page 27: "Those who do not allow relations on an empty universe consider (∃x)x=x and its consequences as theses; we, however, do not share this abhorrence, with so little logical ground, of a vacuum."

[2] P. Odifreddi, Classical Recursion Theory (1989) p.421. North-Holland, 0-444-87295-7

[1]

[2]

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy projective Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo