LudovicoVan
Posts:
3,598
From:
London
Registered:
2/8/08


Re: Can we count N ?!
Posted:
Jun 9, 2013 5:28 AM


"Julio Di Egidio" <julio@diegidio.name> wrote in message news:kovcsm$g74$1@dontemail.me...
> It seems easy enough to count the subsets of N, i.e. P(N), by traversing > the complete binary tree breathfirst and a mapping between nodes and > subsets of N. Something like (details omitted): > > "" > "*" > "0*", "1*" > "00*", "01*", "10*", "11*" > "000*", "001*", "010*", "011*", "100*", "101*", "110*", "111*" > ... > > "" > "1" > "01", "11" > "001", "011", "101", "111" > "0001", "0011", "0101", "0111", "1001", "1011", "1101", "1111" > ... > > {} > {0} > {1}, {0,1} > {2}, {1,2}, {0,2}, {0,1,2} > {3}, {2,3}, {1,3}, {1,2,3}, {0,3}, {0,2,3}, {0,1,3}, {0,1,2,3} > ... > > Now, the immediate objection to any such attempts is that: infinite > subsets are not captured. > > To which we reply, informally (as we cannot be more formal than the > objection is!), that, despite we cannot but write down few entries of any > infinite sequence, the sequence itself cannot be more "incomplete" than > N={0,1,2,3,...} itself is, i.e. that infinite subsets are surely captured > as long as N itself is fully captured. Namely, the objection is > illogical, as an attempt at its formalisation would possibly show.
Illogical within the potentially infinite setting:
We can capture N = {0,1,2,3...} (indeed, what would such notation otherwise mean?) by a most simple sequence of finite sets:
{0} {0,1} {0,1,2} {0,1,2,3} ...
By "capturing" we mean that every initial segment of N is produced.
By the same token, the set of even numbers is captured by the sequence of subsets of N shown initially, because the following is a subsequence of it (i.e. these entries get produced):
{0} {0,2} {0,2,4} {0,2,4,6} ...
By the same token, the sequence of subsets of N shown initially captures *all* subsets of N, finite and (potentially) infinite.
Bottom line, within the potentially infinite, P(N) is countable.
Julio

