Kripke–Platek set theory


Kripke–Platek set theory

The Kripke–Platek axioms of set theory (KP) (IPAEng|ˈkrɪpki ˈplɑːtɛk) are a system of axioms of axiomatic set theory, developed by Saul Kripke and Richard Platek. The axiom system is written in first-order logic; it has an infinite number of axioms because an axiom schema is used.

The axioms of KP

* Axiom of extensionality: Two sets are the same if and only if they have the same elements.
* Axiom of induction: If φ("a") is a proposition, and if for all sets "x" it follows from the fact that φ("y") is true for all elements "y" of "x" 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 Σ0-separation: Given any set and any Σ0-proposition φ("x"), there is a subset of the original set containing precisely those elements "x" for which φ("x") holds. (This is an axiom schema.) Here, a Σ0, or Π0, or Δ0 proposition is one whose quantifiers are all bound, that is, are of the form forall u in v or exist u in v. (More generally, we would say that a formula is Σ"n"+1 when it is obtained by adding existential quantifiers in front of a Π"n" formula, and that it is Π"n"+1 when it is obtained by adding universal quantifiers in front of a Σ"n" formula: this is related to the arithmetical hierarchy but in the context of set theory.)
* Axiom of Σ0-collection: Given any Σ0-proposition φ("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. (See Axiom of collection.)

If one knew that some set existed, then the axiom of separation would give us the empty set.

These axioms differ from ZFC in as much as they exclude the axioms of: infinity, powerset, and choice. Also the axioms of separation and collection here are weaker than the corresponding axioms in ZFC because the predicates φ used in these are limited to bound quantifiers only.

The axiom of induction here 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".

{a} = {a, a} exists by the axiom of pairing. {a, b} exists by the axiom of pairing. Thus (a, b) = { {a}, {a, b} } exists by the axiom of pairing.

If p is intended to stand for (a, b), then a Δ0 formula expressing that is:exist r in p (a in r and forall x in r (x = a)) and exist s in p (a in s and b in s and forall x in s (x = a or x = b)) and forall t in p ((a in t and forall x in t (x = a)) or (a in t and b in t and forall x in t (x = a or x = b))).

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

Abbreviate the formula above by psi (a, b, p)!. Then exist a in A psi (a, b, p) is Δ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:forall a in A exist p in v psi (a, b, p) and forall p in v exist a in A psi (a, b, p).

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

Putting exist b in B in front of that last formula and we get that the set {A×{b} | b in B} itself exists by the axiom of separation.

Finally, A×B = cup{A×{b} | b in B} exists by the axiom of union. This is what was to be proved.

Admissible sets

If Lα is a standard model of KP set theory, then it is said to be an "admissible set" and α is called an "admissible ordinal". 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

* Axiomatic set theory
* Constructible universe
* Admissible ordinal
* Kripke–Platek set theory with urelements

References

*citation|last= Gostanian|first= Richard|year= 1980|title=Constructible Models of Subsystems of ZF|journal=Journal of Symbolic Logic|volume= 45|issue=2
url=http://links.jstor.org/sici?sici=0022-4812%28198006%2945%3A2%3C237%3ACMOSOZ%3E2.0.CO%3B2-Y


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Kripke–Platek set theory with urelements — The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements that is considerably weaker than the familiar system ZF. PreliminariesThe usual way of stating the axioms presumes a two sorted first order… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • List of set theory topics — Logic portal Set theory portal …   Wikipedia

  • Descriptive set theory — In mathematical logic, descriptive set theory is the study of certain classes of well behaved subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to other… …   Wikipedia

  • Hyperarithmetical theory — In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an… …   Wikipedia

  • Axiom of empty set — In set theory, the axiom of empty set is one of the axioms of Zermelo–Fraenkel set theory and one of the axioms of Kripke–Platek set theory. Formal statement In the formal language of the Zermelo–Fraenkel axioms, the axiom reads::exist x, forall… …   Wikipedia

  • Axiom of power set — In mathematics, the axiom of power set is one of the Zermelo Fraenkel axioms of axiomatic set theory.In the formal language of the Zermelo Fraenkel axioms, the axiom reads::forall A , exists P , forall B , [B in P iff forall C , (C in B… …   Wikipedia

  • Hereditarily countable set — In set theory, a set is called hereditarily countable if and only if it is a countable set of hereditarily countable sets. This inductive definition is in fact well founded and can be expressed in the language of first order set theory. A set is… …   Wikipedia

  • Alpha recursion theory — In recursion theory, the mathematical theory of computability, alpha recursion (often written α recursion) is a generalisation of recursion theory to subsets of admissible ordinals alpha. An admissible ordinal is closed under Sigma 1(L alpha)… …   Wikipedia

  • Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia