Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The field of “useful reals” between rational and real numbers (2019)

chittur.dev

Post reply on HN
Print view View original

81–90 of 121 posts

Re: The field of “useful reals” between rational and real numbers (2019)

#81

Post by solinent »

OscarCunningham wrote: post #48
solinent wrote: post #43

Earlier quoted context omitted.

Another argument that's not completely non-constructive. The real numbers have to be constructed. Typically, a number is represented by a Cauchy sequence or a Dedekind cut. To determine if a real number is representable symbolically, we simply need a finite sequence of symbols which stands for this Cauchy sequence, lets say. Theroem: The real numbers and definable numbers are the same set. Assume a real number exists…

I don't understand that argument. But in any case, Cantor's argument is very constructive. It literally gives you the decimal expansion of the new number not in your set.

I didn't do it that much justice because I was discovering it independently, my arguments can easily be made rigorous, but you'd need a background in pure mathematics to understand it. However, there's a section on Wiki:

https://en.wikipedia.org/wiki/Definable_real_number#Definabi...

They start with a stronger definition of a definable number, so they find that they do exist.

I think given the argument above there must be a hole in my own argument, I'd have to go beyond ZFC.

Re: The field of “useful reals” between rational and real numbers (2019)

#83

Post by bloomer »

Sniffnoy wrote: post #36
emacdona wrote: post #10

The author claims in the notes that "The useful reals are similar, but not quite equivalent to other ideas in mathematics, such as [...] computable numbers." Is that correct? What is the complement of the Computable Numbers in the Useful Reals? What is the complement of the Useful Reals in the Computable Numbers? I've always thought of Computable Numbers as all numbers able to be represented by a finite string, ie: a…

The standard term is "definable", not "useful": https://en.wikipedia.org/wiki/Definable_real_number But yes, Chaitin's constant is an example of a number that is definable but not computable.

Yeah I think this terminology is odd because I think that the computable numbers are much more “useful” than the definable numbers.

Re: The field of “useful reals” between rational and real numbers (2019)

#84

Post by D_Alex »

If you look at the integers between say Graham's number (https://en.wikipedia.org/wiki/Graham%27s_number) and TREE3(https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem) you can observe that practically all of these integers, while "computable", cannot be defined within the known constraints of this universe.

Which raises an interesting question: In what meaningful sense do these numbers exist? They are just out of reach as the non-definable real numbers...

Re: The field of “useful reals” between rational and real numbers (2019)

#85

Post by dwohnitmok »

Sniffnoy wrote: post #35

