Associated Topics || Dr. Math Home || Search Dr. Math

### Countability of Primes and Composites

```Date: 05/18/2002 at 11:25:37
From: Robin
Subject: Countability of Primes and Composites

I know that the union of a countable number of countable sets is
countable, but I was wondering if you take a countable set that is
the union of two infinite sets, is it possible that one of these sets
that makes up the original countable set is not countable?

For example, consider primes (p), composites (c), and positive
integers (n):

p U c = n

So does this mean that the primes and the composites are each
countable sets because together they create the counting numbers?
```

```
Date: 05/18/2002 at 12:38:03
From: Doctor Mitteldorf
Subject: Re: Countability of Primes and Composites

Yes, any subset of a countable set is countable.  In particular, the
primes and the composites are countable sets.  If you write a computer
program that could, in principle, go on generating all the prime
numbers one after another, that is a sufficient demonstration that the
prime numbers are countable.

- Doctor Mitteldorf, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/18/2002 at 12:44:29
From: Doctor Paul
Subject: Re: Countability of Primes and Composites

Well, we know that the natural numbers (another name for the positive
integers) are countable.  So any subset of the natural numbers will
have cardinality less than or equal to the that of the natural
numbers and hence will be countable as well.  Thus the set of primes
and the set of composite numbers are both countable (since they are
both subsets of the natural numbers).

It is not possible to take the union of an uncountable set A and any
set B (either finite, inifinite countable or infinite uncountable)
and produce a countable set.  The operation of taking unions can only
add to the number of elements in a set.  Thus if we start with a set
that has uncountably many elements (this is the set A), A U B will
always contain everything in A with the possibility of adding more
elements (specifically, the elements in B which are not in A).  Thus
A U B will contain uncountably many elements as well since it
contains at least as many elements as are in the uncountable set A.

Make sense?

I hope this helps.  Please write back if you'd like to talk about
this some more.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/19/2002 at 13:37:51
From: Robin
Subject: Countability of Primes and Composites

I just wanted to say thanks for all your help. Some of my
mathematical misconceptions have been cleared up :)

Robin
```
Associated Topics:
College Logic
High School Logic
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search