cardinality of $V_\omega$

Question

I'm unfamiliar with set theory so bear with me.

Let $V_\alpha$ be the members of the von Neumann Hierarchy, so $$V_0 = \{ \}, V_{\alpha + 1 } = \mathcal{P} (V_\alpha), V_\lambda = \bigcup_{\alpha < \lambda} V_\alpha$$. (Note that $\mathcal{P} (S)$ denotes the power set of $S$.) In particular, $V_\omega = \bigcup_{n < \omega} V_n$. I claim that $|V_\omega| = \aleph_0$. My idea is that essentially, each $V_n$ has finitely many elements, so we can list all the elements of all the $V_n$ in a countable list. Then removing duplicates gives us the elements of $V_\omega$, so $|V_\omega| = \aleph_0$.

Is the above argument valid (especially the "listing the elements" part)? Thanks in advance!

Answer 1

Your proof is essentially correct, albeit pretty informal. Here are three ways to formally prove that $V_\omega$ is countable.

Proof 1. Fix, for each $1 \le n < \omega$, $k_n < \omega$ and a bijection $f_n \colon k_n \to V_n \setminus V_{n-1}$. This is possible, since each $V_n$ is finite. Now let $k_0 := 0$ and $$ f \colon \omega \to V_{\omega}, x \mapsto f_n(x- \sum_{i=0}^{n-1} k_i), $$ where $n$ is maximal such that $\sum_{i=0}^{n-1}k_i \le x$. This is a bijection.

Proof 2. Since $V_n$ is finite for each $n < \omega$, $V_\omega = \bigcup_{n < \omega} V_n$ is a countable union of countable (in fact finite) sets. Using the general result that countable unions of countable sets are countable, it follows that $V_\omega$ is countable.

Proof 3. Recursively define a function (known as Ackermann's coding function) $$ f \colon \omega \to V_\omega $$ with the following property: If $(n_i, \ldots, n_k)$ is the binary coding of $n$ - by which I mean that $n_i \in \{0,1\}$ and $n = \sum_{i=0}^k n_i 2^i$ - then $$ f(n) := \{ f(i) \mid n_i = 1 \}. $$ It's a nice exercise to prove that $f$ is well-defined and in fact a bijection.

Answer 2

In ZF it is not a theorem that every countable union of finite sets is countable.

Another way to show that $|V_{\omega}|=\omega$ :

$V_0=\phi$ has a (unique, empty ) well-order $<_0.$ For $n\in \omega,$ suppose $<_n$ is a well-order on $V_n.$ Define $<_{n+1}$ on $V_{n+1}$ as follows:

(i). If $x,y\in V_n$ then $x<_{n+1}y\iff x<_ny.$

(ii). If $x\in V_n$ and $y\in V_{n+1}$ \ $V_n$ then $x<_{n+1}y.$

(iii). If $x, y\in V_{n+1}$ \ $V_n$ with $x\ne y,$ let $z$ be the $<_n$-least member of $(x$ \ $y)\cup (y$ \ $x).$ Let $x<_{n+1}y\iff z\in y.$

For $x,y\in V_{\omega}$ let $n$ be the least (or any) $m\in \omega$ such that $\{x,y\}\subset V_m.$ Define $x<_{\omega}y\iff x<_ny.$ Then $<_{\omega}$ is a well-order on $V_{\omega}.$

For $y\in V_{\omega},$ let $y\in V_n$ with $n\in \omega.$ Then pred$_{<_{\omega}}y= \{x:x<_{\omega}y\}\subset V_n,$ which is finite. A well-order in which every initial segment is finite is order-isomorphic to $\omega$ or to a member of $\omega.$

Answer 3

I'm late, but I think I have an even easier solution: Note that for all $n\in \omega$, $V_n$ is finite, so we may construct a bijection $f_n: V_n \rightarrow \{0,\dots,|V_n|\}$, a numbering of the elements of $V_n$. Then define an injection $g:V_\omega \rightarrow \omega^2$ by $g(a) = (\text{rank}(a), f_{\text{rank}(a)}(a))$. Since $|\omega^2| = |\omega|$, we have shown $|V_\omega| \leq \aleph_0$. It's trivial to construct an injection from $\omega \rightarrow V_\omega$ (take the identity mapping), so by Schroder-Bernstein, $|V_\omega| = \aleph_0$.