Talk:Constructible universe

Comment by Dori

While the definition of V and V_alpha is correct, the definition of constructible universe given here is completely wrong.

The universe V is the union of all the V_alpha sets. The constructible universe L is the union of a different hierarchy L_alpha, which is obtained by iterating something weaker than powerset.

You contributions to the article would be most welcome if they help improve its accuracy. Please feel free to make any edits you deem useful. I don't know anything about the topic and the original author(s) may not take notice of your comments. thanks, Dori | Talk 21:09, Dec 17, 2003 (UTC)

I'm the original author, and since I did it from memory I'm quite willing to believe I've got it wrong. Please do fix it. Onebyone 21:36, 17 Dec 2003 (UTC)

This definition is wrong for L, but it's perfect for the Von Neumann universe V. So I just moved it there! (The intro, in contrast, really does belong here.) -- Toby Bartels 22:40, 28 Jan 2004 (UTC)

This new defintion copied from Goedel's constructible universe needs to be cleaned up, but I can't do it now. -- Toby Bartels 23:00, 28 Jan 2004 (UTC)

I removed the text

Let x represent the set of all finite non-reproducible sets. Let S(x;n) represent the set of finite non-reproducible sets taken over the field of real numbers. Then S(n;n) is not admittive of all possible universes of sets that do not include S(n;n) as a possible finite reproducible subset. Mamoun's Eternal Party Method innovation to Goedel's theorem was to point out that S(n; not n), taken over the field of real numbers leads to a non-ergodic finite state of dimensional indeterminacy that co-incides in all cases except S(n;n), interpreted as to content in terms of determinate finite states, with the resultant universe of reproducible sets. This likewise corresponds with the Monster Set but, remarkably, compactifies the set to include a self-referential mapping of the set configuration states such that the Monster Set - S(n;n) complements are mappings that are mutually onto and into; this is equivalent to a finite state indeterminacy in all forms except the union of determinate and indeterminate states, which maintains supersymmetric conservation parity of all dynamic states taken over the field of complex numbers. The immediate application to D-brane anti-deSitter spaces allows for a non-ergodic complete state manifold capable of describing any cyclically descriptive dynamic (1...n-1) when taken over the field of Monster Set classes

I looks like it does not make sense, and even if it does, it is not connected with Gödel's constructible universe. Aleph4 19:24, 23 Jun 2004 (UTC)

A standard model?

What is a standard model of set theory? I know what a transitive well founded model that contains all the ordinals is. Is there a reference (in print) for using the word standard to refer to such a model? The article would benefit from additional clarity on this point. I have also noticed this issue at the Kripke-Platek set theory article, where the phrase standard model apparently means well founded transitive model. I'm not interested in philosophy here; I'm just asking whether this use of the phrase standard model to mean well founded transitive model is common in the literature. CMummert 13:38, 24 July 2006 (UTC)

As it says in Inner models, "A model of set theory is called 'standard' or 'transitive' when the base class is a transitive class of sets and the element relation of the model is the actual element relation restricted to the base class. A model of set theory is assumed to be standard unless it is explicitly stated that it is non-standard. Inner models are usually standard because their ordinals are actual ordinals.". JRSpriggs 03:50, 26 July 2006 (UTC)

This old Usenet post by Bob Solovay mentions Kunen's and Jech's books on set theory as possible references. 75.62.6.87 (talk) 12:20, 3 April 2009 (UTC)

Usual notion of constructive?

The article includes sentences such as

The usual notion of constructive would not allow that ...

I doubt that there is a usual notion of constructive, and I think the majority usage would be that constructive means proved without using the axiom of choice (which is not the sense intended by the article). There are several incompatible definitions of constructivity in various schools of constructive mathematics. It would benefit the article if the specific sense of constructive that is meant could be defined. CMummert 13:52, 24 July 2006 (UTC)

I think that "usual" here means "in the sense of Constructivism (mathematics)". Aleph4 16:04, 24 July 2006 (UTC)

I agree. Unfortunately, constructivism in mathematics is like conservatism in politics - it means different things to different people. There is no single movement that carries the mantle of constructivism for everyone else to see. Also, the statement in the article that $L_{\omega _{1}^{\operatorname {CK} }}$ consists of “constructive sets” is strange because although you can call a proof technique constructive, it is less obvious what it means for a set to be constructive. Here's a particular example: the truth set of first order arithmetic is in $L_{\omega _{1}^{\operatorname {CK} }}$; in what sense(s) is this set constructive? CMummert 18:07, 24 July 2006 (UTC)

I changed the article to include a definition of what I meant by "constructive". To wit, set being constructive means that it has a code (set theory) which is recursive. How do you know that the truth set of arithmetic is in $L_{\omega _{1}^{\operatorname {CK} }}$? If you are correct (which I doubt), then it refutes my identification of the set of constructive sets. JRSpriggs 03:58, 26 July 2006 (UTC)

Because the truth set of first order arithmetic is at Turing degree $0^{(\omega )}$. After you have the set of natural numbers, each additional level of the L hierarchy gets you (at least) one more Turing jump, so after $\omega$ levels you have all the finite jumps. Then an instance of $\Sigma _{0}$ collection allows you to collect these into a single set from which $0^{(\omega )}$ is computable.

I think it is easier than that to see that $L_{\omega _{1}^{\mathrm {CK} }}$ does not consist exclusively of sets with recursive codes. Given a recursive code for a set of natural numbers (finite von Neumann ordinals), the question of whether n is in the coded set is decidable from $0''$. Thus if every set in $L_{\omega _{1}^{\mathrm {CK} }}$ had a recursive code then every set of natural numbers in that model would be recursive in $0''$, which is impossible this collection of sets is closed under Turing jump. CMummert 13:16, 26 July 2006 (UTC)

You are right. I rewrote the second paragraph of the section on constructive sets. Please check it over again. JRSpriggs 11:21, 13 August 2006 (UTC)

The definition of L is wrong

I know that this is a subtle point which often confuses beginners, but the definition of L given in the article makes no sense from a formal point of view. It mixes the formal theory and the metatheory in a way which is not allowed. I think it can still stay as it is, since it is "morally" correct, but a comment should be added explaining how a "formally" correct definition may be formulated. I made such a comment but it was at once removed with an explanation that I did not understand. Anyone has thoughts on this issue? -- Neithan Agarwaen 11:47, 14 July 2007 (UTC)

You are the one who does not understand. Given a set S, all of the formulas (with one free variable) which talk about elements of S and have quantifiers restricted to range over elements of S can be encoded by a single formula (using unrestricted quantifiers) which has two free variables: one whose value is a formula interpreted as ranging over S, and the other which stands for the value of the free variable used by that formula. This is discussed in the article in Constructible universe#L can be well-ordered and Constructible universe#Constructible sets are definable from the ordinals. Also see reflection principle. The language of set theory is very powerful and does not suffer from some of the limitations which you may be used to from other theories. JRSpriggs 04:41, 15 July 2007 (UTC)

Yes, what you say is correct, but this is not what the article says. The definition of Def as given in the article does not make sense. I know that other parts of the article refer to some correct definitions, but the one given in the first section is incorrect. The problem is that this encoding of formulas as sets does not correspond to actual formulas of the formal language: you cannot define a one to one correspondance between the two kinds of objects, because it makes no sense to associate a formula to each element of a set. To each formula it is possible to define a constant which denotes the set corresponding to the formula, and that is the only relation that can be asserted between formulas and "encoded formulas". As I said, this is subtle, but it becomes apparent when working syntactically in the first-order language. Formal languages were introduced to this purpose: eliminate flawed statements such as this one. You are using the word "formula" on the one hand for some objects of the real world (sequences of symbols) and on the other hand for a defined predicate in a formal theory (a single symbol with some defining axiom), but the two cannot be identified, even heuristically. The correct definition of Def uses the second object, so it makes no reference to actual first-order formulas. It would be enough just to mention that in the definition, "first-order formulas" do not refer to actual formulas, but abbreviates some predicate of the theory. The definitions of the predicate itself and of the notation {y|yεX and Φ(y,z₁,...,z_n) is true in (X,ε)} need not be given here, since they are rather complicated and not very illuminating. But they are of course required to prove anything about L. Neithan Agarwaen 08:40, 15 July 2007 (UTC)

Let me add something about the obscure "even heuristically" that I wrote. One may think that this obstacle to the identification of formulas with "set-formulas" is only a syntactical one, and that it can nevertheless be seen to be true "platonistically". This is not so for the following reason. Consider a platonistic universe U whose objects are assumed to satisfy ZF. Then as usual we call an object of the universe "finite" if it belongs to the first limit ordinal ω. This definition of "finite" is, a priori, different from the intuitive notion of finite, which is: a set is finite in the intuitive sense if it has finitely many objects of U as members. Now the fact that an ordinal x be finite (in the intuitive sense) can be expressed platonistically as an infinite disjunction: x=0 or x=S0 or ... or x=S...S0 or etc. It is easy to see that if an ordinal x is finite in the intuitive sense, then it is a member of ω. But the converse need not hold! That is, there may be an ordinal x in U which is a member of ω but has nevertheless infinitely many (in the intuitive sense) objects of U as members. Such an ordinal cannot be characterized by a formula. Then for such an ordinal there will be set-formulas (i.e. objects of U) which consist of infinitely many (in the intuitive sense) symbols. Such an object A cannot correspond to a formula of the first-order language, but it will nevertheless be true in U that A is a set-formula.

I hope this convinces you that one has to be very careful when trying to define a set using properties of real-world objects such as formulas. In the cas of L, the "naive" definition which we want L to satisfy (and which is given in the article) does not work, not even from a platonistic point of view, and certainly not in proof theory. Neithan Agarwaen 12:29, 15 July 2007 (UTC)

It seems you are mostly concerned with using the word "formula" in situations where the Godel numbers can be nonstandard? Although this is a matter of personal opinion, I do think there is a nice heuristic identification between Godel numbers (possibly nonstandard) and formulas; the nonstandard Godel numbers correspond to infinitely long "formulas", which are not actual formulas, but because they have Godel numbers it's still possible to decompose them into subformulas and prove theorems about them by induction.

If you would like to add a couple sentences about the fact that the definition of the Def predicate uses Godel numbers rather than actual formulas, I wouldn't object. I suppose your point is that when the definition of the Def predicate is formalized within set theory, it isn't possible to quantify directly over formulas because ZFC uses first-order logic, but it is possible to quantify over codes for formulas recognizable by their structural properties, some of which may not correspond to actual formulas. — Carl (CBM · talk) 13:13, 15 July 2007 (UTC)

To Neithan Agarwaen: I am not concerned about non-standard models. I am only interested in defining things in a way that works for standard models. The definition given here is based on page 26 of "Models of ZF-Set Theory" by Ulrich Felgner. The formulas I am talking about are formulas in the language of set theory, not "a defined predicate in a formal theory (a single symbol with some defining axiom)". Your statement "... you cannot define a one to one correspondence between the two kinds of objects, because it makes no sense to associate a formula to each element of a set." is nonsensical. JRSpriggs 04:01, 16 July 2007 (UTC)

You clearly do not understand. Model theory has nothing to do with this. And your source is wrong: check Kunen for a correct definition of Def, or Gödel for a direct definiton of L. You will see that the definition is quite a bit more complicated. The definition of the article is completely nonsensical. As Carl said, you cannot quantify over formulas. The "definition" of Def in the article is essentially

$y\in \operatorname {Def} (x)\leftrightarrow y\in \operatorname {P} (x)\wedge \exists \Phi (\Phi {\text{ is a first-order formula and etc.}})$.

This is not a first-order formula. Compare "the smallest integer which cannot be defined with less than 40 words". My second post was explaining that even for a platonist (as you seem to be), who sees both formulas and sets as "real objects" and for whom the definition of the article might have an intuitive meaning, it still isn't the correct meaning. I will add some comments later on as Carl suggested. Please modify them if you can make them clearer, but do not remove them altogether! Neithan Agarwaen 11:47, 16 July 2007 (UTC)

On the face of it it's not correct to say you "cannot quantify over formulas". You certainly can. It's not any harder than quantifying over the natural numbers that are their Gödel numbers.

The reference to Berry's paradox would be relevant if the thing you were asking about a formula given by a variable were, say, whether the formula were true. But the problem with formalizing the paradox, in this context, is not a problem with quantifying over variables, but rather a problem with defining "true" as a formula.

In the case of L, though, this is not a problem, because your "and etc" part of the above formula does not ask whether Φ is true of an element of x whose membership in y we wish to determine, but only whether the structure (x,∈) satisfies Φ at that element. And satisfaction, unlike truth, is first-order definable, in the ordinary Tarskian way. (To avoid irrelevant complications, it should probably be required that x be transitive.) --Trovatore 15:48, 16 July 2007 (UTC)

I think Neithan's concern is that when quantifying over natural numbers there is no way to know that you will not get some nonstandard ones, and hence some nonstandard "formulas". Of course these are standard numbers from the point of view of the model that contains them, which I believe is why this distinction is almost universally ignored in presentations of L. — Carl (CBM · talk) 16:04, 16 July 2007 (UTC)

Well, but of course there's a way of knowing you don't get any nonstandard formulas. You do the construction inside the true, standard universe of set theory, and it doesn't have any nonstandard formulas (though it knows about models that do). It's a very strange sort of context mixing to take language that's phrased in absolute terms ("there is a formula..."), and then suddenly worry about whether there's a nonstandard model in the background with respect to which we might have been interpreting the language (we hadn't mentioned any model). We don't do that with, say, arithmetic, and I can't see any motive to do it here. --Trovatore 18:32, 16 July 2007 (UTC)

In arithmetic, people do distinguish between "Φ is provable", which is not a first order formula, and "Pvbl(#Φ)", which is. I think Neithan is concerned about the same issue here ("Y is definable inside X" versus "Y ∈ Def(X)"). But I'm not completely sure. I agree that the standard text book conception of L ignores these issues, being visualized inside a fixed model of set theory. As you say, the point is that inside the standard model there is a first-order way of capturing definability inside a set X. — Carl (CBM · talk) 18:49, 16 July 2007 (UTC)

Well, I am not personally concerned with what you call nonstandard numbers at all. I am only concerned with distinguishing different levels of discussion. Either we are discussing the first-order theory, with symbols and expressions, or we "place ourselves within the theory" and "translate" expressions in English. If we choose the latter then there are no more symbols and expressions: only sets and membership. But it is completely absurd to mix the two points of view. So indeed, it is incorrect to say that we cannot quantify over formulas: what is correct is that the phrase "quantify over formulas" has no meaning as it is in the article. It makes sense of course to quantify over actual formulas, as in "for every formula A, (A or not A) is provable", and in the theory, eg. $\forall x(\operatorname {Fmla} (x)\rightarrow \dotsb )$. I only wish to precise in the article that "first-order formulas" do not refer to first-order formulas. You may think that this is nitpicking, but it truly isn't. Neithan Agarwaen 19:06, 16 July 2007 (UTC)

We're doing semantics (sets and membership), not syntax. But the semantics is powerful enough to capture the syntax. There is no inappropriate level-mixing in taking note of that fact. The first-order formulas as coded by sets are completely isomorphic to first-order formulas as conceived informally (except, I suppose, insofar as someone's informal conception might require that a formula be feasibly expressed, say within the bounds of the observable physical universe or something -- I don't think that's the point you're making). Therefore I do think the points you're suggesting making are, not merely nitpicking, but actively misleading; they suggest the existence of a problem when there just isn't one. --Trovatore 20:24, 16 July 2007 (UTC)

To Neithan Agarwaen: If your point is that the right side of "Define Def (X) = { {y|yεX and Φ(y,z₁,...,z_n) is true in (X,ε)} | Φ is a first order formula and z₁,...,z_n are elements of X}." is not a formula in the language of set theory (despite being written to look like one), then I concede that. It is written in a semi-formal human readable form. However, there is a real formula of set theory which effectively says the same thing and gives the same resulting set Def (X). [By the way we always use a transitive X here.] So what is the problem? JRSpriggs 02:43, 17 July 2007 (UTC)

The problem is that these statements: "The first-order formulas as coded by sets are completely isomorphic to first-order formulas as conceived informally" and "However, there is a real formula of set theory which effectively says the same thing and gives the same resulting set Def(X)" are incorrect (nonsensical, in fact!). It's like saying that there is a bijection between natural numbers (actual ones) and members of ω. It makes no sense, because I either live in the world of natural numbers, where ω is just a symbol, or in the world of sets, where natural numbers are members of ω. Such an "isomorphism" can be expressed neither in the metatheory nor in the formal theory.

Now, in all this discussion, I note that you have always presupposed that the formulas used in the definition were "encoded ones", so I think it wouldn't hurt to mention it in the article. You may think that there is an identification between those and actual formulas, but this cannot be justified. And it's not about being formal or not. I have read good books both highly formal and completely naive which, justly, use different words for formulas and formulas. It's also hard for me to believe that "the standard text book conception of L ignores these issues", for the only place where I have seen these issues ignored is in this article. Neithan Agarwaen 11:32, 17 July 2007 (UTC)

Here is an example. If n is a natural number, then we can associate to it the term S...S0, abbreviated n, with n occurrences of S. The definition of Def in the article is then completely analogous to defining ω by ω = {n | n is a natural number}, which involves "quantifying over natural numbers", and is as illegit as "quantifying over formulas". This is of course made valid by formalizing a notion which we think of as meaning "being a natural number" (resp. "being a formula"). Neithan Agarwaen 11:32, 17 July 2007 (UTC)

I can see that this sort of consideration can come up when you're trying to encode the predicate x∈L into a first-order formula with one free variable x, but we're not doing that here. We're just trying to tell people what L actually is. The fact that the predicate is first-order definable is important, of course, but its proof is an implementation detail and not really relevant.

Just the same, the definability of the satisfaction predicate is sort of non-obvious and possibly interesting to mention here, in the context of the definability of Def(). I would think that that would be the line to take, rather than quibbling on a supposed distinction between "actual natural numbers" and elements of ω on the grounds that they are described by different formal theories -- the latter approach would take us rather far afield and require a discussion of different philosophical schools. The philosophical differences should be discussed somewhere, but not here; this is a mathematics article. --Trovatore 18:45, 17 July 2007 (UTC)

For reference, here's how Jech treats it:

Recall that a set X is definable over a model (M,∈) (where M is a set)
if there exists a formula φ∈Form (the set of all formulas over the language {∈})
and some a1,...,an∈M such that $X=\{x\in M:(M,\in )\vDash \phi [x,a_{1},\ldots ,a_{n}]\}$.
Let
def(M)={X ⊂ M : X is definable over (M,∈)}.

Then he goes on to do the transfinite recursion as in this article (but more tersely). I think Carl's right; this is indeed the "standard textbook treatment", taken from the standard textbook itself :-). --Trovatore 19:14, 17 July 2007 (UTC)

To Neithan Agarwaen: You are still not making any sense to me. You need to try harder to explain the assumptions underlying your argument. One of those assumption is no doubt false, but I have to see what they are before I can tell you which one. And I think your analogy with the natural numbers and omega is not apt. JRSpriggs 01:58, 18 July 2007 (UTC)

Neithan hasn't responded here in a while, so I'll take the liberty of speculating as to what I think he's talking about. Of course I may be wrong, which could make my interpretations look like strawmen; that's not my intent and he's welcome to clarify if I'm wrong.

I think he means that sets are not real things, and that statements about them are to be interpreted as claims that there's a formal proof of some formal statement in the language of set theory. It's not clear to me whether he thinks formulas, and natural numbers, are real things. Let's go with the idea that they are; makes the discussion simpler (I don't think it's essentially different, though, in case they're not).

In that case, it would make sense to say that natural numbers and formulas, being real things, cannot be matched up injectively with sets, which don't really exist except as a manner of conveniently translating formal sentences into natural language. That would be a natural position for a certain sort of formalist to take. But surely if this sort of objection were applied to all mathematical discussion, it would quickly become unweildy -- not sure why we have to have it specifically here. The formalist should translate in her head, as a penalty for having such an unreasonable philosophy :-).

Another possibility is that he means what he literally says about different things existing in different "contexts", a sort of "fragmented ontology" such as is required by the "many-worlds" or "plenitudinous platonism" approaches. Personally I think those approaches are barely even coherent. If something exists in a "world", then it exists, period (though it might be misinterpreted by denizens of the "world" because of the other things they know about, much as a nonstandard model thinks one of its nonstandard naturals is an honest-to-God natural). I think many-worlds theorists are really crypto-fictionalists, and not realists at all -- they just want to have a more vivid metaphor for their fictions.

In any event, it seems clear that Neithan does not really understand realism; otherwise he would not have made the claim that a realist cannot correctly match up natural numbers with elements of ω on the grounds that some model of ZF has objects that it thinks are elements of ω, but that actually are not any finite number of successors of the 0 of that model. To the realist, such a model does of course exist, but it is simply deceived about what the natural numbers are (up to order-isomorphism). Every natural number does correspond precisely to one element of the real ω, and vice versa. --Trovatore 04:23, 19 July 2007 (UTC)

Hold on. I don't want to introduce any kind of formalism in the article. As you say, it would complicate things considerably. The essence of my objection is not formalism at all. I think we all agree that the formula defining Def is not a first-order formula, as it involves quantifying over formulas. We also agree that the definition in the article is correct if "first-order formula", "truth", etc. are understood as translations of some set-theoretic concepts (formalized or not). Where our views diverge is in your claim that the definition is also correct if this is not the case, and that both definitions are equivalent, whatever that can mean. But you are the ones doing philosophy if you want to draw a parallel between the two, because such a parallel is not expressable or provable in any imaginable mathematical context (intuitive, platonistic, formalized, whatever). So even if for you, the definition in the article makes sense (it doesn't for me), it certainly isn't the correct definition.

To Trovatore: Actually, the fourth paragraph you wrote is the most relevant. Of course, there aren't "different planes of existence". There is just one. It is a matter of philosophy to decide in what way sets exist in it, and how they can interact with one another. One may believe that all sets exist exactly as they are described by ZF, for instance (i.e. that V exists). But in all cases, it is possible to define the first-order theory ZF, in the usual way. This is just a set of axioms, and it "exists". We can do derivations in ZF and write formulas of ZF, although when doing this, it is usual to translate everything in English. Now there comes a risk of confusion, because two identical discussions may be about two completely unrelated things: the one about sets, and the other about a formal system (note that both "exist"). So in order to avoid such confusion, one calls sets "level 0 sets", and we use "level 1 sets" when we are only translating the language of ZF in English. Thus we may speak of level 0 or 1 natural numbers, formulas, etc. And these levels can go on forever. For in ZF (actually, in a formal system which is an extension of ZF by formal definitions), there is a constant symbol ZF* which we think of as a level 1 counterpart to the level 0 ZF. We can derive many theorems of ZF (really of the above mentioned extension) involving ZF*. For example, if ZF* is chosen suitably, there is an instance of the level 1 completeness theorem, which is a formula translated as "ZF* has a model if and only if ZF* is consistent" (where "model" and "consistent" are level 1, of course). Maybe we can actually derive in ZF either side of this equivalence, and maybe neither. In either case this has no direct implication on the consistency of ZF itself, which is an altogether different thing. Now the translation of level 1 into level 0 material has the following consequence: the level 1 formulas which constitute ZF* can also be thought of as describing "level 2 sets", and so on. But the only thing that really exist is level 0. This hierarchy of levels is completely independent of the point of view one might take on sets or mathematics in general. With any possible point of view, "mixing levels" is absurd. In fact, the very thought of mixing them arise from the fact that any level is usually discussed in English. Neithan Agarwaen 20:49, 21 July 2007 (UTC)

I don't need your level 1, 2, etc sets. All I need is your level 0 sets. When I make an assertion about sets, I'm not saying ZF can prove that assertion, but simply that the assertion is true. Is that where the disconnect is? You want to interpret my assertions as "ZF can prove such and such?" Let me be explicit, then: When I say there's a bijection between the natural numbers and the elements of ω, or that a model M satisfies formula φ at element x if and only if a certain formula holds of M, (a code for) φ, and x, I am not asserting that ZF can prove these facts. I am simply asserting that they are true. --Trovatore 03:47, 22 July 2007 (UTC)

typography check, someone who is knowledgeable, please!

"(L,ε) is a substructure of (V,ε)" should possibly be replaced with "(L,∈) is a substructure of (V,∈)" but since I wasn't sure I didn't fix it. --Sigmundur (talk) 09:11, 19 January 2010 (UTC)

You are correct, that would be the preferable notation. One does occasionally see ε used for the elementhood relation, but ∈ is much more usual (and to your implied question, yes, elementhood is what's intended here). --Trovatore (talk) 09:15, 19 January 2010 (UTC)

I noticed that and fixed it (before I saw this section of talk). JRSpriggs (talk) 20:57, 19 January 2010 (UTC)

Ah, I just looked at this in Konqueror, and here I see the ∈ as a little box, indicating that it doesn't know that Unicode (or doesn't have it in its current font). Likely that's why someone put ε in the first place. --Trovatore (talk) 21:02, 19 January 2010 (UTC)

Yes, if I remember correctly, when I first wrote that section I was using Internet Explorer rather than Firefox. So ∈ did not appear to produce ∈. JRSpriggs (talk) 22:34, 19 January 2010 (UTC)

The difference between constructible and constructive

I have removed the following section:

All constructive sets are constructible, where a set being constructive means that it has a code which is recursive. On the other hand, constructible sets are not necessarily constructive. When constructing constructible sets one is given free use of the ordinal numbers and also of the hierarchy L_α. This may not be constructive because there are ordinals which are not the order type of a recursive well-ordering of the natural numbers. And generating Def(X) from X is not a constructive operation, especially quantifying over X when it is infinite. Nor is taking the union of L_β at non-constructive limit ordinals.

Every set in L_ω is constructive, but some non-constructive sets appear as early as L_ω+1. Every ordinal less than $\omega _{1}^{\mathrm {CK} }$ is constructive. Every constructive set belongs to the admissible set $L_{\omega _{1}^{\mathrm {CK} }}$, which is a standard set model of Kripke–Platek set theory plus the axiom of infinity.

My objection is twofold. First, it's not stated what sort of code has to be computable. I could claim that 0# is constructive, because it has a computable code consisting of the numeral 0 and the sharp sign. There's a link to code (set theory), but set theory uses all sorts of coding schemes; there's not enough clarity here.

More seriously, I do not believe this is especially standard usage. I don't think there is any agreement as to what, if anything, constitutes a "constructive set". --Trovatore (talk) 20:11, 31 July 2010 (UTC)

Power set implies V=L

Using transfinite induction, it may be provable that V=L. Consider V_α for which we already proven V_α∈L. For beginning we can even use V₀. Then, by axiom of power set, P(V_α)∈L. By definition of Von Neumann universe, P(V_α)=V_α+1. So V_α+1∈L. By axiom of pairing, we construct set {V₀,V₁,...} up to limit ordinal α. Then, by axiom of union, union of {V₀,V₁,...}∈L. So, for every successor and limit ordinal α, V_α∈L. So V is within L. From definition L is subset of V, so V=L, Q.E.D. Wojowu (talk) 19:00, 3 June 2012 (UTC)

There is something in L that appears to be powerset of a given set A, but it is actually L∩P(A) rather than P(A). JRSpriggs (talk) 04:16, 4 June 2012 (UTC)

L can be well-ordered

Can someone give a book reference for the "formula of set theory" in this paragraph?

"Notice that this well-ordering can be defined within L itself by a formula of set theory with no parameters, only the free-variables x and y. And this formula gives the same truth value regardless of whether it is evaluated in L, V, or W (some other standard model of ZF with the same ordinals) and we will suppose that the formula is false if either x or y is not in L."

Alternatively, could someone give an indication of how the "formula of set theory with no parameters" is structured or derived? The Joseph R. Shoenfield book "Mathematical logic" gives a fairly full description of the constructible universe model, and defines Ord(x) for all constructible sets x as the minimum ordinal number from which x is constructed, but it is not immediately obvious that Ord(x) can be defined as a first-order language formula without using the metamathematical ordering.

I'm a bit skeptical about the claim. It seems to imply that there is a formula within ZF which well-orders the set of constructible real numbers or the set of all constructible subsets of the integers. Can a finite formula really do that?
--Alan U. Kennington (talk) 20:47, 2 December 2012 (UTC)

This is just a question of notation. "Ord (x)" as used in this article means "x is an ordinal number.". Evidently your source uses it for a different purpose. Both concepts are legitimate and important concepts, but they should be indicated by distinct symbols. However, it is impossible to use a notation consistent with all sources. JRSpriggs (talk) 20:58, 2 December 2012 (UTC)

@JRSpriggs: You're right. I've been collecting mathematical logic notations from the 30 or so books on this subject in my collection, and there is a very wide range of notations out there. It's difficult to find two authors with the same notations.
--Alan U. Kennington (talk) 09:20, 3 December 2012 (UTC)

@Alan U. Kennington: A reference would be Jech's book *Set Theory*, Third Millennium edition, theorem 13.18 on page 188 (I'm a bit too lazy to fill in the {{cite}} template right now), and also lemma 13.19. And yes, there is a (finite) formula which well-orders L and, in particular, the constructible real numbers. In fact, this formula can even be written in Σ₁ fashion (i.e., starting with an unbounded existential quantifier, after which all quantifiers are bounded). The expanded expressin for "x<y" looks something like: "there exists α such that α is an ordinal, and such that we have x≪y for every pair (M,≪) where M is a function defined on α which satisfies M(0)=∅ and M(γ+1)=Def(M(γ)) for every γ<α and M(δ)=⋃_γ<δM(γ) for δ limit and ≪ is a total order relation on the union of the M(γ) which orders M(γ) before M(γ′) when γ<γ′ and which orders Def(M(γ)) according to the smallest formula defining the element (and its parameters)" (of course, I would still need to elaborate on the end, but I hope this is convincing enough). --Gro-Tsen (talk) 22:01, 2 December 2012 (UTC)

