Talk:Kripke–Platek set theory

Latest comment: 8 years ago by 84.15.185.70 in topic Motivation?

Motivation?

edit

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)Reply

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)Reply
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)Reply

Constructible models of KP?

edit

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)Reply

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   might be the smallest transitive model of KP which satisfies the axiom of infinity. — Emil J. 17:25, 22 June 2009 (UTC)Reply
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)Reply

Consistency

edit

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)Reply

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   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)Reply
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  ). 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   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 Σ0-collection. So, putting things together, Vκ=H(κ) is a model of KP. Conversely, if Vκ satisfies Σ1-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)Reply
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)Reply
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 Σ0-collection.
  is a countable ordinal, so there is a bijection between ω and and it. This bijection induces a well-ordering of ω of order type  . That well-ordering has rank ω, so it is an element of   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   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   because it has rank   This contradiction shows that   is not a model of KP, in particular it does not satisfy collection. JRSpriggs (talk) 02:11, 17 July 2012 (UTC)Reply
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)Reply


Axioms

edit

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)Reply

Yes. I think that what is intended is:
Suppose that the free variables of φ are among w1, ..., wn, 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   or   for some variable s.
Then the axiom schema is:
 
JRSpriggs (talk) 20:46, 4 November 2014 (UTC)Reply