1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 12, 2015 #1

    s3a

    User Avatar

    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. jcsd
  3. Apr 12, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Apr 12, 2015 #3

    s3a

    User Avatar

    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:

  5. Apr 13, 2015 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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##.
     
  6. Apr 15, 2015 #5

    s3a

    User Avatar

    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##?"

    ?
     
  7. Apr 15, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Let [ ] be a countable number of finite sets. Prove [ ]
  1. Prove set is countable (Replies: 2)

Loading...