Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We can define a binary relation as a set of ordered pairs. Alternatively, we can call the set of ordered pairs the "graph" of the relation, and define the relation itself as a triple $(X,Y,f)$, where $f$ is the graph, $X$ is its domain and $Y$ is its codomain. The same goes for functions; they can be defined as sets of ordered pairs, or as triples. So my question is, given that its more lightweight to define a binary relation simply as its graph, why is the ordered-triple approach much more common?

Here's a list of reasons and possible objections that I've come up with.

Reason 0: The ordered-triple approach allows us to distinguish between surjections and non-surjections. Possible Objection: This could be read another way, as suggesting that surjectivity is a contrived concept. Maybe we should only every say "$f \in \mathrm{Surj}(X,Y)$" but never simply say "$f$ is a surjection."

Reason 1: Category theory works that way. Possible Objection: Perhaps this is a "hint" that maybe there's room for improvement in the basic definitions of category theory.

Reason 2: The ordered triple approach allows us to define the complement of a relation by $f^c = X \times Y \setminus f$. Thus, the set of all relations with domain $X$ and codomain $Y$ form a Boolean algebra. Possible Objection: This is a pretty minor advantage, given that we can just write "Defining $A^c = X\times Y \setminus A$, it follows that..." whenever we need to.

So my question is, what's the payoff of the ordered triple approach?

share|cite|improve this question
Apparently, people weigh the three pro-reasons more than your three objections. I follow especially the category argument, as in other categories than Set you either have no "elements" of objects at all or have a great problem to speak of all morphisms from $A$ to $B$ as you must then speak of all homomorphisms from $A$ to some $C$ where $C$ happens to be a subobject (what is that?) of $B$. Then again, you are right esp. in set theory, where one merely uses predicates $\Phi(x,y)$ with $\Phi(x,y_1)\land \Phi(x,y_2)\to y_1=y_2$, as e.g. transfinite recursion might be difficult otherwise. – Hagen von Eitzen Nov 22 '12 at 7:17
Good question! My undoubtedly unpopular opinion is that formal definitions usually don't matter very much, as long as we agree on what objects we are really talking about. By that criterion, a reasonably precise definition of continuous function is useful, since the nicely behaved functions of one's untutored geometric imagination are very much not "typical" continuous functions. – André Nicolas Nov 22 '12 at 7:21
@AndréNicolas That's an interesting point of view. I don't think I agree, but would be interested in reading anything that you've written on this idea. – goblin Nov 23 '12 at 7:07

In the definition of relations as graphs (i.e., no domains, no codomains explicitly mentioned) the elements in a relation $R$ should be pairs of elements, presumably coming from some universal set $U$. So, to be more precise:

Graph-like definition of relations: Let $U$ be some universal set. A gr-relation in U is a subset of $U\times U$.

Domain-codomain definition of relations: A dc-relation is a triple $(A,B,R)$ with $A,B$ sets and $R\subseteq A\times B$.

The latter definition can be used to define a category, $Rel$, whose objects are all sets and where morphisms $A\to B$ are all relations $(A,B,R)$. Composition is the usual composition of relations and identities are the identity functions.

Now, in any category $C$ an object $x\in ob(C)$ determines a category - the full subcategory spanned by $x$ - call it $C(x)$. It is automatically a monoid, with the monoid operation being the category composition. In particular, choose your favourite universal set $U\in ob(Rel)$ and look at $Rel(U)$. Behold: its arrows are precisely all gr-relations in $U$, with the correct notion of composition.

To conclude, the suggestion to define relations by means of gr-relations in $U$ is completely contained within the existing formalism of category theory. So, not only is there no reason (or at least the motivation you give is no reason) to tinker with the foundations of category theory, these foundations are actually strong enough to capture both notions of relations.

Moreover, if you still wish to tinker with the foundations, I see no way to define category theory with no domains or codomains in a way more in line with the gr-relations definition that will allow for a simple and elegant codification of dc-relations. Perhaps it can be done, in which case it could be an interesting alternative, but I seriously doubt it. At any rate, without any further evidence, I believe there is no real grounds for the cons you present and the pros are already contained within the standard formulation.

share|cite|improve this answer
Well I didn't present any "pros," but merely refuted some "cons"; I'm not trying to convince anyone to change. I just wanted to make sure that I'm not damning myself in some way; I don't want to get to a point where I realize, "Oh no; I can't progress beyond this point until I start talking about codomains and surjections." Also, regarding Category theory you state that "these foundations are actually strong enough to capture both notions of relations" and this is technically true, but then for example categorical products no longer coincide with Cartesian products, I think, which is very bad. – goblin Nov 23 '12 at 7:02
What do you mean by 'categorical products no longer coincide with Cartesian products'? The two notions are synonymous. Unless you are thinking of some 'obvious' product notion for relations, in which case you can specify what it is and then we can see which categorical properties it has. – Ittay Weiss Nov 23 '12 at 7:05
Isn't the problem that the categorical product of sets $X$ and $Y$ no longer coincides with $\lbrace (x,y)|x \in X, y \in Y \rbrace$, because there is only one object in the category, namely $U$? I apologize if I have misunderstood what's going on, set theory is much more familiar to me than category theory. – goblin Nov 23 '12 at 7:12
in any category there might be categorical products or not. If they exist they are also called cartesian products. In the category Set a categorical product of sets A and B can be constructed as AxB. In the category Rel products still exist and are actually isomorphic to coproducts. This is not a problem, it just shows that different categories behave differently. – Ittay Weiss Nov 23 '12 at 7:16
A and B don't exist as object or morphisms in Rel(U) (which is the category I think you are referring to), so the question is ill-posed. – Ittay Weiss Nov 23 '12 at 7:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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