@Gro-Tsen: Many thanks. That's what I wanted to know. I have the Jech "Axiom of choice" book, but not the Jech "Set theory" book (which is very expensive on a well-known online bookstore right now). In my opinion, the explicit well-ordering for all constructible sets is a core fact about set theory, perhaps almost as important as Skolem's paradox. The axiom of choice is accepted by most practical mathematicians, but not by people like me because it seems very non-constructive indeed when applied to uncountable models. But with the countably infinite constructible universe, paradoxically the axiom of choice is easily proved in the model. (Shoenfield "Mathematical Logic" uses a different model for ZFL to what this wikipedia article does, mapping the class of ordinals to constructible sets very explicitly using the 9 Gödel binary operations. Jech "The Axiom of Choice", page 38, uses 8 Gödel operations and a less explicit construction, more like what is in the wikipedia article, but does not give any well-ordering for the universe of sets.) The surprising thing is that the metamathematical well-ordering can be "seen" within the first-order language.

Obviously the particular well-ordering imported from the model into the language will depend on the interpretation. But it would still be useful to have at least one well-ordering on the wikipedia page, because it seems to me like the existence of a well-ordering for all (constructible) sets is an even greater paradox than Skolem's. It seems to imply that one can write out an explicit closed expression for a Lebesgue non-measurable set and function for example.
--Alan U. Kennington (talk) 09:20, 3 December 2012 (UTC)

And another question....
Maybe there should be an explanation of why mathematicians don't just stick with the constructible universe and ignore all of the other models. It would make life so simple. You get AC and GCH without effort. You get explicit well-orderings of the real numbers, and explicit Lebesgue non-measurable functions. Every linear space has a well-ordered basis. And all the sets of constructible! What's not to like? Mathematicians only need ZF and AC and GCH.
--Alan U. Kennington (talk) 17:39, 3 December 2012 (UTC)

Moschovakis would be a good source for this, and some of the earlier work of Maddy (maybe Believing the axioms, I or Believing the axioms, II). This is not the right place to answer questions as such (you can bring it up on WP:RD/Math if you like) but an executive summary would be that you appear to get a more and more complete view of set-theoretic reality as you add more and more stuff that's not in L. L then appears to be just a restricted view of the world, made by ignoring, not models so much, as objects, and there seems to be no special gain in restricting to it, because anything you would want to prove by assuming that V=L is still good mathematics without assuming it, just interpreting it as referring to, not all sets, but just the ones in L. --Trovatore (talk) 18:14, 3 December 2012 (UTC)

@Alan U. Kennington: This is a philosophical question, so I'll give you a philosophical answer (but I should say that I'm a mild Platonist: I believe that the natural numbers exist in some kind of Platonic heaven, but I don't really believe this for sets, so I don't think it really makes sense to ask whether V=L is "true" or not, it's mostly a matter of what sets are more convenient—and I certainly agree that L is a pleasant place to work in and a nice object to study).

Intuitively, L should be thought of as the class of sets which are "computable" in some very generalized way: what you do when you construct L, starting from the hereditarily finite (HF) sets (L_ω) is basically to iterate the Turing jump as far as it makes sense: the first steps give you recursive sets (Δ⁰₁ sets of integers—or of HF sets which makes little difference), then recursive sets in the halting oracle (Δ⁰₂ sets of integers), then recursive sets in the halting oracle relative to the halting oracle, etc., all of which, together, form arithmetic sets which are basically what you get in (L_ω+1); then you do it again, and again, and again: at the Church–Kleene ordinal you get hyperarithmetic sets which are the first major step in recursion theory (the first hyperjump, which has lots of characterizations: basically you have Δ¹₁ sets of integers; this is also the first model of Kripke–Platek set theory beyond the HF sets, and also the first model of arithmetic Δ¹₁ comprehension); but you keep on going, pursuing the Turing jump as far as it can take you, or pursuing ever stronger comprehension axioms: when you reach the "ordinal of ramified analysis" β₀, you run out of sets of integers to add, because you have a model of full second-order arithmetic (aka "classical analysis"), so there is a first "gap" where the constructible universe adds no sets of integers and it becomes essential to keep track of sets of higher rank, but we can still agree to call this iterating the Turing jump; going on, we encounter larger and larger gaps until we reach ω₁^L after which every set of integers that L will ever add has been added, and the construction of L proceeds only with sets of higher rank. Jensen's theory of the "fine structure of L" explains in much more detail.

