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.
Upon re-reading my reply, it might be worthwhile to simply quote Hamkins' conclusion in full.
> And therefore neither are you able to do this in general. The claims made in both in your question and the Wikipedia page [the Wikipedia page has now since been updated] on the existence of non-definable numbers and objects, are simply unwarranted. For all you know, our set-theoretic universe is pointwise definable, and every object is uniquely specified by a property.
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?
Looks like the wikipedia page says there's a Chaitin's constant for each Computable Function, so yeah, countable. That's if I'm reading it correctly. Even if the constant differs for every program that computes a given Computable Function... still countable, though (if I'm doing my math right).
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.
GP did not mix up anything. Some of those finite formulas also will be too long to be written within the constraints of this universe. The pigeonhole principle applies just as much to finite formulas as it does to finite strings of decimal digits.
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?
You cannot write a general Cauchy sequence of useful reals with a finite number of symbols. Hence you cannot in general express its limit with a finite number of symbols.
There are uncountably many Cauchy sequences of useful reals. You can’t write them all down. So now you have to also restrict yourself to “useful Cauchy sequences of useful reals”.
Set theorists have located the "end" for all practical and most impractical purposes. Let M be the minimal countable transitive model of ZFC. Declare a real to be useful if and only if it is in M.
I am a bit shocked, because that seems like a really dishonest way of doing things. “Surprise! Actually, I am not talking about Cauchy sequences, but only computable Cauchy sequences.”
If you change the rules you had better be up front about it.
What you are describing is a completely different definition for “complete metric space” than what is commonly accepted by the mathematical community at large. So do not be surprised that by using different definitions, you come to different conclusions.
>
I am a bit shocked, because that seems like a really dishonest way of doing things. “Surprise! Actually, I am not talking about Cauchy sequences, but only computable Cauchy sequences.”
Rather: If countability is important to you, you should change the rules so that the property that the field is closed w.r.t limits of Cauchy sequences does not make your set uncountable.
Redefining the rules if something does not work is how you do mathematics works all the time:
- A PDE does not have a solution in a classical sense and you hate this? No problem: You invent the theory of weak solutions and distributions and simply change the concept what is to be considered a solution of the PDE.
- The concept of algebraic varieties turns out to be to limiting to obey the rules that you would love them to have? No problem: You define the concept of algebraic schemes and now talk about algebraic schemes instead of varieties (https://en.wikipedia.org/w/index.php?title=Scheme_(mathemati...).
TLDR: Mathematics is often the art of "defining your problems away".
> If countability is important to you, you should change the rules so that the property that the field is closed w.r.t limits of Cauchy sequences does not make your set uncountable.
Ok, fine: I hereby declare that the set Q of rationals is a closed field, because I define "closed" to mean "closed under Cauchy sequences whose limit points are rational numbers".
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".
Another nit, not all algebraic extensions are finite dimensional. Just adjoin an infinite number of linearly independent roots (square roots, cube roots, etc). Algebraic, but not finite
Slight correction. Your first bullet point, and hence your proof that ℚ cannot contain π, is correct.
A number x is algebraic over ℚ if and only if it generates a finite field extension, i.e. if x, x^2, x^3, etc. have a linear dependence relation.
However, as jopolous pointed out, you can get infinite dimensional algebraic field extensions by adjoining infinitely many algebraic numbers. For example, the set of all numbers which are algebraic over ℚ is a field, and this field is an infinite degree extension of ℚ.
I don't think that's the usual definition of algebric extension. Wikipedia (https://en.wikipedia.org/wiki/Algebraic_extension) says that an algebraic extension is one where every element is the root of some nonzero polynomial over the base field. So for example the algebraic numbers would be algebraic over the rationals, even though they're infinite dimensional over the rationals.
There are two ways we can go about this. We can either take a closer look at the Lindemann theorem, or we can talk about the definition of “transcendental number”. I’m not going to put a full proof here.
If you look at the Lindemann theorem, you can transform the equation so that it uses π instead of e. Multiply all of the exponents by i (which is algebraic!) and then use Euler’s identity. You end up with the same formula, but with π instead of e.
However, if we already know that π is transcendental (which is proven by the Lindemann theorem using the above technique), we can rewrite any linear combination of B = {1, π, π², π³, …} as P(π) where P is a polynomial with coefficients in ℚ. Because π is transcendental, we know that P(π)=0 only if P is the zero polynomial (that is the definition of transcendental number).
In general, one of the big tricks here is that the set of polynomials is a vector space, and the powers B = {1, x, x², x³, …} span the entire vector space.
You're totally right, I could have worded that differently. I actually posted an infinite field extension that is algebraic elsewhere in this thread, but usually those are tricky and I haven't seen them pop up as often as finite algebraic extensions
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).
Unlike most of the time, I read the article first and now that I'm here, that was the question I had - clearly it's smaller than reals, but how and why is this field larger than rational numbers? Guess it's not.
It’s larger than the rational numbers in the sense that it is a strict superset. Cardinality is what a lot of people reach for when they are talking about “larger” or “smaller”, but there are lots of other useful concepts which we can translate to “larger” and “smaller”.
So when someone says “larger” or “smaller”, your first step might be to try and translate that relationship into a more precise mathematical concept, like cardinality or measure.
Casual terminology also leads to weird discussions. Like when someone asks whether some function is “close” to another, and these functions are defined in terms of vector spaces. Unfortunately, “closeness” does not necessarily exist in a vector space. So the answer may be that the question does not make sense.
> “closeness” does not necessarily exist in a vector space.
The asker will give a definition. For example, two vectors are close if sqrt of dot product of difference of the two vectors is smaller than some number delta.
There is a 1-to-1 mapping between the sets, so by definition that means they have the same cardinality.
Let me give a more common example. Consider these two sets: N, the set of non-negative integers, and Z, the set of all integers. Clearly, everything in N is also in Z, and then some. But N and Z still have the same cardinality, because there are 1-to-1 mappings between the two sets. Here is one example of such a mapping:
..etc. The formula for this mapping would be floor(n/2)*(-1)^(n%2). Clearly everything in the left set has exactly one corresponding item in the right set and vice versa, so they must be the same "size", even though the right set contains every item in the left set and then some.
> that was the question I had - clearly it's smaller than reals, but how and why is this field larger than rational numbers?
As pdonis points out sidethread, this isn't really a valid question. (Or rather, the question is fine, but the answer to all questions of this form is already well-known, so there's no point in asking this specific question.)
It is not possible to prove that a set is both smaller than the reals and larger than the rationals, because such a set would disprove the continuum hypothesis. (And symmetrically, it isn't possible to prove that no such set exists, because that would be a proof of the continuum hypothesis.)
Not really. The words are used in closely analogous ways. But the "hypothesis" in "continuum hypothesis" is part of the name of the continuum hypothesis, carried over from a time when we didn't know the answer.
Names are just names. Euclid's Algorithm is an algorithm. The Division Algorithm is a theorem.
"It is not possible to prove that a set is both smaller than the reals and larger than the rationals, because such a set would disprove the continuum hypothesis."
Sure, even without much of a mathematical background, people generally take it for granted. Which is why it's disappointing that a suggestion of overturning it isn't fulfilled.
Suggestion of overturning it? It's a proof. That article would be headlined "disproving the independence of the continuum hypothesis" or some such; it would be huge news, not somebody's fun blog post.
Given that continuum hypothesis is independent of ZF, it would be very interesting to find a set of interest to a general audience whose cardinality lies between the rationals and the reals.
A "theorem" is a proved proposition, so there is no such thing as a theorem that might well be unprovable.
The proposition you refer to (which is not a theorem since no proof is known, and in fact it has been shown that this proposition is logically independent of the usual foundations of set theory, so it cannot be proved in that framework) is called the Continuum Hypothesis:
Technically you can't compare two countable sets using the Lebesgue measure, because they will both have measure 0.
EDIT: You could instead say something like 'the useful reals are an infinite-degree field extension of the rationals'. (Although as I mentioned elsewhere it's actually impossible to define the useful reals.)
> 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?
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.
> 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).
In this case you can define an order without using Choice. By definition of 'useful number' each useful number has some finite string that describes it. The finite strings can be put into lexicographic order, and then the useful numbers can be ordered according to the position of the lexicographically first string that describes 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.
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:
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.
We don't "come up" with ideas from other ideas using some closed form rules of logic, like in Coq or some Turing machine. Instead, we discover new ideas.
There is a world of ideas and the real world. People live in both worlds. When they discover a new idea, often by accident, they label it with a symbol and use it in the real world. Other people can see the same idea and since they can't fully describe it with words, they agree to use the new symbol.
We describe new concepts with words, but those definitions are underspecified: they refer to things with vague or non existent descriptions, or just common sense. What is "set" for example? The same words often mean different things in different contexts. This extra meaning that's always attached to words is what makes these definitions non countable.
Even if ideas come from an uncountable set (not convinced yet), there are still only countably many ideas people will ever have. Each time anyone comes up with an idea, I can assign it a new integer.
Im merely trying to drag the concept of separating ideas and reality as two different but very real worlds under the spotlight of everyone's attention. This concept is fundamental and very old. I won't be able to defend this idea with formal proofs.
So long as every real number exists, has properties and so on. Every such number is a separate idea. They exist, no matter whether we know about them or not.
Ah. Personally, I distinguish between potential ideas and actual ideas. To be an actual idea, it has to reside in someone's brain (or a computer, or some other data-processing system). The reals correspond to the set of potential ideas, but the set of actual ideas is not only countable, but almost certainly finite.
We can call it a materialized idea, like an implemented software algorithm. I'm indeed talking about the world of ideas that's not real, i.e. non material. The proof of the Fermat's theorem has always existed, but only recently it's been discovered by Wales.
The same word can have infinitely many meanings. So even if we restrict the length of proofs to 140 chars and restrict the alphabet to Latin, there will be infinitely many proofs there: well just start inventing new meanings for the same words.
> The same word can have infinitely many meanings.
But only countably many because definitions have to be finite too. The combination of proof + definitions must also be finite, so there can only be countably many of them.
What's the definition of "set"? Or what's the definition of the implication symbol, i.e. when someone says that something obviously follows from the previous theorems? We don't bother to define a lot of foundational things in math.
The implication symbol doesn't have a definition, it's part of a completely different kind of reasoning process. Formal symbolic reasoning is a completely different animal than informal arguments involving words that have definitions.
Definitional recursion has to bottom out somewhere. (OK, it can also be circular, but I'm guessing you would not find that satisfactory.) Whatever words I use to define "function" you can always turn around and insist that I define those words. It's a never-ending game. It ultimately boils down to the definitions of words like "true" and "false, "same" and "different", whose meanings can only be communicated by way of examples: X and X are the same, X and Y are different.
But none of this has anything to do with the matter at hand. There are a finite number of atoms in the universe. Those atoms can only arrange themselves into a finite number of sentient creatures (or computers), each of which has only a finite brain in which can reside only a finite number of thoughts. So no matter how you slice it, the number of realized ideas in this universe is going to be not only countable but actually finite because there is only a finite amount of time before heat death.
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.
Completeness in the "full" reals is a useless feature, though. All is gives you is an emotional crutch to pretend your cauchy sequences can be mapped to regular numbers. But it doesn't give you anything you didn't already have in the cauchy sequences and useful reals.
You are of course right, reals are isomorphic to equivalence classes of Cauchy sequences on Q. But once you are dealing with equivalence classes of Cauchy sequences on Q you might as well give it a name. Maybe call it R.
His point is different. You cannot (by definition) ever write a "name", a formula, a rule, a lim expression, anything really, for a real that is not in the useful reals.
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.
Elaborating, the hypothesis that Cantor disproves is "The real numbers are countable -- that is to say, the real numbers can be put into one-to-one correspondence with the natural numbers".
You never have to use the axiom of choice, because the hypothesis tells you there is a one-to-one function between the reals and the naturals. You can then order the reals in the order suggested by their image in the naturals: f(0), f(1), f(2), ...
(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