Results 1 to 6 of 6

Math Help - Isomorphisms and Cardinality

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Isomorphisms and Cardinality

    Show that the set of all isomorphism types of relations on X has cardinality less than 2^{2^{|X|^2}}.
    I have no idea what to do here.

    From the previous question, I know that if B(X) denotes all the bijections X \rightarrow X, then |X| \leq |B(X)| \leq |X|^{|X|}.

    I also know that if |X|^2=|X|>1 then |B(X)|=2^{|X|}.

    I'm not sure if the previous question applies to this one. If it does, then I think I need to show that |X|=2^{|X|^2}. Unfortunately, this doesn't satisfy the |X|^2=|X| condition. I also can't see why this would be the case.

    Does anyone see how to do this question?
    Last edited by Showcase_22; February 28th 2011 at 01:21 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1781
    Awards
    1
    Tell us what is X?
    What does "isomorphism types of relations" mean?
    What is |X|^2=|X|~?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    My understanding is that X is any set closed under some binary relation.

    I think "isomorphism types of relations" means any binary relation that X is closed under.

    |X|^2=|X| means that |X|^2=|X|.|X|=|X \times X|=|X|
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Well a relation on X is a subset of X\times X, thus an element of \mathcal {P}(X\times X). So the set of all such relations is a subset of \mathcal{P}(\mathcal{P}(X\times X)) which has the stated size..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Quote Originally Posted by Showcase_22 View Post
    |X|=2^{|X|^2}.
    This is never true for any X.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1781
    Awards
    1
    Quote Originally Posted by Showcase_22 View Post
    |X|=2^{|X|^2}.
    Quote Originally Posted by DrSteve View Post
    This is never true for any X.
    You can see why I asked about the notations.
    I think that this question is hopeless confused.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Isomorphisms
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: July 11th 2011, 11:56 PM
  2. Isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 28th 2010, 10:03 PM
  3. isomorphisms......
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 27th 2010, 11:11 PM
  4. Z2 + Z2 + Z3 isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 2nd 2008, 07:34 PM
  5. isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 30th 2008, 07:20 PM

Search Tags


/mathhelpforum @mathhelpforum