Results 1 to 6 of 6

Thread: 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 $\displaystyle X$ has cardinality less than $\displaystyle 2^{2^{|X|^2}}$.
    I have no idea what to do here.

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

    I also know that if $\displaystyle |X|^2=|X|>1$ then $\displaystyle |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 $\displaystyle |X|=2^{|X|^2}$. Unfortunately, this doesn't satisfy the $\displaystyle |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; Feb 28th 2011 at 12:21 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Tell us what is $\displaystyle X$?
    What does "isomorphism types of relations" mean?
    What is $\displaystyle |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 $\displaystyle X$ is any set closed under some binary relation.

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

    $\displaystyle |X|^2=|X|$ means that $\displaystyle |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 $\displaystyle X$ is a subset of $\displaystyle X\times X$, thus an element of $\displaystyle \mathcal {P}(X\times X)$. So the set of all such relations is a subset of $\displaystyle \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
    $\displaystyle |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
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by Showcase_22 View Post
    $\displaystyle |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: Jul 11th 2011, 10:56 PM
  2. Isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 28th 2010, 09:03 PM
  3. isomorphisms......
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 27th 2010, 10:11 PM
  4. Z2 + Z2 + Z3 isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Dec 2nd 2008, 06:34 PM
  5. isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Oct 30th 2008, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum