4
$\begingroup$

I am not sure to fully understand the concept (I read many of the wikipedia definitions for many of these issues but I am still confused). For instance, is a surreal number an example of non-constructible real? Can a non-constuctible real be represented as an infinite sequence of digits (so, is it a regular no-computable real after all)? Is a constructible real the analogy to non-standard naturals (something outside the intended model of natural numbers, or in this case, of real numbers? What makes them non-constuctible?

$\endgroup$
  • 3
    $\begingroup$ Usually, "constructible" means "constructible with straightedge and compass" in the sense of geometry. Is that what you are asking about, or something else? Your question seems to be asking about non-computable reals, which is very different. $\endgroup$ – MJD Mar 17 '14 at 19:26
  • $\begingroup$ It has nothing to do with surreal numbers or non-standard models, one is talking about ordinary reals, the kind we meet every day when we walk on the number line. $\endgroup$ – André Nicolas Mar 17 '14 at 19:30
  • 1
    $\begingroup$ Sometimes these ideas are used about Real Numbers which can be defined by some mathematical formula (i.e. constructed out of mathematical symbols). Since there are uncountably many reals and only countably many formulae, there must be real numbers which can't be expressed in this way. $\endgroup$ – Mark Bennet Mar 17 '14 at 19:41
  • 1
    $\begingroup$ Your question is far from clear, as the word "constructibility" is used to mean different things in different contexts. The choice of tags makes me suspect you mean constructibility in the standard set theoretic sense, as used by Gödel. Is this what you mean? $\endgroup$ – Andrés E. Caicedo Mar 17 '14 at 19:46
  • 1
    $\begingroup$ That was the point of my first comment to julian: "Constructible" in the sense of "constructivism" is not the same as "constructible" in the set theoretic sense. $\endgroup$ – Andrés E. Caicedo Mar 17 '14 at 21:24
8
$\begingroup$

The real numbers are the usual thing. Surreal numbers are not real numbers, so no, they are not an example of non-constructible reals. Any real $r$ can be written as an infinite sequence $(n;d_1,d_2,\dots)$ where $n$ in an integer and the $d_i$ are digits. Whether the real is rational, constructible or not, is irrelevant. Any rational number, in fact, any algebraic number, and any transcendental number we ever encounter in analysis, number theory, or even computability theory, is constructible. So, every non-constructible real is transcendental and noncomputable, but the converse is not true. There is no analogy between constructible/non-constructible reals and standard/non-standard natural numbers. They are completely different things.

I think that directly answers your questions. As for the main one: A model of set theory consists of a class (maybe a set, maybe a proper class) $M$, together with a binary relation $E$ on $M$ such that $(M,E)$ satisfies the axioms of set theory (whether this means $\mathsf{ZF}$, $\mathsf{ZFC}$, or some variant thereof does not matter much for this discussion). This use of the word model is not quite the canonical use in model theory, but it will do for us.

The obvious model of set theory is the class $V$ of all sets, with $E$ being standard membership. But there may be other models. Gödel identified one, that we call $L$ and whose elements we call constructible. $E$ is again standard membership. However, we restrict what sets belong to $L$. In order to be in $L$, a set needs to be "definable" in a very precise sense: $L$ is organized by stages, indexed by the ordinals. We start with the empty set. At a given stage we have built an approximation $L_\alpha$ to $L$, and we go to the next stage $L_{\alpha+1}$ by adding to $L_\alpha$ all sets that are first-order definable collections in the structure $(L_{\alpha},\in)$, allowing parameters. We collect what we have so far at limit stages, and $L$ is simple the union of all these approximations.

In a sense, this class appears rather restrictive. The sets that belong to $L$ not only need to be definable, which already may be seen as a bad restriction, but on top of that, their definition is "local", from the ground up. This is another restriction, as nothing prevents a set from being definable in terms of the whole universe of sets, or maybe in terms of a large fragment of the universe, without it being definable in the way that we require here. For instance, we could define a real by $$ r=0.d_1d_2\dots $$ where $d_i=1$ iff $2^{\aleph_i}=\aleph_{i+1}$, and $d_i=0$ otherwise. This real may well not be constructible, as the $L_\alpha$ (and even $L$) do not appear to have access to the true power set operation, and so may not "know" whether $2^{\aleph_i}$ is $\aleph_{i+1}$ or not. Of course, maybe $r$ is constructible "by accident" (for all we know, $r$ could be $0$, for example).

What Gödel proved is that the standard axioms of set theory do not suffice to identify a single non-constructible set. More precisely, Gödel proved that $L$ is a model of set theory, and that in this model, the statement "every set is constructible" is true. Hence, it is consistent that there are no non-constructible reals, and since all of classical mathematics can be readily formalized within standard set theory, all real numbers we encounter in practice are constructible. In fact, once we settle on what model of the reals we are to use (whether Dedekind cuts, or classes of Cauchy sequences, etc) we can easily verify that all reals we encounter in practice appear in some $L_\alpha$ and, if we have patience for that sort of thing, we can even provide decent upper bounds for how large $\alpha$ needs to be.

That said, the prevailing view among practicing set theorists is that (if discussion of these matters makes sense at all) not all sets are constructible and, moreover, not all reals are constructible. Beyond that, there is not much more that can be said in full generality. If we accept the existence of certain large cardinals, we can exhibit specific reals that are not constructible, but these reals are not objects that we encounter in classical mathematics, and the way we "exhibit" them is far beyond from the usual way we describe a number in (say) analysis. For example, it is common to mention $0^\sharp$ as a canonical non-constructible real, but this is an object that we do not study from the point of view of number theory or classical analysis, and whether its fifth digit is $3$ or not is the sort of question we do not really care about.

One of the key discoveries in 20th century set theory is the fact that there are many natural statements that are not decidable by the usual axioms, that is, for each of these statements $\phi$ there are models of set theory where $\phi$ holds and models where it fails. If we accept $\phi$ as part of what is true of the universe of sets, it is quite possible that $\phi$ implies the existence of non-constructible reals. For example, $\phi$ could be the statement "The Borel conjecture is true". This statement means that if a set of reals is strongly null, then it is countable. Since this statement implies the negation of the continuum hypothesis, and the continuum hypothesis is true in the constructible universe, then we have that there must be non-constructible reals. Beyond that, not much can be said.

Of course the discussion here is in context, so in a model of set theory there may not be non-constructible reals, in another there may be, and in a third model there may be as well, even though the latter two have nothing in common. (Also, in the above, I am assuming tacitly the consistency of the theories discussed to avoid cluttering the text with comments on relative consistency.)

$\endgroup$
  • 1
    $\begingroup$ Thanks Andres, your example of a non-constructible real clarified a lot of the fog in my mind. I might still make a few more question on this issue (after some more reading and thinking) but next time I hope to be able to be careful enough to leave as much ambiguity away as possible. $\endgroup$ – Wolphram jonny Mar 18 '14 at 0:46
  • $\begingroup$ @Andres: If all the reals used in ordinary mathematics are constructible, can one say that, for all practical purposes, GCH is true for ordinary mathematics in the same way that we can say that CH holds for all Borel sets? If not, why not? $\endgroup$ – Thomas Benjamin Apr 12 '14 at 8:47
  • $\begingroup$ @ThomasBenjamin I think that the theory we obtain from strong set theoretic assumptions (such as assuming the existence of large cardinals, or strong reflection principles) fits better with the intuitions we have developed in the last century or so. These assumptions contradict the axiom of constructibility. We have been doing number theory for millennia, and set theory for less than a century an a half, so it seems premature to conclude anything about the set theoretic universe from intuitions developed in a theory where the infinite did not play any role. (Cont.) $\endgroup$ – Andrés E. Caicedo Apr 12 '14 at 14:41
  • $\begingroup$ @ThomasBenjamin In particular, it seems to me we are currently just developing the tools that will allow us gain a reasonable intuition with respect to $\mathsf{GCH}$, and what we understand as "ordinary mathematics" is transforming as well, so it seems more prudent to wait. Besides, we have workarounds if we see that, say $\mathsf{CH}$ is reasonable in analysis (in the sense that all sets we actually use have the perfect set property), even if not in general: We can assume we are working in $L(\mathbb R)$ when doing classical analysis. (Cont.) $\endgroup$ – Andrés E. Caicedo Apr 12 '14 at 14:45
  • $\begingroup$ @ThomasBenjamin This is akin to assuming in physics that all functions are smooth, or even real analytic. We do not really "believe" this, but restricting the universe of discourse accordingly may make sense give our current level of understanding, with the expectation that the collection of relevant functions will likely grow with time. See here and here. (Cont.) $\endgroup$ – Andrés E. Caicedo Apr 12 '14 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.