For subsets $A$ and $B$ of $[0,1)$, say $A\sim B$ iff $\lambda(A\Delta B)=0$ where $\lambda$ is Lebesgue measure.

Question: How many equivalence classes of subsets of $[0,1)$ are there given AC?

I would guess the answer is $2^c$ given AC, but I haven't got a proof.

What got me thinking about this was trying to find a way to say that there are more nonmeasurable sets than measurable ones. There are, of course, $2^c$ of each, but modulo null sets there are only $c$ measurable ones (at least given AC), so if there were more than $c$ subsets modulo null sets, we could say that modulo null sets there are more nonmeasurable sets than measurable ones.

  • $\begingroup$ I don't think that this is really a question about the axiom of choice. I mean, if this is a question about the axiom of choice, we need to start tagging many other questions like that as well. $\endgroup$
    – Asaf Karagila
    Mar 19, 2015 at 20:53
  • $\begingroup$ Agreed, though there are questions about what values for the cardinality are options without AC. (E.g., if all sets are measurable then we get $\le c^2$, assuming that the proof that there are $c$ Borel sets goes through without AC.) $\endgroup$ Mar 20, 2015 at 0:18
  • $\begingroup$ Luckily $\mathfrak c^2=\mathfrak c$ without using choice. Unluckily, the assumption that there are $\frak c$ Borel sets does use the axiom of choice. $\endgroup$
    – Asaf Karagila
    Mar 20, 2015 at 13:54
  • $\begingroup$ Does it use anything beyond countable choice? $\endgroup$ Mar 20, 2015 at 16:14
  • $\begingroup$ I don't think so. $\endgroup$
    – Asaf Karagila
    Mar 20, 2015 at 16:21

2 Answers 2


Yes, there are $2^\mathfrak{c}$ equivalence classes. In fact, I claim that there is a collection $S$ of $\mathfrak{c}$ disjoint non-null subsets of $[0,1)$; taking all unions of subcollections of $S$ gives $2^\mathfrak{c}$ inequivalent subsets of $[0,1)$.

To construct this $S$, let $N$ be the set of all null Borel sets and enumerate $N\times\mathfrak{c}$ with order type $\mathfrak{c}$. Using this enumeration, define a function $f:[0,1)\to\mathfrak{c}$ by induction such that for each $(n,\alpha)\in N\times\mathfrak{c}$, $f^{-1}(\{\alpha\})\not\subseteq n$. We can do this because at each stage of the induction, we have defined $f$ at fewer than $\mathfrak{c}$ points, and the complement of $n$ has cardinality $\mathfrak{c}$. The collection $S=\{f^{-1}(\{\alpha\})\}_{\alpha\in\mathfrak{c}}$ then consists of $\mathfrak{c}$ disjoint non-null sets.

Here is an earlier version of my answer, which is a slight variant on a standard argument that nonmeasurable sets exist and shows there must be more than $\mathfrak{c}$ equivalence classes, but does not show there must be $2^\mathfrak{c}$ of them. Let $S$ be any collection of $\mathfrak{c}$ subsets of $[0,1)$; we will find a subset $A\subseteq[0,1)$ that is not equivalent to any element of $S$. Let $N$ be the set of all Borel null sets and enumerate $N\times S$ with order type $\mathfrak{c}$. Define the characteristic function of $A$ inductively such that for each $(n,B)\in N\times S$, $A\Delta B\not\subseteq n$; we can do this because at each stage of the induction we have defined the characteristic function at fewer than $\mathfrak{c}$ points and the complement of $n$ has cardinality $\mathfrak{c}$.

  • $\begingroup$ But does "more than $c$" imply "$2^c$"? $\endgroup$
    – Fan Zheng
    Mar 19, 2015 at 21:25
  • 1
    $\begingroup$ Thanks! The existence of a set $S$ with the requisite properties (well, or the equivalent claim on the square) also follows from Sierpinski's 1938 partition of the square into perfect sets such that any choice of one element of each of the perfect sets gives a set with full outer measure: eudml.org/doc/213031 $\endgroup$ Mar 20, 2015 at 0:14

Edit. I had posted this answer to complement Eric's original answer, which showed that the number of classes was at least ${\frak c}^+$, since at that time we didn't quite yet know whether there were $2^{\frak c}$ classes. Afterwards, however, Eric improved his answer to get $2^{\frak c}$ directly. Following the comments, though, I have left this answer up.

Let me complement Eric's answer by showing that it is relatively consistent to have strictly more than ${\frak c}^+$ many equivalence classes. Indeed, it is relatively consistent with ZFC to have $2^{\frak c}$ many equivalence class, in a case where this is larger than ${\frak c}^+$.

Specifically, I claim that if the continuum hypothesis holds and there is a thick Kurepa tree (an $\omega_1$ tree with $2^{\omega_1}$ many branches), then there are $2^{\omega_1}=2^{\frak c}$ many equivalence classes. Indeed, I shall construct an almost-disjoint family of $2^{\omega_1}$ many Vitali sets.

To see this, let $T$ be a thick Kurepa tree, and let $\langle A_\alpha\mid\alpha<\omega_1\rangle$ enumerate the equivalence classes of reals under translation-by-a-rational. Label the $\alpha^{th}$ level of $T$ with the countably many elements of $A_\alpha$. For any path $s$ through $T$, the set $A_s$ of labels appearing on the nodes of $s$ will be a Vitali set, and therefore non-measurable. Further, any two distinct paths $s\neq t$ will have $A_s\cap A_t$ being countable, and so $A_s\not\sim A_t$. Since $T$ is a thick Kurepa tree, we therefore have $2^{\omega_1}$ many branches and thus this many equivalence classes modulo your relation. The collection $\{\ A_s\mid s\in[T]\ \}$ is an almost-disjoint family of $2^{\omega_1}$ many Vitali sets.

Finally, let me explain that it is relatively consistent from an inaccessible cardinal that there is a thick Kurepa tree, yet CH holds and $2^{\omega_1}$ is very large. One way to do this is as follows. Start with $\kappa$ inaccessible in $V$ and $2^\kappa$ very large (by forcing if necessary). Let $V[G]$ be the forcing extension by the Levy collapse, so that $\kappa=\omega_1^{V[G]}$. Consider the tree $T=(2^{<\kappa})^V$ in the model $V[G]$. Since every ordinal less than $\kappa$ was made countable, this has become an $\omega_1$-tree. Yet, since $2^\kappa$ was very large and cardinals $\kappa$ and above were preserved, we have $(2^\kappa)^V$ many branches through this tree. So it is thick.

  • $\begingroup$ Ah, Eric has now improved his answer to give $2^{\frak c}$ directly. So that subsumes the need for this argument. $\endgroup$ Mar 19, 2015 at 21:38
  • $\begingroup$ Vote up this comment if I should delete. $\endgroup$ Mar 19, 2015 at 21:39
  • 11
    $\begingroup$ Vote up this comment if you (as I) think that JDH should NOT delete his answer. $\endgroup$ Mar 19, 2015 at 22:07
  • 1
    $\begingroup$ You might just edit the first paragraph to clarify that it doesn't extend Eric's (current) result. $\endgroup$ Mar 20, 2015 at 4:53
  • 1
    $\begingroup$ @EmilJeřábek : More like a way to redeem oneself for whatever sin you think you have commited, mostly related to (sneaky) reputation gain. $\endgroup$
    – Hachino
    Mar 20, 2015 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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