Results 1 to 2 of 2

Math Help - Transfinite Cardinal Numbers..plz help...

  1. #1
    Member
    Joined
    Mar 2006
    Posts
    82

    Transfinite Cardinal Numbers..plz help...

    Hi! I am studying for my finals and I need some help. Thank you so much in advance.

    1) Prove that the set F(S) of finite subsets of a countable set S is countable, and it is (countably) infinite if and only if S is (countably) infinite.


    2) Suppose that E is an equivalence relation on a countably infinite set S, and let S/E be the associated family of eqivalence classes. Explain why S/E is countable.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2005
    Posts
    39
    1) I don't know if this the standard proof, but I think it works. WLOG we can take our countably infinite set to be the natural numbers. Now, define a function f:F(N) --> [0,1) as follows: for an element S of F(N), declare the mth binary digit of the real number f(S) to be 1 if m is a member of S, 0 otherwise. For example,

    f({1,2,4,6}) = .01101010000000.....

    where we have a 1 in the 1st, 2nd, 4th and 6th decimal place, 0's elsewhere (we count the place just after the decimal as the "0th" place). Notice first that this is an injective function (no two distinct finite subsets can define the same real number). And secondly, every finite subset maps to a rational number, since we always end with a tail of zeroes. Thus we have an injective function from F(N) to the rationals in [0,1), and the latter set is countable.

    2) The projection map x --> [x] mapping every element of S to its own equivalence class is an onto mapping. Thus S/E is no bigger than S itself.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. cardinal numbers
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 6th 2010, 08:45 PM
  2. Cardinal numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 16th 2010, 01:25 PM
  3. Distributivity of Cardinal Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2009, 05:29 AM
  4. Cardinal Numbers
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 24th 2009, 05:39 AM
  5. Cardinal numbers proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 22nd 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum