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.