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.

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 Σ₀-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 Σ₀-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 unique 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 Σ₀, or Π₀, or Δ₀ 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.$ (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.)

Some but not all authors include an axiom of infinity (in which case the empty set axiom is unnecessary as it can be proven to exist using Separation).

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 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). Not adopting Regularity or the Axiom of Choice, KP can be studied as a constructive set theory by dropping the law of excluded middle, without changing any axioms.

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

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

exists by the axiom of pairing as well.

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

\exists r\in p\,(a\in r\,\land \,\forall x\in r\,(x=a))\,\land \,\exists s\in p\,(a\in s\,\land \,b\in s\,\land \,\forall x\in s\,(x=a\,\lor \,x=b))\,\land \,

\forall t\in p\,((a\in t\,\land \,\forall x\in t\,(x=a))\,\lor \,(a\in t\land b\in t\land \forall x\in t\,(x=a\,\lor \,x=b))).

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

Denote the formula for p above by $\psi (a,b,p)$ . Then the following formula is also Δ₀

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

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

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

\forall a\in A\,\exists p\in v\,\psi (a,b,p)\,\land \,\forall p\in v\,\exists a\in A\,\psi (a,b,p)\,.

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

Putting $\exists 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 Σ₁(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 Σ₀-collection, then it is said to be an "amenable set".

gollark: Can you control the laser from the phone somehow?

gollark: ... with a laser?

gollark: Er, what would you want a laser for when camping?

gollark: Someone said that it was because the MEMS microphones have amplifier chips in them, which have big transistors (which apparently makes them more photosensitive) to handle the analog signal better.

gollark: Red/green/blue.

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

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. Association for Symbolic Logic. 45 (2): 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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.”

Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement De Morgan's laws Disjoint union Intersection Power set Set difference Symmetric difference Union
Concepts Methods	Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Transfinite induction Venn diagram
Set types	Countable Empty Finite (hereditarily) Fuzzy Infinite (Dedekind-infinite) Recursive 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	Abraham Fraenkel Bertrand Russell Ernst Zermelo Georg Cantor John von Neumann Kurt Gödel Paul Bernays Paul Cohen Richard Dedekind Thomas Jech Thoralf Skolem Willard Quine

Mathematical logic
General	Formal language Formation rule Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Rule of inference Relation Theorem Logical consequence Type theory Symbol Syntax Theory
Systems	Formal system Deductive system Axiomatic system Hilbert style systems Natural deduction Sequent calculus
Traditional logic	Proposition Inference Argument Validity Syllogism Square of opposition Venn diagram
Propositional calculus and Boolean logic	Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables Many-valued logic
Predicate logic	First-order Quantifiers Predicate Second-order Monadic predicate calculus
Naive set theory	Set Empty set Element Enumeration Extensionality Finite set Infinite set Subset Power set Countable set Uncountable set Recursive set Domain Codomain Image Map Function Relation Ordered pair
Set theory	Foundations of mathematics Zermelo–Fraenkel set theory Axiom of choice General set theory Kripke–Platek set theory Von Neumann–Bernays–Gödel set theory Morse–Kelley set theory Tarski–Grothendieck set theory
Model theory	Model Interpretation Non-standard model Finite model theory Truth value Validity
Proof theory	Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax
Computability theory	Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function