Idempotent Relation¶

A binary relation on one set is idempotent when composing it with itself yields exactly the same related pairs.

Version: v1 · 2026-10-07 · History
Domain-specific #: 13911
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Relation Algebra, Discrete Mathematics → Mathematics

Core Idea¶

An idempotent relation is a binary relation \(R\subseteq X\times X\) for which \(R\circ R=R\). A pair \((x,z)\) belongs to \(R\circ R\) when some \(y\in X\) satisfies \(xRy\) and \(yRz\). Self-composition therefore neither introduces a pair absent from \(R\) nor loses a pair already in \(R\). The intermediary may equal an endpoint.^[1]^[2]

The equality has two independently testable halves. \(R\circ R\subseteq R\) is transitivity: every two-step chain closes to a direct pair. \(R\subseteq R\circ R\) demands a two-step factorization of every direct pair. Reflexivity is sufficient for the latter, but not necessary. Rational strict order and modular congruence show different ways to satisfy it.^[1]^[2]

Structural Signature¶

Homogeneous binary carrier — constitutive bearer. State one set \(X\) and one relation \(R\subseteq X\times X\). Self-composition is then well typed.^[1]
Two-step composition — constitutive operation. Replace \(xRz\) with a witness \(y\) linking \(xRy\) and \(yRz\). The operation is relational composition, not repeated function evaluation on one point.^[1]
No new pairs — constitutive containment. Require \(R\circ R\subseteq R\); failure is a two-step path whose endpoints are not related.^[1]
No lost pairs — constitutive containment. Require \(R\subseteq R\circ R\); failure is a direct pair with no possible intermediary.^[1]

The two containments together, and only together, give idempotence. A finite relation can be checked by Boolean matrix multiplication or by enumerating intermediary witnesses; an infinite relation generally requires a proof about all pairs.^[2]

What It Is Not¶

It is not merely a transitive relation. Strict less-than on the integers is transitive, yet \(1<2\) has no integer strictly between its endpoints, so that pair vanishes under self-composition. It is not necessarily reflexive: strict less-than on the rationals has a midpoint for every ordered pair, despite having no diagonal pairs.^[2]

It is also not idempotence of an arbitrary function. The shared formal pattern is a repeat-product equality, but here the object is a set of ordered pairs and the product is relational composition. A relation can be represented by a relational-image map on subsets, which makes the link to general Idempotence precise without changing the named carrier.^[1]

Scope of Application¶

Use the entry for endorelations on a declared set, including order, congruence, and reachability relations, when the same relation is composed with itself. The definition applies to finite or infinite carriers. It does not require symmetry, antisymmetry, reflexivity, or totality; each of those is a separate condition.^[2]

Composition conventions differ about the written left-to-right order of different relations. For \(R\circ R\) that orientation does not alter the two-step test. The identity concerns exactly two steps, which by associativity also implies all positive composition powers equal \(R\); it says nothing by itself about zero-step identity pairs.^[1]

Clarity¶

The most reliable test is mutual inclusion. To establish \(R\circ R\subseteq R\), take an arbitrary chain \(xRyRz\) and show \(xRz\). To establish \(R\subseteq R\circ R\), take an arbitrary \(xRz\) and produce an intermediary \(y\) with both links. A proof of only the first half establishes transitivity and leaves idempotence unresolved.^[1]

The intermediary need not be a distinct middle point. A reflexive relation can factor \(xRz\) as \(xRxRz\). A strict dense order instead needs a genuinely intermediate element. Confusing these mechanisms makes reflexivity look necessary when it is only one sufficient route.^[1]^[2]

Manages Complexity¶

The equation compresses a potentially unbounded collection of path questions into two local obligations. Once the equality holds, a pair obtainable through any positive number of \(R\) steps is already an \(R\) pair, and every \(R\) pair remains obtainable through two steps. This is an algebraic fact about the relation; it does not state that finding witnesses is computationally cheap.^[1]

The split also locates failures. A new pair from two steps breaks transitivity; a missing factorization breaks the reverse containment. These failures require different repairs or different definitions of the relation. Adding reflexive loops can supply endpoint witnesses, but it changes \(R\), and may be inappropriate for a strict order.^[1]

Abstract Reasoning¶

For an unknown relation, first type its carrier as \(R\subseteq X\times X\). Then prove the two containments separately, using an arbitrary chain for the first and an arbitrary direct pair for the second. A single counterexample in either direction disproves idempotence. If a theorem yields reflexivity plus transitivity, the second half follows by choosing an endpoint as witness.^[1]

For \(<\) on the rationals, transitivity handles two-step chains, while \(y=(x+z)/2\) gives a rational witness whenever \(x<z\). For \(<\) on the integers, adjacent endpoints show the reverse containment fails. These are direct mathematical deductions from the sourced definition, not worked examples attributed to the lecture materials.^[2]

Knowledge Transfer¶

The no-new/no-lost test transfers between different relation families. Rational strict order is irreflexive and obtains factorization through density. Congruence modulo a fixed integer is reflexive and obtains factorization through an endpoint. Both have a typed ordered-pair carrier, relational self-composition, and the same two containment obligations. Their distinct witness mechanisms explain why no one ancillary property defines the class.^[1]^[2]

The broader repeat-operation equation belongs to the live Idempotence Prime. The binary endorelation carrier belongs to live Binary Relation. The present entry combines them in relation algebra, so transfer to a function, matrix, or retryable API operation uses the broader Prime but does not make those objects idempotent relations.

Examples¶

Dense strict order on the rationals¶

