Category of relations

The category Rel whose objects are sets and whose morphisms are binary relations composed by existential relational composition.

Version

v2 · 2026-09-19 · History

Domain-specific #

3617

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomain

Category Theory → Mathematics

Core Idea

Rel has identities given by equality relations and composition S∘R relating x to z when some y satisfies xRy and ySz. Existential elimination of the intermediate element makes associativity hold, while converse relations provide a dagger structure and Cartesian product supplies monoidal structure. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

The load-bearing residual is not the broad topic of category theory. It is the domain-specific identity determined by objects are sets, arrows are relations, identities are diagonals, and composition is the declared existential rule.

How would you explain it like I'm…

Friend-of-a-Friend Arrows

Think of strings tied between kids in one group and toys in another group. A kid can have strings to many toys, or to none. If you also have strings from toys to snacks, you can say a kid is connected to a snack whenever there's some toy in between that links them. The category of relations is all such groups with all such ways of tying strings.

Chaining Connections

A relation between two sets is a list of which things in the first set are linked to which things in the second — any thing can be linked to many things, one, or none. In the category of relations, the objects are sets and the arrows are relations. To combine two relations, you link x to z whenever there is at least one middle thing y with x linked to y and y linked to z. The "do nothing" arrow links each thing only to itself. You can also flip any relation around to point the other way.

Sets with Relations as Arrows

The category of relations, Rel, has sets as its objects and relations as its arrows: a relation from A to B is any subset of A × B, saying which elements of A are related to which elements of B. The identity arrow on a set is equality (the diagonal: each element related only to itself). Composition S∘R relates x to z exactly when there is some intermediate y with x R y and y S z. Because this just asks 'does some middle element exist?', composing three relations gives the same answer however you group them, so composition is associative. Rel also has extra structure: every relation can be reversed (its converse), and the Cartesian product of sets lets you combine relations side by side. Unlike the category of sets and functions, an arrow here may relate one element to several or to none.

 

Rel is the category whose objects are sets and whose morphisms R: A → B are binary relations R ⊆ A × B. Identities are the diagonal (equality) relations, and composition is relational: x (S∘R) z iff ∃y with x R y and y S z. Associativity follows because the existential quantification over intermediate elements can be eliminated in either order. Taking converse relations gives a dagger structure (R† : B → A), which is an involution reversing composition, and the Cartesian product of sets, with the product of relations, gives a monoidal structure. The category of sets embeds in Rel by viewing functions as their graphs, but Rel is strictly larger, since relations need not be total or single-valued. To be Rel, the construction must have exactly these ingredients: sets as objects, relations as arrows, diagonals as identities, and the existential composition rule.

Scope of Application

Category of relations belongs to category theory and is useful where the analyst can specify the typed category theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases and comparison targets, then evaluate objects are sets, arrows are relations, identities are diagonals, and composition is the declared existential rule. The scope is broad within that domain but bounded by the need for objects are sets, arrows are relations, identities are diagonals, and composition is the declared existential rule. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity

The abstraction clarifies a crowded vocabulary by making objects are sets, arrows are relations, identities are diagonals, and composition is the declared existential rule the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Category of relations can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Category of relations. Category of relations compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning

1. Identify the carrier. State what the elements, states, objects, or observations are: the typed category theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
2. Lock the constitutive rule. Express objects are sets, arrows are relations, identities are diagonals, and composition is the declared existential rule independently of one notation or implementation.

Knowledge Transfer

Knowledge transfers strongly among subfields of category theory because they reuse the typed category theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases and comparison targets, Existential elimination of the intermediate element makes associativity hold, while converse relations provide a dagger structure and Cartesian product supplies monoidal structure., and type the carrier, state every parameter and convention in the definition, test that objects are sets, arrows are relations, identities are diagonals, and composition is the declared existential rule, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions

Current abstraction Category of relations Domain-specific

Parents (1) — outgoing typed relations

• Category of relations is a kind of Relation Prime

  What makes it its own entry: the domain-specific identity determined by objects are sets, arrows are relations, identities are diagonals, and composition is the declared existential rule.

Hierarchy path (1) — routes to 1 parentless root

• Category of relations → is a kind of Relation

Neighborhood in Abstraction Space

Category of relations sits in a crowded region of the domain-specific corpus (1^st percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Category Theory Foundations (48 abstractions)

Nearest neighbors

• Subcategory — 0.94
• Inserter category — 0.94
• Category theory — 0.94
• Opposite category — 0.94
• Symmetric relation — 0.94

Computed from structural-signature embeddings · 2026-10-25