0
$\begingroup$

I have a homework question that goes like this: Prove that $N \times N$ is of the same cardinality as $N$.

Please correct me if I'm wrong, but isn't this conjecture false? Consider if $N = \{ a, b \}$. Then $|N|$ = 2 and $N \times N = \{ (a, a), (a, b), (b, a), (b, b) \}$ right? So $|N \times N| = 4$ while $|N| = 2$?

If $|N \times N| = |N|$, what did I do wrong?

|cite|improve this question
$\endgroup$
  • 8
    $\begingroup$ You are completely correct, if $N$ is a finite set. I suspect your homework is referring to $\mathbb{N}$, the set of natural numbers, which is infinite, and for which the claim is true. $\endgroup$ – mweiss Sep 1 '14 at 0:57
  • $\begingroup$ ... wrong if $N$ is finite and $|N|>1$. $\endgroup$ – Ittay Weiss Sep 1 '14 at 1:16
1
$\begingroup$

If you know that the set of rational numbers (in this case with positive numerator and positive denominator) has the same cardinality as the set of natural numbers, this proof becomes quite easy, because we can think of any rational number of this sort as an element in $\mathbb N \times \mathbb N$.

When we biject the natural numbers to these rational numbers, whichever natural number is assigned to a particular rational number, $a \over b$, let that same natural number be assigned to $(a,b)$. Thus, $\mathbb N \times \mathbb N$ has the same cardinality as $\mathbb N$

|cite|improve this answer
$\endgroup$
1
$\begingroup$

I think $N$ is the natural numbers set $\Bbb{N}$, in this case try exhibit a injective fuction between $\Bbb{N}\times\Bbb{N}$ and $\Bbb{N}$.

Hint: Try $f(m,n)=2^m3^n$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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