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?


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.