Talk:Kripke–Platek set theory

Motivation?

Besides describing what KP is, it would also be nice to know why it is important by way of some motivation. - 72.58.19.66 20:24, 29 May 2006 (UTC)

Whether it is important or not and why is somewhat subjective. These axioms are the subset of the axioms of ZFC which results from removing those axioms which are problematical because they are nonconstructive. And KP has a connection to admissible sets which are connected to recursion theory. Sorry, but I do not know enough about KP to explain the motivation better than that. JRSpriggs 04:05, 30 May 2006 (UTC)

Well, but that is a fine start: "...removing those axioms which are problematical because they are nonconstructive". 84.15.185.70 (talk) 20:03, 12 June 2016 (UTC)

Constructible models of KP?

Some quick questions for the cognoscenti:

(1) Does ZF prove that a transitive set is a model of KP if and only if it is closed under "Gödel operations" (Jech Defn 13.6)?

(2) Is it true (again, under ZF) that the second smallest model of KP is L_{omega_1^CK}, where omega_1^CK is the Church-Kleene ordinal?

If these hunches are indeed standard facts about KP, I think it would make sense to put them in the article. —Preceding unsigned comment added by 92.24.100.22 (talk) 17:08, 22 June 2009 (UTC)

See the section "Admissible sets" in the article, and the links contained in that section. (1) is not true, since there is no reason why such a set would satisfy bounded collection. As for (2), the smallest model of KP is L_ω = V_ω. I gather that $L_{\omega _{1}^{CK}}$ might be the smallest transitive model of KP which satisfies the axiom of infinity. — Emil J. 17:25, 22 June 2009 (UTC)

Ah, of course - with Gödel operations alone one couldn't even reach ω+ω. Thanks Emil. —Preceding unsigned comment added by 92.24.100.22 (talk) 17:58, 22 June 2009 (UTC)

Consistency

As far as I know Church-Kleene ordinal's existence is theorem of ZFC, so L_CK (with CK being earlier mentioned ordinal) also exists. Does that imply consistence of KP? And is that provable in ZFC? On the other hand, what is second (after V_omega) smallest transitive model of KP being some step in VonNeumann universe construction? — Preceding unsigned comment added by 31.61.217.245 (talk) 18:15, 12 July 2012 (UTC)

In ZF, one can prove that V_ω is a model of Kripke–Platek set theory and thus that Kripke–Platek set theory is consistent.

In ZF, one can prove that $L_{\omega _{1}^{\mathrm {CK} }}\,$ is a model of Kripke–Platek set theory plus the axiom of infinity and thus that Kripke–Platek set theory plus the axiom of infinity is consistent.

Much more powerful results can be obtained. See reflection principle. JRSpriggs (talk) 03:58, 13 July 2012 (UTC)

To answer the other question (what is the second smallest α such that V_α is a model of KP), I believe it is the smallest fixed point of the beth function (i.e., the limit of $\aleph _{0},\beth _{\omega },\beth _{\beth _{\omega }},\ldots$). The key idea is that if κ is the ordinal in question (which is a singular cardinal), then V_κ also coincides with the set H(κ) of sets of hereditarily of cardinality less than κ. As at any limit ordinal, V_κ satisfies ZC (i.e., ZFC without replacement); but the Lévy absoluteness lemma (see, e.g., Barwise, Admissible sets and structures (1975), theorem 9.1 on p.76, except that it is stated there only for $\aleph _{1}$ whereas it is valid for any uncountable cardinal, but I don't have any better reference) shows that H(κ) is a 1-elementary submodel of the Universe, hence satisfies Σ₀-collection. So, putting things together, V_κ=H(κ) is a model of KP. Conversely, if V_κ satisfies Σ₁-replacement, it constructs the beth function, so κ must be a fixed point of that. (This is all very sketchy, I can elaborate if absolutely necessary.) --Gro-Tsen (talk) 23:07, 13 July 2012 (UTC)

I thought V_CK is also model of KP, because first five axioms (maybe expect induction) are true in it, and separation is true because for any ordinal a Def(V_a) is contained in V_a+1. I'm not sure about collection and induction axioms. Where can I found proof or sketch that CK is smallest admissible ordinal? — Preceding unsigned comment added by 31.61.225.33 (talk) 19:08, 16 July 2012 (UTC)

If A is any transitive set, then A with the restriction of the true element relation to A satisfies the axiom of induction. Because, let B be the set of elements x of A such that A satisfies φ(y) (i.e. with quantifiers restricted to A) for every y in the transitive closure of {x} (which is a subset of A). If B=A, then we are done. Otherwise, use the axiom of regularity (in V) to get an element z of A-B which is disjoint from A-B, that is, z is a subset of B but not an element of B. Since z is a subset of B, for every element y of z A satisfies φ(y). So by the hypothesis of the axiom of induction in A, A must satisfy φ(z). But then everything in the transitive closure of z is satisfied and thus z is an element of B. This contradicts the choice of z, so B=A and the axiom of induction holds in A.

So if λ is a limit ordinal, then V_λ satisfies all the axioms of KP except possibly Σ₀-collection.

$\omega _{1}^{\mathrm {CK} }\,$ is a countable ordinal, so there is a bijection between ω and and it. This bijection induces a well-ordering of ω of order type $\omega _{1}^{\mathrm {CK} }\,$. That well-ordering has rank ω, so it is an element of $V_{\omega _{1}^{\mathrm {CK} }}\,.$ For any n in ω, we can call the restriction of the bijection to the set of k which are less than n in the well-order a good function f. The relationship between n and the good function f (using the well-ordering as a parameter) can be defined by a formula which only uses bound quantifiers. Thus by the axiom of collection, there must be a superset of the set of good functions within $V_{\omega _{1}^{\mathrm {CK} }}\,,$ if it is a model of KP. If we apply the axiom of separation to get just the good functions and form their union, we recover the original bijection. But that bijection cannot be an element of $V_{\omega _{1}^{\mathrm {CK} }}\,$ because it has rank $\omega _{1}^{\mathrm {CK} }\,.$ This contradiction shows that $V_{\omega _{1}^{\mathrm {CK} }}\,,$ is not a model of KP, in particular it does not satisfy collection. JRSpriggs (talk) 02:11, 17 July 2012 (UTC)

Actually this argument works for any countable limit ordinal. And it can be generalized to show that for any limit ordinal λ which is not the initial ordinal of a cardinal, V_λ is not a model of KP. JRSpriggs (talk) 16:33, 18 July 2012 (UTC)

Axioms

In the axiom of collection for KP, can the formula phi use parameters from the model? As far as I can see, the proof of the existence of Cartesian products uses parameters (like A and b). Farmerss (talk) 18:18, 4 November 2014 (UTC)

Yes. I think that what is intended is:

Suppose that the free variables of φ are among w₁, ..., w_n, x, y; but neither u nor v is free in φ. And all bound variables in φ are bounded, for example, if z were a bound variable in φ, then it is quantified by either $\forall z\in s$ or $\exists z\in s$ for some variable s.

Then the axiom schema is:

$\forall w_{1},\ldots ,w_{n}\,[(\forall x\,\exists \,y\,\phi (x,y,w_{1},\ldots ,w_{n}))\Rightarrow \forall u\,\exists v\,\forall x\in u\,\exists y\in v\,\phi (x,y,w_{1},\ldots ,w_{n})]$

JRSpriggs (talk) 20:46, 4 November 2014 (UTC)