1) Another interesting way to rephrase it is that a single real number can contain an infinite amount of information. In contrast, other numbers discussed in this chapter can only encode finite amounts.
2) Some readers may wonder why we talk about "classes" to describe a collection of sets that share common property. Isn't a class just a set of sets?
Well, if you allow sets to be constructed from a universe of all imaginable mathematical objects - a principle known as unrestricted comprehension - you end up with contradictions. Most famously, you risk Russell's paradox: let P be a set of all sets that aren't members of themselves. Is P a member of itself? If not, then it should have been selected by the criteria - and should have been a member! But if we make it a member, it no longer satisfies the selection criteria, and we're back to square one.
To avoid this, in standard set theory, you're limited to constructing new sets by selecting objects from the sets you already have. This is known as restricted comprehension. In this context, we can still talk about collections of mathematical objects without showing how to build them, but we call these collections "classes". They may have set-like properties, but we're not supposed to do set operations on them. We can, however, do operations on any representative set in that class.
3) You might also encounter an alternative way to define reals using Cauchy sequences. In essence, we define ℝ in terms of converging sequences of rational numbers that get arbitrarily close to any real (and in the limit at infinity, point to the real *exactly*). As with Dedekind cuts, we're not saying how each of these sequences looks like, just that every real number is a converging sequence of rationals. Both of these methods are functionally equivalent; if you're interested in rational approximations of reals, you might get a kick out of this article: https://lcamtuf.substack.com/p/approximation-game
4) In the first article in the series (https://lcamtuf.substack.com/p/09999-1), we asserted that reals follow the Archimedean property, i.e., they don't include infinitesimals. It's an axiom, but we can show it follows from the construction approach discussed here, too. Every integer is finite. If so, the stepover between rational numbers can be arbitrarily small, but is always strictly larger than any conceivable notion of an infinitesimal (ε = "1/∞"). So, the partitions of ℚ made for x and x+ε must be indistinguishable, because the delta is smaller than the spacing of rational numbers.
5) In the same article, I introduced hyperreals without explaining their construction in a rigorous way. Hyperreals extend reals by adding infinitesimal and infinite quantities. There are several ways to approach this task, but one is to express infinitesimals as sequences of real numbers that converge to zero at different rates (and infinite values as the inverse).
I got a D in analysis. I can believe that 0 = {} but I had a hard time believing 1 = { 0, {}}. I can see how a Dedekind cut defines numbers but thats all a x b to me is not really {a-lower, a-upper} x {b-l, b-u}. Really the LUB was nonsense to me except for one thing, .9999... = 1.
Cardinality, ordinality and measure are what we have in the real world. I do believe there are irrational, transcendent, uncomputable and other numbers. Hyper reals, not sure, its just epsilon to me.
"Some of the tiles are redundant (e.g., 2 is the same as 4/2), but this is not important for the proof" there is therefore not an exact matchup on diagnolization of Q.
The professor said series do not equal sequences when I asked why can't you use the series test on a sequence. Isn't that what category theory is for.
Then there was how a differential equation is not a difference equation,
One Graduate student said quantum theory is not commutative and another professor said it was.
I also don't get Tropical analysis, the Collatz conjecture, modular forms and many other things.
I mean, I talk about a bit in the earlier article and the comments attached to it (https://lcamtuf.substack.com/p/how-has-mathematics-gotten-so-abstract). I think we're just finding ways to restate the principles of propositional logic in increasingly weird ways. It probably doesn't mean anything more than that. In particular, I don't think it describes physics or the real world. And maybe all the weirdness we keep discovering is an artifact of the underlying principles being flawed. I wouldn't be surprised if we're using a different model of logic or mathematics in 50-100 years, maybe causing all the talk of cardinalities disappear.
Or maybe it's going to unfold the way it did with negative numbers? In 200 years, every child will know about infinite ordinals and it will be weird to them that the ancients had some qualms about such a basic concept.
In the meantime... it's still sort of useful? Calculus is a prime example - we struggled with infinity for millennia, then came up with a framework that didn't really have a good mathematical basis but seemed to work, and then we developed formalizations that help us make sense of the whole thing.
> "Some of the tiles are redundant (e.g., 2 is the same as 4/2), but this is not important for the proof" there is therefore not an exact matchup on diagnolization of Q.
There are construction and traversal methods that skip over the duplicates to show the cardinality is the same, but I didn't feel the extra complexity is worth it for the article.
I feel like we are assuming that we can define “before” and “after” like a function with two rational numbers as input and true or false as output, then assuming we can “type cast” a real into these functions and they still work properly. Like you can say cutting rationals before five and after five leaves five but thats only because five itself is a rational and can have the greater than and less than functions defined on it.
That's the finer point of Dedekind cuts that I was trying to hint at: the construction of reals doesn't give you the function is_less(r, q) and is_greater_or_equal(r, q). Instead, it basically says "the set of real numbers is the set of all Dedekind cuts of ℚ". Which is both maddeningly vague and useful in that it lets you define the arithmetic of ℝ and reason about some properties of real numbers.
Dedekind cuts can be imagined as intervals, just a specific type of an interval. The lower half has no least or greatest element. You could maybe write it in interval terms as A = (-∞, x), but it's sloppy because ∞ is not a number. The upper half is always the "complementary" interval - the rest of ℝ - and may or may not have a least element (depending on whether x is rational).
But yeah, to your other point, this is basically what we're doing here. We're spelling out the rules for defining and manipulating natural numbers for aliens who have no intuition about it. We then extend it to integers without really explaining what integers "are" - we just define them as pairs of naturals. And then we derive rational numbers roughly the same way - just pairs with arithmetic rules. And reals follow from that.
It's a worthwhile exercise because maybe we're gonna meet aliens one day, but more importantly, because it lets us more rigorously reason about corner cases where intuition fails (chiefly when dealing with infinities, infinitesimals, etc).
Like lets say we are aliens who live in integer land and our integer brains cannot comprehend rationals, then we say you can simply cut the integers so that you have every number greater than 3 but less than 4 but we can never define it. But we can add it subtract it compare it etc. but really we are just doing arithmetic on integer pairs. The mysterious number called one half can be multiplied by three and we know its greater than one but our machines cannot determine how much greater any more exactly than an epsilon.
Not sure if pun, but if you're serious... I guess one fundamental question is whether the fabric of reality is continuous or quantized. Which sort of requires knowing what that fabric might be, and I'm not convinced we're close to answering that.
Anyway, if it's continuous, then arguably, you could have a model of computation more powerful than Turing machines that use a finite alphabet of symbols / states. Maybe. I don't know if this lends itself to more powerful computation, but it probably does in some ways. I'm sure someone ended up writing a paper about that.
If it's quantized, then... it could still behave in non-Turing-computable ways, but I guess it would be more surprising if it did? Like, you know, a quantum particle interaction that solves the halting problem for whatever reason.
I love the pun but it's a serious question that has been vexing me for a while. As you say, it depends on the nature of reality. We *know* (or do I mean "know"?) matter and energy are quantized but time and space are open questions (and seemingly smooth). GR defines a continuum, and even QM takes place in the (presumed) smooth background of spacetime.
But real numbers in physical reality suggest crazy things. Felt charge depends on distance, inverse square, so what happens when distances become infinitely small? Charge becomes infinitely large? The Planck limit is just the size scale where our physics stops working. Nothing prevents reality from working on smaller scales. But does it?
A most vexing question. And it absolutely has implications for what's computable.
Some postscripts:
1) Another interesting way to rephrase it is that a single real number can contain an infinite amount of information. In contrast, other numbers discussed in this chapter can only encode finite amounts.
2) Some readers may wonder why we talk about "classes" to describe a collection of sets that share common property. Isn't a class just a set of sets?
Well, if you allow sets to be constructed from a universe of all imaginable mathematical objects - a principle known as unrestricted comprehension - you end up with contradictions. Most famously, you risk Russell's paradox: let P be a set of all sets that aren't members of themselves. Is P a member of itself? If not, then it should have been selected by the criteria - and should have been a member! But if we make it a member, it no longer satisfies the selection criteria, and we're back to square one.
To avoid this, in standard set theory, you're limited to constructing new sets by selecting objects from the sets you already have. This is known as restricted comprehension. In this context, we can still talk about collections of mathematical objects without showing how to build them, but we call these collections "classes". They may have set-like properties, but we're not supposed to do set operations on them. We can, however, do operations on any representative set in that class.
3) You might also encounter an alternative way to define reals using Cauchy sequences. In essence, we define ℝ in terms of converging sequences of rational numbers that get arbitrarily close to any real (and in the limit at infinity, point to the real *exactly*). As with Dedekind cuts, we're not saying how each of these sequences looks like, just that every real number is a converging sequence of rationals. Both of these methods are functionally equivalent; if you're interested in rational approximations of reals, you might get a kick out of this article: https://lcamtuf.substack.com/p/approximation-game
4) In the first article in the series (https://lcamtuf.substack.com/p/09999-1), we asserted that reals follow the Archimedean property, i.e., they don't include infinitesimals. It's an axiom, but we can show it follows from the construction approach discussed here, too. Every integer is finite. If so, the stepover between rational numbers can be arbitrarily small, but is always strictly larger than any conceivable notion of an infinitesimal (ε = "1/∞"). So, the partitions of ℚ made for x and x+ε must be indistinguishable, because the delta is smaller than the spacing of rational numbers.
5) In the same article, I introduced hyperreals without explaining their construction in a rigorous way. Hyperreals extend reals by adding infinitesimal and infinite quantities. There are several ways to approach this task, but one is to express infinitesimals as sequences of real numbers that converge to zero at different rates (and infinite values as the inverse).
I got a D in analysis. I can believe that 0 = {} but I had a hard time believing 1 = { 0, {}}. I can see how a Dedekind cut defines numbers but thats all a x b to me is not really {a-lower, a-upper} x {b-l, b-u}. Really the LUB was nonsense to me except for one thing, .9999... = 1.
Cardinality, ordinality and measure are what we have in the real world. I do believe there are irrational, transcendent, uncomputable and other numbers. Hyper reals, not sure, its just epsilon to me.
"Some of the tiles are redundant (e.g., 2 is the same as 4/2), but this is not important for the proof" there is therefore not an exact matchup on diagnolization of Q.
The professor said series do not equal sequences when I asked why can't you use the series test on a sequence. Isn't that what category theory is for.
Then there was how a differential equation is not a difference equation,
One Graduate student said quantum theory is not commutative and another professor said it was.
I also don't get Tropical analysis, the Collatz conjecture, modular forms and many other things.
I mean, I talk about a bit in the earlier article and the comments attached to it (https://lcamtuf.substack.com/p/how-has-mathematics-gotten-so-abstract). I think we're just finding ways to restate the principles of propositional logic in increasingly weird ways. It probably doesn't mean anything more than that. In particular, I don't think it describes physics or the real world. And maybe all the weirdness we keep discovering is an artifact of the underlying principles being flawed. I wouldn't be surprised if we're using a different model of logic or mathematics in 50-100 years, maybe causing all the talk of cardinalities disappear.
Or maybe it's going to unfold the way it did with negative numbers? In 200 years, every child will know about infinite ordinals and it will be weird to them that the ancients had some qualms about such a basic concept.
In the meantime... it's still sort of useful? Calculus is a prime example - we struggled with infinity for millennia, then came up with a framework that didn't really have a good mathematical basis but seemed to work, and then we developed formalizations that help us make sense of the whole thing.
> "Some of the tiles are redundant (e.g., 2 is the same as 4/2), but this is not important for the proof" there is therefore not an exact matchup on diagnolization of Q.
There are construction and traversal methods that skip over the duplicates to show the cardinality is the same, but I didn't feel the extra complexity is worth it for the article.
I feel like we are assuming that we can define “before” and “after” like a function with two rational numbers as input and true or false as output, then assuming we can “type cast” a real into these functions and they still work properly. Like you can say cutting rationals before five and after five leaves five but thats only because five itself is a rational and can have the greater than and less than functions defined on it.
That's the finer point of Dedekind cuts that I was trying to hint at: the construction of reals doesn't give you the function is_less(r, q) and is_greater_or_equal(r, q). Instead, it basically says "the set of real numbers is the set of all Dedekind cuts of ℚ". Which is both maddeningly vague and useful in that it lets you define the arithmetic of ℝ and reason about some properties of real numbers.
How is this different than the arithmetic of interval of rationals? Sorry i have been struggling with this for thirty years as an amateur
Dedekind cuts can be imagined as intervals, just a specific type of an interval. The lower half has no least or greatest element. You could maybe write it in interval terms as A = (-∞, x), but it's sloppy because ∞ is not a number. The upper half is always the "complementary" interval - the rest of ℝ - and may or may not have a least element (depending on whether x is rational).
But yeah, to your other point, this is basically what we're doing here. We're spelling out the rules for defining and manipulating natural numbers for aliens who have no intuition about it. We then extend it to integers without really explaining what integers "are" - we just define them as pairs of naturals. And then we derive rational numbers roughly the same way - just pairs with arithmetic rules. And reals follow from that.
It's a worthwhile exercise because maybe we're gonna meet aliens one day, but more importantly, because it lets us more rigorously reason about corner cases where intuition fails (chiefly when dealing with infinities, infinitesimals, etc).
Like lets say we are aliens who live in integer land and our integer brains cannot comprehend rationals, then we say you can simply cut the integers so that you have every number greater than 3 but less than 4 but we can never define it. But we can add it subtract it compare it etc. but really we are just doing arithmetic on integer pairs. The mysterious number called one half can be multiplied by three and we know its greater than one but our machines cannot determine how much greater any more exactly than an epsilon.
Good article. The real numbers are so weird as to raise the question: Is reality rational but not real?
Not sure if pun, but if you're serious... I guess one fundamental question is whether the fabric of reality is continuous or quantized. Which sort of requires knowing what that fabric might be, and I'm not convinced we're close to answering that.
Anyway, if it's continuous, then arguably, you could have a model of computation more powerful than Turing machines that use a finite alphabet of symbols / states. Maybe. I don't know if this lends itself to more powerful computation, but it probably does in some ways. I'm sure someone ended up writing a paper about that.
If it's quantized, then... it could still behave in non-Turing-computable ways, but I guess it would be more surprising if it did? Like, you know, a quantum particle interaction that solves the halting problem for whatever reason.
I love the pun but it's a serious question that has been vexing me for a while. As you say, it depends on the nature of reality. We *know* (or do I mean "know"?) matter and energy are quantized but time and space are open questions (and seemingly smooth). GR defines a continuum, and even QM takes place in the (presumed) smooth background of spacetime.
But real numbers in physical reality suggest crazy things. Felt charge depends on distance, inverse square, so what happens when distances become infinitely small? Charge becomes infinitely large? The Planck limit is just the size scale where our physics stops working. Nothing prevents reality from working on smaller scales. But does it?
A most vexing question. And it absolutely has implications for what's computable.
Once again a marvelous article.
Thank you man. You make learning these issues so intuitive.