Interpretation of a Question

Printable View

February 19th 2010, 06:45 AM
jackprestonuk

Interpretation of a Question

Hi, this seems to me like a bit of a silly question, but I've had a problem in set theory given to me, and I'm having trouble working out exactly what it wants - the question word for word is;

Show that the set of all isomorphism classes of relations on $X$ has cardinality less than $2^{2^{{|X|}^2}}$ .

Am I right in taking these isomorphism classes as the sets containing relations $\leq$ and ${\leq}^{\prime}$ such that $(X,\leq)$ is isomorphic to $(X,{\leq}^{\prime})$ , or is there some way that relations can themselves be isomorphic, and the isomorphism classes are actually just of isomorphic relations?

I hope the question is clear here!
February 19th 2010, 02:48 PM
wgunther

You have the right idea; an isomorphism classes partition the set of all relations on X, where two things are in an isomorphism class iff they're isomorphic.

What does it mean for two relations to be isomorphic? There's a natural model-theoretic definition of an isomorphism. If you have a language $L=\langle R\rangle$ where $R$ is a binary relation (the upper bound you gave gives me the impression we're only interested in binary relations. Doesn't really matter in ZFC though, as there are just as many binary relations as n-ary relations).

Two L-structures M,N are isomorphic iff there is a function $f:M\to N$ bijective such that $\forall a,b\in \text{dom}(M)\text{\huge .}(a,b)\in R^M \iff (f(a),f(b))\in R^N$ , where $R^M$ is the interpretation of the relation R in the model M.

Sorry I was long winded. I'm not sure if you were asking for the formal definition of isomorphism, so I thought I'd be safe and state it.
February 21st 2010, 10:28 AM
jackprestonuk

Haha, long winded is what I'd like in this kind of situation! Thanks very much for your help, this clears it up!