In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.

The relative rank $\rank(S:A)$ of a subset $A$ of a semigroup $S$ is the minimum cardinality of a set $B$ such that $\langle A\cup B\rangle=S$. It follows from a result of Sierpiński that, if $X$ is infinite, the relative rank of a subset of the full transformation semigroup $\mathcal{T}_{X}$ is either uncountable or at most $2$. A similar result holds for the semigroup $\mathcal{B}_{X}$ of binary relations on $X$.

A subset $S$ of $\mathcal{T}_{\mathbb{N}}$ is dominated (by $U$) if there exists a countable subset $U$ of $\mathcal{T}_{\mathbb{N}}$ with the property that for each $\sigma$ in $S$ there exists $\mu$ in $U$ such that $i\sigma\le i\mu$ for all $i$ in $\mathbb{N}$. It is shown that every dominated subset of $\mathcal{T}_{\mathbb{N}}$ is of uncountable relative rank. As a consequence, the monoid of all contractions in $\mathcal{T}_{\mathbb{N}}$ (mappings $\alpha$ with the property that $|i\alpha-j\alpha|\le|i-j|$ for all $i$ and $j$) is of uncountable relative rank.

It is shown (among other results) that $\rank(\mathcal{B}_{X}:\mathcal{T}_{X})=1$ and that $\rank(\mathcal{B}_{X}:\mathcal{I}_{X})=1$ (where $\mathcal{I}_{X}$ is the symmetric inverse semigroup on $X$). By contrast, if $\mathcal{S}_{X}$ is the symmetric group, $\rank(\mathcal{B}_{X}:\mathcal{S}_{X})=2$.

AMS 2000 Mathematics subject classification: Primary 20M20