Talk:Definable real number

From Wikipedia, the free encyclopedia

1 Berry's paradox, definability of definability
2 Problems with this article
3 Proposed rewrite
4 Rewrite in place
5 Countably many OD reals
6 Example of non-definable real?
7 Problem with this page
8 “Undefinable real number” is a self-contradiction
9 explanation of revert
10 Still more problems
11 Induction
12 Original research tag
13 Absoluteness of the definition of a particular real number

[edit] Berry's paradox, definability of definability

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

I think that's the problem with the whole page. If you nail down what "definable" means, you'll find that the set of definable reals itself is not definable in that sense. "Definable" is a moving target; the whole field of descriptive set theory is in some sense an exercise in watching the target move. --Trovatore 04:00, 19 July 2005 (UTC)

So it's not very clear to me what should be done with the page, even if it should be kept at all. I'm torn because it exposits a useful notion, but it doesn't say anything very precise about just what the notion is, and in some sense it never can. Moreover since there isn't any fixed notion standardly called a "definable number", it's almost a neologism page. Maybe it could be saved by showing various precise notions of definability without parameters and observing that they all give rise to countable sets of "definable reals", albeit different countable sets. --Trovatore 04:00, 19 July 2005 (UTC)

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.

And this passage above doesn't even make sense. What does it mean to prove in ZFC that φ(a) is true? We don't even have a definition for a, in advance; that's what φ is supposed to be giving us. It does make sense to talk about proving that there exists a unique real number that makes φ true -- but now we don't have a around anymore. We can add it back in by requiring, in addition, that φ(a) really be true, semantically, i.e. in the Von Neumann universe V. But now what do we need the uniqueness proof in ZFC for? Isn't it enough that φ have a unique real solution? No, the whole thing is just horribly muddled; needs major surgery. --Trovatore 04:24, 19 July 2005 (UTC)

I don't see what's wrong with it. I don't understand anything you're saying about proving versus "be true"/"have a unique solution". The wording you say does make sense is just a rewording as far as I can see.--MarSch 09:37, 19 July 2005 (UTC)

For an arbitrary real number a, there is no notion of "proving" φ(a) from ZFC, because to prove φ(a), you first have to be able to write it down--and we don't know how to write down a. --Trovatore 16:38, 19 July 2005 (UTC)

The defect here seems obvious; not that a is the unique real number but that there is a unique real number a. Emending text accordingly. Are there other factuality disputes? Septentrionalis 19:51, 19 July 2005 (UTC)

Bunches of 'em. I'll start a new section below, with a list.--Trovatore 20:18, 19 July 2005 (UTC)

[edit] Problems with this article

A nonexaustive list of problems with this page, as of 20:20, 19 July 2005 (UTC).

Septentrionalis' fix to the "unique real number" problem now reads

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 there exists a unique real number a which makes the statement φ(a) true.

- Note that the first instance of a is free, and the second is bound. Therefore the a in the part about φ(a) being true has nothing to do with the real number a whose definability we are evaluating.

Why do we care about whether existence/uniqueness is provable in ZFC, specifically? How about PA, or KM, or ZFC+"there exists a supercompact cardinal"?

We can make definability precise in lots of ways. Here would be one possible attempt:

a real number a is called definable if there is a first-order formula φ of the language of set theory, with one free variable, such that a is the unique real number such that φ(a) is true

- This version is at least meaningful, and many of the assertions in the article are true using this notion. But here's one that's not:

The definable numbers form a field containing all numbers that have ever been or can be unambiguously described.

- To see this is not true (of the profferred notion of "definable"), observe that we can list all definable reals by the Gödel numbers of their defining formulas, and then run the diagonal argument to find an unambiguously-described real that is not on the list.

What's a "theorem of calculus"? Is the Cauchy completeness of the reals a theorem of calculus? If not, why not? This is in reference to the following passage:

In fact, all theorems of calculus remain true if the field of real numbers is replaced by the field of definable numbers

