Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook