![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
The formula φ(x) is not restricted to first-order statements.
There are restrictions on φ, though, thaks to Berry's paradox. Should this be mentioned here?
Good point; yes, I think we should mention Berry's paradox and explain which φ's are allowed. Which ones are allowed? --AxelBoldt
Formally, a real number a is called definable if there is some logical formula φ(x) in set theory which contains a single free variable x and such that one can prove from the Zermelo-Fraenkel-Choice set theory axioms that a is the unique real number which makes the statement φ(a) true.
A nonexaustive list of problems with this page, as of 20:20, 19 July 2005 (UTC).
I've taken a first cut at a rewrite, to address the issues above. It may be viewed at User:Trovatore/Sandbox/Definable number.
Some things to note:
-- Trovatore 01:43, 20 July 2005 (UTC)
Having heard no objection, I have copied the rewrite to the main page. Comments solicited. -- Trovatore 05:10, 21 July 2005 (UTC)
Here's the proof that it's consistent with ZFC that there are only countably many OD reals. Someone may want to check it (or finding a ref would be even better).
Start with L, in which every real (in fact every set) is OD. Now force to collapse (the forcing conditions are finite partial functions from to ).
Any real that's OD in the extension is OD in the ground model, by homogeneity of the forcing, but in the extension, there are only countably many reals of L, thus only countably many OD reals.
(Actually the argument is more general; you don't have to start with L, or a model of CH, or a model in which all reals are OD. Just collapse to be countable using finite conditions, and in the extension there will be only countably many ground-model reals, and every OD real will be in the ground model. Therefore the extension will have only countably many OD reals. This establishes the consistency of only countably many OD reals with large cardinals.) -- Trovatore 02:59, 22 July 2005 (UTC)
You state that most reals are not definable. I'd like you to give me one example. -- Fermatprime 01:14, 5 September 2005 (UTC)
Definable_number#Notion_does_not_exhaust_.22unambiguously_described.22_numbers makes a reference to Gödel numbers of defining formulas - but you need actual expansions of the numbers (with respect to some basis - binary, decimal or other) to use the Cantor's diagonal argument. There is a fundamental problem if we try to construct the set of ALL definable real numbers. Even if we assume that there are infinitely many orders of defining formulas (but countably many), we could take the union of sets of definable reals of all orders and one may expect to obtain the set of all definable real numbers. But if we assume that we have this set (with an ordering), then by the Cantor's diagonal argument we can obtain a definable number that does not belong to the set. This is a contradiction with our initial assumption that we had the set of all definable reals. Does anybody have a non-trivial solution of this paradox? (The trivial solution is that the set of all definable real numbers does not exist). HTG 3:48, Sept. 27th, 2006.
But what about the set of all definable reals, as suggested above? HTG 27 Sept. 2006
This is the problem with this page as I see it:
This is the most correct definition of definable number I can conceive:
Obviously, this definition is unformalisable due to Godel's theorem. But it is I think the true one.
Another definition might be:
That perfectly captures in my view the concept of a definable number, but by it is inexpressible in a formal language, since Godel's theorem does not permit a formal language to quantify over every possible formal languages and every possible model. Also, I think its informalizable because we won't not just any old model M but the "correct" one, a notion which I don't believe is formalizable either.
--SamKat
All _real numbers_ are definable and countable --- just pick any irrational number (say, pi) which is definable and any real number can be defined by how it differs digit-for-digit with pi with their place-value-positional-numeral-system (say, decimal or binary) expansion point aligned.
First, consider: 1234567890123… --- this is not an integer (hence, not a rational nor real number) because integers have a finite count of digits!
Next, consider: 1234567890.123… --- this is now a “real number” that lies between 1234567890.1230 and 123456789.1239. Or is it? What made it a “real number”? --- the decimal point!? Well, does the decimal point sufficiently make it a “real number”? If it is a “real number” then is it equal to 1234567890.1230, 1234567890.1231, 1234567890.1232, …, or 123456789.1239? Well, let us not forget 1234567890.12301, 1234567890.12302, …, 1234567890.12309, 1234567890.123011, 1234567890.123012, …, etc., etc., etc.
Isn’t 1234567890.123… actually an “interval” and not a “real number point”? Again, what makes 0.5, square root of 2, e and pi real numbers? --- all their digits are well-defined (so they are definable --- that is, they are constants)! Thus, real numbers are constants! But what is an “interval”? Well, 1234567890.123… could really be defined as 1234567890.1230 <= x <= 1234567890.1239. Aha! The notorious “x” symbol! --- that is, 1234567890.123… is in fact an _interval_ --- that is, 1234567890.123… is a _variable_ --- that is, 1234567890.123… is not a constant --- that is, 1234567890.123… is not a true real number!!!
Every one in the mathematical world agrees that, say, the 5th decimal digit of pi is “9” but what is the 5th decimal digit of 1234567890.123…? If you can answer this last question then you can truly define 1234567890.123… (of course, that is if you could also answer what its nth digit is for any natural number n) --- thus, what makes a sequence of decimal digits with a decimal point a real number is that _all_ the digits are definable! Thus, “Undefinable real number” is a _self-contradiction_! --- so is “Cantor’s diagonal argument” untenably used to “prove” the uncountability of real numbers and many other flawed claims of “modern mathematics” (please read my Wikipedia discussion notes on this article as well as on “Cantor’s theorem”, “Cantor’s first uncountability proof”, “Ackermann’s function”, and “Entscheidungsproblem”)
Cantor’s anti-diagonal “number”, Borel’s “number”, Chaitin’s “number”, etc. are _variables_ (or, at best, they are arbitrary constants) whose claim for being “real numbers” merely emanates from their prefixed decimal point. They have the “form” of a fractional real number (that is, they lie between 0 and 1 only because of the prefixed decimal point) but they do not have “substantive” information of a true “real number” (a constant!) --- only that of an interval --- to convey.
BenCawaling@Yahoo.com [09 December 2005] BenCawaling 06:20, 28 March 2006 (UTC)
The section Ian Maxwell edited probably could use some touching up (in particular, getting rid of "in the sense of this article") but the edit I reverted introduced a syntax/semantics confusion. Objects are definable "over structures", not "in theories"; it doesn't make sense to ask if a particular object is definable in a theory. Given an undefinable object, how do you ask if a particular theory can define it? The theory can't even talk about it. -- Trovatore 21:01, 15 December 2005 (UTC)
This looks a lot like original research WP:NOR to me. The article even says “This should not be understood to be standard terminology.” The article also has some questionable content, such as:
CMummert 20:06, 13 June 2006 (UTC)
While reading the article a got an idea like this:
The set of definable reals(,complex numbers,and probably even R^n) is countable, therefore there exists a bijection to natural numbers. Now you can use induction to prove theorems about definable numbers. Of course they do not apply to all reals but will still apply to almost every number you will ever use.
Im guessing it would be a bit hard to actually construct a bijection that is useful, but is there something else wrong with the idea? 85.156.185.105 01:39, 31 August 2006 (UTC)
FYI, I have tagged this article with the Original Research tag. While it's an interesting topic, the article appears to be primarilly original research conducted by the primary authors. The article even flat out says in the introductiom that the term "Definable number" is not a standard mathematical term.
So basically as fun a topic as this is, the entire article appears to not be based on external, independent, verifiable references. This is a major problem, because if the article can not back up its definitions and terms using external references it could be ultimately deleted or moved to another website as original research. Dugwiki 18:41, 13 November 2006 (UTC)
FYI, someone tried to remove the unreferenced tag on this article. Note that the only reference provided is a paper discussing Computable numbers that does not specifically go into topics regarding definable numbers, as is mentioned by some of the posters in this thread above. So at the moment, the unreferenced tag still applies. Dugwiki 20:46, 13 November 2006 (UTC)
Anyone who looks on google scholar will see the term "definable real number" in many published research papers. If one were to wonder which to cite here, my guess is one of the books on computable real functions would be the best for present purposes. It hasn't really made it to the textbook level, so that's probably the reason for this hand-wringing. And, given that we have a concept of the reals as a complete ordered field, and also a concept of first-order definability, why is this so problematic? (And, note that "definable natural number" is found in lots of textbooks.) Michael Hardy 21:11, 13 November 2006 (UTC)
Given the fact that there may be many different models of ZFC, it seems to me that we should require that the formula defining a real number be absolute, i.e. independent of the model. That is, the formula would define the same real number in each model. Otherwise, the real number defined could be both larger than and smaller than the same rational number depending on which model it is in, or defined in some models and undefined in others.
If we define definable real numbers that way, then they would be the intersection of the set of real numbers with the minimal model of ZFC.
JRSpriggs 07:08, 14 November 2006 (UTC)
Well yeah, this is clearly Original "Research". Which is why I am putting it here in the talk rather than in the article. But it is fun to speculate about it.
Expanding my second definition -- a definable real number, r, is given by a pair of parameterless predicates φl(q) and φu(q) which satisfy these conditions:
The difference between my first and second definitions is that in the second I would allow a particular definition to have a value in one model but no value in another. However, any super-model of one which has the real in question should also contain it.
With this second definition, the diagonalization argument would fail. You could diagonalize over one model in a super-model which contains it as a set. But the resulting real number would depend on the choice of the original model. So there is no inconsistency with a notion of definable real number which is model dependent, as this one is.
JRSpriggs 08:04, 15 November 2006 (UTC)
I think the part of the article mentioning definable complex numbers is mistaken. I am familiar with the phenomenon that, having determined that there are two roots of the polynomial , there is no way, short of invoking the Axiom of Choice, to select one to be labeled ---the two roots share all properties. (If we took every math book in the world and replaced every occurence of "" with "", they would all remain precisely as accurate as they already were.) The upshot of this is that no nonreal complex number is first-order definable.
I'd rather wait for comment before altering the article to reflect this, since I have made inaccurate edits in the past. I'll give a week or so, since the error isn't serious. -- Ian Maxwell ( talk) 18:44, 8 April 2008 (UTC)
Another way to think about this: Usually when we start talking about the complex numbers, we ask the following:
For your information, the article fr:Nombre définissable has been deleted today, due to the same problems you mentioned here. We'll possibly replace it with an article focused on Borel's "inaccessible numbers". -- Michel421 ( talk) 20:41, 28 February 2010 (UTC)
Kuratowski called "inaccessible numbers" what we know now as "inaccessible cardinals" ; but Borel's "inaccessible numbers" are related to probabilities, etc... Here's a review : http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.bams/1183518025. -- Michel421 ( talk) 20:37, 1 March 2010 (UTC)
What can be said about the relation of definable numbers to elements of the ring of periods of Zagier? Tkuvho ( talk) 16:08, 29 July 2010 (UTC)
I think it's a good thing that Emil has opened this can of worms, because this article has been hanging around for a long time with bad problems and something needs to be done about it. However I don't agree with his solution, as I've explained in the edit summary and at the refdesk.
There is no doubt that there are only countably many reals that are first-order definable in the language of set theory; that is not the problem. It's true that the argument cannot be formalized in ZFC (nor even stated in the language of ZFC), but it is nevertheless completely solid.
The biggest problem is that it's not clear the article should exist at all. Before I got to it, quite some time ago, it was not talking about first-order definability in LST; it was talking about reals that are definable period, in any way. But that's not really a mathematical notion at all. Putative sources were things like the Turing paper, which I think Emil quite properly objected to; they would point out that such and such a real was definable, but would not attempt to demarcate how a real could fail to be definable.
So I "fixed" it so that it at least talked about a definite thing, first-order definability in LST. But in addition to the problem of sourcing it (that kind of definability isn't very useful or particularly well-studied), it's not clear at all that that concept, if it deserves an article, should appear under the title definable real number.
I don't know what to do about all this; I've been scratching my head over it for years. We should talk about it and figure it out. -- Trovatore ( talk) 17:18, 8 December 2010 (UTC)
I think the current state of this article is likely create widespread confusion about "definable real numbers" rather than widespread understanding of them. The article seems to be a popular read for people who are (naturally enough) interested in "cool" logic things, but at the same time I think the article tends to mislead them because the subtleties in the assumption that we are looking at def inability over the standard model only. Most of the arguments underlying the article are, as far as I know, not really expounded anywhere.
Moreover, as Joel Hamkins points out in this MathOverflow thread , the issue is much more subtle than this article currently suggests. He also has a set of slides on the topic.
I feel somewhat strongly we should rewrite this article to be about definability in general, rather than about definability over the standard model. In the short term, we could even use Hamkins' posts as a source, along with some set theory texts. In the longer term I think Hamkins is going to publish the results, although he doesn't seem to post preprints. This is not to say our article should espouse Hamkins' POV in every respect. But the issue that definability cannot be expressed in set theory should not be glossed over like it is at the moment. — Carl ( CBM · talk) 14:48, 30 March 2011 (UTC)
--- I am confused by the apparently-necessary assumption of "set theory" at the beginning of this article. Lost after the first sentence, I retreated to my ancient number theory book Hardy and Wright 2000 (1st published 1938) chapter XI Approximations of Irrationals by Rationals (pages 154-177, ending with proofs that pi and e are transcendental). I sought out, in particular, pages 159ff to remind myself of the definitions of algebraic and transcendental numbers (why is this word missing from the article?), the definition of "orders of approximation" by use of rationals, and in particular theorems 189: "The aggregate of algebraic numbers is enumerable", theorem 190: "Almost all real numbers are transcendental", theorem 191 "Any real algebraic number of degee n is not approximable to any order greater than n", and theorem 192 "a number defined by a sufficiently rapid sequence of rational approximations is necessarily transendental". I'm perfectly comfortable with, and think in terms of, the notion of "natural number" and a "theory" such as that of "arithmetic" (requiring notions of 0, successor, sum and product) applied to a "system" containing a computational machine. So do I have to assume, and know, set theory to understand the Hardy and Wright chapter? Isn't simple old-fashioned number theory good enough? True, Hardy and Wright do invoke the notion of measure, as in "the aggregate of real algebaric numbers has measure 0" but this obscure-to-me notion doesn't seem necessary to their proof of theorem 189. Bill Wvbailey ( talk) 17:05, 31 March 2011 (UTC)
Regarding the recent edits [3], although the text is not perfect, I think it is an improvement on the previous version. In general, the countability argument works if we have a (set) model of ZFC, but it requires much more clarification otherwise. I would prefer not to go back to the previous statement which just claims that not every real is definable via a countability argument.
For people coming from a more realist position, the key point to emphasize, I believe, is Tarski's theorem on the undefinability of truth. This means that we must examine definability from outside V, rather than from inside V. On the other hand, there are models of ZFC where every real is definable, and where every real is not definable. If we cannot find a clear statement of what property on V would be required to show (from outside) that not every real is definable, then I think we should leave that out.
I am going to try editing the article in some other ways, based on my comments from 2011 above. — Carl ( CBM · talk) 14:18, 5 March 2016 (UTC)
Ok, after thinking about this some more I'm back to the opinion that the denial of the existence of undefinable numbers is crankery, a sophisticated variation of Cantor-diagonal-denial.
It is a theorem in ZFC that there are uncountably many real numbers. It is true in all models of ZFC, regardless of whether those models are themselves (externally) countable.
Likewise, it is a theorem in ZFC that, for any function f from strings to real numbers (modeling your favorite choice of what it means to be definable), the image of f is countable and therefore there exist real numbers not defined by f. Again, this has nothing to do with model theory, and is true in all models of ZFC, regardless of whether the models are countable.
We might want to clarify that in this argument, by "countable" we mean countable within ZFC rather than in some chosen model of ZFC, but that clarification would be tautological (it is never interesting to talk about whether an object within ZFC is externally-countable, because in a countable model the answer is always yes). — David Eppstein ( talk) 20:47, 5 March 2016 (UTC)
The comment(s) below were originally left at Talk:Definable real number/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.
Maybe mid, but we are trying to lower importance/priority ratings. (Please replace this by a more helpful comment.) Geometry guy 21:47, 1 June 2007 (UTC) |
Last edited at 21:47, 1 June 2007 (UTC). Substituted at 01:59, 5 May 2016 (UTC)
We can find an undefinable real number in this way. (Although undefinable numbers cannot be found by anyone in the future, since they cannot be described with language)
Step 1: Make a finite English sentence of all definable numbers (e.g. 7 is "seven", is "two thirds", is "the square root of 2"), the sentence must uses only ASCII characters.
Step 2: Regard the sentences as base 95 numbers, we regard the character with ASCII code x as the digit x-32 (i.e. space character is the digit 0, "!" is the digit 1, "0" is the digit 16, "A" is the digit 33, "a" is the digit 65, etc. The digits are in the range [0, 94], since the ASCII code of the characters must be in the range [32, 126]) (Note that since the sentences are not start with space character, so the base 95 numbers are not started with the digit 0)
Then we can find an injective function f : D → N. (let D be the set of definable numbers)
Step 3: For n belong to N, if there is a definable number a such that f(a) = n, then we write such ns and as, if there is no such a, then we skip this n.
Step 4: Make a bijective function g : f(D) → N, if n is the mth smallest number in the range of f, then we let g(n) = m.
Step 5: Let the a such that gf(a) = 1 is a1, the a such that gf(a) = 2 is a2, the a such that gf(a) = 3 is a3, etc. Then the function gf : D → N, is also bijective.
Step 6: Use Cantor's diagonal argument to find a number not in the list of definable numbers: Write all definable numbers a1, a2, a3, ... in decimal, and we will find a new number b, first, let the integer part of b is 0 (i.e. 0 ≤ b < 1), second, if the m-th digit after the decimal point of am is 7, then we let the m-th digit after the decimal point of b is 4, otherwise, we let the m-th digit after the decimal point of b is 7. Thus, b ≠ am for any m, since the m-th digit after the decimal point of b and am are different, and b cannot be any definable number. Thus, this b is an undefinable number!!! — Preceding unsigned comment added by 101.9.132.67 ( talk) 13:58, 5 April 2017 (UTC)
A recent edit called my attention to this text:
Where does this come from? Is this really what Hamkins thinks? Informally, it's obvious nonsense. Every subcollection of a set is a set.
The only way I can see that this claim is at all defensible is if you're thinking formalistically; that is, you're making reference to the fact that you can't apply the
separation axiom to show the existence of such a set, because there's no first-order property that defines it. But then I don't see how you formulate the claim at all; there's no way to talk about the collection in the first place.
We really need to fix this. Right now it looks really bad and obviously nonsensical. Paging
User:CBM; we've had discussions in this neighborhood in the past. --
Trovatore (
talk) 21:11, 10 April 2017 (UTC)
"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." ( [5]) Boris Tsirelson ( talk) 21:41, 5 February 2018 (UTC)
Is a real number undefinable with respect to first-order formulae iff it's indiscernible? C7XWiki ( talk) 03:58, 2 March 2021 (UTC)
![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
The formula φ(x) is not restricted to first-order statements.
There are restrictions on φ, though, thaks to Berry's paradox. Should this be mentioned here?
Good point; yes, I think we should mention Berry's paradox and explain which φ's are allowed. Which ones are allowed? --AxelBoldt
Formally, a real number a is called definable if there is some logical formula φ(x) in set theory which contains a single free variable x and such that one can prove from the Zermelo-Fraenkel-Choice set theory axioms that a is the unique real number which makes the statement φ(a) true.
A nonexaustive list of problems with this page, as of 20:20, 19 July 2005 (UTC).
I've taken a first cut at a rewrite, to address the issues above. It may be viewed at User:Trovatore/Sandbox/Definable number.
Some things to note:
-- Trovatore 01:43, 20 July 2005 (UTC)
Having heard no objection, I have copied the rewrite to the main page. Comments solicited. -- Trovatore 05:10, 21 July 2005 (UTC)
Here's the proof that it's consistent with ZFC that there are only countably many OD reals. Someone may want to check it (or finding a ref would be even better).
Start with L, in which every real (in fact every set) is OD. Now force to collapse (the forcing conditions are finite partial functions from to ).
Any real that's OD in the extension is OD in the ground model, by homogeneity of the forcing, but in the extension, there are only countably many reals of L, thus only countably many OD reals.
(Actually the argument is more general; you don't have to start with L, or a model of CH, or a model in which all reals are OD. Just collapse to be countable using finite conditions, and in the extension there will be only countably many ground-model reals, and every OD real will be in the ground model. Therefore the extension will have only countably many OD reals. This establishes the consistency of only countably many OD reals with large cardinals.) -- Trovatore 02:59, 22 July 2005 (UTC)
You state that most reals are not definable. I'd like you to give me one example. -- Fermatprime 01:14, 5 September 2005 (UTC)
Definable_number#Notion_does_not_exhaust_.22unambiguously_described.22_numbers makes a reference to Gödel numbers of defining formulas - but you need actual expansions of the numbers (with respect to some basis - binary, decimal or other) to use the Cantor's diagonal argument. There is a fundamental problem if we try to construct the set of ALL definable real numbers. Even if we assume that there are infinitely many orders of defining formulas (but countably many), we could take the union of sets of definable reals of all orders and one may expect to obtain the set of all definable real numbers. But if we assume that we have this set (with an ordering), then by the Cantor's diagonal argument we can obtain a definable number that does not belong to the set. This is a contradiction with our initial assumption that we had the set of all definable reals. Does anybody have a non-trivial solution of this paradox? (The trivial solution is that the set of all definable real numbers does not exist). HTG 3:48, Sept. 27th, 2006.
But what about the set of all definable reals, as suggested above? HTG 27 Sept. 2006
This is the problem with this page as I see it:
This is the most correct definition of definable number I can conceive:
Obviously, this definition is unformalisable due to Godel's theorem. But it is I think the true one.
Another definition might be:
That perfectly captures in my view the concept of a definable number, but by it is inexpressible in a formal language, since Godel's theorem does not permit a formal language to quantify over every possible formal languages and every possible model. Also, I think its informalizable because we won't not just any old model M but the "correct" one, a notion which I don't believe is formalizable either.
--SamKat
All _real numbers_ are definable and countable --- just pick any irrational number (say, pi) which is definable and any real number can be defined by how it differs digit-for-digit with pi with their place-value-positional-numeral-system (say, decimal or binary) expansion point aligned.
First, consider: 1234567890123… --- this is not an integer (hence, not a rational nor real number) because integers have a finite count of digits!
Next, consider: 1234567890.123… --- this is now a “real number” that lies between 1234567890.1230 and 123456789.1239. Or is it? What made it a “real number”? --- the decimal point!? Well, does the decimal point sufficiently make it a “real number”? If it is a “real number” then is it equal to 1234567890.1230, 1234567890.1231, 1234567890.1232, …, or 123456789.1239? Well, let us not forget 1234567890.12301, 1234567890.12302, …, 1234567890.12309, 1234567890.123011, 1234567890.123012, …, etc., etc., etc.
Isn’t 1234567890.123… actually an “interval” and not a “real number point”? Again, what makes 0.5, square root of 2, e and pi real numbers? --- all their digits are well-defined (so they are definable --- that is, they are constants)! Thus, real numbers are constants! But what is an “interval”? Well, 1234567890.123… could really be defined as 1234567890.1230 <= x <= 1234567890.1239. Aha! The notorious “x” symbol! --- that is, 1234567890.123… is in fact an _interval_ --- that is, 1234567890.123… is a _variable_ --- that is, 1234567890.123… is not a constant --- that is, 1234567890.123… is not a true real number!!!
Every one in the mathematical world agrees that, say, the 5th decimal digit of pi is “9” but what is the 5th decimal digit of 1234567890.123…? If you can answer this last question then you can truly define 1234567890.123… (of course, that is if you could also answer what its nth digit is for any natural number n) --- thus, what makes a sequence of decimal digits with a decimal point a real number is that _all_ the digits are definable! Thus, “Undefinable real number” is a _self-contradiction_! --- so is “Cantor’s diagonal argument” untenably used to “prove” the uncountability of real numbers and many other flawed claims of “modern mathematics” (please read my Wikipedia discussion notes on this article as well as on “Cantor’s theorem”, “Cantor’s first uncountability proof”, “Ackermann’s function”, and “Entscheidungsproblem”)
Cantor’s anti-diagonal “number”, Borel’s “number”, Chaitin’s “number”, etc. are _variables_ (or, at best, they are arbitrary constants) whose claim for being “real numbers” merely emanates from their prefixed decimal point. They have the “form” of a fractional real number (that is, they lie between 0 and 1 only because of the prefixed decimal point) but they do not have “substantive” information of a true “real number” (a constant!) --- only that of an interval --- to convey.
BenCawaling@Yahoo.com [09 December 2005] BenCawaling 06:20, 28 March 2006 (UTC)
The section Ian Maxwell edited probably could use some touching up (in particular, getting rid of "in the sense of this article") but the edit I reverted introduced a syntax/semantics confusion. Objects are definable "over structures", not "in theories"; it doesn't make sense to ask if a particular object is definable in a theory. Given an undefinable object, how do you ask if a particular theory can define it? The theory can't even talk about it. -- Trovatore 21:01, 15 December 2005 (UTC)
This looks a lot like original research WP:NOR to me. The article even says “This should not be understood to be standard terminology.” The article also has some questionable content, such as:
CMummert 20:06, 13 June 2006 (UTC)
While reading the article a got an idea like this:
The set of definable reals(,complex numbers,and probably even R^n) is countable, therefore there exists a bijection to natural numbers. Now you can use induction to prove theorems about definable numbers. Of course they do not apply to all reals but will still apply to almost every number you will ever use.
Im guessing it would be a bit hard to actually construct a bijection that is useful, but is there something else wrong with the idea? 85.156.185.105 01:39, 31 August 2006 (UTC)
FYI, I have tagged this article with the Original Research tag. While it's an interesting topic, the article appears to be primarilly original research conducted by the primary authors. The article even flat out says in the introductiom that the term "Definable number" is not a standard mathematical term.
So basically as fun a topic as this is, the entire article appears to not be based on external, independent, verifiable references. This is a major problem, because if the article can not back up its definitions and terms using external references it could be ultimately deleted or moved to another website as original research. Dugwiki 18:41, 13 November 2006 (UTC)
FYI, someone tried to remove the unreferenced tag on this article. Note that the only reference provided is a paper discussing Computable numbers that does not specifically go into topics regarding definable numbers, as is mentioned by some of the posters in this thread above. So at the moment, the unreferenced tag still applies. Dugwiki 20:46, 13 November 2006 (UTC)
Anyone who looks on google scholar will see the term "definable real number" in many published research papers. If one were to wonder which to cite here, my guess is one of the books on computable real functions would be the best for present purposes. It hasn't really made it to the textbook level, so that's probably the reason for this hand-wringing. And, given that we have a concept of the reals as a complete ordered field, and also a concept of first-order definability, why is this so problematic? (And, note that "definable natural number" is found in lots of textbooks.) Michael Hardy 21:11, 13 November 2006 (UTC)
Given the fact that there may be many different models of ZFC, it seems to me that we should require that the formula defining a real number be absolute, i.e. independent of the model. That is, the formula would define the same real number in each model. Otherwise, the real number defined could be both larger than and smaller than the same rational number depending on which model it is in, or defined in some models and undefined in others.
If we define definable real numbers that way, then they would be the intersection of the set of real numbers with the minimal model of ZFC.
JRSpriggs 07:08, 14 November 2006 (UTC)
Well yeah, this is clearly Original "Research". Which is why I am putting it here in the talk rather than in the article. But it is fun to speculate about it.
Expanding my second definition -- a definable real number, r, is given by a pair of parameterless predicates φl(q) and φu(q) which satisfy these conditions:
The difference between my first and second definitions is that in the second I would allow a particular definition to have a value in one model but no value in another. However, any super-model of one which has the real in question should also contain it.
With this second definition, the diagonalization argument would fail. You could diagonalize over one model in a super-model which contains it as a set. But the resulting real number would depend on the choice of the original model. So there is no inconsistency with a notion of definable real number which is model dependent, as this one is.
JRSpriggs 08:04, 15 November 2006 (UTC)
I think the part of the article mentioning definable complex numbers is mistaken. I am familiar with the phenomenon that, having determined that there are two roots of the polynomial , there is no way, short of invoking the Axiom of Choice, to select one to be labeled ---the two roots share all properties. (If we took every math book in the world and replaced every occurence of "" with "", they would all remain precisely as accurate as they already were.) The upshot of this is that no nonreal complex number is first-order definable.
I'd rather wait for comment before altering the article to reflect this, since I have made inaccurate edits in the past. I'll give a week or so, since the error isn't serious. -- Ian Maxwell ( talk) 18:44, 8 April 2008 (UTC)
Another way to think about this: Usually when we start talking about the complex numbers, we ask the following:
For your information, the article fr:Nombre définissable has been deleted today, due to the same problems you mentioned here. We'll possibly replace it with an article focused on Borel's "inaccessible numbers". -- Michel421 ( talk) 20:41, 28 February 2010 (UTC)
Kuratowski called "inaccessible numbers" what we know now as "inaccessible cardinals" ; but Borel's "inaccessible numbers" are related to probabilities, etc... Here's a review : http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.bams/1183518025. -- Michel421 ( talk) 20:37, 1 March 2010 (UTC)
What can be said about the relation of definable numbers to elements of the ring of periods of Zagier? Tkuvho ( talk) 16:08, 29 July 2010 (UTC)
I think it's a good thing that Emil has opened this can of worms, because this article has been hanging around for a long time with bad problems and something needs to be done about it. However I don't agree with his solution, as I've explained in the edit summary and at the refdesk.
There is no doubt that there are only countably many reals that are first-order definable in the language of set theory; that is not the problem. It's true that the argument cannot be formalized in ZFC (nor even stated in the language of ZFC), but it is nevertheless completely solid.
The biggest problem is that it's not clear the article should exist at all. Before I got to it, quite some time ago, it was not talking about first-order definability in LST; it was talking about reals that are definable period, in any way. But that's not really a mathematical notion at all. Putative sources were things like the Turing paper, which I think Emil quite properly objected to; they would point out that such and such a real was definable, but would not attempt to demarcate how a real could fail to be definable.
So I "fixed" it so that it at least talked about a definite thing, first-order definability in LST. But in addition to the problem of sourcing it (that kind of definability isn't very useful or particularly well-studied), it's not clear at all that that concept, if it deserves an article, should appear under the title definable real number.
I don't know what to do about all this; I've been scratching my head over it for years. We should talk about it and figure it out. -- Trovatore ( talk) 17:18, 8 December 2010 (UTC)
I think the current state of this article is likely create widespread confusion about "definable real numbers" rather than widespread understanding of them. The article seems to be a popular read for people who are (naturally enough) interested in "cool" logic things, but at the same time I think the article tends to mislead them because the subtleties in the assumption that we are looking at def inability over the standard model only. Most of the arguments underlying the article are, as far as I know, not really expounded anywhere.
Moreover, as Joel Hamkins points out in this MathOverflow thread , the issue is much more subtle than this article currently suggests. He also has a set of slides on the topic.
I feel somewhat strongly we should rewrite this article to be about definability in general, rather than about definability over the standard model. In the short term, we could even use Hamkins' posts as a source, along with some set theory texts. In the longer term I think Hamkins is going to publish the results, although he doesn't seem to post preprints. This is not to say our article should espouse Hamkins' POV in every respect. But the issue that definability cannot be expressed in set theory should not be glossed over like it is at the moment. — Carl ( CBM · talk) 14:48, 30 March 2011 (UTC)
--- I am confused by the apparently-necessary assumption of "set theory" at the beginning of this article. Lost after the first sentence, I retreated to my ancient number theory book Hardy and Wright 2000 (1st published 1938) chapter XI Approximations of Irrationals by Rationals (pages 154-177, ending with proofs that pi and e are transcendental). I sought out, in particular, pages 159ff to remind myself of the definitions of algebraic and transcendental numbers (why is this word missing from the article?), the definition of "orders of approximation" by use of rationals, and in particular theorems 189: "The aggregate of algebraic numbers is enumerable", theorem 190: "Almost all real numbers are transcendental", theorem 191 "Any real algebraic number of degee n is not approximable to any order greater than n", and theorem 192 "a number defined by a sufficiently rapid sequence of rational approximations is necessarily transendental". I'm perfectly comfortable with, and think in terms of, the notion of "natural number" and a "theory" such as that of "arithmetic" (requiring notions of 0, successor, sum and product) applied to a "system" containing a computational machine. So do I have to assume, and know, set theory to understand the Hardy and Wright chapter? Isn't simple old-fashioned number theory good enough? True, Hardy and Wright do invoke the notion of measure, as in "the aggregate of real algebaric numbers has measure 0" but this obscure-to-me notion doesn't seem necessary to their proof of theorem 189. Bill Wvbailey ( talk) 17:05, 31 March 2011 (UTC)
Regarding the recent edits [3], although the text is not perfect, I think it is an improvement on the previous version. In general, the countability argument works if we have a (set) model of ZFC, but it requires much more clarification otherwise. I would prefer not to go back to the previous statement which just claims that not every real is definable via a countability argument.
For people coming from a more realist position, the key point to emphasize, I believe, is Tarski's theorem on the undefinability of truth. This means that we must examine definability from outside V, rather than from inside V. On the other hand, there are models of ZFC where every real is definable, and where every real is not definable. If we cannot find a clear statement of what property on V would be required to show (from outside) that not every real is definable, then I think we should leave that out.
I am going to try editing the article in some other ways, based on my comments from 2011 above. — Carl ( CBM · talk) 14:18, 5 March 2016 (UTC)
Ok, after thinking about this some more I'm back to the opinion that the denial of the existence of undefinable numbers is crankery, a sophisticated variation of Cantor-diagonal-denial.
It is a theorem in ZFC that there are uncountably many real numbers. It is true in all models of ZFC, regardless of whether those models are themselves (externally) countable.
Likewise, it is a theorem in ZFC that, for any function f from strings to real numbers (modeling your favorite choice of what it means to be definable), the image of f is countable and therefore there exist real numbers not defined by f. Again, this has nothing to do with model theory, and is true in all models of ZFC, regardless of whether the models are countable.
We might want to clarify that in this argument, by "countable" we mean countable within ZFC rather than in some chosen model of ZFC, but that clarification would be tautological (it is never interesting to talk about whether an object within ZFC is externally-countable, because in a countable model the answer is always yes). — David Eppstein ( talk) 20:47, 5 March 2016 (UTC)
The comment(s) below were originally left at Talk:Definable real number/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.
Maybe mid, but we are trying to lower importance/priority ratings. (Please replace this by a more helpful comment.) Geometry guy 21:47, 1 June 2007 (UTC) |
Last edited at 21:47, 1 June 2007 (UTC). Substituted at 01:59, 5 May 2016 (UTC)
We can find an undefinable real number in this way. (Although undefinable numbers cannot be found by anyone in the future, since they cannot be described with language)
Step 1: Make a finite English sentence of all definable numbers (e.g. 7 is "seven", is "two thirds", is "the square root of 2"), the sentence must uses only ASCII characters.
Step 2: Regard the sentences as base 95 numbers, we regard the character with ASCII code x as the digit x-32 (i.e. space character is the digit 0, "!" is the digit 1, "0" is the digit 16, "A" is the digit 33, "a" is the digit 65, etc. The digits are in the range [0, 94], since the ASCII code of the characters must be in the range [32, 126]) (Note that since the sentences are not start with space character, so the base 95 numbers are not started with the digit 0)
Then we can find an injective function f : D → N. (let D be the set of definable numbers)
Step 3: For n belong to N, if there is a definable number a such that f(a) = n, then we write such ns and as, if there is no such a, then we skip this n.
Step 4: Make a bijective function g : f(D) → N, if n is the mth smallest number in the range of f, then we let g(n) = m.
Step 5: Let the a such that gf(a) = 1 is a1, the a such that gf(a) = 2 is a2, the a such that gf(a) = 3 is a3, etc. Then the function gf : D → N, is also bijective.
Step 6: Use Cantor's diagonal argument to find a number not in the list of definable numbers: Write all definable numbers a1, a2, a3, ... in decimal, and we will find a new number b, first, let the integer part of b is 0 (i.e. 0 ≤ b < 1), second, if the m-th digit after the decimal point of am is 7, then we let the m-th digit after the decimal point of b is 4, otherwise, we let the m-th digit after the decimal point of b is 7. Thus, b ≠ am for any m, since the m-th digit after the decimal point of b and am are different, and b cannot be any definable number. Thus, this b is an undefinable number!!! — Preceding unsigned comment added by 101.9.132.67 ( talk) 13:58, 5 April 2017 (UTC)
A recent edit called my attention to this text:
Where does this come from? Is this really what Hamkins thinks? Informally, it's obvious nonsense. Every subcollection of a set is a set.
The only way I can see that this claim is at all defensible is if you're thinking formalistically; that is, you're making reference to the fact that you can't apply the
separation axiom to show the existence of such a set, because there's no first-order property that defines it. But then I don't see how you formulate the claim at all; there's no way to talk about the collection in the first place.
We really need to fix this. Right now it looks really bad and obviously nonsensical. Paging
User:CBM; we've had discussions in this neighborhood in the past. --
Trovatore (
talk) 21:11, 10 April 2017 (UTC)
"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." ( [5]) Boris Tsirelson ( talk) 21:41, 5 February 2018 (UTC)
Is a real number undefinable with respect to first-order formulae iff it's indiscernible? C7XWiki ( talk) 03:58, 2 March 2021 (UTC)