*This is a compendium of proofs for some mathematical statements that are used several times on this blog. They are listed by topic below. Scroll down to find a desired proof.*

A disjoint countable union of countable sets is countable.

**Proof**: Let

*A*= {

*S*

_{1},

*S*

_{2},

*S*

_{3},...} be a countable collection of countable sets. In other words, each

*S*

_{i}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

*n*th member of the

*m*th set be denoted

*m*_{n}. We can construct the following bijection between the

*m*_{n}and the natural numbers:

1→

**1**

_{1}, 2→

**1**

_{2}, 3→

**2**

_{1}, 4→

**1**

_{3}, 5→

**2**

_{2}, 6→

**3**

_{1}, 7→

**1**

_{4}, 8→

**2**

_{3}, 9→

**3**

_{2}, 10→

**4**

_{1},...

In general, the member

*m*_{n}is indexed by the following formula the following formula:

((

*m*+

*n*)(

*m*+

*n*- 1))/2 - (

*n*- 1)→

*n*_{m}

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,

**1**

_{1}, 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

**2**

_{1}. 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

*n*

_{1}, one must increase the value by

*n*

_{1}- 1, since

*n*

_{1}- 1 + 1 =

*n*

_{1}. Thus,

*n*_{m}

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,

**3**

_{2}is indexed by ((4)(5))/2 - 2 + 1 = 9, as before.

## No comments:

Post a Comment