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
    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.2012-11-22
  • 1
    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.2012-11-22
  • 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
    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.2012-11-23
  • 0
    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.2012-11-23
  • 0
    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.2012-11-23
  • 0
    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.2012-11-23
  • 0
    If we only want one object in our category, namely $U$, what morphisms do we need to choose so that $A \times B$ is isomorphic to $\lbrace (x,y)|x \in X, y \in Y \rbrace$?2012-11-23
  • 1
    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.2012-11-23
  • 0
    Yes that's exactly my point. How do we even pose the question? Can we do within the existing formalism of category theory? Or do we need to modify it?2012-11-23
  • 0
    all I showed was that your notion of relations is captured within category theory. Category theory already handles set theory quite well as well as many other mathematical objects. So, what is it that you are trying to ask?2012-11-23
  • 0
    Suppose I am doing set theory. I define relations as gr-relations. I define functions as gr-functions. I define the product of sets $A$ and $B$ by writing $A \times B = \lbrace (a,b)|a \in A, b \in B \rbrace $. Now at some point I want to do category theory. I want to confirm that $A \times B$ has been defined "correctly." So I choose a single object $U$. My morphisms are gr-functions. That is, they're relations $f$ such that if $(x,y) \in f$ and $(x,y') \in f$, then $y=y'$. Now how do I proceed?2012-11-23
  • 0
    Well, if the category you try to interpret set product is Rel(U) then you'll find out there are no sets there at all. Your gr-functions are not morphisms in a category where the objects are sets since you just got rid of all domains and codomains, thus you don't need them anymore. The price you pay is that this is a very weird category indeed, one where you can't interpret set product at all.2012-11-23
  • 0
    Exactly. Now if that's all that can be said about this topic, then gr-functions are "incorrect" and dc-functions are "correct." However, I suspect there is more to be said. Here's one possible approach. Perhaps there are gr-functions that can act as surrogates for sets. Intuitively, we expect that these are gr-functions of the form $\lbrace (x,x) | x \in X \rbrace$. There should be a way of characterizing these in purely categorical terms. Once we've done that, we may be able to recover the notion of a categorical product by tweaking the definition.2012-11-23
  • 0
    Anyway, going on holiday now. I'll be able to reply in about 3 days.2012-11-23
  • 0
    enjoy your holiday and good luck re-axiomatizing ;)2012-11-23