Can a binary relation on a set $S$ isomorphically embed every binary relation on $S$?

Question

Is there any binary relation $R$ on a non-empty set $S$ such that $R$ isomorphically embeds every binary relation on $S$?

(By "$R$ isomorphically embeds $Q$" I mean: there is a one-to-one function $\phi : S \to S$ such that for every $x, y \in S$, $Q(x, y)$ iff $R(\phi(x), \phi(y))$. In other words, some restriction of $R$ to a subset is isomorphic to $Q$.)

It seems like a Cantorian argument should rule this out, but I haven't figured it out yet.

Answer 1

Asaf shows that no such universal relation $R$ can exist on a finite nonempty set. But there is a binary relation $R$ on a countably infinite set $S$ which isomorphically embeds every other binary relation on a countable (finite or infinite) set, namely the Fraïssé limit of the class of finite sets equipped with a binary relation.

More generally, given a language $L$ consisting of relation and function symbols (but no constant symbols!), the class of finitely generated $L$-structures (sets with interpretations of the symbols) is a Fraïssé class (meaning it has the hereditary, joint embedding, and amalgamation properties). Note that finitely generated is the same as finite if $L$ has no function symbols. The Fraïssé limit construction gives rise to a countably infinite ultrahomogeneous structure $M$ (ultrahomogeneous means any isomorphism between finitely generated substructrues of $M$ extends to an automorphism of $M$) such that every finitely generated $L$-structure embeds into $M$.

Now to see that every countable $L$-structure $A$ embeds into $M$, write $A$ as the union of a countable increasing chain of finitely generated substructures, $A = \bigcup_{i\in\omega}A_i$. Embed each of these into $M$, by $f_i:A_i\to M$, using ultrahomogeneity to ensure that $f_i \subseteq f_j$ when $i\leq j$. Then the union of the embeddings is an embedding $A\to M$.

Answer 2

The answer in general is no.

Note that for non-empty finite sets, $R$ isomorphically embeds $Q$ if and only if they are isomorphic (since $\phi$ has to be a bijection). So just pick two non-isomorphic relations (e.g. the empty set and the identity relation) and there is no relation which is isomorphic to both at the same time.