Cf: Relation Theory • 2
I am putting a new edition of my Relation Theory article on my blog
and transcribing a plaintext copy for whatever discussion may arise,
but please see the above-linked blog post for better-formatted copy.
Two definitions of the relation concept are common in the literature.
Although it is usually clear in context which definition is being used
at a given time, it tends to become less clear as contexts collide, or
as discussion moves from one context to another.
The same sort of ambiguity arose in the development of the function concept
and it may save a measure of effort to follow the pattern of resolution that
worked itself out there.
When we speak of a function f : X → Y we are thinking of
a mathematical object whose articulation requires three
pieces of data, specifying the set X, the set Y, and
a particular subset of their cartesian product X × Y.
So far so good.
Let us write f = (obj₁f, obj₂f, obj₁₂f) to express what has been said so far.
When it comes to parsing the notation “f : X → Y”, everyone takes the part
“X → Y” as indicating the type of the function, in effect defining type(f)
as the pair (obj₁f, obj₂f), but “f” is used equivocally to denote both the
triple (obj₁f, obj₂f, obj₁₂f) and the subset obj₁₂f forming one part of it.
One way to resolve the ambiguity is to formalize a distinction between the
function f = (obj₁f, obj₂f, obj₁₂f) and its “graph”, defining graph(f) = obj₁₂f.
Another tactic treats the whole notation “f : X → Y” as a name for the triple,
letting “f” denote graph(f).
In categorical and computational contexts, at least initially, the type is
regarded as an essential attribute or integral part of the function itself.
In other contexts we may wish to use a more abstract concept of function,
treating a function as a mathematical object capable of being viewed under
many different types.
Following the pattern of the functional case, let the notation “L ⊆ X × Y”
bring to mind a mathematical object which is specified by three pieces of data,
the set X, the set Y, and a particular subset of their cartesian product X × Y.
As before we have two choices, either let L = (X, Y, graph(L)) or let “L” denote
graph(L) and choose another name for the triple.