Is the size of any set constructible from the set of natural numbers?

102 Views Asked by At

I like to prove that for any set there exists a set of simple graphs that have the trivial automorphism group and such that there are no homomorphisms between them. I have an idea how to prove this, but this only works if the following holds:

If we start from the set of natural numbers, for any set $S$ we can construct a set $N$ from the natural numbers such that $|S|<|N|$, where the construction only includes taking the power set and unions. By this I also mean unions of infinitely many sets, so $B$ is also included in this example.

$$A_0:=\mathbb{N}$$ $$A_n:=\mathcal{P}(A_{n-1})$$ $$B=\bigcup_{n\in\mathbb{N}}A_n$$

Is it possible to use this, and if so, do i need the MK or NBG extensions, or hypotheses such as the continuum hypothesis?

1

There are 1 best solutions below

0
On BEST ANSWER

This is possible in $ZF$ in particular using the foundation and replacement axiom.

Define $V_0 = \emptyset$. If $V_\alpha$ has been defined let $V_{\alpha + 1} = \mathcal{P}(V_\alpha)$. If $\alpha$ is a limit ordinal, then $V_{\alpha} = \bigcup_{\gamma < \alpha} V_\gamma$. Let $\text{WF} = \bigcup_{\alpha < \text{Ord}}V_\alpha$.

So starting with $\emptyset$, $V_{\alpha + 1}$ formalizes taking power sets. For limit $\alpha$, $V_{\alpha}$ formalizes taking the union of all sets already constructed in this way.

Using the axiom of foundation, it can be shown that $V = \text{WF}$. Therefore every set $S \subseteq V_\alpha$ for some ordinal $\alpha$.