Does ZF assert the existence of an actual formula, that one could express in ZF with a finite string of symbols, defining a well-ordering on the-real-numbers-as-we-know-them? I know it ‘proves’ the existence of a well-ordering on the set we’d call the real numbers if we endorsed the statement “V=L”. I want to know about the nature of that set, and how much ZF can prove without V=L or any other form of choice.
ZF is consistent with many negations of strong choice. For example, ZF is consistent with Lebesgue measurability of every subset in R. Well-ordering of R is enought to create unmeasurable set.
So, if ZF could prove existence of such a formula, ZF+measurability would prove contradiction, but ZF+neasurability is equiconsistent with ZF and ZF would be inconsistent.
It is very hard to say anything about any well-ordering of R, they are monster constructions...
Constructible version of R (if it is inside R and not the whole R) is just like Q: dense, small part of the whole, and usually zero-measure. So, this construction will yield something of measure zero if you define measure on the whole R.
Here’s a sort of related argument (very much not a math expert here): Any well ordering on the real numbers must be non-computable. If there was a computable order, you could establish a 1-1 correspondence between the natural numbers and the reals (since each real would be emitted on the nth step of the algorithm).
Well, yes, but mostly because most real numbers cannot ever be specified to an algorithm or received back from it. So you are right, ordering of R is about incomputable things.
The difference here is that we talk about ZFC formulas which can include quite powerful tricks easily.
This is true, but not, I think, the corect point to focus on.
The big obstacle is that the real numbers are uncountable. Of course, their uncountability is also why there exist uncomputable reals, but let’s put that aside for now, because the computability of individual reals is not the point.
The point is that computers operate on finite strings over finite alphabets, and there are only countably many of these. In order to do anything with a computer, you must first translate it into a problem about finite strings over a finite alphabet. (And the encoding matters, too—“compute the diameter of a graph” is not a well-specified problem, because “compute the diameter of a graph, specified as an adjacency matrix” and “compute the diameter of a graph, specified with connectivity lists” are different problems. And if of course I was implicitly assuming here the output was in binary—if we wanted it in unary, that would again technically be a different problem.)
So the whole idea of an algorithm that operates on or outputs real numbers is nonsensical, because there are only countably many finite strings over a given finite alphabet, and so no encoding is possible. Only specified subsets of real numbers with specified encodings can go into computers.
Notice that the whole notion of the computability of a real number appears nowhere in the above. It’s also a consequence of uncountability, but really not the point here.
I’m going to go into your original comment a bit more here:
If there was a computable order, you could establish a 1-1 correspondence between the natural numbers and the reals (since each real would be emitted on the nth step of the algorithm).
You seem to be under the impression that a countably infinite well-ordering must be isomorphic to omega, or at least that a computable one must be. I don’t think that would make for a useful definition of a computable well-ordering. Normally we define a well-ordering to be computable if it is computable as a relation, i.e. there is an algorithm that given two elements of your set will compare them according to your well-ordering. We can then define a well-order type (ordinal) to be computable if it is the order type of some computable well-ordering. By this definition, omega+1, and basically all the countable ordinals you usually see, are computable (well, except for the ones explicitly made not to be).
So the whole idea of an algorithm that operates on or outputs real numbers is nonsensical
You can work with programs over infinite streams in certain situations. For example, you can write a program that divides a real number by 2, taking an infinite stream as input and producing another infinite stream as output. Similarly, you can write a program that compares two unequal real numbers.
True, I forgot about that. I guess that would allow extending the notion of “computable well-ordering” to sets of size 2^aleph_0. Of course that doesn’t necessarily mean any of them would actually be computable, and I expect none of them would. Well, I guess it has to be the case that none of them would, or else we ought to be able to prove “R is well-orderable” without choice, but there ought to be a simpler argument than that—just as computable ordinals in the ordinary sense are downclosed, I would expect that these too ought to be downclosed, which would immediately imply that none of the uncountable ones are computable. Now I guess I should actually check that they are downclosed...
Upvoted on reflection for the part I quoted, which either answers the question or gives us some reason to distinguish R-in-L (the set we’d call the real numbers if we endorsed the statement “V=L”) from “the-real-numbers-as-we-know-them”.
Yes. In ZF one can construct an explicit well-ordering of L(alpha) for any alpha; see e.g. Kunen ch VI section 4. The natural numbers are in L(omega) and so the constructible real numbers are in L(omega+k) for some finite k whose value depends on exactly how you define the real numbers; so a well-ordering of L(omega+k) gives you a well ordering of R intersect L.
I’m not convinced that R intersect L deserves the name of “the-real-numbers-as-we-know-them”, though.
Separate concern: Why constructible real numbers are only finitely higher than Q? Cannot it be that there are some elements of (say) 2^Q that cannot be pinpointed until a much higher ordinal?
Of course, there is still a formula that specifies a high enough ordinal to contain all members of R that are actually constructible.
I figured out the following after passing the Society of Actuaries exam on probability (woot!) when I had time to follow the reference in the grandparent:
The proof that |R|=|2^omega| almost certainly holds in L. And gjm may have gotten confused in part because L(omega+1) seems like a natural analog of 2^omega. It contains every subset of omega we can define using finitely many parameters from earlier stages. But every subset of omega qualifies as a subset of every later stage L(a>omega), so it can exist as an element in L(a+1) if we can define it using parameters from L(a).
As another likely point of confusion, we can show that for each individual subset, a|x|, this says if V=L then 2^omega must stay within or equal L(omega1). The same proof tells us that L satisfies the generalized continuum hypothesis.
Let’s see. Assume measurability axiom—every subset of R has Lebesgue measure. As we can use the usual construction of unmeasurable set on L intersect R, our only escape option is that it has zero measure.
So if we assume measurability, L intersect R is a dense zero-measure subset, just like Q. These are the reals we can know individually, but not the reals-as-a-whole that we know...
Looks OK to me, though I can’t guarantee that there isn’t a subtle oops I haven’t spotted. (Of course it assumes you’ve got some definition for what sort of a thing (a ⇐ b) is; you might e.g. use a Kuratowski ordered pair {{a},{a,b}} or something.)
Does ZF assert the existence of an actual formula, that one could express in ZF with a finite string of symbols, defining a well-ordering on the-real-numbers-as-we-know-them? I know it ‘proves’ the existence of a well-ordering on the set we’d call the real numbers if we endorsed the statement “V=L”. I want to know about the nature of that set, and how much ZF can prove without V=L or any other form of choice.
Nope.
ZF is consistent with many negations of strong choice. For example, ZF is consistent with Lebesgue measurability of every subset in R. Well-ordering of R is enought to create unmeasurable set.
So, if ZF could prove existence of such a formula, ZF+measurability would prove contradiction, but ZF+neasurability is equiconsistent with ZF and ZF would be inconsistent.
It is very hard to say anything about any well-ordering of R, they are monster constructions...
Does a well-ordering on the constructable version of R provably do this? I fear I can’t tell if you’ve addressed my question yet.
Constructible version of R (if it is inside R and not the whole R) is just like Q: dense, small part of the whole, and usually zero-measure. So, this construction will yield something of measure zero if you define measure on the whole R.
Here’s a sort of related argument (very much not a math expert here): Any well ordering on the real numbers must be non-computable. If there was a computable order, you could establish a 1-1 correspondence between the natural numbers and the reals (since each real would be emitted on the nth step of the algorithm).
Is that remotely right?
Well, yes, but mostly because most real numbers cannot ever be specified to an algorithm or received back from it. So you are right, ordering of R is about incomputable things.
The difference here is that we talk about ZFC formulas which can include quite powerful tricks easily.
Oh right, I forgot that real numbers could be individually non-computable in the first place.
This is true, but not, I think, the corect point to focus on.
The big obstacle is that the real numbers are uncountable. Of course, their uncountability is also why there exist uncomputable reals, but let’s put that aside for now, because the computability of individual reals is not the point.
The point is that computers operate on finite strings over finite alphabets, and there are only countably many of these. In order to do anything with a computer, you must first translate it into a problem about finite strings over a finite alphabet. (And the encoding matters, too—“compute the diameter of a graph” is not a well-specified problem, because “compute the diameter of a graph, specified as an adjacency matrix” and “compute the diameter of a graph, specified with connectivity lists” are different problems. And if of course I was implicitly assuming here the output was in binary—if we wanted it in unary, that would again technically be a different problem.)
So the whole idea of an algorithm that operates on or outputs real numbers is nonsensical, because there are only countably many finite strings over a given finite alphabet, and so no encoding is possible. Only specified subsets of real numbers with specified encodings can go into computers.
Notice that the whole notion of the computability of a real number appears nowhere in the above. It’s also a consequence of uncountability, but really not the point here.
I’m going to go into your original comment a bit more here:
You seem to be under the impression that a countably infinite well-ordering must be isomorphic to omega, or at least that a computable one must be. I don’t think that would make for a useful definition of a computable well-ordering. Normally we define a well-ordering to be computable if it is computable as a relation, i.e. there is an algorithm that given two elements of your set will compare them according to your well-ordering. We can then define a well-order type (ordinal) to be computable if it is the order type of some computable well-ordering. By this definition, omega+1, and basically all the countable ordinals you usually see, are computable (well, except for the ones explicitly made not to be).
You can work with programs over infinite streams in certain situations. For example, you can write a program that divides a real number by 2, taking an infinite stream as input and producing another infinite stream as output. Similarly, you can write a program that compares two unequal real numbers.
True, I forgot about that. I guess that would allow extending the notion of “computable well-ordering” to sets of size 2^aleph_0. Of course that doesn’t necessarily mean any of them would actually be computable, and I expect none of them would. Well, I guess it has to be the case that none of them would, or else we ought to be able to prove “R is well-orderable” without choice, but there ought to be a simpler argument than that—just as computable ordinals in the ordinary sense are downclosed, I would expect that these too ought to be downclosed, which would immediately imply that none of the uncountable ones are computable. Now I guess I should actually check that they are downclosed...
What does it mean to be downclosed?
I mean closed downwardly—if one is computable, then so is any smaller one. (And so the Church-Kleene ordinal is the set of all computable ordinals.)
Upvoted on reflection for the part I quoted, which either answers the question or gives us some reason to distinguish R-in-L (the set we’d call the real numbers if we endorsed the statement “V=L”) from “the-real-numbers-as-we-know-them”.
ZF does not imply well ordering of R, ZFC does. ZF with the Axiom of Choice.
Strictly speaking.
Yes. In ZF one can construct an explicit well-ordering of L(alpha) for any alpha; see e.g. Kunen ch VI section 4. The natural numbers are in L(omega) and so the constructible real numbers are in L(omega+k) for some finite k whose value depends on exactly how you define the real numbers; so a well-ordering of L(omega+k) gives you a well ordering of R intersect L.
I’m not convinced that R intersect L deserves the name of “the-real-numbers-as-we-know-them”, though.
Separate concern: Why constructible real numbers are only finitely higher than Q? Cannot it be that there are some elements of (say) 2^Q that cannot be pinpointed until a much higher ordinal?
Of course, there is still a formula that specifies a high enough ordinal to contain all members of R that are actually constructible.
I figured out the following after passing the Society of Actuaries exam on probability (woot!) when I had time to follow the reference in the grandparent:
The proof that |R|=|2^omega| almost certainly holds in L. And gjm may have gotten confused in part because L(omega+1) seems like a natural analog of 2^omega. It contains every subset of omega we can define using finitely many parameters from earlier stages. But every subset of omega qualifies as a subset of every later stage L(a>omega), so it can exist as an element in L(a+1) if we can define it using parameters from L(a).
As another likely point of confusion, we can show that for each individual subset, a|x|, this says if V=L then 2^omega must stay within or equal L(omega1). The same proof tells us that L satisfies the generalized continuum hypothesis.
Um. You might well be right. I’ll have to think about that some more. It’s years since I studied this stuff...
While some of the parent turns out not to hold, it helped me to find out what the theory really says (now that I have time).
Let’s see. Assume measurability axiom—every subset of R has Lebesgue measure. As we can use the usual construction of unmeasurable set on L intersect R, our only escape option is that it has zero measure.
So if we assume measurability, L intersect R is a dense zero-measure subset, just like Q. These are the reals we can know individually, but not the reals-as-a-whole that we know...
Seems reasonable to me.
Is this a correct statement of what a well-ordering of R is?
Looks OK to me, though I can’t guarantee that there isn’t a subtle oops I haven’t spotted. (Of course it assumes you’ve got some definition for what sort of a thing (a ⇐ b) is; you might e.g. use a Kuratowski ordered pair {{a},{a,b}} or something.)