[edit] Proposed rewrite

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:

I've deleted the claim that the definable numbers contain all reals that can ever be unambiguously described, and added a section that explains why this isn't true.

I've also deleted the claim about calculus. I'm not opposed to its being there--if someone can explain just what it means, and give references. It looks like it may have been motivated by some sort of neo-logicist project; if so, the project should be named. (I don't really see how you're going to get, say, the Lebesgue integral, just with definable reals, but maybe someone has managed--certainly it wouldn't be the standard treatment, though, so "all the theorems of calculus" seems to be overstating the case.)

I've left the bit about "standard" numbers, but I don't understand it, and would like someone to explain it.
- So when I got around to following the link, it made a certain amount of sense. Not sure it belongs just here, though. --Trovatore 07:46, 20 July 2005 (UTC)

The section about other notions of definability is not ready for prime time; it's just an outline of what I'd like to put there.

--Trovatore 01:43, 20 July 2005 (UTC)

I'm not sure I'm convinced by your diagonalization argument. You are talking about an explicit diagonal process that will, given a list of denumerably many Gödel numbers of well-formed definitions of real numbers, produce another Gödel number of a well-formed definition of a real number. This is a complicated enough idea that you will probably need to give an example of such a procedure--I have never seen an example even of a diagonalization producing a natural number from a list of natural numbers. --Ian Maxwell 03:02, 19 October 2005 (UTC)

No, actually, I'm not talking about doing what you say in your second sentence above--at least, I don't claim to recover a Gödel number of a definition in the same language. The language is not rich enough to define definability in the language, or at least not to definably get from a definition to the thing defined. That's kind of the whole point. It's analogous to Tarski's result on the undefinability of truth. --Trovatore 03:09, 19 October 2005 (UTC)

[edit] Rewrite in place

Having heard no objection, I have copied the rewrite to the main page. Comments solicited. --Trovatore 05:10, 21 July 2005 (UTC)

[edit] Countably many OD reals

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 $\aleph_1$ (the forcing conditions are finite partial functions from $\aleph_1$ to $ω$ ).

(Actually, make that finite partial functions from

ω

to $\aleph_1$ --the other direction might work but it's harder to see.)--Trovatore 07:11, 22 July 2005 (UTC)

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 $2^{\aleph_0}$ 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)

[edit] Example of non-definable real?

You state that most reals are not definable. I'd like you to give me one example. --Fermatprime 01:14, 5 September 2005 (UTC)

See the qualification on the sort of definability being considered in the article, first-order definability in the language of set theory, without parameters. Then the section Definable_number#Notion_does_not_exhaust_.22unambiguously_described.22_numbers provides an answer to your question, --Trovatore 02:20, 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.

It's not that the set doesn't exist; it's just not well-specified. That is, the notion of "definable" is itself not definable (and the notion of "well-specified" is not well-specified). There are lots of different notions of definability. For any completely well-specified such notion N, the set of all N-definable reals exists, and is well-specified, but not N-definable. --Trovatore 01:53, 27 September 2006 (UTC)

However, the proof of the statement rests on there only being countably many definitions, and so only countably many definable numbers. Since the reals are non-countable, almost all reals are not definable (click for the sense of almost all being used here.) Septentrionalis 19:12, 5 September 2005 (UTC)

It is 100% probable that the gravitational constant (given in SI units) is a number not first-order definable in ZFC set theory. --66.228.95.2 19:41, 20 October 2005 (UTC)

I doubt that that number is well enough specified to make sense of this assertion. The gravitational "constant" may change (very slightly) from time to time or place to place, and the assumptions used to make the SI system seem well specified probably break down past some finite number of significant figures. --Trovatore 19:46, 20 October 2005 (UTC)

But what about the set of all definable reals, as suggested above? HTG 27 Sept. 2006

I moved your comment to the bottom of the thread. I am not sure what you are asking. Your idea that diagonalization could be used to construct a new definable real fails for several reasons:

The set of all definable reals may or may not be definable in a particular model of set theory. If this set is not definable, then the real you obtain by diagonalization has no reason to be definable.
When the set of all definable reals over a model is definable within the model, it will never be countable inside the model, because otherwise the model would already include the real that you are trying to construct by diagonalization. Your argument assumes that the set of definable reals is countable inside the model.

CMummert 11:52, 27 September 2006 (UTC)

1)The idea that a (countable) set already contains the number which is going to be constructed by the Cantor's diagonal argument is clearly false - the construction guarantees that the constructed number differs from each element of the set considered.

