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

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

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

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

Quote:

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