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!

Family of subset of N is countable?

  1. Sep 14, 2008 #1
    1. The problem statement, all variables and given/known data
    I am trying to show that a family F {A[tex]\subseteq[/tex][tex]N[/tex]: A is finite} Show that F is countable.

    I found a proof in a book but I don't understand it. Could you help me please?


    2. Relevant equations



    3. The attempt at a solution

    If A is finite, then F is clearly also finite and the claim becomes trivially true. We therefore suppose that A is countable infinite.

    To prove that F is countable it would be sufficient to show that the family of all finite subsets of "Naturals" is countable. For each n an element of "Naturals", let Mn denote the family of all subsets N of "Naturals" satisfying N[tex]\subseteq[/tex] {1,2,...,n}.
    Mn is obviously finite.

    If M is the family of all finite subsets of "Naturals", we see that it can be expressed as M= the union of all Mn from n=1 to infinity. From the theorem that "union of countable sets is countable" we see though that M is countable and hence see that the family F is also countable.

    ---
    My first question is as follows. In the beginning, how do they know that if A is finite, then F is clearly also finite?
     
  2. jcsd
  3. Sep 14, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If A is finite and the number of elements in A is n. Then the number of subsets of A is 2^n. You can prove this be induction. But it's pretty obvious if you think about how to choose a subset. For each element a of A you can either have a in the subset or a not in the subset.
     
  4. Sep 14, 2008 #3
    Thanks Dick,

    but why, if the problem states that A is finite, must they prove the case in which A is countable infinite?
     
  5. Sep 14, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The problem doesn't state A is finite. It wants you to prove that the infinite set N has a countable number of finite subsets. 'A' is just a dummy variable in the set notation. In the proof M_n are the sets that are finite.
     
  6. Sep 14, 2008 #5
    Thanks again Dick,

    Why is it that F is stated as the family of all subsets A, but the proof uses M? Could they have used F without loss?
     
  7. Sep 14, 2008 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't know why they switched from F to M in the proof. They are both the set of all finite subsets of N.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Family of subset of N is countable?
Loading...