1

I am trying to show that the cardinality of $\mathbb{N}\times \mathbb{N}$ is the same as the cardinality of $\mathbb{N}$.

Let's look at the function $f(a, b)=2^a(2b+1)-1, f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$. How does one come up with it?

We have to show that $f$ is surjective and injective. For the injectivity if we take $f(a,b)=f(a',b')$, we can see that $a=a'$ and $b=b'$.

How do we prove the surjectivity, though? If we take an arbitrarily $n\in\mathbb{N}$, we are supposed to show that there are $a,b\in\mathbb{N}$ such that $f(a,b)=n$. How do we do that? I don't see that it's necessary for such $a,b$ to exist.

Remark: We consider $0$ to be a natural number, so $0\in\mathbb{N}$.

Trifon
  • 113
  • If you divide $n+1$ by the largest power of $2$, say $2^{a}$ that divides $n$, you will be left with an odd number $2b+1$. – geetha290krm Nov 13 '23 at 09:41
  • @geetha290krm, I really don’t understand these ideas. Why would we be left with an odd number when diving n+1 by the largest power of 2 that divides n? – Trifon Nov 13 '23 at 09:44
  • 1
    If it is even then $2$ would divide it. But I have already pulled out the highest power of $2$ from $n+1$. – geetha290krm Nov 13 '23 at 09:49

1 Answers1

1

You need to show that for that the equation $z = 2^a(2b + 1) - 1$ has solution for every $z \in \mathbb{N}$. Observe that

$$ \frac{z + 1}{2^a} - 1 = 2b $$

So if $z$ is even and $a = 0$ then equation is simply $$ z = 2b $$

Which has solution for any fixed even $z$. If $z$ is odd then $z + 1$ is even so fiz $a = 1$ so we can write

$$ z + 1 - 2 = 2b \iff z = 2b + 1 $$

which again has solution for any $z \in \mathbb{N}$. So we can conclude that

$$ f \left( \bigcup_{b \in \mathbb{N}} \left\{ (0,2b)\right\} \cup \left\{ (1,2b + 1)\right\} \right) = \mathbb{N} $$

That's your surjectivity.

user8469759
  • 5,285