A disjoint countable union of countable sets is countable.
Proof: Let A = {S1,S2,S3,...} be a countable collection of countable sets. In other words, each Si is countable and there is one for each natural number 1,2,3,.... Introduce the following notation, which gives an "address" for every member of a set in the collection. Since the members of the collection and the members of each member can be put into one-to-one correspondence with the natural numbers, we can index them with natural numbers. Let the nth member of the mth set be denoted mn. We can construct the following bijection between the mn and the natural numbers:
1→ 11, 2→ 12, 3→ 21, 4→ 13, 5→ 22, 6→ 31, 7→ 14, 8→ 23, 9→ 32, 10→ 41,...
In general, the member mn is indexed by the following formula the following formula:
((m + n)(m + n - 1))/2 - (n - 1)→ nm
To see how this formula works, note that the above sequence can be partitioned into groups by the sum of m and n. The first member, 11, has m + n = 2. The next two have m + n = 3, the following three m + n = 4, and so on. The first element has m + n ≤ 2, the first 1 + 2 = 3 elements have m + n ≤ 4, and, generally, the first 1 + 2 + 3 + ... + k - 1 elements have m + n < k. The last sum is equal, by a familiar formula, to ((k - 1)(k))/2. In particular, the ((k - 1)(k))/2)-th element is the last one in the sequence for the sum m + n = k. For example, the ((3 - 1)(3))/2 = 3rd element is the last for which m + n = 3, namely 21. Clearly this is the element for which n = 1. Moving backward in the sequence one element increases the value of n by one. To get the value of n to any particular value n1, one must increase the value by n1 - 1, since n1 - 1 + 1 = n1. Thus, nm
is given index ((k - 1)(k))/2 - (n - 1) and since k = m + n, the above formula results.
Q.E.D.
Example: By the formula, 32 is indexed by ((4)(5))/2 - 2 + 1 = 9, as before.
No comments:
Post a Comment