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: Set of all finite subsets of N (real analysis)

  1. Sep 12, 2010 #1
    1. The problem statement, all variables and given/known data

    Show that the set of all finite subsets of N is a countable set.

    3. The attempt at a solution

    At first I thought this was really easy. I had A = {B1, B2, B3, ... }, where Bn is some finite subset of N. Since any B is finite and therefore countable, and since a union of finite sets is countable, then the set of all finite subsets is countable. But I'm pretty sure this is false because its sort of assuming that the set A is countable.

    So I got to thinking that I could consider a1 to be the set of all finite one-element subsets of N. And then perhaps expand that idea to an+1 to be any of these such sets. From here though, I'm not sure how to prove that the set of all of these subsets is countable.

    Im thinking induction, and the basis step is a pretty obvious bijection with N. But I dont know where to go from here.
  2. jcsd
  3. Sep 13, 2010 #2
    Try thinking about how you should go about showing your bijection onto N. How would you make sure you didnt miss any elements?
  4. Sep 13, 2010 #3
    Are you familiar with the Cantor-Schroeder-Bernstein theorem? If so this isn’t so bad. Let’s call N'
    your set of all finite subsets of N.

    N->N'should be trivial

    Hint for N’->N. Consider the set Nb' the set of N' in binary format. So {1,3,5} -> {1,11, 101}. Clearly Nb' and N' are bijective.

    Is there an easy way to uniquely map every element of Nb' into N by using digits other than “0” and “1”
  5. Sep 13, 2010 #4
    Im trying it with induction.

    Let A be the set of all finite subsets of N

    Let an , n>=1 be a set of subsets of N each with cardinality of n.

    Claim: Any an is countable, so the union from n=0 to infinity of an is countable, and thus A would be countable. Prove by induction.

    basis: n=1, a1: N: 1 2 3...
    a1: {1}{2}{3}... and we have an obvious bijection.

    Inductive hypothesis: Assume an is countable. Show an+1 is countable.

    For any set S is an element of an+1, remove an arbitrary element K. The resulting sets are T and P such that T is an element of an, and K is an element of P is an element of a1.

    By inductive hypothesis, T is countable. By basis step we know a1 is countable. So the union of T and P is countable, so an+1 is countable. Therefore A is countable.

    Does this look right?
  6. Sep 13, 2010 #5
    this step doesn't follow:
    So the union of T and P is countable, so an+1 is countable. Therefore A is countable.

    The union of T and P is your S, not your an+1
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook