Eretrandre Mathematics Forum - Linearly ordering the powerset of reals

Pages: 1 2

Well, since this forum's purpose is expressly to discuss strange/incomplete mathematical ideas, I'm going to take the liberty to post about something crazy. $Smile$

We can get from the natural numbers to the reals by taking sequences of natural numbers and doing a lexicographic ordering on them. This ordering gives us the linear ordering of the reals.

I wonder if it's possible to apply an analogous process to get from the reals to a linearly ordered superset (hopefully with cardinality $2^c$ ). The "obvious" method of taking sequences of reals and doing lexicographic ordering on them doesn't give us $2^c$ ; it gives us at most $c^{\aleph_0} = c$ . So instead of using sequences, which are inherently countable, we generalize the concept of digit strings to functions $f:X\rightarrow\{0,1\}$ . When X is the set of natural numbers, this gives us the reals. If X is the set of positive reals, and it will give us a set of cardinality $2^c$ .

The tricky part, however, is how to ensure linear ordering. Given two digit strings functions f and g, we want to have an analogue of lexicographic ordering. The naive approach is that $f< g$ if there exists $x_0$ such that $f(x) < g(x)$ for all $x\geq x_0$ , but this is actually not a linear ordering, only a partial ordering. (It is possible to find two distinct functions such that $f< g$ and $g<f$ .)

Now, this problem can be solved if we create a well-ordering of the positive reals (every subset has a minimal element), because then it is possible to define a lexicographic ordering for the digit string functions. However, the well-ordering of reals is only guaranteed by the Axiom of Choice, and is non-constructible. But is there a way to at least approximate the structure of such a well-ordering (constructively), so that we can at least have a glimpse into how we could linearly order the powerset of reals?

Let the discussion begin.

Hm, let me repeat the problem:
If we wanted to compare the digit functions in the usual lexicographic way, i.e. for f, g let $S=\{x\in\mathbb{R}:\ f(x)\ne g(x)\}$ and let $x_0$ be the smallest element of S, then we would define $f<g$ as $f(x_0)<g(x_0)$ .
Taking the smallest element would of couse only be possible in a well order of $\mathbb{R}$ .

If we would otherwise regard the usual order on $\mathbb{R}_+$ for example we take the 2 functions $f,g:\ \mathbb{R}_+\to \{0,1\}$ , where $f(x)=1$ exactly at the rational numbers $x>1$ and $g(x)=1$ exactly at the irrational numbers $x>1$ , then S would be the numbers $x>1$ and the infimum of S would be 1 though $f(1)=g(1)=0$ , so we can not order f and g because in each interval $(1,1+\varepsilon)$ there are (rational) x with $1=f(x)>g(x)=0$ and (irrational) x with $0=f(x)<g(x)=1$ .

Hm, what regards the axiom of choice - I like it, it makes many things easier to handle. I would also guess that it is necessary here to perform such constructions. But more involved in such topics are of course the reverse mathematicians.

The following points crossed also my mind:
1. (I think I have heard) It is not possible to well order the (positive) real (and the (positive) rational) numbers compatible with addition and multiplication (or even merely with addition?).
2. The binary sequences $(b_i)_{i\in\mathbb{N}}$ have a meaning $\sum_{i=0}^\infty b_i 2^{-i}$ . What a meaning would the binary functions $(b_x)_{x\in\mathbb{R}_+}$ have?
3. The non-usability of the usual order on $\mathbb{R}_+$ for the purpose of lexicographic ordering is not specific to the reals but occurs already on the fractions. For example consider two functions $f,g:\ \mathbb{Q}_+\to \{0,1\}$ , where $f(x)=1$ exactly if $x=y^2$ for some $y>1$ and $g(x)=1$ exactly if $x\neq y^2$ for every $y>1$ . Then again is S the set of rational numbers $x>1$ and in each interval $(1,1+\varepsilon)$ there are x with $f(x)>g(x)$ and x with $f(x)<g(x)$ .

bo198214 Wrote:[...]
The following points crossed also my mind:
1. (I think I have heard) It is not possible to well order the (positive) real (and the (positive) rational) numbers compatible with addition and multiplication (or even merely with addition?).

I've never heard about that, but it doesn't surprise me. What I have heard, though, is that a well-ordering of the reals is so complex that it is not possible to describe it with a finite number of symbols, so we will probably never be able to explicitly construct such an ordering. Nevertheless, I want to explore just how far we can go in that direction.

Quote:2. The binary sequences $(b_i)_{i\in\mathbb{N}}$ have a meaning $\sum_{i=0}^\infty b_i 2^{-i}$ . What a meaning would the binary functions $(b_x)_{x\in\mathbb{R}_+}$ have?

