117
$\begingroup$

Ten years ago, when I studied in university, I had no idea about definable numbers, but I came to this concept myself. My thoughts were as follows:

  • All numbers are divided into two classes: those which can be unambiguously defined by a limited set of their properties (definable) and those such that for any limited set of their properties there is at least one other number which also satisfies all these properties (undefinable).
  • It is evident that since the number of properties is countable, the set of definable numbers is countable. So the set of undefinable numbers forms a continuum.
  • It is impossible to give an example of an undefinable number and one researcher cannot communicate an undefinable number to the other. Whatever number of properties he communicates there is always another number which satisfies all these properties so the researchers cannot be confident whether they are speaking about the same number.
  • However there are probability based algorithms which give an undefinable number as a limit, for example, by throwing dice and writing consecutive numbers after the decimal point.

But the main question that bothered me was that the analysis course we received heavily relied on constructs such as "let $a$ be a number such that...", "for each $s$ in the interval..." etc. These seemed to heavily exploit the properties of definable numbers and as such one can expect the theorems of analysis to be correct only on the set of definable numbers. Even the definitions of arithmetic operations over reals assumed the numbers are definable. Unfortunately one cannot take an undefinable number to bring a counter-example just because there is no example of undefinable number. How can we know that all of those theorems of analysis are true for the whole continuum and not just for a countable subset?

$\endgroup$
16
  • 45
    $\begingroup$ I just wrote a long answer to this question, but it was closed just as I was about to click submit. Can we re-open please? I think that there are a number of very interesting issues here. $\endgroup$ Oct 29, 2010 at 12:48
  • 5
    $\begingroup$ Meta thread: tea.mathoverflow.net/discussion/729/… . I have also voted to reopen. $\endgroup$ Oct 29, 2010 at 13:07
  • 47
    $\begingroup$ I disagree with the continuing votes to close. The topic of definability is mathematically rich and forms the basis of huge parts of model theory, particularly where it connects with algebra and algebraic geometry, such as in the deep work of o-minimality. In the set-theoretic context, various technical meta-mathematical issues become prominent. The question is well-motivated, sincere and has mathematically interesting answers. $\endgroup$ Oct 30, 2010 at 22:43
  • 8
    $\begingroup$ In particular, I can imagine further technical answers arguing the line that in a model of $V=HOD$, the definable objects indeed form an elementary substructure of the universe, fulfilling the OPs observation that statements of analysis can be viewed as ultimately about definable objects. $\endgroup$ Oct 30, 2010 at 22:43
  • 7
    $\begingroup$ Similar issues with definability lay at the heart of this MO question: mathoverflow.net/questions/34710/… $\endgroup$ Oct 30, 2010 at 23:27

4 Answers 4

235
$\begingroup$

The concept of definable real number, although seemingly easy to reason with at first, is actually laden with subtle metamathematical dangers to which both your question and the Wikipedia article to which you link fall prey. In particular, the Wikipedia article contains a number of fundamental errors and false claims about this concept.   (Update, April 2018: The Wikipedia article, Definable real numbers, is now basically repaired and includes a link to this answer.)

The naive treatment of definability goes something like this: In many cases we can uniquely specify a real number, such as $e$ or $\pi$, by providing an exact description of that number, by providing a property that is satisfied by that number and only that number. More generally, we can uniquely specify a real number $r$ or other set-theoretic object by providing a description $\varphi$, in the formal language of set theory, say, such that $r$ is the only object satisfying $\varphi(r)$.

The naive account continues by saying that since there are only countably many such descriptions $\varphi$, but uncountably many reals, there must be reals that we cannot describe or define.

But this line of reasoning is flawed in a number of ways and ultimately incorrect. The basic problem is that the naive definition of definable number does not actually succeed as a definition. One can see the kind of problem that arises by considering ordinals, instead of reals. That is, let us suppose we have defined the concept of definable ordinal; following the same line of argument, we would seem to be led to the conclusion that there are only countably many definable ordinals, and that therefore some ordinals are not definable and thus there should be a least ordinal $\alpha$ that is not definable. But if the concept of definable ordinal were a valid set-theoretic concept, then this would constitute a definition of $\alpha$, making a contradiction. In short, the collection of definable ordinals either must exhaust all the ordinals, or else not itself be definable.