2)I strongly believe that countability or uncountability of a set is an inherent and absolute property of the set. If there are two models which differ with respect to countability of a given set, then at least one of them is deficient (e.g. a countable model of reals according to the Lowenheim-Skolem theorem, where the least-upper-bound axiom is not satisfied). HTG 28 Sept. 2006

[edit] Problem with this page

This is the problem with this page as I see it:

Intuitively, "Definable number" means "there exists a formula uniquely identifying"
However, in what language? Due to Godel's theorem, whenever you tie down the definition to a particular formal language, there are going to be numbers which are not definable in that formal language, but which are definable in the intuitive sense, definable in
So really, the intuitive notion of "definable" is impossible to formalise
So, the attempt of this article to provide a formal definition of the intuitive concept of "definable number" is to some extent pointless (unless that particular formal definition has some other value)
Really, this intuitive concept of "definable number" belongs not to mathematics, but the philosophy of mathematics -- it is unformalizable

This is the most correct definition of definable number I can conceive:

A number is definable if there exists a proposition capable of being conceived by a mind of at least human-level intelligence which is true for that number and false for every other number.

Obviously, this definition is unformalisable due to Godel's theorem. But it is I think the true one.

Another definition might be:

A number x is definable if, for some formal language F and associated model M, there exists a statement S(x) in F such that S(x) is true in M and for all numbers y S(y) is true in M iff x=y.

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

Much of your analysis is right on. A quibble: Gödel's theorem per se is not really relevant; that's about syntax, whereas when we talk about a real that's not definable in a language, we've moved beyond syntax and are talking about the real number, semantically, as an object. So it's more like Tarski's theorem on the undefinability of truth. But they are very similar in style.

But if you want to see a page with much worse problems along the lines of the ones you discuss, take a look at the page before I got to it. That should make my criticisms on this talk page more understandable.

Your criticisms still have merit, but I don't really see a solution short of deleting the page. --Trovatore 16:48, 20 October 2005 (UTC)

Oh, to avoid confusion I should also say that your attempt above with the language F and model M isn't going to work; it would make every real number definable. Just put a function symbol f in the language, and now for any real x that you want to make definable, choose your model M so that it interprets f to assign to each natural number n the n^th decimal digit of x. Details to be filled in by you. You're thinking along the right lines, though. --Trovatore 17:17, 20 October 2005 (UTC)

[edit] “Undefinable real number” is a self-contradiction

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)

[edit] explanation of revert

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)

Oh, and a minor point: The change from [[Gödel number]]s to [[Gödel number|Gödel numbers]] was quite unnecessary; the first form works fine and the source is easier to read. --Trovatore 21:03, 15 December 2005 (UTC)

[edit] Still more problems

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:

The claim that definable numbers form a field, and thus are a set. How exactly is the existence proved? It seems equally likely to me that this set does not exist. Is there even a known proof that the existence of the set of definable reals is consistent with ZFC?
The example of Chaitin's constant, which is just an element of the Turing degree 0'. Kleene's O would be a better example of a noncomputable definable real. Or the truth predicate for second-order arithmetic. Or 0^#...

CMummert 20:06, 13 June 2006 (UTC)

