Talk:Definable real number

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)

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

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)

I've been reading this article and the discussion, and I'm was trouble understanding how we get an "unambiguously described" number from the diagonalization argument. I'm going to attempt to clarify it. —Preceding unsigned comment added by Maxsklar (talk • contribs) 00:19, 1 March 2009 (UTC)

I tried to do this, but I'm still not happy with it. I have a feeling that there's some larger idea or paradox here. It would be nice if someone could explain it more thoroughly and add a citation. Maxsklar (talk) 01:07, 1 March 2009 (UTC)

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)

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 $\omega$).

(Actually, make that finite partial functions from $\omega$ 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)

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

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)

“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.

[email protected] [09 December 2005]BenCawaling 06:20, 28 March 2006 (UTC)

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)

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 \exists !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)

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)

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)

1. 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.
2. 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)

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} \land \phi _{l}(q)\}=\inf\{q|q\in \mathbf {Q} \land \phi _{u}(q)\}$ and

$\phi _{l}\in \Sigma _{1}\land \phi _{u}\in \Sigma _{1}$ and

$\mathrm {ZFC} \vdash \forall p\in \mathbf {Q} \forall q\in \mathbf {Q} ((\phi _{l}(p)\land \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)

There are no definable nonreal complex numbers.

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 $x^{2} 1$, there is no way, short of invoking the Axiom of Choice, to select one to be labeled $i$---the two roots share all properties. (If we took every math book in the world and replaced every occurence of "$i$" with "$(-i)$", 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)

Well, it really depends on your language and how (if at all) you're representing the complex numbers within some larger structure. For example, if you consider the complex numbers to be ordered pairs of reals, with (x,y) being interpreted as x yi, then certainly i is definable -- it's just (0,1). Granted that you could have equally well stipulated that (x,y) represent x−yi -- but you didn't.

The entire article is problematic on this sort of point. I made an effort to fix some of the most glaring issues back in July of '05, but it is still very seriously flawed. --Trovatore (talk) 18:57, 8 April 2008 (UTC)

Another way to think about this: Usually when we start talking about the complex numbers, we ask the following:

Suppose there is a set of numbers that includes the real numbers, and a non-real number "i" that has the property i*i = -1. Then suppose that this system is closed under addition and multiplication. The system that we get is the imaginary numbers. The number "i" is well defined in the system because one of the underlying assumptions of this system is that "i" exists. Maxsklar Maxsklar (talk) 23:54, 28 February 2009 (UTC)

Umm -- close. I would quibble on your wording, though. The reason that i is well-defined is not that you assume it exists; it's that you have a name for it. You could assume that there is a number whose square is −1, but if you don't give it a name, then that would not make the number definable. --Trovatore (talk) 22:14, 28 February 2010 (UTC)

WP:fr article has been deleted

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)

I am not familiar with these — can you give me a pointer? I did take a look at the deletion discussion (here: fr:Discussion:Nombre définissable/Suppression) and I saw that various people had the same concern I had, that inaccessible number would most probably be taken to mean inaccessible cardinal. One contributor linked three papers, in all of which (from a brief scan) it appeared that inaccessible number or translation thereof was being taken to mean either "inaccessible cardinal" or "weakly inaccessible cardinal". But certainly this is not an insurmountable obstacle, as the name can always be made clear. --Trovatore (talk) 22:26, 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)

Relation to ring of periods?

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)

According to that article, all periods are computable; the computable numbers are a proper subset of the definable numbers. — Carl (CBM · talk) 19:37, 29 July 2010 (UTC)

Thanks, I should have realized that. This takes some steam out of the remark that the periods provide an countable intermediate system between Q-bar and C. Tkuvho (talk) 02:30, 30 July 2010 (UTC)

BRD

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)

Oh, I should correct one point on the history of this — actually the Turing article showed up later. The version before I got to it had no putative sources at all. I don't think that really affects the substance of what I said. --Trovatore (talk) 10:18, 9 December 2010 (UTC)

I agree with all this, it matches my memory of the history of this article (which was, as Trovatore says, even worse).

I think that it woudl be nice if we had an article that covered (in a summary sort of way) definability within set theory. This could include things like the Df relation Kunen defines, the inner models L and HOD, pointwise definable models of set theory, and definability in the standard model of set theory. Perhaps the article could be titled Definability in set theory. There are certainly plenty of sources for that.

I don't think there is any strong argument in favor of an article that focuses only on definability of real numbers, rather than definability of sets in general. — Carl (CBM · talk) 17:24, 8 December 2010 (UTC)

I see, so it's even worse than I thought, the article is basically patched up OR. In that case I think the best course of action would be to scratch the current article and start all over, sticking to sourceable information. I don't have Kunen's book, but your outline sounds fine. I also agree that there is no particular reason to restrict it to reals.—Emil J. 18:53, 8 December 2010 (UTC)

I agree with that description (in fact, it's OR patched up with other OR) and agree that it's probably best to start over. I also agree with treating L and HOD and might throw in stuff like the lightface pointclasses as well. But I'm not so sure it's not worth treating the reals separately. The reals are the first place the question shows up, and there are many natural questions about the definability of reals (or subsets of the naturals, same diff) that arise specifically there. --Trovatore (talk) 10:17, 9 December 2010 (UTC)

What I meant is that general properties of definability that apply to all sets should not be restricted to reals. We can certainly include information specific to reals.—Emil J. 12:47, 9 December 2010 (UTC)

I'm not against having an article on definability in general. I'm just saying it may be worth having an article on definability of reals specifically. --Trovatore (talk) 20:04, 9 December 2010 (UTC)

What would the content of that article be? — Carl (CBM · talk) 21:01, 9 December 2010 (UTC)

Starting over

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)

The emphasis on definability over V was my attempt to make the article actually about some well-specified thing. If you think it's bad now, look back in the history to before I did that. I am fine with the idea of a complete rewrite; while I am somewhat proud of having made a terrible article into a mediocre one, that doesn't mean I want it to stay mediocre.

However, while there should probably be an article on definability in general, I'm not sure it should be the replacement for this article. I would like to see this article rewritten more from a descriptive-set-theoretic POV than a general-logic one. Rather than starting with full-blown definability without params in some extremely expressive context, start more from the bottom up — rational, algebraic, computable, arithmetical, definable in second-order arithmetic, and so on. Not sure where to find sources though; could be open to a charge of original synthesis. --Trovatore (talk) 20:47, 30 March 2011 (UTC)

That option sounds good to me. I do think the article is much better now than, say, [2]. There are actually several articles listed on the dab page definability, but none of them would really be a good redirect target for this article in the shape they are in. So some sort of patching would help.

As for the synthesis issue, I think we have just as much of a problem in the current article. At least the other idea would be less likely to be misunderstood, and more helpful. — Carl (CBM · talk) 00:18, 31 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)

Recent edit on definability in ZFC

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)

Hmm, I'm not so sure it's an improvement. I agree that the matter has to be dealt with more carefully than it was previously, and we need to take into account Hamkins' comments, probably.

However, fundamentally, the "naive" argument is correct, and Hamkins is wrong. Yes, there are models of ZFC in which every real is definable. However, those models necessarily have only countably many reals, and therefore do not have all the reals. The fact that they exist is a demonstration of the limited expressive power of first-order logic.

You cannot conclude that the existence of the models shows that it is "consistent" that every real is definable. Deriving consistency from the existence of (first-order) models works only for first-order statements, and "every real is definable" cannot be expressed in first-order logic at all. --Trovatore (talk) 18:30, 5 March 2016 (UTC)

I want to clarify that when I say Hamkins is wrong, I don't mean about the mathematics. I haven't checked but I'm quite confident that he got that part right. He's an excellent mathematician. What I think he got wrong is the interpretation. --Trovatore (talk) 18:42, 5 March 2016 (UTC)

Trovatore, I think I understand at least somewhat somewhat your realist position on set theory, but I think we need to be more neutral in this article. I have modified the previous edit to say that the naive argument is "problematic" rather than "fallacious", and to emphasize that the naive argument is not carried out in ZFC. I think that is somewhat more neutral.

A better fix overall might be to explain that, although ZFC can prove that every uncountable model M of ZFC has reals that are not definable in M, ZFC cannot prove the same thing about V, because ZFC cannot formalize definability in V. I will try to make that edit next. — Carl (CBM · talk)

Ultimately I think we should try to implement the plan we provisionally agreed on in 2011. If we just start talking about definability bottom-up, we can maybe avoid the annoyance about definability sempliciter, whatever that might mean.

The philosophical dispute is an interesting one and I'm not saying it shouldn't be included at some point, but we might need to wait for it to filter into more traditional sources. I wonder if Peter Koellner could be induced to write something about it. He would do a superb job and cover all the angles. --Trovatore (talk) 18:56, 5 March 2016 (UTC)

Yes, I agree. — Carl (CBM · talk) 19:03, 5 March 2016 (UTC)

I'd just like to say that it's quite embarrassing that the aforementioned edit was the first one to introduce (at least somewhat) sourced statements, considering that the article had some discussion about its contents almost five years ago and has been tagged with maintenance templates for almost two years. An anonymous contributor edited the article shortly before that, essentially removing unsourced statements, which is exactly what's done on Wikipedia in similar cases, but his edit was reverted without much scrutiny. —Matěj Grabovský (talk) 20:51, 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)

Well, I'm not willing to call Joel a crank :-). He's a key player in current set theory and his statements have to be taken into account. The problem is that he's signed on as the leader of this so-called full-blooded Platonism, which is formalism in not-very-convincing makeup, and tends to confuse discussions.

I don't think "countable within ZFC" really makes sense. ZFC is a fundamentally syntactic object, and countable-full-stop can't be understood that way. --Trovatore (talk) 20:59, 5 March 2016 (UTC)

I would think it may be more accurate to describe Hamkins' arguments via his own terminology - multiverses - rather than "full blooded platonism", which has different connotations. Hamkins has described them as having "affinities" [4]. — Carl (CBM · talk) 21:05, 5 March 2016 (UTC)

Could be. It's frequently hard for an outsider to understand distinctions within a movement. My objections to both multiverses and full-blooded Platonism are pretty much identical, so I don't really distinguish them, but of course I don't want to misrepresent his position. --Trovatore (talk) 21:15, 5 March 2016 (UTC)

Re David Eppstein: The two things that you say are theorems are indeed theorems, as everyone here agrees. Nobody (so far) has been pushing crankish ideas, and indeed many of us have PhDs in logic. The problem that the new references are getting at, of course, is that there is no reason a model of ZFC should have a function which takes a formula and returns the real defined by that formula (or 0 if the formula does not define a real); the naive argument seems to assume a function of that sort, in order to draw a contradiction. The existence of models of ZFC in which every real is definable shows that we cannot directly infer "there are undefinable real numbers" only from the assumption that our favorite universe of sets satisfies the ZFC axioms.

In any case, this article has been sitting too long. I am glad that Matěj Grabovský made the edits he did, if it helps to get the ball rolling to make some long-overdue improvements. — Carl (CBM · talk) 21:00, 5 March 2016 (UTC)

The argument is not that such a function must exist in the model, just that it must exist, period. This is not a ZFC argument, per se. But it's informally clear. --Trovatore (talk) 21:33, 5 March 2016 (UTC)

Ok, the new version and its classification of different types of definability makes things much clearer to me. It seems weird that there might not exist a function from formulas uniquely satisfiable over the reals to their satisfiers, but lots of things in set theory are weird when one first encounters them. Anyway, I'm happy to retract my accusations of crankery. —David Eppstein (talk) 22:27, 5 March 2016 (UTC)

My view is that what you say is "weird" is in fact too weird to be true. The "naive" argument is correct as it stands. But it's not a first-order argument from ZFC, and that does need to be clear in anything we say about it. --Trovatore (talk) 22:30, 5 March 2016 (UTC)

It may help if you write out (not in the article) the details of the "naive" argument, including in particular how to justify that the set of definable reals is countable. This would help isolate which axioms beyond the axioms of ZFC are actually being used. The fact that the set of formulas is countable seems unobjectionable; it's the intermediate conclusion that the set of definable reals i countable where the naive argument is shaky. — Carl (CBM · talk) 22:58, 5 March 2016 (UTC)

"Which axioms are actually being used." I think you know I don't hold the axiomatic-foundationalist view. I think the argument is complete as it stands; I don't see any need to add to it. --Trovatore (talk) 22:59, 5 March 2016 (UTC)

OK, sorry, that was maybe a bit abrupt. I think I can point you to the key issue. You say you agree there are countably many definitions, so there's a surjection from naturals to definitions. Then each definition defines a unique real, but you're concerned that there isn't a surjection from naturals to the reals thus defined.

But such a surjection would be (in the usual implementation) just a set of ordered pairs (n, r_n) where r_n is the real defined by definition n. For each n, that clearly makes sense, so you seem to be concerned that the pairs can't be collected into a set.

But the point is, the whole idea of the von Neumann universe is that every successor stage is the powerset of the stage before it. Not the powerset relative to some model, but the real honest-to-God absolute powerset. It contains absolutely all ways of gathering together possibly some, but not necessarily all, elements of the previous stage. It cannot be extended, because it is complete and contains absolutely everything of the correct form.

So it certainly must contain the desired set of ordered pairs. --Trovatore (talk) 08:31, 6 March 2016 (UTC)

Assessment comment

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)

Find an undefinable real number

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", ${\frac {2}{3}}$ is "two thirds", ${\sqrt {2}}$ 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 a₁, the a such that gf(a) = 2 is a₂, the a such that gf(a) = 3 is a₃, 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 a₁, a₂, a₃, ... 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 a_m 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 ≠ a_m for any m, since the m-th digit after the decimal point of b and a_m 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)

It seems you have rediscovered the Berry paradox. Step 1 cannot be made precise enough to cover all definitions of numbers, and the remainder of the construction only finds a number not in the list from step 1. — Carl (CBM · talk) 16:21, 5 April 2017 (UTC)

Why? All definable number a can be described with some (finite) English sentence. If and only if a can be described with some (finite) English sentence, then a is a definable number. e.g. ${\sqrt {2}}$ can be described with the English sentence "the square root of 2", and it maps to the natural number $84\cdot 95^{19} 72\cdot 95^{18} 69\cdot 95^{17} 0\cdot 95^{16} 83\cdot 95^{15} 81\cdot 95^{14} \dots 70\cdot 95^{2} 0\cdot 95^{1} 18\cdot 95^{0}$.

I'm sorry; this is more specifically Richard's paradox. — Carl (CBM · talk) 17:02, 5 April 2017 (UTC)

The definitions (sentences) in the article of Richard's paradox (e.g. "not divisible by any integer other than 1 and itself") has many numbers (all primes). Thus, it does not describe to one number, and we skip the n to the sentence. An example of sentence we include is "seven", which describes to one number (7), and the n to the sentence ("seven") is $83\cdot 95^{4} 69\cdot 95^{3} 86\cdot 95^{2} 69\cdot 95^{1} 78\cdot 95^{0}=6820343533$. Thus, the definable number 7 maps to the natural number 6820343533. — Preceding unsigned comment added by 101.9.164.60 (talk) 17:31, 5 April 2017 (UTC)

"may not form a set"

A recent edit called my attention to this text:

Because the notion of definability in the language of set theory cannot itself be expressed in the language of set theory, the collection of real numbers definable in the language of set theory may not form a set. However, assuming they do form a set, the real numbers definable in the language of set theory over a particular model of ZFC form a field.

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)

That sentence would most naturally be read as "the real numbers definable in a model of set theory may not be a set in that model" - which certainly seems correct to me. We have to talk about the definable reals of a given model from outside that model, as usual. The first clause does seem to be referring to the separation axioms, but that clause could be omitted. The important point IMO is that we need to assume the definable numbers form a set in order to prove they form a field. Including that point should be unproblematic for a realist, because the assumption is trivial from a realist perspective; but including it helps to highlight that the situation with the definable numbers being a field is not their closure under the arithmetic operations, it's whether they are actually a set. The proof that the definable reals of a model form a field is also written from a perspective outside the model. — Carl (CBM · talk) 01:54, 12 April 2017 (UTC)

I don't have a problem with writing "the real numbers definable in a model of set theory may not be a set in that model" (assuming you/we can find an example, probably easy but I'm not instantly thinking of one — obviously it's not the case for those countable models in which all reals are definable, because in that case the set of all reals definable in the model is just the set of reals of the model). I don't agree at all that that's the natural reading of the text as it stands. --Trovatore (talk) 02:09, 12 April 2017 (UTC)

Mathoverflow criticizes us

"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)

Well, this is not Math Overflow criticizing us, so much as Hamkins criticizing us (if I've understood correctly who wrote the answer). Hamkins has a particular foundational view, one I personally sharply disagree with (not that my opinions are relevant per se).

But in any case I think he has not kept up with the evolution of the page, unless the answer was written some time ago. He doesn't say specifically what are the "fundamental errors and false claims", but he had made earlier remarks along the same lines, and since then, the article has been almost entirely rewritten (mostly by CBM I think; I contributed a general plan of action, which I think influenced the rewrite). --Trovatore (talk) 22:03, 5 February 2018 (UTC)

Ah, I just saw the date on Hamkins's answer — October 29, 2010. So yes, some time ago. --Trovatore (talk) 22:06, 5 February 2018 (UTC)

This article was heavily revised since then, and the problems that were present at the time are all reasonably addressed, in my opinion. — Carl (CBM · talk) 00:31, 6 February 2018 (UTC)

Yes, and we owe Carl a rising vote of thanks. Nice work. --Trovatore (talk) 01:18, 6 February 2018 (UTC)

Indiscernibility

Is a real number undefinable with respect to first-order ${\mathcal {L}}_{\in }$ formulae iff it's indiscernible? C7XWiki (talk) 03:58, 2 March 2021 (UTC)

@C7XWiki: Per WP:TALK#TOPIC, we're not supposed to discuss that here unless it's part of a discussion of what should appear in the article. For questions about the topic, we have the refdesks. Why don't you ask at WP:RD/Math? We could use some interesting questions there. --Trovatore (talk) 04:48, 2 March 2021 (UTC)