3
$\begingroup$

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?

  • 0
    @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.2012-11-23

1 Answers 1

1

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.

  • 0
    enjoy your holid$a$y and good luck re-axiomatizing ;)2012-11-23