The point is that the concept of definability is a second-order concept, that only makes sense from an outside-the-universe perspective. Tarski's theorem on the non-definability of truth shows that there is no first-order definition that allows us a uniform treatment of saying that a particular particular formula $\varphi$ is true at a point $r$ and only at $r$. Thus, just knowing that there are only countably many formulas does not actually provide us with the function that maps a definition $\varphi$ to the object that it defines. Lacking such an enumeration of the definable objects, we cannot perform the diagonalization necessary to produce the non-definable object.

This way of thinking can be made completely rigorous in the following observations:

  • If ZFC is consistent, then there is a model of ZFC in which every real number and indeed every set-theoretic object is definable. This is true in the minimal transitive model of set theory, by observing that the collection of definable objects in that model is closed under the definable Skolem functions of $L$, and hence by Condensation collapses back to the same model, showing that in fact every object there was definable.

  • More generally, if $M$ is any model of ZFC+V=HOD, then the set $N$ of parameter-free definable objects of $M$ is an elementary substructure of $M$, since it is closed under the definable Skolem functions provided by the axiom V=HOD, and thus every object in $N$ is definable.

These models of set theory are pointwise definable, meaning that every object in them is definable in them by a formula. In particular, it is consistent with the axioms of set theory that EVERY real number is definable, and indeed, every set of reals, every topological space, every set-theoretic object at all is definable in these models.

  • The pointwise definable models of set theory are exactly the prime models of the models of ZFC+V=HOD, and they all arise exactly in the manner I described above, as the collection of definable elements in a model of V=HOD.

In recent work (soon to be submitted for publication), Jonas Reitz, David Linetsky and I have proved the following theorem:

Theorem. Every countable model of ZFC and indeed of GBC has a forcing extension in which every set and class is definable without parameters.

In these pointwise definable models, every object is uniquely specified as the unique object satisfying a certain property. Although this is true, the models also believe that the reals are uncountable and so on, since they satisfy ZFC and this theory proves that. The models are simply not able to assemble the definability function that maps each definition to the object it defines.

And therefore neither are you able to do this in general. The claims made in both in your question and the Wikipedia page on the existence of non-definable numbers and objects, are simply unwarranted. For all you know, our set-theoretic universe is pointwise definable, and every object is uniquely specified by a property.


Update. Since this question was recently bumped to the main page by an edit to the main question, I am taking this opportunity to add a link to my very recent paper "Pointwise Definable Models of Set Theory", J. D. Hamkins, D. Linetsky, J. Reitz, which explains some of these definability issues more fully. The paper contains a generally accessible introduction, before the more technical material begins.

$\endgroup$
38
  • 30
    $\begingroup$ @Anixx: No, this is not what Joel was saying. He did not say that it is consistent to "postulate in ZFC that undefinable numbers do not exist". What he was saying was that ZFC cannot even express the notion "is definable in ZFC". And no, this has absolutely nothing to do with constructivism (also please note that even in constructivism uncountable means "not countable", whereas you stated that it means "no practical enumeration" whatever that might mean). $\endgroup$ Oct 29, 2010 at 14:50
  • 41
    $\begingroup$ Joel made a very fine answer, please study it carefully. Joel states that there are models of ZFC such that every element of the model is definable. This does not mean that inside the model the statement "every element is definable" is valid. The statement is valid externally, as a meta-statement about the model. Internally, inside the model, we cannot even express the statement. $\endgroup$ Oct 29, 2010 at 15:13
  • 10
    $\begingroup$ This is off-topic, but: it makes no sense to claim that "constructivist continuum is countable in ZFC sense". What might be the case is that there is a model of constructive mathematics in ZFC such that the continuum is interpreted by a countable set. Indeed, we can find such a model, but we can also find a model in which this is not the case. Moreover, any model of ZFC is a model of constructive set theory. You see, constructive mathematics is more general than classical mathematics, and so in particular anything that is constructively valid is also classically valid. $\endgroup$ Oct 29, 2010 at 15:15
  • 9
    $\begingroup$ A minor technical comment on the first bullet point in Joel's answer: To use the minimal transitive model, one needs to assume that ZFC has well-founded models, not just that it's consistent. The main claim there, that there is a pointwise definable model of ZFC, is nevertheless correct on the basis of mere consistency, essentially by the second bullet point plus the consistency of V=HOD relative to ZFC. $\endgroup$ Oct 29, 2010 at 16:44
  • 7
    $\begingroup$ Following the comment of Andreas got me thinking: as a topos theorist (which I am not) I would look at the syntactic model of ZFC (the "Lindenabaum algebra") in order to get to both the minimal model and the one in which every set is definable. But I suppose set theorists don't like that kind of model too much because they prefer transitive models that are "really made of sets". Is that so? Historically, where does this tendency come from? $\endgroup$ Oct 29, 2010 at 21:02
19
$\begingroup$

You can also talk about arithmetically definable real numbers: those for which the Dedekind cut of rationals is of the form: $$\{m/n: \forall x_1 \exists x_2 \ldots \forall x_{k-1} \exists x_k\, p(m,n,x_1,\ldots,x_k)=0\},$$ where the $x$'s range over integers, and $p$ is a polynomial with integer coefficients.

Then on this definition of definability: $e$ and $\pi$ and all the familiar reals are definable. Only countably many numbers are definable. There must be other real numbers which are undefinable. And it all makes sense, and is even provably consistent, in ordinary set theory.

A standard reference for this way of thinking is the system $ACA_0$ in Simpson's Subsystems of Second-Order Arithmetic.

The cost of this metamathematical simplicity is a small change to the mathematics: any definable bounded sequence of reals has a definable least upper bound, but an uncountable definable set of reals may not. Feferman's notes on Predicative Foundations of Analysis show how to develop standard analysis on this basis. If we changed mathematics as taught in universities to be based on predicative analysis, few undergraduates or people outside the math department would notice much difference.

$\endgroup$
7
  • $\begingroup$ Interesting. What are polynomials for $e$ and $\pi$? $\endgroup$ Sep 1, 2017 at 12:25
  • 2
    $\begingroup$ @GeraldEdgar, start from $e$ as $$\{m/n: \exists x\exists y\exists z\ y=(1+x)^x\ \&\ z=x^x\ \&\ m/n<y/z\}.$$ The rest is standard coding, of which the only difficult part is using Godel's $\beta$ lemma to encode lists verifying $y=(1+x)^x$ and $z=x^x$. The easy references are from the use of these techniques in Hilbert's 10th problem, e.g. section 1 here: maa.org/sites/default/files/pdf/upload_library/22/Ford/… $\endgroup$
    – user44143
    Sep 1, 2017 at 13:45
  • $\begingroup$ In more detail, using 13 positive-integer variables: $$\newcommand{\e}{\exists} e = \{m/n: \e a \e b \e c \e d\, \e q \e r \e s \e t \e u\, \forall v \e w \e x \e y\\ (mc-nb + d)^2+\\ (q - (1+r)s - c)^2+ (q - (1+ra)t - b)^2+ (r - u - b)^2+\\ (v + 1 - w - a)^2 ((q - wa - (1+(v+1)r)x)^2+(q - w(1+a) - (1+vr)y)^2)=0 \}$$ $\endgroup$
    – user44143
    Sep 4, 2017 at 9:17
  • 2
    $\begingroup$ @ZachTeitler, you can replace $x^y=z$ with its Diophantine definition (again, as in the references on Hilbert’s 10th problem), and that will convert these definitions from exponential polynomials to ordinary polynomials. $\endgroup$
    – user44143
    Apr 30, 2018 at 20:29
  • 3
    $\begingroup$ @ZachTeitler It's not saying $x^x$ or $(1 + x)^x$ are polynomials, rather that for the expressions $y = (1 + x)^x$ and $z = x^x$ there exist polynomial expressions (using extra variables) that are satisfiable if and only if the original ones are (equisatisfiable). $\endgroup$
    – orlp
    Jul 8, 2020 at 18:16
17
$\begingroup$

While you cannot define undefinable numbers, you can quantify over all real numbers, whether or not they are definable. "Let $a$ be a number" does not assume that $a$ is definable, but is merely a shorthand for quantification over $a$. The theorems in analysis are safe.

Definability is a subtle issue that was only partially dealt with in Joel David Hamkins excellent answer. $(V,∈)$-definability (as a predicate on sets) is $(V,∈)$-definable if and only if every ordinal is already $(V,∈)$-definable (in which case, $(V,∈)$-definability coincides with ordinal definability; a set is $(V,∈)$-definable iff it is first order parameter-free definable in $(V,∈)$). Intuitively, not every ordinal is $(V,∈)$-definable, and this can be formalized and proved by adding a $(V,∈)$ satisfaction relation Tr and replacement axiom schema for formulas involving Tr (this is not conservative over ZFC and does not hold in the minimal transitive model of ZFC). However, every consistent theory T extending ZF has a model (called definable ordinal model or Paris model) in which every ordinal is definable; for a complete T with a well-founded model, all Paris models are well-founded. This applies even if T proves that the set of ordinal definable real numbers is countable. It also applies to theories with Tr by using $(V,∈,\mathrm{Tr})$ definability, and analogously with other extensions.

In any case, we can speak of existence of $(V,∈)$-definable examples without ambiguity since there is a $(V,∈)$-definable set satisfying $P$ iff there is an ordinal definable set satisfying $P$ (and analogously if $P$ has parameters and we allow definability with those parameters). A set is ordinal definable iff it is definable in some $V_κ$. Now, V=HOD is $Π^V_2$ conservative over ZFC (and over ZFC + $φ$ for a $Σ^V_2$ $φ$), so even if the proofs assumed definability (which they do not), the theorems (which for analysis and 'ordinary mathematics' are all $Π^V_2$) would still be correct.

That does not mean that the theorems have definable examples. In second order arithmetic (where the examples are real numbers), existence of definable examples holds assuming projective determinacy (and for $Σ^1_2$ predicates in just ZFC), but existence of ordinal definable nonmeasurable sets (and likely other 'non-well-behaved' sets of reals) is independent of ZFC and ordinary large cardinal axioms.

$\endgroup$
2
$\begingroup$

It might be of some small interest to note the following result of Kenneth McAloon (from his paper, "Consistency Results About Ordinal Definability", Annals of Mathematical Logic, Vol. 2,No. 4 (1971) 449-467--note that he denotes as '$K$ = $V$' the statement "Every set is ordinal-definable" so his result also holds for $HOD$ as well):

Theorem. If $ZF$ is consistent, then so are

(i) $ZF$ + $GCH$ + $V$ = $OD$ + $V$ $\neq$ $L$;

(ii) $ZF$ + $V$ = $OD$ + $2^{\aleph_0}$ $\neq$ $\aleph_1$. [Since Andres is correct in pointing out that McAloon abbreviates "Every set is ordinal-definable" ($V$ = $OD$) as '$V$ = $K$' and also notes that "...if $V$ = $OD$ then $V$ = $HOD$", I wil replace McAloon's $V$ = $K$ with $V$ = $OD$ in order to strike an uneasy balance between directly quoting from a Source and paraphrasing the Source]

Since one can replace $V$ = $OD$ with $V$ = $HOD$, the models of these theories might be interesting universes for analysts to study in case mathematical practice should ever find use for definable non-constructible sets.

$\endgroup$
12
  • 2
    $\begingroup$ You misquoted the result. Again, the confusion is identifying a model with a theory. $\endgroup$ Aug 31, 2017 at 13:06
  • 2
    $\begingroup$ (Using $K $ is unfortunate here, since the letter now has a different, technical meaning.) $\endgroup$ Aug 31, 2017 at 13:08
  • 1
    $\begingroup$ (cont.) I can always re-edit. Thanks in advance for your help in this matter, it is always appreciated. $\endgroup$ Sep 1, 2017 at 3:44
  • 1
    $\begingroup$ $V=K$ makes no sense if $K$ is a statement. $\endgroup$ Sep 1, 2017 at 3:44
  • 1
    $\begingroup$ I also have the paper, in fact. What is written there is that "The proposition `Every set is ordinal-definable' is abbreviated ${\rm V} = {\rm K}$'' (p. 449). This is different in an essential way from what you wrote. $\endgroup$ Sep 1, 2017 at 3:51

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