Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Asaf Karagila Oct 5 '12 at 12:00
add comment

2 Answers

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|$.

share|improve this answer
add comment

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.

share|improve this answer
    
Thank you I am using surjections because I haven't learned much about axiom of choice yet. –  mehdi Oct 8 '12 at 12:42
1  
@mehdi: But the definition of the cardinal ordering is by injections; not by surjections. –  Asaf Karagila Oct 8 '12 at 16:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.