Suppose we have two countably infinite sets, which means we can find injection (one-to-one) relation to natural numbers.
In other words, we could literally assign natural number indexes to only one of each member of the set.
So, we have with cardinality , and with cardinality
Then cartersian product (set of all possible pairs from A and from B) – is also infinite, but countable. I mean, for , we can assign single natural number for each member of P.
Lets prove it. Suppose we injections f and g, so that and
Lets define function this way:
Then for and , because of unique division into primes and f,g injectivity (a,b)=(c,d).
Therefore there is injection from p(a,b) to natural numbers, and cartesian product is infinitely countable.