Now, if L consists of "computable" sets, even with a very general notion of computability, there is one obvious thing it cannot contain: random numbers. So philosophically, or intuitively, most real numbers (in the sense of Lebesgue measure) shouldn't be in L, because a random number isn't determined by any rule. And indeed, there is a notion of a random real over L (it can be defined as a number which doesn't belong to any Borel set of measure zero whose "code" is constructible), and they don't belong to L (this is tautological, but the point is that this notion makes sense and is interesting).

Another thing is that L does not see the larger "large cardinals". For example, the existence of a measurable cardinal is inconsistent with V=L. Of course, the measurable cardinal still exists (as an ordinal) in L, but it ceases to be measurable: it becomes indiscernible in a strong sense from any uncountable cardinal (in V). In a nutshell, the contradiction between measurability and V=L is because the existence of a measurable cardinal allows you to construct a well-founded ultrapower of the universe, in which the universe elementarily embeds, but if V=L then L is the smallest model containing all the ordinals so you would have an elementary embedding of L into itself which moves the first measurable cardinal (a definable property), a contradiction. Intuitively, what this says is that L is too rigid (because it is too "thin", or because it consists of "computable" sets) to allow for something like a measurable cardinal.

Well, you might say, maybe we don't care about having a measurable cardinal? But the problem isn't only that L can't have them: it can't see them, because V=L implies that measurable cardinal cannot exist in any transitive model [this is wrong, see below]. Having a measurable cardinal entails a very great consistency strength, and this consistency strength is lost when passing to L. Of course, you could add the axiom "ZFC + measurable cardinal is consistent" to ZFC + V=L, but the models you get are then highly artificial, because they can't be well-founded. So if you add V=L as an axiom, you close the door to any study of "large" large cardinals, which is really inconvenient.

--Gro-Tsen (talk) 21:11, 4 December 2012 (UTC)

To Gro-Tsen: If there is a measurable cardinal, κ, in V, then "ZFC + measurable cardinal is consistent" "(ZFC + a measurable cardinal exists) is consistent" is true. And it is a statement about natural numbers, so it is absolute for transitive models. So it holds in L.

Let μ be a κ-additive, non-trivial, 0-1-valued normal measure on the power set of κ. Using the downward Löwenheim–Skolem theorem, one gets a countable transitive model containing ν (the image of μ) which appears to be such a measure within this countable model. How do you know that ν cannot be constructible as you implied? If it is, then there should be a countable ordinal α such that L_α(ν) is a transitive model of "ZFC + measurable cardinal is consistent" within L, right? JRSpriggs (talk) 12:36, 5 December 2012 (UTC)

Sorry, I haven't been very clear about what I meant and I also made a mistake: let me clarify both.

First, I didn't mean to say that V=L forbids the consistency of a measurable cardinal (obviously, if V satisfies "(ZFC + a measurable cardinal exists) is consistent" then, since this is—as you point out—an arithmetic statement, L also does, and every transitive model of ZFC does because they share the same ω). What I mean to say—from the philosophical point of view—is that if you believe in V=L (or at least, if you want to work within L), then introducing the axiom "(ZFC + a measurable cardinal exists) is consistent" is highly artificial and ad hoc, because it posits the existence of a combinatorial structure in a model that does not exist in the universe.

Next, there is the question of transitive (or equivalently, well-founded) models. We all agree that L can have models of "ZFC + a measurable cardinal exists" (supra), and we all agree that L can have transitive models of "(ZFC + a measurable cardinal exists) is consistent" (again, because that's an arithmetic statement). If I gave the impression of disputing the latter, I was being unclear and I really wanted to dispute that L can have transitive models of "ZFC + a measurable cardinal exists". But this was a mistake anyway.

(The reason why I made this mistake is that constructibility is absolute: if M is a transitive model then L^M is some L_α, where α is the least ordinal not in M; so if M has a measurable cardinal κ then there is an elementary embedding of L_α inside itself which moves κ and I thought this must surely be a contradiction with V=L.)

Now in fact something of the opposite is true: if there exists a transitive model of "ZFC + a measurable cardinal exists", then there exists such a transitive model inside L (so I was as wrong as I could possibly be). This is actually a straightforward consequence of some variations of the Shoenfield absoluteness theorem (see theorem 8.1 and theorem 8.10 of Barwise's book Admissible Sets and Structures cited in the article; or theorem 36 of §14 in the old edition of Jech's Set Theory).

This certainly weakens the position that "V=L cannot see measurable cardinals", but I think the basic idea reamains that it is strangely artificial to rely for consistency strength on something that is going on in a submodel (even a transitive one) rather than the universe.

--Gro-Tsen (talk) 15:51, 5 December 2012 (UTC)

Guys, this is really not the place, per WP:TALK. It's a very interesting discussion and I would have stuff to say, but not here, please. --Trovatore (talk) 19:28, 5 December 2012 (UTC)

Instead of telling us this is not the right place, may I suggest that you tell us where a better place is, post the stuff you have to say over there, and let us follow? --Gro-Tsen (talk) 09:30, 6 December 2012 (UTC)

I did that up top — WP:RD/Math. I was thinking of moving this entire discussion there — any objection? --Trovatore (talk) 09:44, 6 December 2012 (UTC)

Sorry, I missed that. For my part, I'm fine with this discussion being moved anywhere else on Wikipedia, as long as a link is given. --Gro-Tsen (talk) 00:24, 7 December 2012 (UTC)

I'd prefer to keep this material here. The whole point of the Talk web page is to discuss what should be on the corresponding real web page. It's not a discussion only about what is true and what is not, but rather a discussion about what should be on the main web page. And I think that is important. There are plenty of other places to discuss these questions in isolation from this wikipedia page. The points here are directly relevant to the wiki entry content.

I find this discussion enormously useful, not just for my own interest, but because I am sure that I am not the only non-expert who would like to have these matters clarified on the wiki page about the constructible universe. The outcome of this discussion will hopefully be a better clarification of the significance of this kind of interpretation of ZF. The purpose of wikipedia is, as I understand it, to enable the experts to summarise topics so that the non-experts can make some initial sense of them. At present, I think too many of the mathematical logic wiki pages are just experts talking to other experts. That's pointless. That's not what encyclopedias are supposed to do. That's what research monographs and conferences and research journals do. Since I am a non-expert in the subject of ZF models, I think that if the questions are clarified for me, then probably others could benefit also.

Therefore please do not remove this discussion from here. The kind of discussion here is exactly what the Talk pages are intended for. I.e. discussion of wiki page content. But sometimes that discussion does need to go into some detail to reach resolution.
--Alan U. Kennington (talk) 15:00, 6 December 2012 (UTC)

Explicit well-ordering of the sets within L

To Gro-Tsen: Thanks especially for the comment about the random numbers. Random real numbers (and other such incompressible infinite-choice objects) can never be stored in any finite memory system, nor passed through any finite-bandwidth information channel. Therefore no entity in the universe can ever contemplate or communicate such numbers. That was originally my objection to them for the last few years. But it seems to me that all use of such random objects in mathematics is done in aggregate. I.e. Individual objects are never referred to. Thus Lebesgue non-measurable sets exist as an aggregate in ZFC, but no individual such object can be written down.

One could plausibly argue that all of the complexity of ZF model theory could be relegated to the dustbin, except that then measure theory becomes difficult. And measure theory is needed for probability theory, and you can't do much in physics, engineering etc. without probability theory.

So I was hoping that someone could (1) add an explicit well-ordering for the constructible universe on the wiki page, at least in outline, indicating that it is "visible" from within the first-order language. Then (2) indicate in general terms why the constructible universe is not suitable for all of mathematics. This would be similar to the way in which people make lists of "what you will lose" if you don't accept the axiom of choice. I was hoping there could be a kind of "what you will lose" if you adopt the constructible universe as the basis of mathematics. This could help to motivate some of the highly technical stuff that is written about ZF model theory.

In other words, I'm hoping for a new section or subsection titled "Why the constructible universe is not a suitable basis for mathematics", or something like that. Most presentations of this topic seem to be motivated simply by the desire to show that AC and GCH are consistent with ZF. I guess that was the original reason for defining such interpretations. But that's history. The question is what is this universe good for now?
--Alan U. Kennington (talk) 15:18, 6 December 2012 (UTC)

Unfortunately, I lack any kind of source to back up my semi-philosophical ramblings about L. The best I could find was: Hamkins, Joel (2012). "A multiverse perspective on the axiom of constructibility". arXiv:1210.6541 [math.LO]. --Gro-Tsen (talk) 00:24, 7 December 2012 (UTC)

To Alan: Whether L is all of V or not, it is certainly an important part of V.

This article already contains (at Constructible universe#L can be well-ordered) an outline of how a formula could be written to well-order L. However, translating that into the actual language of set theory would be so difficult that I doubt that anyone has actually done it. And the resulting formula might be extremely long (perhaps hundreds of pages??), so that it would be impractical to include it in this article. It would also be pointless, since no one would read it (or be able to read it). JRSpriggs (talk) 06:29, 7 December 2012 (UTC)

To JRSpriggs: I suspect the difficulties there are caused by the complexity of the Gödel numbering. And that's caused by the particular interpretation in the section What is L?, which generates the constructible sets via formulas. There's a very much nicer interpretation in Shoenfield "Mathematical logic", 1967, pages 270–276. This maps the class of ordinal numbers to constructible sets using 9 Gödel operations. Then a unique ordinal number Od(x) associated with each constructible set x as the minimum ordinal which generates x. This has the neat advantage that one can then define well-orderings of any class of sets by simply saying that x<y whenever Od(x)<Od(y), However, I can't immediately see how to write down the function Od. I think it would be a quite practical task though. And it should be easier than working with Gödel numbers for formulas. Maybe I should write it out as an exercise, and then see if anyone agrees that I have it right. However, this would also imply a change in the wiki article — i.e. the interpretation in the wiki article via formulas would have to be replaced (or augmented) by the statement of the Shoenfield interpretation. I was hoping that someone out there would just happen to have the answer written down somewhere so that they could copy/paste it into the article!!!

Also, I'm still hoping that someone will be willing to write a section called "What you lose in L" to motivate why people study other models.
--Alan U. Kennington (talk) 07:40, 7 December 2012 (UTC)

On the German Wikipedia, there is an article, de:Konstruierbarkeitsaxiom, which includes some information about the functions you mentioned which build constructible sets. Perhaps it might help here. JRSpriggs (talk) 09:58, 7 December 2012 (UTC)

To JRSpriggs: The method of the German wikipedia article on the constructibility axiom is very similar to the Shoenfield construction. However, in the section on the constructibility axiom, they do not give details of their bijection $J\colon On\times On\times \{0,\dotsc ,8\}\rightarrow On$ except to say that it exists and is unique, whereas the Shoenfield book gives much more detail about the construction by transfinite induction of a bijection from On to On×On. Shoenfield then uses this bijection to construct a map from On to the class of constructible sets. This seems like a better basis for writing out an explicit expression for a well-ordering of On.

However.... this does all start to look like hard work. If I find the time and energy to write out an explicit well-ordering, and it it is simple enough to not frighten the horses, I'll add it on the wiki page. Otherwise not. — Preceding unsigned comment added by Alan U. Kennington (talk • contribs)

One could take J to be

$9+J(\alpha ,\beta ,\gamma )=9\cdot 2^{\alpha }\cdot (2\cdot \beta +1)+\gamma \land \gamma <9\,.$

However, the formula just to implement this would be rather long. And worse, it would have to be explicitly repeated each time J was used in the larger formula because the language of set theory does not contain macros (or subroutines) such as one has available in computer or human languages. JRSpriggs (talk) 18:42, 8 December 2012 (UTC)

To JRSpriggs: Yes, my choice of title for the sub-section was poorly chosen. Definitely well-ordering of the class of all sets was what I was thinking of.

As to the construction of a bijection from On×On×{0,...8} to On, it needs to be for all ordinal numbers, not just the finite ones. (I'm not certain enough of my ordinal arithmetic to determine if your formula can be extended to all transfinite ordinals.)

The reason why I think an explicit formula for a well-ordering of all constructible sets would be useful is that it would give the paradoxical effect that everything using the axiom of choice could be written out explicitly. Effectively, the axiom of choice would be a theorem, not an axiom, if one accepts (temporarily) that all sets are constructible. This was why I initially made the query here — because I was skeptical that one could explicitly define a well-ordering of the real numbers (via a well-ordering for all sets) and explicitly define a Lebesgue non-measurable set (via the same well-ordering), while maintaining all of the ZF axioms. The paradox lies in the confusion of L with V. An explicit well-ordering is only available for L.

As to my question "What's not to like?", regarding the constructible universe, I think the answer is that one expects mathematics to contain all infinite decimal expansions, including all "random" infinite decimal expansions in aggregate. Clearly L is inadequate for this. Thus I am coming to the view that V might be the "right" universe for the underlying individual objects which are used in models of the real world in physics and other sciences, whereas L is what we can really talk about in a first-order language (with a countable set of variables etc.) as aggregates of those metaphysical individual objects. I'm sure this must seem naive to the experts, of whom I am not one.

Now regarding the wiki page, I still would like (1) some sort of discussion in the "constructible universe" entry of "what you lose". The technical questions of independence, consistency and completeness don't tell the reader why anyone would be interested in a hundred different ZF models. (The Howard/Rubin book "Consequences of the axiom of choice" gives properties of more than 100 ZF models, which is a bit overwhelming.) And (2) I'd like an explicit well-ordering of all constructible sets, because of the psychological effect that should have.

I think that my own questions are answered now. (I'll pursue further details by reading the 30 mathematical logic books on my bookshelf.) It would be nice if other readers of the wiki page could get the same benefit. I think I'll leave this discussion at this point, unless there are dramatic new developments! Many thanks to you and the others for the generous help.
--Alan U. Kennington (talk) 02:29, 9 December 2012 (UTC)

On second thought, I think the pessimism I expressed above was too extreme. By sharing variables which represent partial functions for initial segments of: addition, multiplication, J, etc., one could avoid repeating most of the definitions of those relationships. And the readers might be gracious enough to allow us to use macros for formulas of set theory even though they are not strictly in the language of set theory.

The formula I gave in my previous comment works for transfinite ordinals, not just natural numbers. See ordinal arithmetic. Every ordinal is either even or odd, so decomposition into a power of two times an odd ordinal is universal (except for zero). JRSpriggs (talk) 09:30, 9 December 2012 (UTC)

Using an example ordinal from ordinal arithmetic#Cantor normal form, if we require

$J(\alpha ,\beta ,\gamma )=\omega ^{\omega ^{\omega ^{7}\cdot 6+\omega +42}\cdot 1729+\omega ^{9}+88}\cdot 3+\omega ^{\omega ^{\omega }}\cdot 5+65537\,,$

then

$9+J(\alpha ,\beta ,\gamma )=\omega ^{\omega ^{\omega ^{7}\cdot 6+\omega +42}\cdot 1729+\omega ^{9}+88}\cdot 3+\omega ^{\omega ^{\omega }}\cdot 5+65537\,$

$9\cdot 2^{\alpha }\cdot (2\cdot \beta +1)+\gamma =\omega ^{\omega ^{\omega ^{7}\cdot 6+\omega +42}\cdot 1729+\omega ^{9}+88}\cdot 3+\omega ^{\omega ^{\omega }}\cdot 5+65537\,$

$2^{\alpha }\cdot (2\cdot \beta +1)=\omega ^{\omega ^{\omega ^{7}\cdot 6+\omega +42}\cdot 1729+\omega ^{9}+88}\cdot 3+\omega ^{\omega ^{\omega }}\cdot 5+7281\land \gamma =8\,$

$\alpha =0\land \beta =\omega ^{\omega ^{\omega ^{7}\cdot 6+\omega +42}\cdot 1729+\omega ^{9}+88}\cdot 3+\omega ^{\omega ^{\omega }}\cdot 5+3640\land \gamma =8\,.$

If there are cases which you cannot work yourself, please give them to me and I will show you how to work them out. JRSpriggs (talk) 17:36, 13 December 2012 (UTC)

Another example, to calculate J(ω+1,ω+2,3):

$9+J(\omega +1,\omega +2,3)=9\cdot 2^{\omega +1}\cdot (2\cdot (\omega +2)+1)+3\,$

$9+J(\omega +1,\omega +2,3)=9\cdot 2^{\omega }\cdot 2\cdot (\omega +5)+3\,$

$9+J(\omega +1,\omega +2,3)=\omega \cdot (\omega +10)+3\,$

$J(\omega +1,\omega +2,3)=\omega ^{2}+\omega \cdot 10+3\,$

JRSpriggs (talk) 06:55, 14 December 2012 (UTC)

Cantor diagonalization procedure

To JRSpriggs: On the subject of countability of the constructible universe....
The countability of the countable universe does not seem to be explicitly stated on the wiki page. But numerous books do state that it is a countable universe, In particular, $X=\{x\in 2^{\omega };\,{\hbox{Cons}}(x)\}$ should be countable, where Cons(x) means that that x is constructible. Both you and the textbooks say that constructibility is a property which is expressible within ZF, i.e. not just in the metamathematics.

I can't quite square that with the Cantor diagonalization procedure. Suppose $f:\omega \to 2^{\omega }$ is a function satisfying $X\subseteq {\hbox{Range}}(f)$. Then define $g\in 2^{\omega }$ as the set of ordered pairs $g=\{(i,1-f_{i}(i));\,i\in \omega \}$. Then $g:\omega \to 2=\{0,1\}$ is a function satisfying $g\notin X$. But surely g is constructible if X is constructible. So g is both constructible and not constructible. Where is the error in this argument? Is X not really constructible? Is the Cantor diagonalization procedure not a construction? Does countability not necessarily imply the existence of the map f? I must have missed out on something here.

I think that these questions go to the core of the constructibility issue. So I think they should be directly discussed on the wiki page. If I can be perplexed, then maybe other people can also.
--Alan U. Kennington (talk) 04:09, 16 December 2012 (UTC)

The constructible universe is simply not countable. In fact, it contains all the ordinals (so it is not a set, let alone a countable one). On the other hand, the set $X=\mathbb {R} ^{L}=\mathbb {R} \cap L$ of constructible reals can be countable (it is consistent with ZFC that it be countable), but no function f surjecting ω onto X can be constructible (because X can be constructible in the universe, but not in L) and the function g you define also is not constructible. (If this helps, the situation is quite analogous to recursive sets: there are countably many recursive sets of integers, but they cannot be "recursively counted".) --Gro-Tsen (talk) 12:13, 16 December 2012 (UTC)

To Alan: As Gro-Tsen says, f and g are not constructible. When you said "surely g is constructible if X is constructible", that was a mistake. You would have to have f constructible to get g to be constructible, but it is not so. JRSpriggs (talk) 18:12, 16 December 2012 (UTC)

---

Thanks to both Gro-Tsen and JRSpriggs for that.

However, I am left totally perplexed. I seem to see many contradictions and ambiguities instead of the crisp clarity which I was seeking from the wikipedia article.

1. Reading pages 99–106 of
Cohen, Paul (2008). Set theory and the continuum hypothesis. Mineola, New York: Dover Publications. ISBN 978-0-486-46921-8.
makes me think that L is countable, which makes perfect sense if you have a countable number of variables in the first-order language, and all elements of L can be "named" by propositions in ZF, and all propositions have finite length. (Obviously this does not contradict the fact that the universe is uncountable within ZF itself.) Even the wikipedia article in section "L is absolute and minimal" seems to imply that L is countable.

2. It is said that the well-ordering of L can be accessed within ZF. Then it is not clear why a surjection from ω to the constructible real numbers is not possible. But this is something which I'm sure I can clarify with some further study.

3. It is not quite clear how the diagonalization process is related to constructibility. It should prove that $2^{\omega }$ and the real numbers are uncountable, and implies that you can't construct a surjection from ω to the constructible reals. But this doesn't fit well with the "visibility" of the well-ordering of L within ZF.

I am thinking that I have exceeded the tolerance of the 38 watchers of this Talk-page some time ago. So I will try my hardest not write any more to this page. If I read my 30 books on mathematical logic carefully over the next 12 months, I should have this all sorted out by Xmas 2013. Then I'll contribute the answers to the wiki page if/when I'm certain I know what I'm talking about. — Preceding unsigned comment added by Alan U. Kennington (talk • contribs)

From Constructible universe#Constructible sets are definable from the ordinals, one can see that the cardinality of the sets in a transitive model L_α of ZFC+V=L is ℵ₀+|α| rather than just ℵ₀. In other words, a model containing an uncountable number of ordinals would have uncountably many elements because the formulas which define its elements must contain constant symbols for its ordinals. Although one can use formulas without parameters to define some of the ordinals, others cannot be so defined. L is minimal given its ordinals (so do not take the section title too literally). JRSpriggs (talk) 04:44, 17 December 2012 (UTC)

Citations and references?

Reading through the article, there are only two references, one on the original Godel paper introducing the constructible universe and another on hyperarithmetical subsets. The rest of the article is essay-like in its near complete lack of citations and references. Given the carefully written exposition, it seems silly to slap a "needs citations" tag on the article. But it would be useful to indicate from which references the various results in the article were gleaned. Unfortunately, I don't have the expertise in this field to do so. Mark viking (talk) 06:52, 15 December 2012 (UTC)

I added most of the content of the article, and based most of that on Ulrich Felgner's "Models of ZF-Set Theory". There are six sources listed in Constructible universe#References. These are used throughout the article. Requiring in-line citations for all statements in the article would make the article unreadable (especially for editors). JRSpriggs (talk) 07:06, 15 December 2012 (UTC)

Thanks for the information. I agree, citations for all statements would be too much and that degree of granularity would likely be unhelpful to the reader. Perhaps it would be useful to indicate in the notes or references section that the article is largely based on the Felgner reference? Mark viking (talk) 07:35, 15 December 2012 (UTC)

Well, I used Felgner because that was what I had. It may not be as useful as some of the other sources to a reader who has easy access to them. JRSpriggs (talk) 12:09, 15 December 2012 (UTC)

Eponymous category

It isn't unusual if articles are in both a category and one of its subcategories if the article and the subcategory have the same name, see WP:Eponymous category. I think it is natural (and helpful to the reader) to have the article constructible universe both in the category Set-theoretic universes and its subcategory constructible universe. — Tobias Bergemann (talk) 19:40, 16 December 2012 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Constructible universe/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Content is mostly here but the prose needs editing and cleaning up - this should be aimed at a broad audience since it is part of the independence of CH, which is of broad interest. CMummert · talk 12:00, 14 May 2007 (UTC)

Last edited at 17:16, 29 May 2007 (UTC). Substituted at 01:55, 5 May 2016 (UTC)

These headers are weird

They seem conversational, almost friendly. Like something in a pamphlet. Not a bad pamphlet, but not an encyclopedia. I thought about bringing them more in line with the rest of Wikipedia's style (something dry and brief, like Universe does), then noticed I don't grasp the concept well enough to summarize the chapters.

Someone smarter might want to take a serious go at making them look a bit like "Relative constructability" does. If not, no harm done, probably. InedibleHulk (talk) 22:47, 9 March 2017 (UTC)

Jensen hierarchy

Is Jensen's related $J_{\alpha }$ hierarchy too similar to $L_{\alpha }$ to warrant a separate article? C7XWiki (talk) 10:24, 26 February 2022 (UTC)

I don't think it needs a separate article; it's sort of a technical "implementation detail". At the level of this article it could be mentioned in passing but I wouldn't go into a lot of detail.

Where it starts to get important is when you start talking about fine-structure theory, on which I don't think we currently have an article (fine structure points to a physics concept). I don't understand fine structure super-well but I gather that the J hierarchy is a lot more convenient than the L hierarchy in that context. But even there, again, it's a matter of expository convenience rather than a central concept. --Trovatore (talk) 20:51, 26 February 2022 (UTC)

If you look at Category:Constructible universe, you will see some related articles including Jensen hierarchy and Gödel operation. JRSpriggs (talk) 23:46, 26 February 2022 (UTC)

Thanks, I wasn't aware there already was an article and was asking before I was going to either create one or add a section. However if they're similar, should the articles be merged? C7XWiki (talk) 02:22, 27 February 2022 (UTC)

I wouldn't say so at the current time; probably not worth it. All three articles right now are sort of definitions-plus-lists-of-facts. I can imagine a future where the top-level article (this one) is much more engagingly written and where the details of the hierarchies are skimmed over lightly (they're more handbook-like than encyclopedia-like anyway). In that future we might not really need the other two articles. But it would be a lot of work and I don't know who's going to do it — I'm certainly not volunteering.

It would be very cool if we could get someone who understands fine structure to write an article on it. --Trovatore (talk) 02:52, 27 February 2022 (UTC)