Countability of Primes and CompositesDate: 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 |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/