Kripke–Platek set theory
The Kripke–Platek set theory, pronounced, is an axiomatic set theory developed by Saul Kripke and Richard Platek.
The theory can be thought of as roughly the predicative part of Zermelo–Fraenkel set theory and is considerably weaker than it.
Axioms
In its formulation, a Δ0 formula is one all of whose quantifiers are bounded. This means any quantification is the form or- Axiom of extensionality: Two sets are the same if and only if they have the same elements.
- Axiom of induction: φ being a formula, if for all sets x the assumption that φ holds for all elements y of x entails that φ holds, then φ holds for all sets x.
- Axiom of empty set: There exists a set with no members, called the empty set and denoted or ∅ or 0.
- Axiom of pairing: If x, y are sets, then so is, 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 φ, there is a subset of the original set containing precisely those elements x for which φ holds.
- Axiom of Δ0-collection: Given any Δ0 formula φ, if for every set x there exists a set y such that φ 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 φ holds.
Some but not all authors include an
This axiom is a Σ1 formula. It defines ω.
KP with infinity is denoted by KPω. These axioms lead to close connections between KP, computability 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 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. Furthermore, the existence of a member in the universe of discourse, i.e., ∃x, is implied in certain formulations of first-order logic, in which case the axiom of empty set follows from the axiom of Δ0-separation, and is thus redundant.Comparison with Zermelo–Fraenkel set theory
As noted, the above axioms are together 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.
Opposite of infinity
One could add an axiom of finiteness denying the existence of infinite sets. This would amount to saying that the universe is Vω. This could be done by saying that every set has an injection to a natural number. In formal language:A key point here is to identify natural numbers without referring to ω, which is one of the infinite sets that we are trying to deny. A natural number is a set that is either empty or a successor, and thus not a limit, and all of whose elements are also natural numbers. The elements of f are ordered pairs. See also the axiom of limitation of size. This axiom is Π2. It implies the axiom of choice.
Related definitions
- A set is called admissible if it is transitive and is a model of Kripke–Platek set theory.
- An ordinal number ' is called an admissible ordinal if is an admissible set.
- is called an amenable set''' if it is a standard model of KP set theory without the axiom of Δ0-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 Σ1 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 that consists of all ordered pairs of elements a'' of A and b of B.
Proof:
The singleton set with member a, written, is the same as the unordered pair, by the axiom of extensionality.
The singleton, the set, and then also the ordered pair
all exist by pairing.
A possible Δ0-formula expressing that p stands for the pair is given by the lengthy
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 and collecting with respect to, some superset of exists by collection.
The Δ0-formula
grants that just itself exists by separation.
If ought to stand for this collection of pairs, then a Δ0-formula characterizing it is
Given and collecting with respect to, some superset of exists by collection.
Putting in front of that last formula and one finds the set itself exists by separation.
Finally, the desired
exists by union.
Q.E.D.
Transitive containment
Transitive containment is the principle that every set is contained in some transitive set. It does not hold in certain set theories, such as Zermelo set theory.Theorem:
If A is a set, then there exists a transitive set B such that A is a member of B.
Proof:
We proceed by induction on the formula:
Note that is another way of expressing that B is transitive.
The inductive hypothesis then informs us that
If, then we set which is transitive.
By Δ0-collection, we have:
By Δ0-separation, the set exists, whose union we call D.
Now D is a union of transitive sets, and therefore itself transitive. And since, we know is also transitive, and further contains A, as required. Q.E.D.
Even natural numbers
In KPω, we can prove the existence of a set of all even natural numbers. An even number is either zero or the successor of the successor of an even number. The set of even numbers up to some finite stage can be built up using null set, pairing, and union.From the axiom of infinity, we get the existence of ω and its element 2 =. We apply the axiom of foundation to get a function that gives for k ≤ n for each n in ω. Then we use Δ0-collection to send ⟨ n, 0 ⟩ to n and everything else to 0. We use Δ0-separation and the mod 2 function to remove any extraneous elements. This leaves us with the set of even natural numbers.
Consider any set x. Suppose φ holds for all elements y in x. If x is not in ω, let f be =, which exists by the axioms of null set and pairing. Likewise if x = 0. If x is a nonzero natural number, then it is the successor of some natural number m that is an element of x. So φ holds and we can take g to be the function whose existence is ensured by that. Then there is some u in 2 such that ⟨ m, u ⟩ is in g. Let v be the element of 2 different from u. Let f = g ∪. Then f will be a function that satisfies φ. Thus by the axiom of induction, we know that φ holds for all sets x. Initial segments of the modulo 2 function are identified by: