Informally, a definable real number is a real number that can be uniquely specified by its description. The description may be expressed as a construction or as a formula of a formal language. For example, the positive square root of 2, 2 \displaystyle \sqrt 2 , can be defined as the unique positive solution to the equation x 2 = 2 \displaystyle x^2=2 , and it can be constructed with a compass and straightedge.
Different choices of a formal language or its interpretation give rise to different notions of definability. Specific varieties of definable numbers include the constructible numbers of geometry, the algebraic numbers, and the computable numbers. Because formal languages can have only countably many formulas, every notion of definable numbers has at most countably many definable real numbers. However, by Cantor's diagonal argument, there are uncountably many real numbers, so almost every real number is undefinable.
definable
The second-order language of arithmetic is the same as the first-order language, except that variables and quantifiers are allowed to range over sets of naturals. A real that is second-order definable in the language of arithmetic is called analytical.
A real number a \displaystyle a is first-order definable in the language of set theory, without parameters, if there is a formula φ \displaystyle \varphi in the language of set theory, with one free variable, such that a \displaystyle a is the unique real number such that φ ( a ) \displaystyle \varphi (a) holds.[2] This notion cannot be expressed as a formula in the language of set theory.
Each set model M \displaystyle M of ZFC set theory that contains uncountably many real numbers must contain real numbers that are not definable within M \displaystyle M (without parameters). This follows from the fact that there are only countably many formulas, and so only countably many elements of M \displaystyle M can be definable over M \displaystyle M . Thus, if M \displaystyle M has uncountably many real numbers, one can prove from "outside" M \displaystyle M that not every real number of M \displaystyle M is definable over M \displaystyle M .
This argument becomes more problematic if it is applied to class models of ZFC, such as the von Neumann universe. The assertion "the real number x \displaystyle x is definable over the class model N \displaystyle N " cannot be expressed as a formula of ZFC.[3][4] Similarly, the question of whether the von Neumann universe contains real numbers that it cannot define cannot be expressed as a sentence in the language of ZFC. Moreover, there are countable models of ZFC in which all real numbers, all sets of real numbers, functions on the reals, etc. are definable.[3][4]
The definable closure of S is denoted dcl(S) and the algebraic closure is denoted acl(S). Sometimes we want dcl(S) and acl(S) to be subsets of M, in which case we take dcl(S) and acl(S) to be the sets of singletons in the definable closure and algebraic closure of S, respectively. There is not a very big distinction, because it turns out that a tuple a is in dcl(S) or acl(S) if and only if each coordinate of a is in dcl(S) or acl(S), respectively.
Now holds. And for every tuple c from M, the set is either a singleton or empty. Therefore is the graph of (the transpose of) a 0-definable (partial) function f such that a = f(b).
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?
The concept of definable real number, although seeminglyeasy to reason with at first, is actually laden with subtlemetamathematical dangers to which both your question andthe Wikipedia article to which you link fall prey. Inparticular, the Wikipedia article contains a number offundamental 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.)
But this line of reasoning is flawed in a number of waysand ultimately incorrect. The basic problem is that thenaive definition of definable number does not actuallysucceed as a definition. One can see the kind of problemthat arises by considering ordinals, instead of reals. Thatis, let us suppose we have defined the concept of definableordinal; following the same line of argument, we would seemto be led to the conclusion that there are only countablymany definable ordinals, and that therefore some ordinalsare not definable and thus there should be a least ordinal$\alpha$ that is not definable. But if the concept ofdefinable ordinal were a valid set-theoretic concept, thenthis would constitute a definition of $\alpha$, making acontradiction. In short, the collection of definableordinals either must exhaust all the ordinals, or else notitself be definable.
The point is that the concept of definability is asecond-order concept, that only makes sense from anoutside-the-universe perspective. Tarski's theorem on thenon-definability oftruthshows that there is no first-order definition that allowsus a uniform treatment of saying that a particularparticular formula $\varphi$ is true at a point $r$ andonly at $r$. Thus, just knowing that there are onlycountably many formulas does not actually provide us withthe function that maps a definition $\varphi$ to the objectthat it defines. Lacking such an enumeration of thedefinable objects, we cannot perform the diagonalizationnecessary to produce the non-definable object.
If ZFC is consistent, then there is a model of ZFC inwhich every real number and indeed every set-theoreticobject is definable. This is true in the minimaltransitive model of set theory, by observing that thecollection of definable objects in that model is closedunder the definable Skolem functions of $L$, and hence byCondensation collapses back to the same model, showingthat in fact every object there was definable.
More generally, if $M$ isany model of ZFC+V=HOD, then the set $N$ of parameter-freedefinable objects of $M$ is an elementary substructure of$M$, since it is closed under the definable Skolemfunctions provided by the axiom V=HOD, and thus everyobject in $N$ is definable.
These models of set theory are pointwise definable,meaning that every object in them is definable in them by aformula. In particular, it is consistent with the axioms ofset theory that EVERY real number is definable, and indeed,every set of reals, every topological space, everyset-theoretic object at all is definable in these models.
In these pointwise definable models, every object isuniquely specified as the unique object satisfying acertain property. Although this is true, the models alsobelieve that the reals are uncountable and so on, sincethey satisfy ZFC and this theory proves that. The modelsare simply not able to assemble the definability functionthat 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 Wikipediapage on the existence of non-definable numbers and objects,are simply unwarranted. For all you know, our set-theoreticuniverse is pointwise definable, and every object isuniquely specified by a property.
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.
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.
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.
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.
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): 2ff7e9595c
Comments