nLab relation

Redirected from "binary relations".
Relations

Relations

Idea

A relation is the extension of a predicate. That is, if you have a statement whose truth value may depend on some variables, then you get a relation that consists of those instantiations of the variables that make the statement true. Equivalently, you can think of a relation as a function whose target is the set of truth values.

Definitions

General case

Definition

Given a family (A i) i:I(A_i)_{i: I} of sets, a relation on that family is a subset RR of the cartesian product i:IA i\prod_{i: I} A_i.

Equivalently, this is a function from i:IA i\prod_{i: I} A_i to the set TV\TV of truth values (because TV\TV is the subobject classifier in Set).

Also equivalently, this is a monomorphism in/subobject of the cartesian product

R i:IA i. R \hookrightarrow \prod_{i \colon I} A_i \,.
Remark

For II the 2-element set (a binary relation) this is in particular a binary correspondence

R A 1 A 1. \array{ && R \\ & \swarrow && \searrow \\ A_1 && && A_1 } \,.

Hence relations are precisely the (-1)-truncated correspondences.

This identification induces a natural notion of composition of relations from the composition in the category of correspondences, see below at The 2-poset of binary relations.

Formulated this way, the notion of relation generalizes to categories other than Set and to higher category theory. For more on this see at Generalizations below.

Special cases

A nullary relation is a relation on the empty family of sets. This is the same as a truth value.

A unary relation on AA is a relation on the singleton family (A)(A). This is the same as a subset of AA.

A binary relation on AA and BB is a relation on the family (A,B)(A,B), that is a subset of A×BA \times B. This is also called a relation from AA to BB, especially in the context of the 22-category Rel described below, or sometimes called a heterogenous relation.

A binary relation on AA is a relation on (A,A)(A,A), that is a relation from AA to itself. This is sometimes called a homogenous relation on AA, simply a relation on AA, or just an endorelation with its set implicit as a property if not explicitly mentioned.

An nn-ary relation on AA is a relation on a family of nn copies of AA, that is a subset of A nA^n.

For a binary relation, one often uses a symbol such as \sim and writes aba \sim b instead of (a,b)(a,b) \in \sim. Actually, even when a relation is given by a letter such as RR, one often sees aRba R b instead of (a,b)R(a,b) \in R, although now that does not look so good.

Internal and external relations

In foundations of mathematics with a sort of propositions and a separate sort of sets, such as most presentations of set theory in first-order logic with equality, there are actually two notions of relation. The definition given above is the notion of internal relation, defined as a subset of the Cartesian product of a family of sets. There is a second definition of relation on a set: external relations, which are not defined purely inside of the set theory. Since each set has a type of elements inside of the set, an external relation is simply a proposition in the context of a family of variables x ix_i inside of a family of sets A iA_i

Γ,x 0A 0,x 1A 1,x 2A 2,,x nA nPprop\Gamma, x_0 \in A_0, x_1 \in A_1, x_2 \in A_2, \ldots, x_n \in A_n \vdash P \; \mathrm{prop}

In any unsorted set theory, those variables would be expressed as

Γ,x 0,A 0,x 0A 0true,x 1,A 1,x 1A 1true,x 2,A 2,x 2A 2true,,x n,A n,x nA ntruePprop\Gamma, x_0, A_0, x_0 \in A_0 \; \mathrm{true}, x_1, A_1, x_1 \in A_1 \; \mathrm{true}, x_2, A_2, x_2 \in A_2 \; \mathrm{true}, \ldots, x_n, A_n, x_n \in A_n \; \mathrm{true} \vdash P \; \mathrm{prop}

It is in this second sense of external relation that equality in first-order logic with equality is an equivalence relation, and inequality is a tight apartness relation in a first-order theory with equality presented in classical logic.

In dependent type theory, where propositions are considered to be the subsingletons or the sets/types themselves, there is only one notion of relation, the internal notion given above.

Morphisms

If AA and BB are each sets equipped with a relation, then what makes a function f:ABf: A \to B a morphism of sets so equipped?

There are really two ways to do this, shown below. (We will write these as if each set is equipped with a binary relation \sim, but any fixed arity would work.)

  • ff preserves the relation if xyf(x)f(y)x \sim y \;\Rightarrow\; f(x) \sim f(y) always;
  • f reflects the relation if xyf(x)f(y)x \sim y \;\Leftarrow\; f(x) \sim f(y) always.

Now, if ff is a bijection, then it preserves the relation if and only if its inverse reflects it, so clearly an isomorphism of relation-equipped sets should do both. What about a mere morphism?

In general, it's more natural to require only preservation; these are the morphisms you get if you consider a set with a relation as a models of a finite-limit theory or a simply directed graph.

But in some contexts, particularly when dealing only with irreflexive relations, we instead require (only) that a morphism reflect the relation. Sometimes an even stricter condition is imposed, as for well-orders. But even in these cases, the definition of isomorphism comes out the same.

Binary relations

Binary relations are especially widely used.

Kinds of binary relations

Special kinds of relations from AA to BB include:

Combinations of the above properties of binary relations produce:

Special kinds of binary relations on AA (so from AA to itself) additionally include:

Combinations of the above properties of binary relations produce:

Structure preserving relations

Given pointed sets (A,a)(A, a) and (B,b)(B, b), a binary relation RR from AA to BB is said to preserve the point if R(a,b)R(a, b).