Yeah, the whole article is problematic. I cleaned up some of the totally meaningless stuff a while ago, but I'm not really convinced the article should be here. As to your first point, though; of course the set exists, Platonistically, with the given (nonce) definition of "definable real". This isn't a theorem of ZFC (can't even be phrased in the language of set theory) but it's obviously true. --Trovatore 04:31, 18 July 2006 (UTC)

The same argument could be made for Reinhardt cardinals, but they are inconsistent with ZFC. But I am content with a small disclaimer like the one I put into the article, so I don't want to argue the point any further.

A more serious issue is the original research nature of the article. What if it were rewritten to focus on definability within structures, and had a section that pointed out that one application is to the (class) structure V? So it might include a section on first-order definability, a section on higher order definability, and a section on definability with parameters (mentioning ordinal definability and L). Then if could discuss definability within a class model V of set theory. We could also mention Grothendieck universes, i.e. inaccessible cardinals.

This would probably necessitate a merge with definable set, which would be helpful for that article as well.

CMummert 14:28, 18 July 2006 (UTC)

The merge is not a bad idea. I don't follow your claim about Reinhardt cardinals, though. It's completely clear that, if some reals are first-order definable over V and some aren't, then there must be an element of V consisting of exactly the ones that are; this is by construction. Why there should be a nontrivial j:V→V, on the other hand, I don't see at all. In any case, if you're seriously worried about consistency, note that the existence of the set of all first-order definable reals is a theorem of Kelley—Morse, which has consistency strength less than an inaccessible. --Trovatore 15:47, 18 July 2006 (UTC)

Sorry... why is the set of definable numbers not expressible in the language of set theory, as, say, the set of numbers encoding a P such that $ZFC \vdash \exist! x. P(x)$ ? We can define arithmetic and other real number operations on these, surely. Or is the issue that we are trying to dissociate from a particular formal system? Then when exactly are we talking about? Or is the issue that of representation, i.e. we want to map back to the "real" real numbers somehow? So then it would be expressible in NBG but not ZFC? Or am I off the mark entirely? --Confused 192.75.48.150 19:21, 18 July 2006 (UTC)

We don't have to be trying to dissociate from a particular formal system; there was simply none mentioned. We're talking about the set of reals x such that there is a formula φ such that x is the unique object satisfying φ. Provability is never mentioned; we're talking about what is really, Platonistically true. Note by the way that your attempt does not give you a set of reals at all, but a set of Gödel numbers, and ZFC will not be able to decide (in general) whether two of these Gödel numbers code the same real. --Trovatore 19:39, 18 July 2006 (UTC)

There's that word again, now then, surely we don't mean the concept is interesting only to Platonists. To the latter point about my buggered attempt, you're right, we would need to take $ZFC \vdash \forall x. P(x) \leftrightarrow Q(x)$ as an equivalence relation, which is not decidable, but is definable, and the operations are still functional (in the sense of e.g. a=b -> a+c=b+c) yes? So, I understand this is different from the concept of "definable number" then, though I still don't understand the concept. 192.75.48.150 20:28, 18 July 2006 (UTC)

You aren't going to get any usable concept (I predict) if you keep prepending "ZFC proves" to everything. The problem is not simply that the problem of whether two formulas define the same real is undecidable (as a decision problem). It is undecidable in that sense, of course, but it's worse than that: There will exist lots of pairs P, Q such that ZFC neither proves nor refutes that P and Q define the same real. Anything you do to get around this is going to be extremely unwieldy. Definable reals are reals that have definitions; this does not imply that you can usefully identify them with their definitions. --Trovatore 20:55, 18 July 2006 (UTC)

Well, nevertheless it looks to me like ZFC would still prove it satisfies the field axioms, though not the 2nd order completeness axiom -- which is to be expected, as stated in the article. ZFC failing to prove or refute equality shouldn't be a problem. After all, it also happens for real real numbers (Cauchy sequences), e.g. A_n = 2^-m, if m<n is the first Gödel number of a ZFC proof of 0=1; or A_n = 0, if there is no m<n which is the Gödel number of a ZFC proof of 0=1. ZFC proves A is a real real number, but if it is consistent it does not prove or refute that A is the same real real as 0. 70.30.114.149 00:50, 19 July 2006 (UTC)

So let's make sure I understand you correctly. As I understand it you want the objects of your field to be equivalence classes of formulas in the language of set theory, each formula having one free variable, such that ZFC proves that exactly one object satisfies the formula and that that object is a real number, and you want the equivalence relation to be provable equivalence in ZFC. You haven't really specified what plus and times are supposed to be, but I suppose it's clear enough (equivalence class of P times equivalence class of Q would be the equivalence class of a formula that says "x is the unique object satisfying P times the unique object satisfying Q), and I do think that's well-defined and satisfies the field axioms.

But it's certainly not something you'd naturally call the "definable reals", because for each real having a definition, there are many of these equivalence classes that correspond to it. In particular there's no natural monomorphism from your structure into the reals. --Trovatore 01:34, 19 July 2006 (UTC)

Well, I suppose, and that's also to be expected. No? Just like a computable real: they're algorithms which can spit out successive approximations, and there will be pairs of algorithms which ZFC cannot prove to be equal (same example as above: A is computable). 70.30.114.149 01:48, 19 July 2006 (UTC)

No, a computable real is not an algorithm. A computable real is one that can be computed by an algorithm (in the relevant sense; there are some details). If you have two different algorithms that compute the same real, then they represent the same computable real, not two different ones. That's true whether or not you can prove in ZFC that they compute the same real. --Trovatore 02:05, 19 July 2006 (UTC)

Okay. In the case of computables we can dispense with an appeal to a pre-existing set of reals, of course, but what I'm getting is, this isn't a useful thing to try to do here. 70.30.114.149 03:02, 19 July 2006 (UTC)

I really don't know what you mean by that. Whether talking about computable reals or some other sort of definability, the condition for identifying two reals is that they're the same real, not that you can prove that fact. In the example you give above, your A is the same computable real as 0, in spite of the fact that ZFC can't prove it. --Trovatore 06:27, 19 July 2006 (UTC)

No, right, ZFC provability is not a necessary condition there, to be sure. The point that I am so poorly expressing is that it is not necessary to talk about real numbers at all in order to talk about computable numbers and their equality. To define computable numbers as the real numbers which are computable is like defining the real numbers as the complex numbers which are real, or the rational numbers as the real numbers which are rational, or the natural numbers as the rational numbers which are natural: it's doable, of course, and there's the odd time where it's more convenient, but usually it's not necessary. Now, it might be a fundamentaly different situation here, and we have no choice but to talk about real numbers to talk about definable numbers, but it seems like such a straightforward concept (as these things go), so I'm not quite convinced that this is the case, much less that we need to go all the way to $V_\infty$ and beyond. 72.137.20.109 19:02, 23 July 2006 (UTC)

The only obstacle to ZFC proving the definable numbers form a field is that it seems unlikely that ZFC proves that the definable numbers form a set. In fact, I think that an analysis of Cohen generics would show that the set of definable reals is not definable over any model of ZFC, although I haven't checked it carefully. CMummert 02:04, 19 July 2006 (UTC)

The language of ZFC is not expressive enough to state the claim that the definable numbers form a set. Nevertheless there are models of ZFC (necessarily countable ones) whose every element is definable (so in particular the set of definable reals would be definable, because it would be the set of all reals of the model). For example, take the Skolem hull of the empty set in L, and collapse it. --Trovatore 02:08, 19 July 2006 (UTC)

Yes, of course the you have to talk about definability in a metalanguage. I need to write out the idea I had in my last post to see what's wrong with it. CMummert 02:36, 19 July 2006 (UTC)

About the possible merge. I think it is a good idea, and could resolve much of the original research nature of the current article. Is anyone willing to write a first draft in a sheltered location, for comments? CMummert 02:04, 19 July 2006 (UTC)

[edit] Induction

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)

