Let $\mathbb{N}$ be the set of natural numbers.

Show that $$\mathbb{N} \leq \mathbb{N} \times \mathbb{N}$$

I know this is true but I don't know how to show it.

Please help!


closed as off-topic by user296602, José Carlos Santos, Namaste, Zhanxiong, Rolf Hoyer Nov 27 '17 at 1:00

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Community, José Carlos Santos, Namaste, Zhanxiong, Rolf Hoyer
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What do you mean by $\Bbb N\leqslant\Bbb N\times \Bbb N$? $\endgroup$ – user228113 Nov 26 '17 at 22:57
  • $\begingroup$ In terms of cardinality yes. It means "No larger than". $\endgroup$ – user3765987 Nov 26 '17 at 22:58
  • $\begingroup$ Technically, you presumably want it to mean "(cardinality) smaller or equal than". $\endgroup$ – user228113 Nov 26 '17 at 22:59
  • 2
    $\begingroup$ Why do you know this is true? And what is the definition of $\leq$, not your "intuitive understanding of 'No larger than'"? $\endgroup$ – Asaf Karagila Nov 26 '17 at 22:59
  • $\begingroup$ I don't know how to make the symbol, its not less than or equal too. The symbol does mean "No larger than". $\endgroup$ – user3765987 Nov 26 '17 at 23:03

You are describing Cantor pairing. Construct an infinite table of (x, y), $x \in \mathbb{N}, y \in \mathbb{N}$. The natural numbers have cardinality $\aleph_0$, and so does the set of (x, y) pairs. Why? Because one can construct a 1-to-1 mapping between them, with $45^{\circ}$ boustrophedon traversal of indices starting with: (1, 1), (1, 2), (2, 1), (3, 1), (2, 2).... He used it to show the rationals ($\frac{x}{y}$) have the same cardinality as the natural numbers.

  • 1
    $\begingroup$ Wait, are you claiming that $\Bbb{N\times N}$ is uncountable? Because that's just plain wrong. $\endgroup$ – Asaf Karagila Nov 26 '17 at 23:16
  • $\begingroup$ Asaf, I don't understand your remark. Quoting the cited reference: A set has cardinality $\aleph_{0}$ if and only if it is countably infinite, that is, there is a bijection (one-to-one correspondence) between it and the natural numbers. I gave Cantor's 1-to-1 correspondence between OP's $\mathbb{N} \times \mathbb{N}$, and the countable set $\mathbb{N}$. $\endgroup$ – J_H Nov 26 '17 at 23:24

You have an injection from $\Bbb N$ into $\Bbb {N \times N}$ by $n \to (n,1)$. That is all you need to show less than or equal to. More interesting, and you can find it on this site, is to show they are equal.


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