I am very new to proofs so please excuse any trivial errors.

In lecture we were told that:

A set $\mathbb S$ is called finite if there exists a one-to-one mapping (bijective mapping) between $\mathbb S$ and the set $\mathbb N_n=\{0,1,2,3,...,n-1\}$ for some natural number $n$. A set is called countable infinite if there exists a bijective mapping between $\mathbb S$ and the set $\mathbb N=\{0,1,2,...\} $ of all natural numbers

I want to answer the following questions:

1. Show that the set $\mathbb S=\{a,b,c\}$ is countable

Does countable mean countable infinite? An attempt from another post on this site: For all triples $(a,b,c)$ there exists an according sum $S=a+b+c \implies ...$ But wouldn't the sum be a surjection between $\mathbb S$ and $\mathbb N$ and not a bijection?

2. Show that the set of integer numbers $\mathbb Z=\{0,\pm1,\pm 2,...\}$ is countable infinite

Before I continue with this proof I have a question about mapping. The definition says that "if there exists a bijective mapping...". In this context, can a function $f(x)$ be considered a mapping? If yes, then can't I just define myself some map $$f:\mathbb Z\to \mathbb N$$

and let $\space f$ be: $$x \mapsto \lvert x \rvert$$

which would then automatically imply that $\mathbb Z$ is countable infinite? (or wouldn't it)?

3. Show that $\mathbb S=\mathbb N \times \mathbb N=\{x |x=(p,q),p,q \in \mathbb N\}$ is countable infinite.

I am not sure about this one but if my "intuition" from 2) turns out to be correct I can maybe define some sort of norm and show that it is a bijection between $\mathbb S$ and $\mathbb N$

  • 1
    $\begingroup$ See Countable set: "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set." $\endgroup$ – Mauro ALLEGRANZA Apr 26 '16 at 15:50
  • 1
    $\begingroup$ For 2. You need it to also be one-to-one. The issue with yours is that, for example, $3, -3\in\mathbb{Z}$ both map to $3\in\mathbb{N}$, but reversing it, $3\in\mathbb{N}$ cannot map to both $3$ and $-3$ in $\mathbb{Z}$ $\endgroup$ – Bonnaduck Apr 26 '16 at 16:10
  • $\begingroup$ @Bonnaduck That makes sense. Thanks! $\endgroup$ – bluemoon Apr 26 '16 at 16:17
  1. Any finite set is countable (check the definition of countable)

  2. Define $f : \mathbb{Z} \rightarrow \mathbb{N}$ as follows :

if $n \in \mathbb{N} $, $f(n)=2n$, otherwise (if $n < 0 $) $f(n)= 2|n|-1 $

  1. Define $f : \mathbb{S} \rightarrow \mathbb{N}$ as follows:

$\forall (p,q) \in \mathbb{S}, f(p,q) = \frac{(p+q-1)(p+q)}{2} + p + 1 $

This can be seen as "counting elements in a table by diagonal", usually used in order to show that $\mathbb{Q} $ is countable (https://www.google.fr/?gws_rd=ssl#q=count+rational+numbers)

  • 1
    $\begingroup$ $f(n) = 2 \mid n \mid - 1$ when $n<0$ would fit better if you want $f$ to be a bijection $\endgroup$ – charmd Apr 26 '16 at 15:54
  • $\begingroup$ Cool idea for 2. Thanks for your help! $\endgroup$ – bluemoon Apr 26 '16 at 16:23


  1. Can you assign each member of $\mathbb{S}$ to a member of (for example) $N=\{4,6,9\}$ ($N=\{0,1,2\}$ is the proper set to do this following your definition)?

  2. Note that you can assign 0 from $\mathbb{N}$ to 0 in $\mathbb{Z}$, then 1 from $\mathbb{N}$ to 1 in $\mathbb{Z}$, then 2 from $\mathbb{N}$ to -1 in $\mathbb{Z}$, and so on... (Write this more formally).

  3. Consider the cartesian plane. You can draw the points $(p,q)$ as a grid that covers the first quadrant. You can trace them from $(0,0)$ to (1,0) to (0,1) to (0,2) to (1,1) to (2,0) to (3,0), etc... making something like a zigzag motion. Then each step corresponds to a natural number


Your Answer

