Any uses for non-surjective relations (not just non-surjective functions)?

Question

A function $f \colon X \to Y$ is called surjective if, for every element $y \in Y$, there is an element $x \in X$ such that $f(x) = y$. There can be 1 such element in $X$, or 2, or a hundred - but you'll never find an element in Y you can't "get to" by following the path $f$ lays out from $X$ to $Y$.

I see why surjectivity is a useful property. Among other things, you can use it to prove statements about the cardinality of sets: If I recall correctly, if $f$ is surjective, then $ | X | \geq | Y |$.

Is there any use in a "non-surjective relation" $R \in \mathcal{P}(X \times Y)$?

You can't use it to prove the same inequality, because elements of $X$ can of course map to more than one element in $Y$. At the same time, there could be elements of $Y$ that have no corresponding elements in $X$ that allow them to show up in the relation at all.

So have you ever come across it being used where non-surjectivity was important?

Answer 1

There are lots of examples of non-surjective relations, by which I mean a relation $R$ on a set $X$ which negates the expression $\forall y \in X,\ \exists x \in X,\ x\;R\;y$. Here are a few:

• The relation $<$ on $\mathbb{N}$;
• ...more generally, the relation $<$ on any ordered set with a minimal element;
• ...or any well-founded relation on any non-empty set;
• The successor relation on $\mathbb{N}$, i.e. the relation $S$ defined by $x\;S\;y$ iff $x+1=y$;
• The empty relation on any non-empty set;
• The graph of a non-surjective endofunction (such as the function $x \mapsto x^2$ on $\mathbb{R}$);

The lack of surjectivity of some of these relations is very important. In fact, the definition of what it means for a relation $R$ on a set $X$ to be well-founded is precisely that the restriction of $R$ to every non-empty subset of $X$ is non-surjective. And well-foundedness is an extremely important concept!