It would result in a set of numbers that is a superset of the reals... sequences of reals have been used to define hyperreals, for example. I don't know what kind of structure we will end up with, with binary functions on the reals. Having linear ordering has the nice property that we can probably impose number-like properties on the resulting set.

Quote:3. The non-usability of the usual order on $\mathbb{R}_+$ for the purpose of lexicographic ordering is not specific to the reals but occurs already on the fractions. For example consider two functions $f,g:\ \mathbb{Q}_+\to \{0,1\}$ , where $f(x)=1$ exactly if $x=y^2$ for some $y>1$ and $g(x)=1$ exactly if $x\neq y^2$ for every $y>1$ . Then again is S the set of rational numbers $x>1$ and in each interval $(1,1+\varepsilon)$ there are x with $f(x)>g(x)$ and x with $f(x)<g(x)$ .

Right, so the problem isn't really with the set itself, but the (default) ordering defined on the set. The set of rationals is bijective with the set of natural numbers, so the problem seems to arise from the density of the ordering rather than the set itself. I'm not sure how one would go about constructing a non-dense ordering of the reals, though. All non-dense orderings that I can think of are countable, but maybe there's some way of going beyond countability without needing a dense ordering. IIRC, $\aleph_1$ is the set containing all countable well-orderings, and is uncountable, but this definition doesn't really tell us very much about the structure of such a set.

Concerning the wellordering of the reals: There can be no wellordering of $\mathbb{R}$ or $\mathbb{R}_+$ . One argument to show this: Every linear odering < compatible with the operations of an (Archimedian ordered?) field $\mathcal{F}$ has to be dense. Thus a set of the form $\{x\in\mathcal{F}: a < x\}$ for any fixed $a\in\mathcal{F}$ has no <-minimum.

Dirk

quickfur Wrote:
Quote:2. The binary sequences $(b_i)_{i\in\mathbb{N}}$ have a meaning $\sum_{i=0}^\infty b_i 2^{-i}$ . What a meaning would the binary functions $(b_x)_{x\in\mathbb{R}_+}$ have?
It would result in a set of numbers that is a superset of the reals... sequences of reals have been used to define hyperreals, for example.

This would be an option to investigate. I am not an hyperreal expert, so I can not tell about usage of similar sums there. But perhaps you could sharpen this point a bit more by becoming acquainted with hyperreals.

Quote:I'm not sure how one would go about constructing a non-dense ordering of the reals, though. All non-dense orderings that I can think of are countable, but maybe there's some way of going beyond countability without needing a dense ordering.

I would guess if you have an ordering that is in one direction non-dense, then it is already a well-ordering and vice versa.

DirkU Wrote:Concerning the wellordering of the reals: There can be no wellordering of $\mathbb{R}$ or $\mathbb{R}_+$ . One argument to show this: Every linear odering < compatible with the operations of an (Archimedian ordered?) field $\mathcal{F}$ has to be dense. Thus a set of the form $\{x\in\mathcal{F}: a < x\}$ for any fixed $a\in\mathcal{F}$ has no <-minimum.

Yes, it must be dense, because if it is compatible with addition and multiplication then $a<\frac{a+b}{2}<b$ as one can easily derive.

And this is not only valid for fields, but also for skew fields (multiplication need not to be commutative) and also for (the by me invented) coppices (addition need neither to be associative nor commutative).

I'm nearly convinced that is not provable in ZF (Zermelo Fraenkel set theory without choice) that, say, $2^{\aleph_1}$ is linearly orderable. At the moment I cannot prove this but in my opinion one could get a proof for that by

(1) Analyze the proof / technique to show that Linear Ordering Principle (i.e for every set ther exists a linear ordering) is not provable in ZF;

(2) Since a linear ordering on $2^{\aleph_1}$ provides automatically a choice function on certain kinds of of classes of $2^{\aleph_1}$ subsets (like $M\subset 2^{\aleph_1}$ containing only finite sets - but there are much more) you can also e the problem indirectly via independency results of weak choice principles.

I'm currently try to learn standard techniques for independence proofs in set theory (like permutazion models, or forcing). When I will have learned enough I will look at this problem anew.

Dirk

bo198214 Wrote:
quickfur Wrote:
Quote:2. The binary sequences $(b_i)_{i\in\mathbb{N}}$ have a meaning $\sum_{i=0}^\infty b_i 2^{-i}$ . What a meaning would the binary functions $(b_x)_{x\in\mathbb{R}_+}$ have?
It would result in a set of numbers that is a superset of the reals... sequences of reals have been used to define hyperreals, for example.
This would be an option to investigate. I am not an hyperreal expert, so I can not tell about usage of similar sums there. But perhaps you could sharpen this point a bit more by becoming acquainted with hyperreals.

I am acquianted with the hyperreals, although I am certainly no expert. One possible construction of the hyperreals is to consider sequences of reals (much like the infinite-dimensional vectors idea), and define an ordering based on the pairwise comparison of certain "vector components". Obviously, something special needs to be done here in order to get a linear ordering; the axiom of choice is used here to define an ultrafilter that selects the components that "matter" in a lexicographic comparison such that a linear ordering results. I'm not familiar with the technicalities of this process, but this is a rough overview of how it works.

The resulting set is linearly ordered, and contains the reals plus infinitesimals and infinite numbers, closed under the usual field operations. The hyperreals can be used to define derivatives and integrals by defining an equivalence relation over them so that they become isomorphic to the reals except for infinite numbers (this is called "nonstandard analysis", and does not depend on the use of limits).

Quote:
Quote:I'm not sure how one would go about constructing a non-dense ordering of the reals, though. All non-dense orderings that I can think of are countable, but maybe there's some way of going beyond countability without needing a dense ordering.
I would guess if you have an ordering that is in one direction non-dense, then it is already a well-ordering and vice versa.

Yep. The idea was to simply find a non-dense ordering (possibly in two directions) as a start, and then construct a well-ordering out of it if it isn't already one.

Does anyone know what's the relationship between density and cardinality? Has there been any research into this? It would help to know what is currently known in this area. $Smile$

DirkU Wrote:I'm nearly convinced that is not provable in ZF (Zermelo Fraenkel set theory without choice) that, say, $2^{\aleph_1}$ is linearly orderable.

As far as I know, the axiom of choice is required to prove the existence of a well-ordering of $2^{\aleph_0}$ . This probably means you also need AC for $2^{\aleph_1}$ . We know that all the alephs can be well-ordered (by definition), but since the continuum hypothesis is undecidable in ZFC, there's no obvious way to make the connection with the cardinal numbers.

quickfur Wrote:I am acquianted with the hyperreals, although I am certainly no expert.

So have the there used sequences the same meaning as $(b_i)_{i\in\mathbb{N}}$ have the meaning $\sum_{i=0}^\infty b_i 2^{-i}$ . Your description doesnt look so.
And can the hyperreals give an answer to question of different infinities with respect to your magnitude numbers (i.e. the behaviour of functions at infinity)?

Quote:Yep. The idea was to simply find a non-dense ordering (possibly in two directions) as a start, and then construct a well-ordering out of it if it isn't already one.

And how would this work if we are sure that we need AC? Or is this your question, whether we need AC? If we need AC, then regardless, which way you try to construct the well-ordering.

bo198214 Wrote:
quickfur Wrote:I am acquianted with the hyperreals, although I am certainly no expert.
So have the there used sequences the same meaning as $(b_i)_{i\in\mathbb{N}}$ have the meaning $\sum_{i=0}^\infty b_i 2^{-i}$ . Your description doesnt look so.

I think the hyperreals are defined in such a way that every real number corresponds with a constant sequence, every infinitesimal (which includes 0) converges to 0, and every infinite number diverges to infinity. The function coordinate thing I was describing isn't the same as the hyperreals, although there are similarities.

Quote:And can the hyperreals give an answer to question of different infinities with respect to your magnitude numbers (i.e. the behaviour of functions at infinity)?

Perhaps, although the concept is a bit different. If I remember correctly, the hyperreals are defined based on lexicographic ordering of coordinates, whereas my magnitude numbers idea is based on behaviour at $x=\infty$ . (Not every coordinate of a hyperreal is "significant", because including everything makes the ordering non-linear. An ultrafilter is used to select such coordinates that ensures linear ordering. But as far as I know, the existence of an ultrafilter requires the axiom of choice.)

Quote:
Quote:Yep. The idea was to simply find a non-dense ordering (possibly in two directions) as a start, and then construct a well-ordering out of it if it isn't already one.
And how would this work if we are sure that we need AC? Or is this your question, whether we need AC? If we need AC, then regardless, which way you try to construct the well-ordering.

Well, I don't know this first-hand... I've only seen people mention that a well-ordering of the reals requires the axiom of choice. This is all well and good, except that it gives you no information whatsoever as to what kind of structure the ordering has. What I want to know is, even if we cannot explicitly construct such an ordering, is it possible to at least get some idea about the structure of this ordering, some idea of what it might look like? Maybe some vague glimpse into the full structure, some sort of approximation, since it seems that we have no way of directly deriving such a thing. Or some properties that we can infer, even if it is incomplete.

Pages: 1 2