# Let [ ] be a countable number of finite sets. Prove [ ]

1. Apr 12, 2015

### s3a

1. The problem statement, all variables and given/known data
Problem:
Let A_1 , A_2 , . . . be a countable number of finite sets. Prove that the union S = ⋃_i A_i is countable.

Solution:
Included in the TheProblemAndSolution.jpg file.

2. Relevant equations
Set-theoretic algebra.

3. The attempt at a solution
Unless I missed something, it seems that I understand everything about that solution except why the author chose to use $f(b_{ij}) = m_1 + m_2 + . . . + m_{i - 1} + j$.

Could someone please explain to me why that specific function was constructed? I get that the author is trying to show that there is a one-to-one correspondence between the set S and the set of natural numbers, but I don't understand that particular sum was chosen. What's the logic behind the decision?

Any input would be GREATLY appreciated!

2. Apr 12, 2015

### Dick

You didn't link you jpg correctly. So I can't see it. But it appears the author is just writing a function that counts total number of elements in the finite union of all of the sets before the i'th set and then includes j elements of the i'th set.

3. Apr 12, 2015

### s3a

Oops!

Here is the image I meant to attach (just in case you misinterpreted the situation, which I don't think you did, but just in case).

Is $f(b_{ij}) = m_1 + m_2 + . . . + m_{i - 1} + m_i$ equivalent to $f(b_{ij}) = m_1 + m_2 + . . . + m_{i - 1} + j$? I don't know if it's because it's late as I write this, but I still don't see why the authors chose the specific letters they did.

Also you said "finite union", was that a mistake? I say this, because there can be a countably infinite amount of sets (where each set has a finite number of elements).

#### Attached Files:

• ###### TheProblemAndSolution.jpg
File size:
31.9 KB
Views:
79
4. Apr 13, 2015

### Dick

The author is just counting the elements in $S$ to get a 1-1 correspondence with the natural numbers. If there are three elements in $B_1$ then assign them to 1,2,3. Then if there are four elements in $B_2$ assign them to 4,5,6,7. Etc, etc. That formula just expresses that way of counting. So, for example, for the second element of $B_2$, $b_{22}=3+2=5$.

5. Apr 15, 2015

### s3a

So, would that be a yes to the question

"Is $f(b_{ij}) = m_1 + m_2 + . . . + m_{i - 1} + m_i$ equivalent to $f(b_{ij}) = m_1 + m_2 + . . . + m_{i - 1} + j$?"

?

6. Apr 15, 2015

### haruspex

No. Each member of {bij} must be mapped to a different number. Suppose you have mapped B1 to the first m1, numbers (1 to m1), B2 to the next m2 numbers (m1+1 to m1+m2) and so forth up to Bi-1. We are now in the process of mapping Bi. The first of Bi is mapped to $m_1 + m_2 + . . . + m_{i - 1} +1$, the second to $m_1 + m_2 + . . . + m_{i - 1} + 2$, etc.