2
$\begingroup$

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?

  • 0
    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$?2012-10-29
  • 1
    (If this is the question: Yes, with choice. But it is consistent that choice fails and the answer is no.)2012-10-29
  • 0
    @ Andres : Yes. As for the choice , is it possible without using choice ? Is it neccessarily false if AC is false ?2012-10-29
  • 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.2012-10-29

1 Answers 1

3

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.

  • 0
    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 ?2012-10-29
  • 0
    @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.2012-10-29
  • 0
    AHA that last sentense is intresting. How to prove it ?2012-10-29
  • 0
    @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.2012-10-29
  • 0
    Plz prove that P(R) is well-orderable or at least total orderable.2012-10-29
  • 0
    @mick: No, that is **not** provable without *some* choice. It is *consistent* that the axiom of choice fails and still every set can be totally ordered; and it is *consistent* that the axiom of choice fails and the power set of the real numbers can still be well-ordered. Both proofs are quite difficult and require use of forcing and symmetric extensions, which in turn require a deep understanding of set theory. If you already know about these, I can sketch the arguments, but if not then math.SE is not the place to start with these topics.2012-10-29
  • 0
    @mick: I don't mind *helping* further, but at some point mathematics *is* a difficult thing which cannot be hand-waved across a short post to people without much preliminary knowledge. There are books written on the topic, and for a good reason. It is complicated, *very* delicate, and it requires a lot of understanding of fine points in set theory. I'm sorry if I'm being "mysterious" in any way, it's just how things are. Much like it is impossible to explain to a freshman Wiles' proof of Fermat's theorem, it is impossible to do these things *here* without assuming a lot of previous knowledge.2012-10-29
  • 0
    Thanks for the extension edit of your answer. But what do you mean by "evil twin" ? I do not know much about Halpern-Levy.2012-10-30
  • 0
    @mick: The constructions of Cohen and of Halpern & Levy have the same result (at least in this context), but their approach is different. In some aspects it can be easier to prove some things using the Cohen constructions and other things are easier to prove using the Halpern-Levy approach. I am not a fan of the Halpern-Levy approach, and therefore I call that "the evil twin".2012-10-30
  • 0
    Im must now wonder why you hate it :) Maybe we should continue this on chat sometime.2012-10-30
  • 0
    @mick: I don't hate it. Just because something is "evil" doesn't mean I hate it. I just like the symmetric construction better in most cases. I also *hate* the chat system here, so we probably won't meet there.2012-10-30
  • 0
    Im sorry you hate the chat system. I hope it is not related to my discussion I had today there. Thanks anyway.2012-10-30
  • 0
    @AsafKaragila In the OP, where does "$\sin(1/x)$ near $0$" come into all this?2012-11-01
  • 0
    @Matt: It's just another function...2012-11-01