Talk:Constructible universe

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: A-BB+ Class High Priority  Field: Foundations, logic, and set theory

Contents

[edit] 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)

[edit] 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)

[edit] 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^{\operatorname{CK}}_1} 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^{\operatorname{CK}}_1}; 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^{\operatorname{CK}}_1}? 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(ω). 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 ω levels you have all the finite jumps. Then an instance of Σ0 collection allows you to collect these into a single set from which 0(ω) is computable.
I think it is easier than that to see that L_{\omega^{\mathrm{CK}}_1} 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)

[edit] 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,z1,...,zn) 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,z1,...,zn) is true in (X,ε)} | Φ is a first order formula and z1,...,zn 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)