This article treats relations from the perspective of combinatorics, in other words, as a subject
matter in discrete mathematics, with special attention to finite structures and concrete
set-theoretic constructions, many of which arise quite naturally in applications. This approach to
relation theory, or the theory of relations, is distinguished from, though closely related to, its
study from the perspectives of abstract algebra on the one hand and formal logic on the
other.
Contents
1 Preliminaries
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 some
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 = (obj1 f, obj2 f, obj12 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 ” to specify
the type of the function, that is, the pair (obj1 f, obj2 f), but “f” is used equivocally to denote
both the triple and the subset obj12 f that forms one part of it. One way to resolve
the ambiguity is to formalize a distinction between a function and its graph, letting
graph(f) := obj12 f.
Another tactic treats the whole notation “f : X → Y ” as sufficient denotation 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 an integral part of the function itself. In other contexts it may be desirable to use a
more abstract concept of function, treating a function as a mathematical object that appears in
connection with many different types.
Following the pattern of the functional case, let the notation “L ⊆ X × Y ” bring to mind a
mathematical object that 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.
2 Definition
It is convenient to begin with the definition of a k-place relation, where k is a positive
integer.
Definition. A k-place relation L ⊆ X1 ×… × Xk over the nonempty sets X1,…,Xk is a
(k + 1)-tuple (X1,…,Xk,L) where L is a subset of the cartesian product X1 ×… × Xk.
3 Remarks
Though usage varies as usage will, there are several bits of optional language that are
frequently useful in discussing relations. The sets X1,…,Xk are called the domains of the
relation L ⊆ X1 ×… × Xk, with Xj being the jth domain. If all of the Xj are the same
set X, then L ⊆ X1 ×… × Xk is more simply described as a k-place relation over X.
The set L is called the graph of the relation L ⊆ X1 ×… × Xk, on analogy with the
graph of a function. If the sequence of sets X1,…,Xk is constant throughout a given
discussion or is otherwise determinate in context, then the relation L ⊆ X1 ×… × Xk is
determined by its graph L, making it acceptable to denote the relation by referring to its
graph. Other synonyms for the adjective k-place are k-adic and k-ary, all of which leads
to the integer k being called the dimension, the adicity, or the arity of the relation
L.
4 Local incidence properties
A local incidence property (LIP) of a relation L is a property that depends in turn on the
properties of special subsets of L that are known as its local flags. The local flags of a relation are
defined in the following way:
Let L be a k-place relation L ⊆ X1 ×… × Xk.
Select a relational domain Xj and one of its elements x. Then Lx@j is a subset of L that is referred
to as the flag of L with x at j, or the x@j-flag of L, an object that has the following
definition:
Any property C of the local flag Lx@j ⊆ L is said to be a local incidence property of L with respect
to the locus x@j.
A k-adic relation L ⊆ X1 ×…×Xk is said to be C-regular at j if and only if every flag of L with x
at j has the property C, where x is taken to vary over the theme of the fixed domain
Xj.
Expressed in symbols, L is C-regular at j if and only if C(Lx@j) is true for all x in
Xj.
5 Regional incidence properties
The definition of a local flag can be broadened from a point x in Xj to a subset M of Xj, arriving
at the definition of a regional flag in the following way:
Suppose that L ⊆ X1 ×…×Xk, and choose a subset M ⊆ Xj. Then LM@j is a subset of L that is
said to be the flag of L with M at j, or the M@j-flag of L, an object which has the following
definition:
6 Numerical incidence properties
A numerical incidence property (NIP) of a relation is a local incidence property that depends on
the cardinalities of its local flags.
For example, L is said to be c-regular at j if and only if the cardinality of the local
flag Lx@j is c for all x in Xj, or, to write it in symbols, if and only if |Lx@j| = c for all
x ∈ Xj.
In a similar fashion, one can define the NIPs, (< c)-regular at j, (> c)-regular at j, and so on. For
ease of reference, a few of these definitions are recorded here:
7 Species of 2-adic relations
Returning to 2-adic relations, it is useful to describe some familiar classes of objects in terms of
their local and numerical incidence properties. Let L ⊆ S ×T be an arbitrary 2-adic relation. The
following properties of L can be defined:
If L ⊆ S × T is tubular at S, then L is called a partial function or a prefunction from S to
T. This is sometimes indicated by giving L an alternate name, say, “p”, and writing
L = p : S ⇀ T.
Just by way of formalizing the definition:
If L is a prefunction p : S ⇀ T that happens to be total at S, then L is called a function from S to
T, indicated by writing L = f : S → T. To say that a relation L ⊆ S × T is totally
tubular at S is to say that it is 1-regular at S. Thus, we may formalize the following
definition:
In the case of a function f : S → T, one has the following additional definitions:
8 Variations
Because the concept of a relation has been developed quite literally from the beginnings of logic
and mathematics, and because it has incorporated contributions from a diversity of thinkers from
many different times and intellectual climes, there is a wide variety of terminology that the reader
may run across in connection with the subject.
One dimension of variation is reflected in the names that are given to k-place relations,
for k = 1, 2, 3,…, with some writers using the Greek forms, medadic, monadic, dyadic,
triadic, k-adic, and other writers using the Latin forms, nullary, unary, binary, ternary,
k-ary.
The cardinality of the relational ground, the set of relational domains, may be referred to as the
adicity, the arity, or the dimension of the relation. Accordingly, one finds a relation on a finite
number of domains described as a polyadic relation or a finitary relation, but others count
infinitary relations among the polyadic. If the number of domains is finite, say equal to k, then the
relation may be described as a k-adic relation, a k-ary relation, or a k-dimensional relation,
respectively.
A more conceptual than nominal variation depends on whether one uses terms like predicate,
relation, and even term to refer to the formal object proper or else to the allied syntactic
items that are used to denote them. Compounded with this variation is still another,
frequently associated with philosophical differences over the status in reality accorded formal
objects. Among those who speak of numbers, functions, properties, relations, and sets
as being real, that is to say, as having objective properties, there are divergences as
to whether some things are more real than others, especially whether particulars or
properties are equally real or else which one is derivative in relationship to the other.
Historically speaking, just about every combination of modalities has been used by one
school of thought or another, but it suffices here merely to indicate how the options are
generated.
