# If $A$ and $B$ are countable sets, show that $A \times B$ is countable [duplicate]

My question is If $A$ and $B$ are countable sets, show that $A \times B$ is countable.

I know the definitions to be a countable set are:

1. A set $A$ is countable if $A$ is finite or countably infinite.
2. A set $A$ is countably infinite if $A \thicksim \mathbb{N}$ ( same cardinality)

I just want to be walked through this problem for studying reasons.

## marked as duplicate by Bungo, user228113, Hayden, Shailesh, Rob ArthanSep 10 '16 at 0:24

• In resumen, you must show that exists a bijection $f:\Bbb N\times\Bbb N\to\Bbb N$. – Masacroso Sep 9 '16 at 23:10
• ... and bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ and many others. – user228113 Sep 9 '16 at 23:19
• @WillO This does not require the Axiom of Choice (or any weaker version stronger than Axiom of Finite Choice). – Hayden Sep 9 '16 at 23:22
• @G.Sassatelli and Hayden: You are right. My bad. – WillO Sep 9 '16 at 23:23
• See Cantor proof on the carnality of the rational numbers. Same arguments can be applied. – Doug M Sep 9 '16 at 23:34

If $A$ and $B$ are countable, then they can be listed $A={a_1, a_2,\ldots}$ and $B={b_1,b_2,\ldots}$. Then the map $(a_k,b_n) \rightarrow 2^k3^n$ is an injection from $A\times B$ into $\mathbb{N}$.
If $A= \{a_1,a_2,... \}$ and $B= \{b_1,b_2,... \}$
Let $A_k=\{(a_n,b_k):n \in \Bbb N \}$ and $k=1,2,...$
I think it's clear that $A_k$ are equinumerous to $A$ for all $k=1,2,...$ and therefore countable
This way $A \times B= \bigcup_{k=1}^{\infty}A_k$ and we know that a countable union of countable sets is a countable set