26
$\begingroup$

I was wondering if it is possible to produce an explicit bijection $h\colon \mathbb{R} \rightarrow \mathbb{R}/\mathbb{Q}$. If we can produce an explicit injection $i\colon \mathbb{R} \rightarrow \mathbb{R}/\mathbb{Q}$, can the Cantor-Bernstein-Schroeder Theorem be used constructively?

It is clear that the two sets have the same cardinality, so the existence of such a bijection is trivial. What I am really looking for is a nice-looking bijection, or a proof that no such nice-looking bijection exists, for a definition of "nice-looking" which I cannot quite figure out.

One problem which I think makes finding such a bijection difficult is that any natural injection of $\mathbb{R}/\mathbb{Q}$ (ie, those injections in which one representative is chosen from each coset) produces a non-measurable set, specifically a Vitali set.

I hate to ask such a vague question, but I'm really not sure about whether the correct answer is constructive, or whether it is a proof that any such bijection is in some sense "very complicated."

As a final note, the motivation for this question came from this discussion, in which I was somewhat astonished to see such a clear, constructive bijection given between $\mathbb{R}$ and $\mathbb{R} \setminus S$, where $S$ is countable.

  • 0
    Are you asking a clarification of the previous answers in your discussion link? I didn't take a great look at it, but if it describes a construction between $\mathbb R$ and $\mathbb R \backslash S$ where $S$ is countable, how about you take $S = \mathbb Q$?2012-11-24
  • 0
    Sorry, I should have made it clear. I mean the cosets of $\mathbb{Q}$ in $\mathbb{R}$, not simple "set minus".2012-11-24
  • 0
    @user : Oh! Quotient. Seriously, my bad. I just read it wrong.2012-11-24

1 Answers 1

35

It is not possible.

It is consistent with set theory without choice that $\mathbb R/\mathbb Q$ has strictly larger cardinality that $\mathbb R$. (This looks counter-intuitive, since $\mathbb R/\mathbb Q$ is a quotient.)

This is the case because, using a fact that goes back to Sierpiński (Sur une proposition qui entraîne l’existence des ensembles non mesurables, Fund. Math. 34, (1947), 157–162. MR0023318 (9,338i)), in any model of $\mathsf{ZF}$ where all sets of reals have the Baire property, it is not even possible to linearly order $\mathbb R/\mathbb Q$.

(Sierpiński argues in terms of Lebesgue measure. The argument in terms of the Baire property is analogous, and has the additional technical advantage of not requiring any discussion of consistency strength issues.)

A couple of years ago, Mike Oliver gave a nice talk on this topic (How to have more things by forgetting where you put them); he is not exactly using $\mathbb R/\mathbb Q$, but the arguments easily adapt. The point of the talk is precisely to give some intuition on why we expect the quotient to be "larger".

[Of course, in the presence of choice, the two sets have the same size. The argument above shows that the use of choice is unavoidable.]

  • 2
    It doesn't look counter-intuitive, it looks false... but of course, everything looks wrong without choice. But if we *have* choice, then of course the cardinality of the quotient is the same as that of the reals. Right?2012-11-24
  • 1
    Right, by the argument you indicated.2012-11-24
  • 3
    @PatrickDaSilva it's not that counter-intuitive - we have in most categories that we study that "onto" maps do not have one-sided inverses. Essentially, set theory without choice can be set theory with "structure" to your sets. Often that structure is complexity, and I think this is an obvious case where a quotient space is "more complex" than the parent spaces.2012-11-24
  • 0
    @Thomas : Haven't done enough category theory up to now... wish I had T.T2012-11-24
  • 1
    @PatrickDaSilva That has nothing to do with category theory: it's like saying "haven't done enough English" when someone uses a word you don't know. What Thomas is saying is actually something very simple and you surely know examples of this phenomenon: there are surjective group homomorphisms with no left inverse, there are surjective continuous maps with no left inverse, etc. etc.2012-11-24
  • 1
    @Zhen : I guess "I didn't understand English well enough so that his comment would make sense to me" then! :P2012-11-24
  • 0
    I'm a little confused by $\mathbb{R}/\mathbb{Q}$. Is this set difference? Or groups quotient? Or ring quotient?2018-02-08
  • 0
    @Ovi It is the set of equivalence classes of the relation $a\sim b $ iff $b-a\in \mathbb Q $, so it is the sets of cosets of $\mathbb Q $ in $\mathbb R $ as additive groups.2018-02-08
  • 0
    This answer corrects the mistake that it's provable that R/Q is the same size as R but it does not answer the question because it doesn't prove or disprove that every Vitali set is complicated. Maybe more research is needed then somebody can write an answer that proves in MK that ZF can't define any Vitali set in terms of any real number.2018-04-12
  • 0
    @Timothy It is consistent that any definable set is Lebesgue measurable, and it is provable that Vitali sets are not. The question was not about the complexity of Vitali sets, but about the complexity of bijections $\mathbb R\to\mathbb R/\mathbb Q$.2018-04-12
  • 0
    Is there a reference to an English source with a proof for the fact that any model of ZF where all sets of reals have the Baire property, it is not possible to linearly order R/Q?2018-12-10
  • 0
    @Holo I sketched a proof at https://mathoverflow.net/a/26893/6085. Still, the presentation I gave there is in terms of $2^\omega/E_0$, so a small translation is needed.2018-12-10
  • 0
    @AndrésE.Caicedo thanks!2018-12-10