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 periods...)
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.
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 computer program that would generate the number to any desired precision. How does that differ from the set of numbers with a finite symbolic representation?
Hmmmm... maybe by asking that question I've led myself to the answer. Chaitin's Constant has symbolic representations, one of which being the Wikipedia page that describes it: https://en.wikipedia.org/wiki/Chaitin%27s_constant. Does that mean it's included in the complement of the Computable Numbers in the Useful Reals? Are the Computable numbers a subset of the Useful Reals?
You're mixing up "defined" with "defined via a decimal numeral" we can define these numbers without much difficulty via finite formula that compute them. This is a completely valid definition, it is just not a decimal numeral.
An interesting idea might be "useful integers" which requires whatever definition we have to allow approximation of any finite subsequence with error converging to zero given more computational power.
Sorry if I misunderstand you. If I have a Cauchy sequence of "useful reals", wouldn't the convergence be, by definition, a "useful real"? That is, I can write down the Cauchy sequence, so it's now symbolically noted, right?
Or are you referring to a Cauchy sequence that exists, but can't be defined using our symbology?
Name one such sequence of "useful reals" that is Cauchy but doesn't converge to a "useful real". You can't, can you? "Useful" Cauchy sequences of "useful reals" (i.e. those you can define) all converge to a "useful real".
Not "between" in the sense of having an intermediate cardinality between rationals and reals, since they are exactly the numbers available from strings in some symbolic system or other. Seems to be a slightly expanded case of algebraic numbers, since additional forms (like infinite definite integrals) are allowed.
Note that in mathematics, when not otherwise specified, sets are typically compared by inclusion, not by cardinality. No mathematician would say "set Y lies between X and Z" to mean |X|<|Y|<|Z| and expect to be understood, unless there was some particular context to suggest that interpretation. It would in general be understood to mean, as it does here, that X is a subset of Y which is a subset of Z.
When talking about subsets of an infinite set, and in particular fields, the common understanding of the word “between” means in terms of subsets, not cardinality. For instance, the field Q(sqrt 2) lies between the fields Q and Q(sqrt 2, sqrt 3).
> 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't be precisely described, a contradiction.
You can make it precise if the language in which you define a "useful real" is richer than the language in which individual useful reals must be defined. For instance, model theorists will talk about definable reals in a model of set theory: https://en.wikipedia.org/wiki/Definable_real_number#Definabi...
> A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds (see Kunen 1980, p. 153). This notion cannot be expressed as a formula in the language of set theory.
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 multiple different ways. E.g. the number 2 can be described as 1+1, 1+1+1-1, 1+1+1+1-1-1, ad infinitum.
Furthermore, I'd assume that not every string in that symbolic notation constitutes a valid, precise description of some real.
So Cantor's diagonalization produces some unique description of a number that differs from all of the descriptions - but it's possible and plausible that the description refers to a number that is in the list but has been described differently; and it's possible and plausible that the constructed description does not describe any real whatsoever.
Or am I completely misunderstanding you and you did not intend to apply Cantor's diagonalization to the descriptions?
> 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?
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 but is not definable. This means at the very least we have a mathematical statement saying there exists a number such that some logical predicate is valid (we may not even have a construction in ZFC), which can also be constructed using a Cauchy sequence. This mathematical statement is embedded in ZFC, and since we are humans it must be finite. In fact, you could come up with a binary representation for such a statement using methods from Godel, by mapping each symbol to some binary representation. Therefore, this number can be represented as a sequence of zeros or ones, a contradiction.
Aside from all the other issues people have raised, equality is not decidable for the “useful reals”. While they form a field, they do not form a computably-ordered field, which makes them quite a bit less useful than many other number systems.
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.
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.
Such a weird perspective. The author thought they discovered something that true and interesting and kind of fundamental but wasn't already published, but didn't think it was worth publishing to the math community?
Thinking about maths is fun, and some people do it for leisure and write what they find in innocuous places like blogs. Usually the things you come up with are already well-known by a different name (as was the case here), so one would usually not publish something like this.
Think of it just like a random blog post on someone’s thoughts. Just because it contains maths doesn’t mean it needs to be published or not, it can be free to live its own life.
this reminds me of unit testing, where the tests come up with arbitrarily defined numbers, and the function you test tries to come up with a consistent way to count them. If you can change your function each time a test is added, the tester never wins. Isn’t this similar? It seems like cherrypicking to include simple formulas with e and pi in your numbering system.
There is well defined name for "useful reals": Algebraic numbers. Of course the well-definedness necessitates some limit on how the symbolic description looks like (ie. algebraic numbers are roots of polynomials with rational coefficients) because every real number can be described by some arbitrarily complex symbolic notation.
Edit: I vaguely remember that there used to be some name for the intersection of algebraic and real numbers, but I neither can remember it nor can find it on wikipedia.
> every real number can be described by some arbitrarily complex symbolic notation
This seems like it would have to be false, because otherwise the reals would be countable (iterate through every possible 1-character string, then every possible 2 character string, then 3 chars, etc and in a finite (but potentially very very large) amount of time you would come across the description of any real number that can be described).
The author claims that this set is countable but not sure if that is true. My argument is based on Cantor's theorem [1], which states that the power set has cardinality strictly greater than the set.
In order for the set of symbols to be finite field it must grow therefore since rational is infinitely countable from Cantor it must hold that "useful reals" is uncountable.
If you have a finite set of symbols, then the set of finite sequences of those symbols is countable. The key here is 'finite sequences', if you were to allow for infinite sequences then the set if uncountable.
I think of the "useful reals" being the "reals that have names". Alan Turing developed the Turing machine to get a handle on the "useful reals" since you can make a Turing machine write them out one digit at a time.
Given that, I don't like the term "real numbers" at all because they are phony compared to the "useful reals" -- if you reject the axiom of choice then the construction that Cantor does to construct a real isn't valid.
Despite calling for a rebuild of math and science based on computation, Steve Wolfram has yet to take the critical step of rejecting the axiom of choice. I wish he would man up.
[+] [-] Sniffnoy|6 years ago|reply
(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 periods...)
[0] https://en.wikipedia.org/wiki/Definable_real_number
[1] https://mathoverflow.net/a/44129/5583
[+] [-] dwohnitmok|6 years ago|reply
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.
[+] [-] emacdona|6 years ago|reply
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 computer program that would generate the number to any desired precision. How does that differ from the set of numbers with a finite symbolic representation?
Hmmmm... maybe by asking that question I've led myself to the answer. Chaitin's Constant has symbolic representations, one of which being the Wikipedia page that describes it: https://en.wikipedia.org/wiki/Chaitin%27s_constant. Does that mean it's included in the complement of the Computable Numbers in the Useful Reals? Are the Computable numbers a subset of the Useful Reals?
[+] [-] Sniffnoy|6 years ago|reply
But yes, Chaitin's constant is an example of a number that is definable but not computable.
[+] [-] emacdona|6 years ago|reply
[+] [-] D_Alex|6 years ago|reply
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...
[+] [-] voxl|6 years ago|reply
An interesting idea might be "useful integers" which requires whatever definition we have to allow approximation of any finite subsequence with error converging to zero given more computational power.
[+] [-] circlefavshape|6 years ago|reply
[+] [-] klodolph|6 years ago|reply
So if you have a sequence of “useful reals” that is Cauchy, it will converge to a real number but it may or may not converge to a “useful real”.
[+] [-] function_seven|6 years ago|reply
Or are you referring to a Cauchy sequence that exists, but can't be defined using our symbology?
[+] [-] ummonk|6 years ago|reply
[+] [-] doomrobo|6 years ago|reply
"reals are a field extension of ℚ. They could be considered an algebraic number field..."
This is not an algebraic extension. Pi is a "useful real number" and it is not algebraic over Q.
[+] [-] klodolph|6 years ago|reply
- If it is a field, it contains π, π², π³, … which are linearly independent.
- By definition, an algebraic field extension is finite dimensional.
[+] [-] jepler|6 years ago|reply
[+] [-] Sniffnoy|6 years ago|reply
[+] [-] joppy|6 years ago|reply
[+] [-] xtacy|6 years ago|reply
[+] [-] ramshorns|6 years ago|reply
[+] [-] OscarCunningham|6 years ago|reply
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't be precisely described, a contradiction.
[+] [-] benkuhn|6 years ago|reply
> A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds (see Kunen 1980, p. 153). This notion cannot be expressed as a formula in the language of set theory.
[+] [-] PeterisP|6 years ago|reply
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 multiple different ways. E.g. the number 2 can be described as 1+1, 1+1+1-1, 1+1+1+1-1-1, ad infinitum.
Furthermore, I'd assume that not every string in that symbolic notation constitutes a valid, precise description of some real.
So Cantor's diagonalization produces some unique description of a number that differs from all of the descriptions - but it's possible and plausible that the description refers to a number that is in the list but has been described differently; and it's possible and plausible that the constructed description does not describe any real whatsoever.
Or am I completely misunderstanding you and you did not intend to apply Cantor's diagonalization to the descriptions?
[+] [-] thaumasiotes|6 years ago|reply
Is this true without the Axiom of Choice? Don't you need a choice function to order the numbers before you can diagonalize them?
[+] [-] solinent|6 years ago|reply
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 but is not definable. This means at the very least we have a mathematical statement saying there exists a number such that some logical predicate is valid (we may not even have a construction in ZFC), which can also be constructed using a Cauchy sequence. This mathematical statement is embedded in ZFC, and since we are humans it must be finite. In fact, you could come up with a binary representation for such a statement using methods from Godel, by mapping each symbol to some binary representation. Therefore, this number can be represented as a sequence of zeros or ones, a contradiction.
QED
[+] [-] stephencanon|6 years ago|reply
[+] [-] NelsonMinar|6 years ago|reply
(Note this is different from constructible numbers, which the author mentions. That has to do with classical geometry.)
[+] [-] btilly|6 years ago|reply
All of the other essays in the same book are also good. :-)
[+] [-] dchyrdvh|6 years ago|reply
[+] [-] PureParadigm|6 years ago|reply
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.
[+] [-] lisper|6 years ago|reply
[+] [-] leni536|6 years ago|reply
[+] [-] unknown|6 years ago|reply
[deleted]
[+] [-] lonelappde|6 years ago|reply
[+] [-] joppy|6 years ago|reply
Think of it just like a random blog post on someone’s thoughts. Just because it contains maths doesn’t mean it needs to be published or not, it can be free to live its own life.
[+] [-] superjan|6 years ago|reply
[+] [-] unknown|6 years ago|reply
[deleted]
[+] [-] scarejunba|6 years ago|reply
[+] [-] H8crilA|6 years ago|reply
It is not "useful" in the sense that reals are most "famous" for: it is not complete. Cauchy sequences can diverge in the useful reals field.
[+] [-] currymj|6 years ago|reply
[+] [-] lonelappde|6 years ago|reply
Repeat after me, the Creed of Numbers:
" The imaginary numbers aren't imaginary.
The real numbers aren't real. "
[+] [-] dfox|6 years ago|reply
Edit: I vaguely remember that there used to be some name for the intersection of algebraic and real numbers, but I neither can remember it nor can find it on wikipedia.
[+] [-] JoshuaDavid|6 years ago|reply
This seems like it would have to be false, because otherwise the reals would be countable (iterate through every possible 1-character string, then every possible 2 character string, then 3 chars, etc and in a finite (but potentially very very large) amount of time you would come across the description of any real number that can be described).
[+] [-] evanb|6 years ago|reply
[+] [-] arberavdullahu|6 years ago|reply
In order for the set of symbols to be finite field it must grow therefore since rational is infinitely countable from Cantor it must hold that "useful reals" is uncountable.
[1] https://en.wikipedia.org/wiki/Cantor%27s_theorem
[+] [-] selectionbias|6 years ago|reply
[+] [-] PaulHoule|6 years ago|reply
I think of the "useful reals" being the "reals that have names". Alan Turing developed the Turing machine to get a handle on the "useful reals" since you can make a Turing machine write them out one digit at a time.
Given that, I don't like the term "real numbers" at all because they are phony compared to the "useful reals" -- if you reject the axiom of choice then the construction that Cantor does to construct a real isn't valid.
Despite calling for a rebuild of math and science based on computation, Steve Wolfram has yet to take the critical step of rejecting the axiom of choice. I wish he would man up.
[+] [-] OscarCunningham|6 years ago|reply
Are you talking about Cantor's argument that the reals are uncountable? That doesn't need choice.