Newsgroups: sci.math
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 26 Aug 94 16:42:40 GMT
Subject: Re: Numbers of subsets of N closed under addition.

g...@arp.anu.edu.au (Greg Restall) asks:

> How many subsets of N are closed under addition?
> Of course there are at least countably many.  Each {n,n+1,n+2,...},
> is a candidate.  But are there uncountably many?...

No.  For let G be the GCD of such a set; G is realized as the GCD
of a finite subset, and the fundamental theorem of arithmetic shows
that the closure of that finite subset under addition includes all
sufficiently large multiples of G.  So every closed subset consists of
a finite set together with all the larger multiples of its GCD.  There
are only countably many finite subsets of N, so only countably many
closed sets, QED.

[Also e-mailed]

Dan Hoey
Hoey@AIC.NRL.Navy.Mil