Cardinality of Vitali sets: countably or uncountably infinite?

I am a bit confused about the cardinality of the Vitali sets.

Just a quick background on what I gather about their construction so far:

We divide the real interval $[0,1]$ into an uncountable number of disjoint classes in such a way that two numbers $x$ and $y$ are in the same class if their difference x-y is a rational number. Therefore the equivalence relation on the real numbers would be: $x\sim y\iff x-y\in\mathbb Q$.

The cardinality of our classes is equivalent to the cardinality of $\mathbb Q$, so the classes have countably infinite elements.

How many of these classes are there? As each only has countably infinite elements, but each element of $[0,1]$ lies in one class, there are uncountably infinite classes.

Now, using the axiom of choice, we take one element out of each class and put it in the set V. This is a Vitali set.

Hopefully this is all good at this point.

So each Vitali set should have uncountably many elements (because we have uncountably many classes), but there should be countably many Vitali sets (because each class has countably many elements) correct?

But then why does Wikipedia state that "There are uncountably many Vitali sets..."?

-
You can only find countably many non-intersecting Vitali sets, but the choices that you make when building the set don't have to be entirely distinct for distinct Vitali sets - if 1 and $\pi$ both go into some Vitali set $V_1$, there's nothing to prevent me from using either or both of them in another Vitali set $V_2$. – Steven Stadnicki Nov 6 '12 at 8:31
@StevenStadnicki that actually solved the root of the problem! I was looking at the proof of why the vitali sets are non-measurable where they basically had a vitali set, then created new vitali sets by shifting the original set by a rational number and then performed the "union of a countable number of disjoint sets" to prove that this should add up to a length of 1 but instead is either 0 or infinity. So I was under the impression that there was a countable infinite number of vitali sets. And you made me realize that this is only true if they are disjoint vitali sets – BYS2 Nov 6 '12 at 8:51

4 Answers

You have $\mathfrak c=2^{\aleph_0}$ classes, each of them is of the size $\aleph_0$.

You get the set $V$ by choosing one element from each class. How many possibilities are for such choice? Precisely $$\aleph_0^{\mathfrak c}=2^{\mathfrak c}$$ possibilities. (Size of each class raised to the number of classes - you are basically counting the map from the set of classes, for each class you have countably many possibilities.)

This cardinal number is definitely uncountable: $2^{\mathfrak c}>\mathfrak c>\aleph_0$.

The above cardinal equality holds since $$2^{\mathfrak c} \le \aleph_0^{\mathfrak c} \le \mathfrak c^{\mathfrak c} = (2^{\aleph_0})^{\mathfrak c} = 2^{\aleph_0\cdot\mathfrak c} = 2^{\mathfrak c},$$ so by Cantor-Bernstein Theorem all cardinal numbers in this chain of inequalities are the same.

-
Thanks, that made perfect sense! I was getting confused because I was looking at a proof where they were referring to disjoint vitali sets and how those were countable. But I realize that in the general case, of any random vitali set, there are uncountably many – BYS2 Nov 6 '12 at 8:50

Remark: Throughout this post, I will be assuming the Axiom of Choice. This won't always be necessary (in fact, in most of the instances where we'll use it, we could've instead used weaker choice principles), but it makes things far less messy to prove. Let me know if you're interested in a more choice-free version (or if there's any claim I make herein that you don't believe/understand), and I'll see what I can do. Some choice will be necessary, though, as discussed in this answer.

Given a Vitali set $V$, we get a whole new Vitali set $V'$ if we pick one equivalence class, then swap the unique element of $V$ lying in that equivalence class for another member of that equivalence class, yes? Furthermore, if we'd picked a different equivalence class to perform that swap in--to get a set $V''$, say--then we'd have $V''\neq V$ by the same reasoning, but we'd also have $V''\neq V'$. (Why?) Thus, for each equivalence class--of which there are uncountably many--we can obtain a different Vitali set by performing a swap as described above, and swaps performed in different equivalence classes yield different Vitali sets, so in this fashion, we see that there are uncountably many Vitali sets.

It's worth noting that any collection of pairwise disjoint Vitali sets will be at most countably infinite, but that's another story.

If you're interested in the precise cardinality of the set of Vitali sets--let's call it $\Bbb V$--we can use the following approach. In the following, by $\mathfrak{c}$ I denote the cardinality of $\Bbb R$, and by $\aleph_0$ I denote the countably infinite cardinality. Given any two sets $A,B$, I let $B^A$ denote the set of functions from $A$ to $B$. By definition, we have $|B|^{|A|}:=\bigl|B^A\bigr|.$

First, observe that every Vitali set is, of course, a subset of $\Bbb R$--an element of the power set of $\Bbb R$. There is a ready bijection from the power set of $\Bbb R$ to $\{0,1\}^{\Bbb R}$, given by $A\mapsto\chi_A$--where $\chi_A$ is the characteristic function of $A$. Hence, the power set of $\Bbb R$ has cardinality $\left|\{0,1\}^{\Bbb R}\right|=\left|\{0,1\}\right|^{|\Bbb R|}=2^\mathfrak{c},$ and since $\Bbb V$ is a subset of the power set of $\Bbb R$, then $$|\Bbb V|\leq 2^\mathfrak{c}.\tag{1}$$

