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

  • Thread starter s3a
  • Start date
  • #1
s3a
800
8

Homework Statement


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.

Homework Equations


Set-theoretic algebra.

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!
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
619

Homework Statement


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.

Homework Equations


Set-theoretic algebra.

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!
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
s3a
800
8
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).
 

Attachments

  • #4
Dick
Science Advisor
Homework Helper
26,258
619
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).
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
s3a
800
8
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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,797
5,579
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##?"

?
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.
 

Related Threads on Let [ ] be a countable number of finite sets. Prove [ ]

Replies
3
Views
2K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
6
Views
2K
Replies
3
Views
7K
Replies
30
Views
3K
  • Last Post
Replies
2
Views
17K
Top