Prove this result about construction of sets

139 Views Asked by At

In Enderton's book on Set Theory, the following problem is given after introducing the notion of sets as an infinite hierarchy (I hope this much explanation is sufficient; if not, please mention and I'll include more):

We have stated that $V_{\alpha+1} = A \cup \mathcal P (V_\alpha)$. Prove this at least for $\alpha < 3$.

Here, $\mathcal P$ is the power set, and $V_\alpha$ is the infinite union $V_0 \cup V_1 \cup V_2 \cup \ldots$, and $A$ is the set of all atoms (from which we intend to construct all possible sets).

A word about $V_i$ here. In the construction, $V_{i+1}$ is defined as $V_i \cup \mathcal P(V_i)$, and the first set, the set of all atoms, is $V_0$ or $A$.

I don't see how this can be "proved" at all, let alone for $\alpha < 3$. After all, the given construction of sets is a mere representation that we dreamed up, not something we can verify. At best I can take $A=\phi$ and proceed to construct up to $V_4$, but how do I prove (verify) this?

1

There are 1 best solutions below

2
On BEST ANSWER

Generally, a proof like this one would proceed by transfinite induction: you would prove that the statement is valid for $V_0$, proceed to show that, if it's valid for $V_\alpha$, it's also valid for $V_{\alpha+1}$, and, finally, that if it's valid for all $\beta < \gamma$, it's also valid for $V_\gamma$, where $\gamma = \bigcup\{\beta \; | \; \beta < \gamma\}$.

However, since this is an early exercise in the book, Enderton hasn't introduced the transfinite machinery yet (he introduces induction in Chapter 4 and transfinite induction in Chapter 7, I believe). So the proof here will have to proceed by direct construction: you'll need to literally exhibit the sets in question and show that the target property applies to them. That's why he limited the proof to $\alpha < 3$; the size of each $V_\alpha$ grows rather fast (here's another interesting exercise: try to show how we can capture the size of each $V_\alpha$), so for $\alpha > 3$, the exercise would be impractical. In this particular case, you need to construct $V_0, V_1, V_2$ and show that, for each of these, $V_{\alpha + 1} = V_\alpha \cup \mathcal{P}(V_\alpha) = A \cup \mathcal{P}(V_\alpha)$.

For instance, the construction is clearly true of $V_0$: if we admit atoms, then $V_0 = \{a, b, c, \dots\}$; since it has no predecessors, the theorem is vacuously satisfied. If we don't admit atoms, then $V_0 = \varnothing$, again vacuously satisfying the theorem. Try constructing $V_1$ and $V_2$, and then show that the theorem is true of them. You do this by showing that, say, $V_1 = A \cup \mathcal{P}(V_0) = V_0 \cup \mathcal{P}(V_0)$, which is possible to prove by literally constructing the sets in, say, brace notation.

I'm not giving more details in order not to give away the answer. If you're still having problems, I can construct $V_1$ for you.

EDIT: Incidentally, the reason why the theorem works is that each $V_\alpha$ is a transitive set. Since, for any transitive set $S$, $S \subseteq \mathcal{P}(S)$, it follows that $S \cup \mathcal{P}(S) = \mathcal{P}(S)$.

Also, don't take $V$ so lightly as a "mere representation we dreamed up". They are actually well-defined in our theory (well, they will be by the time you finish Chapter 7) and can be used to prove some interesting results (see the section "Natural Models" in Chapter 9 if you want a preview of some of its uses).