Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Kripke–Platek set theory
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|System of mathematical set theory}} The '''Kripke–Platek set theory''' ('''KP'''), pronounced {{IPAc-en|ˈ|k|r|ɪ|p|k|i|_|ˈ|p|l|ɑː|t|ɛ|k}}, is an [[axiomatic set theory]] developed by [[Saul Kripke]] and Richard Platek. The theory can be thought of as roughly the [[impredicativity|predicative]] part of [[Zermelo–Fraenkel set theory]] (ZFC) and is considerably weaker than it. == Axioms == In its formulation, a Δ<sub>0</sub> formula is one all of whose quantifiers are [[bounded quantifier|bounded]]. This means any quantification is the form <math>\forall u \in v</math> or <math>\exist u \in v.</math> (See the [[Lévy hierarchy]].) * [[Axiom of extensionality]]: Two sets are the same if and only if they have the same elements. * [[Epsilon-induction|Axiom of induction]]: φ(''a'') being a [[well-formed formula#Predicate logic|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 {}. * [[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 schema of predicative separation|Axiom of Δ<sub>0</sub>-separation]]: Given any set and any Δ<sub>0</sub> 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|Axiom of Δ<sub>0</sub>-collection]]: Given any Δ<sub>0</sub> formula φ(''x'', ''y''), if for every set ''x'' there exists a set ''y'' such that φ(''x'', ''y'') 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 φ(''x'', ''y'') holds. Some but not all authors include an * [[Axiom of infinity]] KP with infinity is denoted by KPω. These axioms lead to close connections between KP, [[Mathematical logic#Recursion theory|generalized recursion theory]], and the theory of [[admissible ordinal]]s. 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 <math>c</math> 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 <math>\{x\in c\mid x\neq x\}</math>. Furthermore, the existence of a member in the universe of discourse, i.e., ∃x(x=x), is implied in certain formulations<ref>{{cite book |title=A course in model theory: an introduction to contemporary mathematical logic |url=https://archive.org/details/courseinmodelthe0000poiz |url-access=registration |last=Poizat |first=Bruno |year=2000 |publisher=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."</ref> of [[first-order logic]], in which case the axiom of empty set follows from the axiom of Δ<sub>0</sub>-separation, and is thus redundant. === Comparison with Zermelo-Fraenkel set theory === As noted, the above are 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 (the class of all sets not in the given set). == Related definitions == * A set <math> A\, </math> is called '''[[admissible set|admissible]]''' if it is [[transitive set|transitive]] and <math>\langle A,\in \rangle</math> is a [[model theory|model]] of Kripke–Platek set theory. * An [[ordinal number]] ''<math>\alpha</math>'' is called an '''[[admissible ordinal]]''' if <math>L_\alpha</math> is an admissible set. * <math>L_\alpha</math> is called an '''amenable set''' if it is a standard model of KP set theory without the axiom of Δ<sub>0</sub>-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 Σ<sub>1</sub>(L<sub>''α''</sub>) 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'' which consists of all [[ordered pair]]s (''a'', ''b'') of elements ''a'' of ''A'' and ''b'' of ''B''. '''Proof:''' The singleton set with member ''a'', written {''a''}, is the same as the unordered pair {''a'', ''a''}, by the axiom of '''[[extensionality]]'''. The singleton, the set {''a'', ''b''}, and then also the ordered pair :<math>(a,b) := \{ \{a\}, \{a,b\} \} </math> all exist by '''pairing'''. A possible Δ<sub>0</sub>-formula <math>\psi (a, b, p)</math> expressing that ''p'' stands for the pair (''a'', ''b'') is given by the lengthy :<math>\exist r \in p\, \big(a \in r\, \land\, \forall x \in r\, (x = a) \big)</math> ::<math>\land\, \exist s \in p\, \big(a \in s \,\land\, b \in s\, \land\, \forall x \in s\, (x = a \,\lor\, x = b) \big)</math> :::<math>\land\, \forall t \in p\, \Big(\big(a \in t\, \land\, \forall x \in t\, (x = a)\big)\, \lor\, \big(a \in t \land b \in t \land \forall x \in t\, (x = a \,\lor\, x = b)\big)\Big).</math> 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 <math>b</math> and collecting with respect to <math>A</math>, some superset of <math>A\times\{b\} = \{(a,b)\mid a\in A\}</math> exists by '''collection'''. The Δ<sub>0</sub>-formula :<math>\exist a \in A \,\psi (a, b, p)</math> grants that just <math>A\times\{b\}</math> itself exists by '''separation'''. If <math>P</math> ought to stand for this collection of pairs <math>A\times\{b\}</math>, then a Δ<sub>0</sub>-formula characterizing it is :<math>\forall a \in A\, \exist p \in P\, \psi (a, b, p)\, \land\, \forall p \in P\, \exist a \in A\, \psi (a, b, p) \,.</math> Given <math>A</math> and collecting with respect to <math>B</math>, some superset of <math>\{A\times \{b\} \mid b\in B\}</math> exists by '''collection'''. Putting <math>\exist b \in B</math> in front of that last formula and one finds the set <math>\{A\times \{b\} \mid b\in B\}</math> itself exists by '''separation'''. Finally, the desired :<math>A\times B := \bigcup \{A\times \{b\} \mid b\in B\}</math> 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]] (though its inclusion as an axiom does not add consistency strength<ref>{{cite journal | last=Mathias | first=A.R.D. | title=The strength of Mac Lane set theory | journal=Annals of Pure and Applied Logic | volume=110 | issue=1-3 | date=2001 | doi=10.1016/S0168-0072(00)00031-2 | doi-access=free | pages=107–234}}</ref>). '''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: :<math>\phi(A) := \exist B (A \in B \land \bigcup B \subseteq B)</math> Note that <math>\bigcup B \subseteq B</math> is another way of expressing that ''B'' is transitive. The inductive hypothesis then informs us that :<math>\forall a \in A \, \exist b(a \in b \land \bigcup b \subseteq b)</math>. By '''Δ<sub>0</sub>-collection''', we have: :<math>\exist C \, \forall a \in A \, \exist b \in C (a \in b \land \bigcup b \subseteq b)</math> By '''Δ<sub>0</sub>-separation''', the set <math>\{c \in C \mid \bigcup c \subseteq c\}</math> exists, whose '''union''' we call ''D''. Now ''D'' is a union of transitive sets, and therefore itself transitive. And since <math>A \subseteq D</math>, we know <math>D \cup \{A\}</math> is also transitive, and further contains ''A'', as required. Q.E.D. == Metalogic == The [[ordinal analysis|proof-theoretic ordinal]] of KPω is the [[Bachmann–Howard ordinal]]. KP fails to prove some common theorems in set theory, such as the [[Mostowski collapse lemma]]. <ref>P. Odifreddi, ''Classical Recursion Theory'' (1989) p.421. North-Holland, 0-444-87295-7</ref> == See also == * [[Constructible universe]] * [[Admissible ordinal]] * [[Hereditarily countable set]] * [[Kripke–Platek set theory with urelements]] == References == <references /> ==Bibliography== *{{cite book| last = Devlin | first = Keith J. | title = Constructibility |year = 1984 | location = Berlin | publisher = [[Springer-Verlag]] | isbn = 0-387-13258-9}} *{{Cite journal|last= Gostanian|first= Richard|year= 1980|title=Constructible Models of Subsystems of ZF|journal=[[Journal of Symbolic Logic]]|volume= 45|issue=2|pages= 237|doi= 10.2307/2273185|jstor= 2273185|publisher= [[Association for Symbolic Logic]]|postscript= <!--None--> }} *{{citation|first=S. |last=Kripke|title=Transfinite recursion on admissible ordinals|year=1964|journal=Journal of Symbolic Logic|volume=29|pages=161–162|jstor=2271646|doi=10.2307/2271646}} *{{citation|mr=2615453 |last=Platek|first= Richard Alan |title=Foundations of recursion theory |series=Thesis (Ph.D.)–[[Stanford University]]|year= 1966}} {{Set theory}} {{Mathematical logic}} {{DEFAULTSORT:Kripke-Platek set theory}} [[Category:Systems of set theory]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation
(
edit
)
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:IPAc-en
(
edit
)
Template:Mathematical logic
(
edit
)
Template:Set theory
(
edit
)
Template:Short description
(
edit
)