Isomorphisms and Cardinality

Printable View

February 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?
February 28th 2011, 11:59 AM
Plato

Tell us what is $X$ ?
What does "isomorphism types of relations" mean?
What is $|X|^2=|X|~?$
February 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|$
February 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..
February 28th 2011, 02:01 PM
DrSteve

Quote:

Originally Posted by Showcase_22

$|X|=2^{|X|^2}$ .

This is never true for any X.
February 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.

You can see why I asked about the notations.
I think that this question is hopeless confused.