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: The antichain of a set

  1. Jul 11, 2010 #1
    1. The problem statement, all variables and given/known data

    P(B) refers to the collection of all subsets of B.
    Given a set B, a subset A of P(B) is called an antichain if no element of A is a subset of any other element of A. Does P(N) contain an uncountable antichain?

    2. Relevant equations

    3. The attempt at a solution

    If I can build a bijective map between an antichain of P(N) and another set of known cardinality, then I will be able to know if the antichain is uncountable. Sets I know that are uncountable: R, sequences of 0's and 1's. Is it one of these two?

    Sorry I'm not able to do much with this problem. Any help is appreciated.
  2. jcsd
  3. Jul 12, 2010 #2
    hmm...you've got me interested! but I can't put together a full proof at the moment, maybe in the morning after some sleep haha. If it's of any help, here's one more uncountable set to add to your list: P(N). If this is new to you, read through an explanation of Cantor's Theorem.
  4. Jul 12, 2010 #3


    User Avatar
    Science Advisor
    Homework Helper

    Hint: divide N into pairs, {1,2}, {3,4}, {5,6}... Now form sets by choosing exactly one element of each pair. What properties does the resulting collection of sets have?
  5. Jul 13, 2010 #4
    I think I kinda got it. So this has to do with the cardinality of P(N) right? Because P(N) is uncountable and we could build an antichain of the same cardinality, so the antichain is also uncountable.
    Thank you both!
  6. Jul 13, 2010 #5
    Oh sorry I think I got it wrong. I still need to use Cantor's diagonal Thm.

  7. Jul 13, 2010 #6


    User Avatar
    Science Advisor
    Homework Helper

    Yes. You need to show i) the resulting sets are an antichain and ii) the cardinality of the antichain is the same as P(N).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook