The field of “useful reals” between rational and real numbers (2019)
chittur.dev
chittur.dev
(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.
> 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.
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?
But yes, Chaitin's constant is an example of a number that is definable but not computable.
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...
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.
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”.
Or are you referring to a Cauchy sequence that exists, but can't be defined using our symbology?
This is a rabbit hole with no end.
This does not hold if you demand that, for example, the map
k -> a_k
that represents the Cauchy sequence, is a computable function.
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.
Edit: oops, not that. The sequence itself - not the "useful reals" element of the sequence - has to be non-constructive...
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".
Exploring the consequences of alternative definitions is fantastic, let’s do more of that.
Redefining the terms that somebody else uses in a conversation sucks royally. Everybody hates it when people do that. Don’t be that guy.
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".
Does that seem OK to you?
"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.
- If it is a field, it contains π, π², π³, … which are linearly independent.
- By definition, an algebraic field extension is finite dimensional.
It's not even a finite extension
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 ℚ.
Do we know that? My search doesn’t get more than https://www.encyclopediaofmath.org/index.php/Lindemann_theor..., which proves it for “𝑒, 𝑒², 𝑒³, …“.
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.
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.
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.
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.
Ok, did I miss the explanation of that? Or is it something in "part 2" which I didn't see a link to?
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:
N | Z
---------
0 -> 0
1 -> 1
2 -> -1
3 -> 2
4 -> -2
5 -> 3
6 -> -3
Isn't there a theorem that speaks of the existence or non-existence of a set whose cardinality is strictly larger than Q and strictly smaller than R.
And a conjecture that says this theorem 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:
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.)
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.
Names are just names. Euclid's Algorithm is an algorithm. The Division Algorithm is a theorem.
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.)
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.
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
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.
Is this true without the Axiom of Choice? Don't you need a choice function to order the numbers before you can diagonalize them?
You can order the set of all definitions, by prepending each definition with its length and then using the ordering (numerical order, alphabetical order).
> 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.
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?
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.
(Note this is different from constructible numbers, which the author mentions. That has to do with classical geometry.)
All of the other essays in the same book are also good. :-)
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.
It is a function from objects onto booleans.
> what's the definition of the implication symbol
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.
Next question?
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.
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.
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.
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.
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.
Repeat after me, the Creed of Numbers:
" The imaginary numbers aren't imaginary.
The real numbers aren't real. "
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.
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).
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.
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.
Are you talking about Cantor's argument that the reals are uncountable? That doesn't need choice.
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), ...