I am supposed to determine whether or not the set $A\times Z^{+}$ where $A=\{2, 3\}$ is countably infinite. If so, I should exhibit a one to one correspondence between the set of positive integers and the set in question.
Although I'm pretty sure that the set is countably infinite, I am struggling to find a one to one correspondence from the positive integers to the set since it seems to me that there are twice as many elements in the set $A\times Z^{+}$ than the set of positive integers since its cardinality is double due to the Cartesian product?
Best Answer
The bijection is rather obvious. E.g. for every positive integer $n$ you can define:
$F(2k-1) = (2, k)$ when $n = 2k-1$ (n is odd)
$F(2k) = (3, k)$ when $n = 2k$ (n is even)
Just prove that $F$ is a bijection (which is quite easy).
This bijection is basically a formal writing of this table:
$1 \to (2,1)$
$2 \to (3,1)$
$3 \to (2,2)$
$4 \to (3,2)$
$5 \to (2,3)$
$6 \to (3,3)$
$\dots$
"It seems to me that there are twice as many elements in the set $A\times Z^{+}$ than the set of positive integers since its cardinality is double due to the Cartesian product"
Well, the same intuition is probably there for the sets of positive integers and even positive integers. But there is a bijection between the two sets, hence their cardinalities are equal (one cardinality is not "twice" the other cardinality).
So whenever your intuition says that the number of elements of one set $C$ is 2 or 3 or 10 or $m$ times the number of elements of another set $B$, you should know that the two sets $B$ and $C$ are in fact of the same cardinality. It's somewhat counterintuitive at first sight but that's how it is.