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..."?

Solution 1:

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 maps 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.

Solution 2:

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}.$$

Solution 3:

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$.

Solution 4:

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.