[edit] Original research tag

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)

Yeah, just to recap the history of this a little bit: When I found this article it wasn't clear that it was talking about anything in particular. The term "definable" was never defined (and I would argue that this is a fundamental limitation -- definable full stop really can't be defined). Strictly speaking it probably should have been deleted, but it was linked to from all over the place, and it would have been a mess.

So I rewrote it so that it was at least talking about a definite notion (and threw in the warning about it not being standard usage). It wasn't a perfect solution (and did include some OR by Wiki standards) but seemed least bad at the time, or at least the least bad thing within the constraints of the energy I was willing to give it.

It still could be deleted; that would be the process-wonk solution for sure. But it would still be a mess. --Trovatore 19:09, 13 November 2006 (UTC)

The concept of a "definable number", under that name and as distinct from computable numbers, certainly appears in the literature, notably in Turing's "On computable numbers with an application to the Entscheidungsproblem" [1]. I think the problem with the article is not OR so much as that it doesn't cite sources and should. —David Eppstein 19:10, 13 November 2006 (UTC)

I've already added a link at the bottom to the Turing paper. However, that paper only seems to have part of the info given here. More citations will be needed. JoshuaZ 19:20, 13 November 2006 (UTC)

It appears to me that Turing does not attempt to define "definable number" in that paper, or develop any theory of what a "definable number" in general is. He talks about the existence of a definable number that's not computable, but it's more like "here, you can see that this number is definable", not "this is what a definable number is in general". So I would take that to be more of a nonce term, not something we can write an article about. I would be strongly against writing an article based mainly on Turing's notion of definable taken from that paper, because of the fact that (based really just on a text search; I haven't read the paper yet in detail), he never does really define it. --Trovatore 19:22, 13 November 2006 (UTC)

There are plenty of published references for the concept "definable subset of a first order structure", a la model theory, and this article could be easily rewritten to use this terminology (see for example Jech Set Theory ed. 3 p. 157 where he defines the term "definable set"). The current revision has poor terminology, not original research, and it can be fixed with little work. CMummert 19:39, 13 November 2006 (UTC)

One note - there is a seperate article called Computable number that goes specifically into that concept. Computable numbers, though related, are distinct from the "definable numbers" this article talks about. Also, note that the Computable Number article does contain some citations for verification.

As to rewriting, that would be my preference. I'd rather see the article be rewritten and maybe retitled, with some references backing up the information. After all, the information in the article is presumably accurate, and it's an interesting topic. That's why I didn't simply put it up for possible deletion, for example, because I'd like to think the problem can be corrected. Dugwiki 19:44, 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)

The cited paper of Turing DOES "specifically go into topics regarding definable numbers", as you can see by looking at it. And no posters above said otherwise. One poster above said that Turing does not define the concept. But the fact remains: Turing's paper repeatedly mentions the concept and Turing says in the paper that he gives examples of real numbers that are definable but not computable. Michael Hardy 20:53, 13 November 2006 (UTC)

I did look at it, and it does not specifically go into the formal definitions of definable numbers mentioned in this article. For example, nowhere in Turing's paper does it have the phrase "first-order definable in the language of set theory, without parameters", the bolded terminology used to describe the term in the very first sentence of the article. (In fact, the phrase "first order" or "first-order" never appears either.)

Again, I'm not disputing the article's accuracy. I'm saying that the referenced paper doesn't directly define what the article is discussing. Dugwiki 21:07, 13 November 2006 (UTC)

Let's not spend any time arguing about whether the article needs one or two tags. We've got bigger fish to fry. --Trovatore 20:49, 13 November 2006 (UTC)

The issue is that the tag was removed without discussion. Reverting tags without discussion is not generally a good idea. So fry whatever fish you like, but when I have a tag reverted I'll point it out. Dugwiki 21:07, 13 November 2006 (UTC)

Normally if there's an "unreferenced", the person who adds suitable references deletes the tag. Michael Hardy 21:11, 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)

