Results 1 to 5 of 5

Math Help - equivalence classes of P(N)

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    3

    equivalence classes of P(N)

    hi,

    I apologize in advance for my phrasing, I'm translating this from another language.

    let R be a relation under P(N) where ∀A,B ∈P(N), (A,B)∈R if and only if |A|=|B|.

    R is an equivalence relation, therefore it splits P(N) to equivalence classes.

    The question is what's the cardinality of the equivalence class that N is a member of. I have a feeling it's c (|R|), but I don't know how to show it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2010
    Posts
    3
    I thought of looking at P(N) as a union of all finite subsets and all countably infinite subsets, the latter are in N's equivalence classes. For each countably infinite set, every number of N is either a member of it or not (2 options). Since there are aleph-null natural numbers, the number of possibilities is 2^(aleph-null)=c.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by afterdarkk View Post
    let R be a relation under P(N) where ∀A,B ∈P(N), (A,B)∈R if and only if |A|=|B|.
    R is an equivalence relation, therefore it splits P(N) to equivalence classes.
    The question is what's the cardinality of the equivalence class that N is a member of.
    You do know that \left| N \right| < \left| {\mathcal{P}(N)} \right|
    If A is the set of all finite subsets of N then |\mathcal{A}|=|N|.
    Now note that if X\in \mathcal{P}(N) \setminus\mathcal{A} then X is in the same equivalence class as N.
    So what do you conclude?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2010
    Posts
    3
    Quote Originally Posted by Plato View Post
    You do know that \left| N \right| < \left| {\mathcal{P}(N)} \right|
    If A is the set of all finite subsets of N then |\mathcal{A}|=|N|.
    Now note that if X\in \mathcal{P}(N) \setminus\mathcal{A} then X is in the same equivalence class as N.
    So what do you conclude?
    if A is the set of all finite subsets of N and A is countable, it's easy to show that |P(N)-A|=c. But I'm having a hard time showing that A is countable (even with the help of the thread you linked).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by afterdarkk View Post
    if A is the set of all finite subsets of N and A is countable, it's easy to show that |P(N)-A|=c. But I'm having a hard time showing that A is countable (even with the help of the thread you linked).
    In that link, in the response I posted, I showed an injection from \mathcal{A} \mapsto \mathbb{Z}^+.
    That shows that it is countable.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence classes
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: January 21st 2010, 12:48 AM
  2. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  4. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM
  5. Equivalence classes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 31st 2008, 12:04 AM

Search Tags


/mathhelpforum @mathhelpforum