# How can I prove that these sets are countable infinite?

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$

• 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." – Mauro ALLEGRANZA Apr 26 '16 at 15:50
• 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}$ – Bonnaduck Apr 26 '16 at 16:10
• @Bonnaduck That makes sense. Thanks! – 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)

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

Hints:

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