So first, no doubt the term is used in lots of research papers. The question is, how is it used? Is it used consistently, across the various papers, to mean one precise notion? I seriously doubt it. And if it's not, then creating a referent here for the term is either undue weight or another sort of original research (original synthesis of published material). That's worse than the current OR, which at least warns the reader about it up front.
So you're suggesting that "definable real" should mean definable in the first-order language of ordered fields? That's one plausible meaning, I suppose. Note that a great many reals that are "definable" according to the definition in the current text would no be definable in that sense. And I very seriously doubt that your proposal is the consensus meaning in the literature. --Trovatore 21:19, 13 November 2006 (UTC)

Again, the problem isn't whether or not the concepts in the article make sense; they probably do. It's that they need to have already appeared in a published format elsewhere. And the only way to prove that the article's material has appeared in an external publication is to cite a specific reference. So the fact that google has the term "definable real number" is great, but you'll need to pick one of those references you're saying verifies the article's definitions and cite it. Dugwiki 21:24, 13 November 2006 (UTC)

Mere adherence to process isn't enough in cases like this. I have no doubt that someone can find a paper that states a precise definition of "definable real". But if that definition is not commonly understood by experts in the field, then you can't just uncritically parrot it here, even though it's verifiable. My point is that there is no single notion of "definable real" that's commonly understood by experts in the field, which was the problem from the very start; my solution was certainly imperfect but at least did not hide the problem from the reader. --Trovatore 21:29, 13 November 2006 (UTC)

If there's a lack of consistency among published definitions in the literature, the article should survey those definitions and describe what is in common and what is different between them. Stating "this should not be understood to be standard terminology" and then avoiding any description of the literature in which it is used as if it were standard terminology is not a solution. —David Eppstein 21:54, 13 November 2006 (UTC)

Sounds good. When do you think you can have it done? --Trovatore 22:22, 13 November 2006 (UTC)

[edit] Absoluteness of the definition of a particular real number

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)

Again, another sort of plausible definition I suppose (though it would exclude things like 0# which people ordinarily think of as definable reals; its definition is highly absolute, but not quite as absolute as you require). But the whole point of the recent exchange is that we're not supposed to make stuff up (which this particular article always has done).

My biggest concern is to make sure that no one gloms onto the first paper giving a precise definition and says "Aha!". Because there really isn't any one definition, and can't be; rather, there's a hierarchy of stronger and stronger (well, it might go sideways as well) notions of definability, giving different notions of definable real. If the article must be kept, then that single point is the most important one that a reader should take away from it. --Trovatore 07:28, 14 November 2006 (UTC)

OK. If you want to include zero-sharp, then let us require that the Dedekind cut induced in the rational numbers not change as one makes the model larger. JRSpriggs 08:58, 14 November 2006 (UTC)

Well, you can play around with this as much as you want, and maybe at the end of it you'll have picked out some nice, useful definability class for reals. But firstly it's not going to be the once-and-for-all-final notion of "definable real", because there isn't one; as soon as you nail it down, I'm going to be able to diagonalize out of it and exhibit a definable real, in the intuitive sense, that you've missed. And more to the point for WP, your notion isn't going to be the "standard" notion of "definable real"; I feel comfortable that there isn't one of those either. (I should look at those papers when I get a chance; my guess is that most of them are using the term as Turing did, informally without really specifying what it means, and that the rest of them spread out over different precise meanings that happen to be useful to the individual author at the time.) --Trovatore 07:07, 15 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:

$r = \sup \{ q | q \in \mathbf{Q} \and \phi_l (q) \} = \inf \{ q | q \in \mathbf{Q} \and \phi_u (q) \}$ and

$\phi_l \in \Sigma_1 \and \phi_u \in \Sigma_1$ and

$\mathrm{ZFC} \vdash \forall p \in \mathbf{Q} \forall q \in \mathbf{Q} ( (\phi_l (p) \and \phi_u (q) ) \rightarrow p \leq q ) .$

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)

Retrieved from "http://en.wikipedia.org../../../d/e/f/Talk%7EDefinable_real_number_44c2.html"