Everipedia Logo
Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.
Kripke–Platek set theory

Kripke–Platek set theory

The Kripke–Platek axioms of set theory (KP), pronounced /ˈkrɪpki ˈplɑːtɛk/, are a system of axiomatic set theory developed by Saul Kripke and Richard Platek.

KP is considerably weaker than Zermelo–Fraenkel set theory (ZFC), and can be thought of as roughly the predicative part of ZFC. The consistency strength of KP with an axiom of infinity is given by the Bachmann–Howard ordinal. Unlike ZFC, KP does not include the power set axiom, and KP includes only limited forms of the axiom of separation and axiom of replacement from ZFC. These restrictions on the axioms of KP lead to close connections between KP, generalized recursion theory, and the theory of admissible ordinals.

The axioms of KP

  • 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 {}. (Note: 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 Σ0-separation, and is thus redundant.)

  • 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 Σ0-separation: Given any set and any Σ0-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 Σ0-collection: Given any Σ0-formula φ(x, y), if for every set x there exists a set y such that φ(x, y) holds, then for all sets u there exists a set v such that for every x in u there is a y in v such that φ(x, y) holds.

Here, a Σ0, or Π0, or Δ0formula is one all of whose quantifiers arebounded. This means any quantification is the formor(More generally, we would say that a formula is Σn+1when it is obtained by adding existential quantifiers in front of a Πnformula, and that it is Πn+1when it is obtained by adding universal quantifiers in front of a Σnformula: this is related to thearithmetical hierarchybut in the context of set theory.)
  • Some but not all authors include an axiom of infinity (in which case the empty set axiom is unnecessary).

These axioms are weaker than ZFC as they exclude the axioms of powerset, 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 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)).

Proof that 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 set {a} (which is the same as {a, a} by the axiom of extensionality) and the set {a, b} both exist by the axiom of pairing. Thus

exists by the axiom of pairing as well.

A possible Δ0 formula expressing that p stands for (a, b) is:

Thus a superset of A×{b} = {(a, b) | a in A} exists by the axiom of collection.

Denote the formula for p above by. Then the following formula is also Δ0

Thus A×{b} itself exists by the axiom of separation.

If v is intended to stand for A×{b}, then a Δ0 formula expressing that is:

Thus a superset of {A×{b} | b in B} exists by the axiom of collection.

Puttingin front of that last formula and we get from the axiom of separation that the set {A×{b} | b in B} itself exists.
Finally, A×B ={A×{b} | b in B} exists by the axiom of union.

QED

Admissible sets

A setis calledadmissibleif it istransitiveandis amodelof Kripke–Platek set theory.

An ordinal number α is called an admissible ordinal if Lα is an admissible 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 Σ1(Lα) mapping from γ onto α. If M is a standard model of KP, then the set of ordinals in M is an admissible ordinal.

If Lα is a standard model of KP set theory without the axiom of Σ0-collection, then it is said to be an "amenable set".

See also

  • Constructible universe

  • Admissible ordinal

  • Kripke–Platek set theory with urelements

References

[1]
Citation Linkopenlibrary.orgPoizat, 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.”
Sep 24, 2019, 6:58 PM
[2]
Citation Link//doi.org/10.2307%2F227318510.2307/2273185
Sep 24, 2019, 6:58 PM
[3]
Citation Link//www.jstor.org/stable/22731852273185
Sep 24, 2019, 6:58 PM
[4]
Citation Link//doi.org/10.2307%2F227164610.2307/2271646
Sep 24, 2019, 6:58 PM
[5]
Citation Link//www.jstor.org/stable/22716462271646
Sep 24, 2019, 6:58 PM
[6]
Citation Link//www.ams.org/mathscinet-getitem?mr=26154532615453
Sep 24, 2019, 6:58 PM
[7]
Citation Linkdoi.org10.2307/2273185
Sep 24, 2019, 6:58 PM
[8]
Citation Linkwww.jstor.org2273185
Sep 24, 2019, 6:58 PM
[9]
Citation Linkdoi.org10.2307/2271646
Sep 24, 2019, 6:58 PM
[10]
Citation Linkwww.jstor.org2271646
Sep 24, 2019, 6:58 PM
[11]
Citation Linkwww.ams.org2615453
Sep 24, 2019, 6:58 PM
[12]
Citation Linken.wikipedia.orgThe original version of this page is from Wikipedia, you can edit the page right here on Everipedia.Text is available under the Creative Commons Attribution-ShareAlike License.Additional terms may apply.See everipedia.org/everipedia-termsfor further details.Images/media credited individually (click the icon for details).
Sep 24, 2019, 6:58 PM