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 based on the ideas of Saul Kripke (1964) and Richard Platek (1966).

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

Here, a Σ0, or Π0, or Δ0 formula is one all of whose quantifiers are bounded. This means any quantification is 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.)

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:

{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, \psi (a, b, p)\!, 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.

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 from the axiom of separation that the set {A×{b} | b in B} itself exists.

Finally, A×B = \cup{A×{b} | b in B} exists by the axiom of union.

QED

Admissible sets

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

References

  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.

Bibliography

This article is issued from Wikipedia - version of the Tuesday, April 12, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.