Dumb, simple, surprising, cardinality question

[jostpuur]

How do you prove that there does not exist a set [itex]X[/itex] such that

[tex]
\textrm{card}(X) < \textrm{card}(\mathbb{N})
[/tex]

but still

[tex]
n < \textrm{card}(X),\quad \forall\;n\in\mathbb{N}
[/tex]

-----------------

edit:

I proved this already. No need to answer...

------------------

I came up with a new question! Is this true?

[tex]
\textrm{card}\Big(\bigcup_{n=1}^{\infty} \mathbb{N}^n\Big) = \textrm{card}(\mathbb{R})
[/tex]

 

[disregardthat]

Nope, a countable union of countable sets is always countable.

 

[jostpuur]

I had forgotten that now... Amazing. But this is true?

[tex]
\textrm{card}(\mathbb{N}^{\mathbb{N}}) = \textrm{card}(\mathbb{R})
[/tex]

So all this implies

[tex]
\textrm{card}\Big(\bigcup_{n=1}^{\infty}\mathbb{N}^n\Big) < \textrm{card}(\mathbb{N}^{\mathbb{N}})
[/tex]

How unfortunante...

 

[henry_m]

But this is true?

[tex]
\textrm{card}(\mathbb{N}^{\mathbb{N}}) = \textrm{card}(\mathbb{R})
[/tex]

Yes it is! Amazingly enough, we actually have the stronger
[tex]
\textrm{card}(\mathbb{R}^{\mathbb{N}}) = \textrm{card}(\mathbb{R})
[/tex].
It's a very worthwhile exercise to try to prove this. It's not straightforward, so ask back for a hint if you get stuck.

Here's another question: is there a set with cardinality strictly between that of N and R?

Amazingly enough, the actual answer to this question isn't "no", BUT neither is it "yes": it's something altogether more weird and interesting. In fact the question has no answer; under the standard axioms of set theory, it can neither be proved nor disproved! Look up "continuum hypothesis" for more info on this if you're interested. Mathematics is a weird place sometimes...

 

[henry_m]

Something to get you started on the problem: First prove that [itex]\mathbb{R}[/itex] has the same cardinality as the power set of [itex]\mathbb{N}[/itex], denoted [itex]2^\mathbb{N}[/itex]. This is the set of all subsets of [itex]\mathbb{N}[/itex]. Then prove that the laws of indices for ordinary numbers still work here...