0
$\begingroup$

I have a proof for the following problem but I am not sure if it is valid or generalizes to infinite number of sets. Please give your suggestions or a better proof.

$|pow(\mathbb{N})|$ is defined as cardinality of power set of natural numbers.

Now for infinite sequence of sets we have , $|\mathbb{N}| < |pow(\mathbb{N})| < |pow(pow(\mathbb{N}))| ....$

Here $pow^n(\mathbb{N})$ is the $n$ th set in the sequence.

$U := \bigcup\limits_{n=0}^\infty pow^n(\mathbb{N}) $

Prove that $ |pow^n(\mathbb{N})| < |U| $ for all natural number $n$

My proof:

We know that there exists no surjection from $pow^n(\mathbb{N})$ to $pow^{n+1}(\mathbb{N})$, namely from a set to its power set, for any natural number $n$.

So an element $e$ in $pow^{n+1}(\mathbb{N})$ does not have an inverse image in $pow^n(\mathbb{N})$. For the set $U$ this specific element $e$ is still in $U$.

So we can't form a surjection from $pow^n(\mathbb{N})$ to $U$, since we still can't find an inverse image for $e$, which implies stricly smaller than relation.

  • 1
    Large cardinals are not just cardinals which are "very big". It is a set-theoretical notion which require additional assumption than the usual axioms of set theory.2012-10-05

2 Answers 2

3

Depending on what facts you already learned, the following might serve as a very short proof. $|pow^n(\mathbb N)|<|pow^{n+1}(\mathbb N)|\leq|U|$.

2

I pointed out in the previous question that you have asked, surjections are generally not enough in order to prove cardinal inequalities. Especially in contexts where the axiom of choice is not explicitly mentioned. Furthermore, the lack of surjection from one set onto another does not imply an injection exists; and the existence of a surjection and and injection need not imply a bijection exists either.

On the other hand, it is obvious that there is an injection from $pow^n(\mathbb N)$ into $U$. It is now enough to show that there is no surjection, since a bijection would imply a surjection exists; and we already know that there is an injection.

Regardless to the obviousness of the above, it is still an important point deserves mentioning.

Your proof seems to have the correct idea, but wording is quite awkward. I will write a complete proof, and I hope it will be an educational proof:


We know that there exists an injection from $pow^n(\mathbb N)$ into $U$, so $|pow^n(\mathbb N)|\leq|U|$. It is sufficient to show that there is no surjection from $pow^n(\mathbb N)$ onto $U$, since a bijection between $pow^n(\mathbb N)$ and $U$ would also be a surjection. If we show that there is no surjection, then the inequality is strict as wanted.

Suppose that $f\colon pow^n(\mathbb N)\to U$ was a surjection, define $g\colon pow^n(\mathbb N)\to pow^{n+1}(\mathbb N)$ as follows: $g(x)=\begin{cases} f(x) & f(x)\in pow^{n+1}(\mathbb N)\\ \varnothing& \text{otherwise}\end{cases}$

Since $f$ was a surjection $g$ is also a surjection from $pow^n(\mathbb N)$ onto $pow^{n+1}(\mathbb N)$, in contradiction to Cantor's theorem, therefore there is no such $f$ in contradiction to our assumption and as wanted.

  • 1
    @mehdi: But the definition of the cardinal ordering is by injections; not by surjections.2012-10-08