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