Is the Cartesian product of two countably infinite sets also countably infinite?

Question

I am trying to determine and prove whether the set of convergent sequences of prime numbers is countably or uncountably infinite.

It is clear that such a sequence must 'terminate' with an infinite repetition of some prime $p$. So for example $${1,2,3,5,5,5,5,...}$$

My idea is to break up the problem into two sub-sequences. The first is a finite subsequence consisting of the first however many terms before it begins the infinite repetition of $p$. Then the second being the infinite set with elements being only $p$.

So in the above example, the two sub-sequences will be $$\{1,2,3\} \{5,5,5,...\}$$

The infinite sub-sequence is countably infinite as it's cardinality is simply the cardinality of the primes, which is countably infinite.

There are infinitely many finite sub-sequences as it can have any number of terms. However, I think it will be countably infinite because it can have $1$ term, $2$ terms, $3$ terms etc, in other words we can construct the bijection to $\mathbb{N}$ by simply naming them according to the number of terms it has. The arrangements is irrelevant as it will be finite.

This is where the title of the question comes in. There are a countably infinite number of these finite sub-sequences say $F$. We also have a countably infinite number of the infinite subsequence $P$, with all elements being some prime $p$.

So in some sense, the set of all convergent sequences of primes is the cartesian product $F\times P$.

As they are both countably infinite, will their cartesian product also be countably infinite? I am thinking yes, as the rationals are countably infinite and they are in some sense a cartesian product of the numerator and denominator, each having cardinality equivalent to the naturals.

If so, and everything is correct, I think I will have then completed the proof. Otherwise, I'd love to have errors pointed out or even perhaps a better solution.

Answer 1

Your thinking is correct. In fact, what you have argued is that there exists a bijection between the set of all convergent sequences of primes and the set $F\times P$. If this is your first example of doing this kind of task I suggest you try to actually write down this bijection. You have argued quite well that it must exist, but it's good exercise to actually do it at least once.

Noy, you also rightly say that $F\times P$ has a bijection to $\mathbb N^2$. As before, I suggest you actually write down this bijection.

Now, you simply need to see if $\mathbb N^2$ is countable, that is:

Does there exist a bijection between $\mathbb N$ and $\mathbb N^2$

To that end, I suggest you look into Cantor's pairing function.