Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is the set $S = \{ f : \mathbb R \to \mathbb R \}$ of functions $f$ from the reals to the reals a totally ordered set ?

I think the question is clear. Note that there is a bijection to $g(x)$ gives $0$ or $1$ with that choice depending on the real $x$. The cardinality of this set is $P(R)$ where $P$ means powerset and $R$ means the cardinality of the reals.

I tried to find a solution but got confused , mainly by functions such as $\sin(1/x)$ near $0$. I guess using the axiom of choice will help, but that seems way too strong. I would prefer not to use AC nor assuming that AC is false. Thus independant of AC can such a total order be given?

share|improve this question
I'm not sure I understand. Are you asking whether it is possible to linearly order the set of all functions $f:\mathbb R\to\mathbb R$? – Andres Caicedo Oct 29 '12 at 22:26
1  
(If this is the question: Yes, with choice. But it is consistent that choice fails and the answer is no.) – Andres Caicedo Oct 29 '12 at 22:27
@ Andres : Yes. As for the choice , is it possible without using choice ? Is it neccessarily false if AC is false ? – mick Oct 29 '12 at 22:30
3  
"Note that there is a bijection to $g(x)$ gives $0$ or $1$ with that choice depending on the real $x$". That sentence doesn't make any sense to me. – kahen Oct 29 '12 at 23:50

1 Answer

up vote 3 down vote accepted

It is consistent without the axiom of choice that $\mathcal P(\mathbb R)$ cannot be linearly ordered. Since $\mathbb R^\mathbb R$ has the same cardinality as $\mathcal P(\mathbb R)$ this means that it is consistent that the set of all functions from $\mathbb R$ to itself cannot be linearly ordered.

Assuming the axiom of choice, of course, this set can be linearly ordered in a myriad of ways (well order; dense order; etc.)

Addressing the issue in the third comment, "Is it neccessarily false if AC is false", the answer is no in a very trivial way. This is quite a local requirement. We can ensure that the axiom of choice holds for sets like this, and even much much larger, but fails miserably in many many ways much later in the hierarchy of sets.

Also, it is known that the assertion "Every set can be linearly ordered" does not imply the axiom of choice. That is to say there are models in which choice fails, but every set can still be linearly ordered. In particular, this one.

Also related: Total order in the power set of the real line


To give some more details:

  1. It is impossible to prove without some choice that $\mathbb R$ can be well-ordered, therefore it is impossible to prove that $\mathcal P(\mathbb R)$ can be well-ordered as well, unless we assume some choice holds.

  2. It is consistent that the axiom of choice fails, but every set can be linearly ordered. This is true in Cohen's first model which is a model in which we begin from the constructible universe, add a countable set of Cohen reals and use finitely supported permutations of $\omega$ to define an inner model of the forcing extension, in which the collection of the generic reals is a Dedekind-finite set.

    In this model every set is definable from an ordinal and a finite set of real numbers, and therefore we can define a linear order of the universe, and in particular we can linearly order any set -- including $\mathcal P(\mathbb R)$. The proof that this property holds is very difficult and far from intuitive.

  3. It is consistent that the axiom of choice fails, and there exists a subset of $\mathcal P(\mathbb R)$ which can be partitioned into countably many pairs, and we cannot choose a point from each pair. Such set cannot be linearly ordered, and therefore $\mathcal P(\mathbb R)$ cannot be linearly ordered in such model.

    One model in which this occurs is Cohen's second model, which is constructed in a similar way as before, only we take a different permutation group and using it we generate not only Dedekind-finite sets of reals, but we generate enough of them to accommodate the elements of the pairs mentioned above.

    It should be remarked that Monro proved that one can actually force above Cohen's first model (or rather its "evil twin", the Halpern-Levy model) that a set that cannot be linearly ordered exists in $\mathcal P(\mathbb R)$, however it is a different set with different properties.

  4. If we do not assume anything about the axiom of choice, it might hold and everything could be linearly ordered; or it might fail at a stage far beyond the real numbers. An example of such model is the model we get from another paper by Monro, this time we perform a very similar construction to Cohen's first model only we use a larger cardinal rather than adding subsets to $\omega$, and if we are careful enough we can ensure not to add any new sets to $\mathcal{P(P(P(P(P}(\mathbb R))))$ and therefore preserve the well-orderability of $\mathcal P(\mathbb R)$, while the axiom of countable choice fails.

share|improve this answer
Does the AC not imply well order and hence Total order ? And similarly does the negation of AC then not imply not totally ordered ? Im confused. Also is it linearly ordered or not ? Say in ZF ? If the set $S$ has total order is this nonconstructable ? – mick Oct 29 '12 at 22:42
@mick: AC implies a well-order and thus a linear order; but it also imply a dense order (which is far from well). Without the axiom of choice it is impossible to decide. For one it is possible that the axiom of choice holds and we just don't know about it; but even if we assume it is not holding we cannot tell where it fails. It is possible, quite possible, that the axiom of choice holds for any set that you can imagine, but fails much beyond that. Not only that it fails, it fails in terrible ways and the most pathological sets exist. However $\mathcal P(\Bbb R)$ is still well-orderable. – Asaf Karagila Oct 29 '12 at 22:44
AHA that last sentense is intresting. How to prove it ? – mick Oct 29 '12 at 22:47
@mick: Which part? I mentioned various things. However I should point that none of these proofs are simple or even close to easy. Most require deep technical and somewhat a philosophical understanding of the universe of set theory; forcing; and other advance set theoretical constructs. – Asaf Karagila Oct 29 '12 at 22:48
Plz prove that P(R) is well-orderable or at least total orderable. – mick Oct 29 '12 at 23:12
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.