Let \(R\) mean \(<\) on \(\mathbb Q\). For every chain \(x<y<z\), transitivity gives \(x<z\), so \(R\circ R\subseteq R\). Conversely, for every \(x<z\), \(y=(x+z)/2\) is rational and satisfies \(x<y<z\), so \(R\subseteq R\circ R\). Thus \(R\circ R=R\) although \(xRx\) is false for every \(x\). This midpoint proof is an editorial derivation from the sourced definition, not a source's quoted example.^[2]

Mapped back: the carrier is rational ordered pairs; composition asks for a middle rational; transitivity prevents new pairs; density prevents lost pairs. Replacing \(\mathbb Q\) by \(\mathbb Z\) destroys the last role at adjacent pairs such as \((1,2)\).

Congruence modulo a fixed integer¶

Let \(R\) relate integers congruent modulo \(n\ge 2\). Transitivity gives \(R\circ R\subseteq R\). If \(aRc\), choose \(y=a\); reflexivity gives \(aRa\) and the original pair gives \(aRc\), proving \(R\subseteq R\circ R\). The result is a direct instance of Kahl's reflexive-and-transitive theorem. The concrete modular example and endpoint choice are editorial deductions rather than a worked case in that proof.^[1]^[2]

Mapped back: the carrier is integer pairs; composition uses a congruent intermediary; transitivity prevents new pairs; reflexivity supplies a witness for every old pair. This differs from rational strict order because no point strictly between endpoints is needed.

Structural Tensions¶

There is no intrinsic structural tradeoff between the two containments: idempotence requires both, and satisfying one does not make the other harder by definition. The useful boundary diagnostic is to ask separately whether every two-step chain collapses to a direct pair and whether every direct pair has a two-step witness. Integer strict order passes the first test and fails the second; a relation with an unclosed two-step chain fails the first.^[1]

A reflexive relation can use an endpoint witness, while a dense irreflexive order can use an interior witness. These are alternative proof mechanisms for the same factorization obligation, not opposing values or a tradeoff. Requiring endpoint witnesses would incorrectly discard the rational-order case.^[2]

Structural–Framed Character¶

Evaluative weight: the equation is descriptive, not praise for a relation. Human-practice dependence: notation and chosen carrier are set by an analyst, but the equation has a checkable truth value once fixed. Institutional origin: no authority creates the equality by decree. Vocabulary travel: “idempotent” travels across algebra and computing because a repeat-product equation survives; “relation” here fixes ordered pairs and relational composition. Import versus recognition: a candidate is recognized by proving both containments, not by borrowing the label from a superficially stable process.^[1]^[2]

The entry is structural within a mathematical frame. Its character: the repeat-product law is portable, while self-composition of one binary endorelation and intermediary witnesses are indispensable to this named relation class. Those latter terms keep it domain-specific rather than a second Prime Idempotence.

Structural Core vs. Domain Accent¶

The core is \(R\subseteq X\times X\), relational self-composition, and exact equality \(R\circ R=R\). Rational density and modular endpoint factorization are different mechanisms for the reverse inclusion, not alternative definitions. Finite matrices and algebraic proofs are different ways to test the same equation.^[1]^[2]

The wider repeat-product skeleton belongs to Prime Idempotence. The ordered-pair carrier belongs to Binary Relation. The residue here is their intersection with a testable two-step witness condition; removing either parent contribution changes the meaning of the child.

This entry is a kind of Binary relation and is a kind of Idempotence.

Idempotence is a strict parent because \(R\circ R=R\) is exact idempotence in the semigroup of endorelations on \(X\). Equivalently, the relational-image map \(F_R(A)=\{z:\exists x\in A,\ xRz\}\) on subsets of \(X\) satisfies \(F_R\circ F_R=F_R\). General idempotent operations need not have ordered-pair relation carriers.

Binary relation is an independent strict parent because every admitted \(R\) is a subset of \(X\times X\), while many binary relations fail the composition equality. Transitive relation expresses the necessary no-new-pairs half, but does not by itself supply factorability and is not asserted as a third direct edge. Equivalence relation is one sufficient subclass; the rational strict-order example prevents treating it as a parent.^[1]^[2]

Relationships to Other Abstractions¶

Current abstraction Idempotent Relation Domain-specific

Parents (2) — more general patterns this builds on

Idempotent Relation is a kind of Binary relation Domain-specific

Every idempotent relation is a homogeneous binary relation with an added composition law.
Idempotent Relation is a kind of Idempotence Prime

Relational self-composition repeats one operation without changing its result.

Hierarchy paths (3) — routes to 3 parentless roots

Idempotent Relation → Binary relation → Relation

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Idempotent Relation sits in a moderately populated region (57^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Set-Theoretic & Order Structures (53 abstractions)

Nearest neighbors

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

Not to Be Confused With¶

Transitivity checks only \(R\circ R\subseteq R\). Reflexivity supplies endpoint witnesses but is not required. A dense strict order is one irreflexive route and is not the definition of relational idempotence. An idempotent function repeats an endofunction, not a set of ordered pairs under relational composition. Transitive closure changes a relation to make paths collapsible; it need not equal the starting relation after exactly one self-composition.^[1]^[2]

References¶

[1] Wolfram Kahl, Logical Reasoning for Computer Science, COMPSCI 2LC3 lecture slides, McMaster University (Fall 2021), Properties of Homogeneous Relations at PDF p. 49 and Reflexive and Transitive Implies Idempotent at PDF pp. 58–59. https://www.cas.mcmaster.ca/~kahl/CS2LC3/2021/COMPSCI_2LC3_Fall2021_Lecture_Slides_10up-A4.pdf registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t

[2] Martin J. Dürst, Properties of Relations, Discrete Math I lecture 10, Aoyama Gakuin University (2 December 2022), Idempotent Relations and Equivalence Relation sections. https://www.sw.it.aoyama.ac.jp/2022/Math1/lecture10.html registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o