1

Let $A$ be countably infinite and $B = \{x,y\}$. How do I prove that $A×B=\{(a,b):a∈A,b∈B\}$ is countably infinite?

I understand that we must show that there is a one to one correspondence from A x B to $Z^+$

So the question becomes, is there a function $f:Z^+$ to (A x B) that is one to one and onto. This is the part I do not understand.

Bret Hisey
  • 223

1 Answers1

1

Since $A$ is countably infinite, there exists a bijection from $A$ to $\mathbb Z^+,$ which assigns a positive integer to every element of $A,$ so that $A$ can be written as $A = \{a_1, a_2, a_3, \dotsc\}.$ Now we have that $$ A \times B = \{(a_1,x), (a_2,x), \dotsc, (a_1,y), (a_2,y), \dotsc\} $$ and the bijection $f: A \times B \to \mathbb Z^+$ defined by $$ f(a_n,x) = 2n - 1 \quad f(a_n,y) = 2n $$ will be sufficient.

Lorenzo Riva
  • 389
  • Thank you for being so straight forward in your answering! – Bret Hisey Nov 27 '17 at 21:41
  • Where do you get the 2n-1 and 2n from. I understand everything up until that point. – Bret Hisey Nov 27 '17 at 21:44
  • You're welcome! We want a bijection, so we need to pair up every positive integer with an element of $A \times B.$ I just chose to associate the elements of the form $(a_n, y)$ with the even numbers ($2n$), and the elements of the form $(a_n, x)$ with the odd numbers ($2n -1,$ since I'm starting from $1$ and not from $0$). – Lorenzo Riva Nov 27 '17 at 23:23
  • I could have chosen any other bijection (say, $f : A \times B \to \mathbb Z$ where the elements with second term $x$ get associated to a negative integer and those with second term $y$ get associated to a non-negative integer); I chose even and odds because you wanted to "count" the elements using the positive integers, but a bijection onto $\mathbb Z$ works as well (why?). – Lorenzo Riva Nov 27 '17 at 23:24