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.

up vote 1 down vote accepted

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.

  • 1
    or you might just observe that $(i,j)\mapsto 2^i3^j$ is an injection. This idea extends easily to $\mathbb N^k$. For example, $(i,j,k)\mapsto 2^i3^j5^k$. – Matematleta Mar 7 '16 at 16:06
  • @Chilango Of course. Though I think that for a "first time user", the actual bijection is more informative than just the construction of an injection (which, I admit, implies a bijection, but also a theorem) – 5xum Mar 7 '16 at 16:32
  • 1
    these maps are not surjective, but that's no problem. An injection into a countable set is enough to say that the domain is countable. All you need is the fact that a subset of a countable set is countable. I agree though, that the pairing function is more interesting and has more applications. – Matematleta Mar 7 '16 at 16:50

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.