1
$\begingroup$

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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}$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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