Cardinality of $A$ and the Natural Numbers

Question

The question asks to show that the set $A$ and the set of natural numbers have the same cardinality. Where $$A=(1,2,3)\times\mathbb{N}$$

So I know I have to prove a bijection, but I am having difficulty coming up with the formula to use. Any tips would be greatly appreciated!

Answer 1

Well, how would we count them?

We've got this set:

$(1,1), (1,2), (1,3), (1,4)........ $

$(2,1), (2,2), (2,3), (2,4)........ $

$(3,1), (3,2), (3,3), (3,4)........ $

How would I count them. Well I imagine I'd point to the first one in the first row and say "Okay, $(1,1)$ you are No. 1" and then I'd point to the first one in the second row and say "Okay, $(2,1)$ you are No. 2", and then I'd point to the first one in the third row and say "Okay, $(3,1)$, you are No. 3". Then I'd point to the second in the first row and say "Okay, $(1,2)$ you are No. 4$.

Then I'd ask myself: "Okay, when I get the the $k$th one in the $b$th row, what number will I have reached?".

And then I'd answer myself: "Well I've gone through $k-1$ terms to get to this $k$th term. And for each of those $k-1$ terms I picked one from each row so that's $3(k-1)$ I've gone through to get to this point. And now I'm on the $b$th row so that's $b$ more terms. So I'm at the $3(k-1) + b$ item I counted."

"So you, $(b, k)$, you are number $3(k-1) + b$".

And that's my bijection: $f:\{1,2,3\}\times \mathbb N\to \mathbb N$ via $f(b, k) = 3(k-1) + b$.

Answer 2

Hint: You can list all the elements of $\mathbb{N}$ in something like an infinite matrix where its entries come from $A=\{1,2,3\}\times \mathbb{N}=\{(x,n): x=1,2,3 \,\text{ and }\, n\in\mathbb{N}\}$ in the following way

$$\begin{bmatrix}1 & 4 & 7 & \cdots \\2 & 5 & 8 & \cdots \\ 3 & 6 & 9 &\cdots\end{bmatrix}$$

So, you're sweeping natural numbers column-wise, i.e. you associate to each entry $(i,j)$, a natural number defined by $3(j-1)+i$ for $i=1,2,3$ and $j \in \mathbb{N}$. For example, we have $(1,2) \mapsto 4$, $(2,1) \mapsto 2$, $(3,3) \mapsto 9$, so on so forth.

---

Addendum: If you are interested in a closed form solution, define $f: A \to \mathbb{N}$ by

$$f(x,n) = 3(n-1)+x$$

Then, since $x=1,2,3$, we have that $f(x,n)=m$ if and only if

$$3(n-1)+1 \leqslant m \leqslant 3(n-1)+3$$ $$n-1<(n-1)+\frac{1}{3} \leqslant \frac{m}{3} \leqslant (n-1)+1 = n$$ $$n-1 < \frac{m}{3} \leqslant n$$

which implies that $n = \big\lceil \frac{m}{3}\big\rceil$ and hence, $x = m - 3\big(\big\lceil \frac{m}{3}\big\rceil -1\big)$.

So, $f^{-1}: \mathbb{N} \to A$, is defined by

$$f^{-1}(m) = \bigg(m - 3\big(\lceil \frac{m}{3}\rceil -1\big), \lceil \frac{m}{3}\rceil\bigg)$$

where $\big\lceil x \big\rceil$ denotes the ceiling function, i.e. the smallest integer $n$ such that $x \leqslant n$.

So, $f: A \to \mathbb{N}$ has an inverse and therefore, it's a bijection between $A$ and $\mathbb{N}$, proving that they have the same cardinality.

Answer 3

Consider the map $$ f(j)=\begin{cases} (1,j)&\quad \text{if }\, j=3k+1\\ (2,j)&\quad \text{if }\, j=3k+2\\ (3,j)&\quad \text{if }\, j=3k\\ \end{cases} $$ (for some $k$) and prove that it is a bijection.

Answer 4

The techniques listed above are great, though I would encourage you to think about the problem starting from the simplest case. Namely, if you had all the values in ur set A, and just started counting in the simplest manner what would it look like?

It would be likely: (1,1) -> 1 , (1,2) -> 2 , (1,3) -> 3, (1,4)->4, ...

Unfortunately that set as you know goes on forever, so though that set is clearly countable, it is also infinite which leaves with an inability to ever start counting (2,1) and onward... So you run into the problem of how can I include the other values in my set that do not have the first coordinate equal to 1? Thats where an idea of “sweeping through” each of the 3 sets comes in handy. You avoid the problem of never finishing counting the first set, allowing you a chance to describe a bijection.