Given sets with endofunctions (A,f A)(A, f_A) and (B,f B)(B, f_B), a binary relation RR from AA to BB is said to preserve the endofunction if for every aAa \in A and bBb \in B, if R(a,b)R(a, b), then R(f(a),f(b))R(f(a), f(b)).

Given magmas (A,μ A)(A, \mu_A) and (B,μ b)(B, \mu_b), a binary relation RR from AA to BB is said to preserve the binary operation if for every aAa \in A, cAc \in A, bBb \in B and dBd \in B, if R(a,b)R(a, b) and R(c,d)R(c, d), then R(μ A(a,c),μ B(b,d))R(\mu_A(a, c), \mu_B(b, d)).

And so forth.

Properties

Every binary endorelation RR has an equivalence relation R\sim_R generated by RR.

Binary relations as a coalgebra

By currying the binary relation R:𝒫(X×X)X×XΩR: \mathcal{P}(X \times X) \cong X \times X \rightarrow \Omega, one gets a coalgebra θ:X(XΩ)X𝒫(X)\theta: X \rightarrow (X \rightarrow \Omega) \cong X \rightarrow \mathcal{P}(X) for the powerset endofunctor on Set.

The 22-poset of binary relations

Binary relations form a 22-category (in fact a 22-poset) Rel, which is the basic example of an allegory.

The objects are sets, the morphisms from AA to BB are the binary relations on AA and BB, and there is a 2-morphism from RR to SS (both from AA to BB) if RR implies SS (that is, when (a,b)R(a,b) \in R, then (a,b)S(a,b) \in S).

The interesting definition is composition

Defintion

If RR is a relation from AA to BB and SS is a relation from BB to CC, then their composite relation – written SRS \circ R or R;SR;S – from AA to CC is defined as follows:

(a,c)R;Sb:B,(a,b)R(b,c)S.(a,c) \in R;S \;\Leftrightarrow\; \exists b: B,\; (a,b) \in R \;\wedge\; (b,c) \in S.

The identity morphism is given by equality.

Remark

The composition operation of relation from def. is induced by the composition of the underlying correspondences, followed by (-1)-truncation.

The special properties of the kinds of binary relations listed earlier can all be described in terms internal to Rel; most of them make sense in any allegory. Irreflexive and asymmetric relations are most useful if the allegory's hom-posets have bottom elements, and linear relations require this. Comparisons require the hom-posets to have finite unions, and well-founded relations require some sort of higher-order structure.

As a function may be seen as a functional, entire relation, so the category Set of sets and functions is a subcategory of Rel (in fact a replete and locally full sub-22-category).

The quasitopos of endorelations

Endorelations on sets are the objects of the quasitopos EndoRelEndoRel or BinBin. It is a reflective subcategory of Quiv the presheaf topos of quivers and its morphisms are quiver morphisms. Endorelations are the separated presheaves for the double negation topology on QuivQuiv. “Separated” here translates to a quiver having at most one arc between pairs of verticies. The reflector QuivEndoRelQuiv \to EndoRel collapses parallel arcs together. Such quivers might also be called singular or simple though sometimes “simple” also means “no loops”.

Relation closures as reflexive subcategories of EndoRelEndoRel

All of the sub-types of endorelations with positive conditions (reflexive, symmetric, transitive, and left and right euclidean) and their combinations have an associated closure that can produce one from an arbitrary relation. Such a closure completes a relation by adding the least number of arcs such that the conditions are satisfied. Within EndoRelEndoRel these closures are reflectors that produce reflective subcategories. For example the symmetric closure sym:EndoRelEndoSymsym: EndoRel \to EndoSym will (possibly) enlarge a quiver that contains any arc v av bv_a \to v_b to one that also contains v bv av_b \to v_a. The transitive and reflexive closure transRef:EndoRelEndoTransReftransRef: EndoRel \to EndoTransRef produces a category which is isomorphic to PreOrd though its objects are the underlying quivers of the preorders which are the objects of PreOrdPreOrd.

In addition to being reflective, the categories from the symmetric, reflexive, and symmetric and reflexive closures are also quasitoposes that can be directly defined through double negation separation. The symmetric and reflexive closure (SimpGph) is also a Grothendieck quasitopos. On the other hand PreOrdPreOrd is not a quasitopos because it is not a regular category.

Ternary relations

Apart from binary relations, there are important ternary relations used in mathematics, which for the most part are families of binary relations indexed by a third set:

Generalisation

Most of the preceding makes sense in any category with enough products; giving rise to internal relations, for instance congruences in the case of internal equivalence relations.

Probably the trickiest bit is the definition of composition of binary relations, so not every category with finite products has an allegory of relations. In fact, in a certain precise sense, a category has an allegory of relations if and only if it is regular. It can then be recovered from this allegory by looking at the functional entire relations.

type of modal logicrelation in its Kripke frames
K modal logicany relation
K4 modal logic?transitive relation
T modal logicreflexive relation
B modal logic?symmetric relation
S4 modal logicreflexive & transitive relation
S5 modal logicequivalence relation

(following BdRV (2001) Table 4.1; cf. Fagin, Halpern, Moses & Vardi (1995) Thm. 3.1.5)

Last revised on June 14, 2024 at 22:05:25. See the history of this page for a list of all contributions to it.