2

Is $A\times B$ referring to the axis here? So an $X$ and $Y$ coordinate plane?

$A$ is countable, therefore a bijection occurs from $A \rightarrow \mathbb{N}$.

$B$ is countable, therefore a bijection occurs from $B \rightarrow \mathbb{N}$.

If these statements hold true then any elements belonging to the sets can be linked and ordered one-by-one from any natural number, thus any coordinate $(a,b)$ would be countable as the elements it represents ($x$ and $y $ coordinates) are countable. Together they preserve their nature of cardinality.

Am I wrong?

vasmous
  • 797
Eddard
  • 65

4 Answers4

4

Let $f:A \to \mathbb{N}$ be a bijection from $A$ to $\mathbb{N}$

Let $g:B \to \mathbb{N}$ be a bijection from $B$ to $\mathbb{N}$

Define $h:A \times B \to \mathbb{N}$ as follows:

$h(x,y)=2^{f(x)}\cdot3^{g(y)}$

barak manos
  • 43,109
  • You can use any pair of distinct prime numbers ($2$ and $3$ are used in this example). In fact, you can use any pair of relatively prime numbers (such that their $\gcd$ is $1$). – barak manos Aug 15 '15 at 08:02
3

Another possibility is along the following lines.

Given enumerations $$ a_1, a_2, a_3, a_4, \ldots $$ and $$ b_1, b_2, b_3, b_4, \ldots $$ of the sets $A$ and $B$ respectively, you can enumerate the set $A\times B$ of pairs as follows $$ (a_1,b_1),(a_2,b_1),(a_1,b_2),(a_3,b_1),(a_2,b_2),(a_1,b_3),(a_4,b_1),(a_3,b_2),(a_2,b_3),(a_1,b_4),... $$ (the pattern should be clear).

AdLibitum
  • 3,003
1

Let $f:\mathbb{N} \to A, g:\mathbb{N} \to B$ be the two bijections, and define $h: \mathbb{N}\times \mathbb{N} \to A\times B$ as $h(m,n) = (f(m),g(n))$. You can show easily that $h$ is bijective. Now you need to show there is bijection from $\mathbb{N}$ to $\mathbb{N}\times \mathbb{N}$. We define $k: \mathbb{N}\times \mathbb{N} \to \mathbb{N}$ as $k(m,n) = (2m-1)\cdot 2^{n-1}$. Check that $k$ is bijective, thus $k^{-1}$ is also bijective.Thus the function $l = h\circ k^{-1}$ is a bijection from $\mathbb{N}$ to $A\times B$, hence $A\times B$ is countable.

DeepSea
  • 77,651
0

Enumeration:

$(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)\dots$

If you are working on sets $A=\{a_0,a_1,\dots\}$ and $B=\{b_0,b_1,\dots\}$ then interpret $(n,m)$ as $(a_n,a_m)$.

drhab
  • 151,093