Proving $\operatorname{Card} (\omega_1)\leq \operatorname{Card} (P(\mathbb{N}))$

Question

Note that $\omega_1$ = first uncountable ordinal. It is the set of all countable ordinals

Still not used to using notations on this site so I'll first give the general idea i have in mind for this proof in steps:

1) for each countable ordinal there exists an order (a subset of $\mathbb{N}\times\mathbb{N}$) such that the ordinal is order-isomorphic with $\mathbb{N}$ or a proper subset of it.

2) Define an equivalence relation on $P(\mathbb{N}\times \mathbb{N})$ where two elements (two subsets of $\mathbb{N}\times\mathbb{N}$) are equivalent if both of them induce some order-isomorphism on the same ordinal.

3) define the map $f\colon\omega_1\to P(\mathbb{N}\times\mathbb{N})$ where each ordinal is mapped to the corresponding equivalence class.

4) Assuming the axiom of choice define a choice function $H$ on the set of equivalence classes which maps each equivalence class to a corresponding element inside the class.

5) take the convolution of $f$ and $H$ to obtain the desired 1-1 function.

I know I have yet to formalize the proof but are the general steps correct? I'm also not sure if parts 4 and 5 are even necessary.

Answer 1

Be careful! In step 3 you say $f$ takes an ordinal to the corresponding equivalence class, but equivalence classes of ordering lives in $P(P(\mathbb{N}\times\mathbb{N}))$. Your approach will work once you fix this.

Here is an slightly different way (really only cosmetically different): we construct a surjection from $P(\mathbb{N})$ to $\omega_1$, where we identify $\mathbb{N}$ with $\mathbb{N}\times\mathbb{N}$ and hence can take order-type for well-orderings, and if not well-ordering just cook up something that hits all of $\omega$ (e.g., $0$ if infinite, otherwise the ordinal corresponding to the cardinality). So we hit all countable ordinals and hence we have $\lvert\omega_1\rvert\leq^*\lvert P(\mathbb{N})\rvert$, and by AC $\leq^*$ and $\leq$ are the same.

Note that the statement cannot be proved with only ZF+DC -- there are models where neither $\omega_1$ nor $P(\mathbb{N})$ injects into each other, so are not comparable.

Answer 2

I guess it's easier: for each $\alpha \in \omega_1$ we choose (AC is used!) a bijection $f_\alpha: \mathbb{N} \mapsto \alpha$, which gives us a well-ordering on $\mathbb{N}$, defined by some subset $\Omega_\alpha\subset \mathbb{N}\times\mathbb{N} \sim \mathbb{N}$. Now the function $\varphi: \omega_1 \mapsto P(\mathbb{N})$: $\varphi(\alpha):=\Omega_\alpha$ is injective (otherwise two different ordinals would be order-isomorphic, which is impossible), which implies $\mathrm{card}(\omega_1)\leqslant \mathrm{card}(P(\mathbb{N}))$ by definition.