# Isomorphisms and Cardinality

• Feb 28th 2011, 11:52 AM
Showcase_22
Isomorphisms and Cardinality
Quote:

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?
• Feb 28th 2011, 11:59 AM
Plato
Tell us what is $\displaystyle X$?
What does "isomorphism types of relations" mean?
What is $\displaystyle |X|^2=|X|~?$
• Feb 28th 2011, 12:34 PM
Showcase_22
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|$
• Feb 28th 2011, 01:10 PM
DrSteve
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..
• Feb 28th 2011, 02:01 PM
DrSteve
Quote:

Originally Posted by Showcase_22
$\displaystyle |X|=2^{|X|^2}$.

This is never true for any X.
• Feb 28th 2011, 02:36 PM
Plato
Quote:

Originally Posted by Showcase_22
$\displaystyle |X|=2^{|X|^2}$.

Quote:

Originally Posted by DrSteve
This is never true for any X.