Now, $[0,1]$ also cardinality $\mathfrak{c}$, and so cannot be the union of less than $\mathfrak{c}$-many sets of cardinality $\aleph_0$. Since $[0,1]$ is the union of the equivalence classes described above, then there must be at least $\mathfrak{c}$-many of them. On the other hand, there can't be more than $\mathfrak{c}$-many such classes, since they're disjoint, and so their union would have cardinality greater than $\mathfrak{c}$ if there were more than $\mathfrak{c}$-many. Hence, there are precisely $\mathfrak{c}$-many equivalence classes. Let $f$ be any bijection from $\Bbb R$ to the set of equivalence classes.

The rationals are countable, so let the sequence $\{q_n\}_{n\in\Bbb N}$ be an enumeration of the rationals. Fix some Vitali set $V$. For any $x\in\Bbb R$, let $g(x)$ be the unique member of $V$ in the equivalence class $f(x)$--that is, $g(x)$ is the unique element of $V\cap f(x)$. Observe that, given any $x\in\Bbb R$, the sequence $\{g(x)+q_n\}_{n\in\Bbb N}$ is an enumeration of the equivalence class $f(x)$.

Now, given any $h\in \Bbb N^{\Bbb R}$ (any function $h:\Bbb R\to\Bbb N$), we'll let $$V_h=\left\{g(x)+q_{h(x)}:x\in\Bbb R\right\}.$$ Then $h\mapsto V_h$ is an injection from $\Bbb N^{\Bbb R}$ to $\Bbb V$, so $$\aleph_0^\mathfrak{c}=\left|\Bbb N\right|^{|\Bbb R|}=\left|\Bbb N^{\Bbb R}\right|\le|\Bbb V|.\tag{2}$$

Finally, observe that $\{1,2\}^{\Bbb R}$ is a subset of $\Bbb N^{\Bbb R}$--that is, every function $\Bbb R\to\{1,2\}$ is a function $\Bbb R\to\Bbb N$--regardless of whether your natural numbers are the positive integers or the nonnegative integers. (If you define your natural numbers any other way...you're just a jerk, lol.) Therefore, $$2^\mathfrak{c}=\left|\{1,2\}\right|^{|\Bbb R|}=\left|\{1,2\}^{\Bbb R}\right|\le\left|\Bbb N^{\Bbb R}\right|=\left|\Bbb N\right|^{|\Bbb R|}=\aleph_0^\mathfrak{c}.\tag{3}$$ Therefore, we have $$|\Bbb V|\overset{(1)}\le 2^\mathfrak{c}\overset{(3)}\le\aleph_0^\mathfrak{c}\overset{(2)}\le|\Bbb V|,$$ so by Schroeder-Bernstein theorem, we have $$|\Bbb V|=2^\mathfrak{c}=\aleph_0^\mathfrak{c}.$$

-
Thank you for the good response! I was getting confused because I was looking at a proof where they were referring to disjoint vitali sets and how those were countable. But I realize that in the general case, of any random vitali set, there are uncountably many. I gave Martin the checkmark because it was a bit clearer for me and he answered first, but yours was good too! – BYS2 Nov 6 '12 at 8:53
Understandable! I'd probably have accepted Martin's answer over mine, were I in your shoes. I've just finished adjusting my answer to give more detail. Does that make it clearer? – Cameron Buie Nov 6 '12 at 9:53
Wow, that was great! thank you very much for the update :D. I feel bad if I were to take away Martin's checkmark and give it to you :p, but this answer covers everything I wanted to know. I really appreciate the time you took to write this out! – BYS2 Nov 6 '12 at 11:28
No problem at all! – Cameron Buie Nov 6 '12 at 11:31

I picture it like this: At each irrational point in $[0,1]$ you "attach" a set of the size of $\mathbb Q$. Then it's clear that there are uncountably many such sets since the cardinality of $\mathbb R \setminus \mathbb Q$ is the same as the cardinality of $\mathbb R$.

And each such set has the size of $\mathbb Q$ because it is a copy of $\mathbb Q$. Defining two elements of $\mathbb R$ to be equivalent if they differ by a rational gives you $\mathbb R / \mathbb Q$ which looks like $x + \mathbb Q$ for each irrational $x$ in $\mathbb R$.

-

The idea that each choice of representative is a Vitali set. We have uncountably many equivalence classes; each class is infinite; so we have uncountably many ways of choosing. In fact we have $2^{2^{\aleph_0}}$ ways of choosing representatives, which gives us a lot Vitali sets, more than the real numbers themselves.

-
Just a quick clarification, you say "We have uncountably many equivalence classes; each class is infinite" do you mean "each class is countably infinite"? – BYS2 Nov 6 '12 at 8:27
@BYS2: Yes, but the fact each class is countably infinite is irrelevant (and trivial). – Asaf Karagila Nov 6 '12 at 8:58
Yup I realize that :), i'm just a bit pedantic on this stuff. even though it doesn't matter to the final result.. Thanks for your response though! – BYS2 Nov 6 '12 at 9:00