None of this is somehow secret. The standard name for this is "definable"[0]. Although, one has to be really careful with this sort of thing; there are apparently a number of subtle logical issues[1] that come up when talking about these... (Note, by the way, that there's any number of other fields one could put inbetween; such as the field of algebraic reals, or computable reals, or the fraction field of the ring of…

Well that Math Overflow post is excellent.

One of the logical issues is that there is a model of ZFC where all reals are definable/useful. I'm guessing that's not what the author of this blog post is going for...

If this seems impossible given that the number of definitions is countable, note first that it is possible that a model of ZFC is itself countable (in a larger ambient model), but it cannot witness the countability of sets within itself. So when we say that a set is uncountable in ZFC, it is sometimes useful to make the distinction that it is only uncountable in the implicit model under discussion.

Then note that definability, unlike countability, cannot be itself defined in the language of ZFC (due to Tarski's undefinability of truth result). Note that this is different from saying it's independent of ZFC. It cannot even be expressed in ZFC. Hence, unlike countability, there is no "relative" concept of definability, at least not relative to first-order ZFC. Therefore the statement "every element of this model is definable" is more absolute than "every element of this model is countable" (but not absolutely absolute, we still have an ambient model we're working in, just a richer theory for that model).

The usual diagonalization argument within our entirely definable model of ZFC to try to construct a definable real number not contained in any countable enumeration of definable real numbers fails because we have no enumeration of definable real numbers. This is not a failure of constructivism (it is ZFC after all, we do have choice), but rather a consequence of the fact that definability cannot be expressed in ZFC so we don't have a way of even talking about the set of all definable real numbers within our model.

Re: The field of “useful reals” between rational and real numbers (2019)

#86

Post by dchyrdvh »

The premise of this idea - that anything describable can be written in a binary firm and is thus countable - seems wrong. It's wrong because we easily invent new concepts and put them into a symbolic form. We could invent a new concept, agree on a new symbol for it and add it to our alphabet. The set of ideas isn't countable and so our alphabet isn't countable. This alphabet can't be translated into some binary form either.

Re: The field of “useful reals” between rational and real numbers (2019)

#87

Post by lisper »

dchyrdvh wrote: post #86

The premise of this idea - that anything describable can be written in a binary firm and is thus countable - seems wrong. It's wrong because we easily invent new concepts and put them into a symbolic form. We could invent a new concept, agree on a new symbol for it and add it to our alphabet. The set of ideas isn't countable and so our alphabet isn't countable. This alphabet can't be translated into some binary form…

What makes you think that the set of ideas isn't countable?

Re: The field of “useful reals” between rational and real numbers (2019)

#88

Post by PureParadigm »

dchyrdvh wrote: post #86

The premise of this idea - that anything describable can be written in a binary firm and is thus countable - seems wrong. It's wrong because we easily invent new concepts and put them into a symbolic form. We could invent a new concept, agree on a new symbol for it and add it to our alphabet. The set of ideas isn't countable and so our alphabet isn't countable. This alphabet can't be translated into some binary form…

Why is the alphabet not countable? If each time you think of a new idea and make a symbol for it, I can also assign it to an integer (because there is always a next integer like there is always a new symbol you can come up with).

When you come up with a new concept, it should also be possible to write out a definition of it. If you can write down your definition (in English, math notation, etc.), then it comes from a countable set, since there are countably many things that you can write down.

Re: The field of “useful reals” between rational and real numbers (2019)

#89

Post by OscarCunningham »

PeterisP wrote: post #69
OscarCunningham wrote: post #38

> A “useful real” is just a real number that can be precisely described (not just approximated!) by some symbolic notation. Obviously, this definition is loose and depends greatly on your choice of symbols and their definitions. In fact, the definition is necessarily loose. If you could make it precise then you could carry out Cantor's diagonalisation procedure to produce a precise description of a real which couldn'…

It seems to me that Cantor's diagonalization fails here because of the very different nature of descriptions vs (for example) decimal notation. Every possible string of digits is a valid, unique number. That does not apply to descriptions. I'd assume that every number that can be precisely described by some symbolic notation can be described in that notation in multiple ways, and likely in an infinite number of multi…

I don't mean to apply the diagonalisation procedure to the descriptions. That wouldn't work for the reason you mentioned, and also because applying Cantor's diagonalisation to a bunch of finite strings might yield an infinite string.

What I meant was to apply Cantor's diagonalisation to the decimal expansions of the describable numbers. Take all of the describable numbers ordered lexicographically by their lexicographically first description, and then look at their decimal expansions and describe a new number that differs from the nth one in the nth decimal place (with the usual details to make sure you don't end up with a second representation of a number already present).

This gives the decimal expansion of an alegedly indescribable number, because it's different from all the ones on the list. But because I can describe the diagonalisation procedure, this decimal expansion is itself a valid description, and hence we have a contradiction.

Re: The field of “useful reals” between rational and real numbers (2019)

#90

Post by OscarCunningham »

lonelappde wrote: post #77
thaumasiotes wrote: post #46

Earlier quoted context omitted.

> the definition is necessarily loose. If you could make it precise then you could carry out Cantor's diagonalisation procedure to produce a precise description of a real which couldn't be precisely described Is this true without the Axiom of Choice? Don't you need a choice function to order the numbers before you can diagonalize them?

Finite descriptions are countable. Axiom of Countable Choice is not counterintuitive like Axiom of (Uncountable) Choice. You can order the set of all definitions, by prepending each definition with its length and then using the ordering (numerical order, alphabetical order).

That doesn't even need Countable Choice. You only need any form of Choice when you can't explicitly specify an order, which you did.
Post reply on HN