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\) on one set \(X\) for which \(R\circ R=R\). A pair is in \(R\circ R\) when its endpoints can be linked by two \(R\) steps through some intermediary. Idempotence says exactly that taking two steps gives the same pairs as taking one.[^{ref-e84b823f8b71][}ref-6d3afcc72d07]

Both directions matter. Transitivity prevents two-step chains from making new pairs, while every existing pair must have a two-step witness so that no pair is lost. Reflexivity is one way to supply a witness, but it is not required.[^ref-e84b823f8b71]

Scope of Application¶

Use this entry for a relation \(R\subseteq X\times X\) composed with itself. The set may be finite or infinite. Orders and congruences can qualify; merely calling a relation transitive, symmetric, or reflexive does not settle the equality by itself. Composition here is relational composition of ordered pairs, rather than function composition or a computer program's repeated effect.[^{ref-e84b823f8b71][}ref-6d3afcc72d07]

Clarity¶

Prove \(R\circ R\subseteq R\) by checking that every \(xRyRz\) implies \(xRz\). Prove \(R\subseteq R\circ R\) by starting with any \(xRz\) and finding some \(y\) such that \(xRy\) and \(yRz\). A proof of only the first containment establishes transitivity, not idempotence. The intermediary can be one endpoint when the relation is reflexive.[^ref-e84b823f8b71]

Manages Complexity¶

The equality packages many path questions into two tests: can a two-step chain create a new pair, and can every old pair be factored into two steps? If both answers have the required form, all positive composition powers reproduce \(R\). That is an algebraic conclusion, not a claim that computing the relation or finding every witness is fast.[^ref-e84b823f8b71]

Abstract Reasoning¶

First state one carrier set and the exact related-pair rule. Check both containments for arbitrary elements, not only a few examples. A single two-step path missing a direct link refutes one side; a single direct pair with no intermediary refutes the other. Reflexivity plus transitivity is a sufficient shortcut because an endpoint can act as intermediary.[^ref-e84b823f8b71]

Strict less-than on integers shows why the shortcut is not the definition: it is transitive, but \(1<2\) has no integer strictly between and so fails factorization. Strict less-than on rationals does have a midpoint for every ordered pair and qualifies despite being irreflexive. These are direct deductions from the sourced definition.[^ref-6d3afcc72d07]

Knowledge Transfer¶

The same carrier/composition/two-containment test transfers between two unlike relation families. Rational strict order factors through a midpoint. Congruence modulo a fixed integer factors through an endpoint because it is reflexive. Both close two-step chains by transitivity. Their witness mechanisms differ, but the equality is identical.[^{ref-e84b823f8b71][}ref-6d3afcc72d07]

Live Idempotence is the broad parent for operations unchanged by repetition; live Binary Relation is the parent for the ordered-pair carrier. This entry fixes both to relational self-composition. An idempotent function or retryable API operation can share the broad pattern without becoming an idempotent relation.

Example¶

Rational strict order. Let \(R\) mean \(<\) on \(\mathbb Q\). Its carrier is ordered pairs of rationals. Composition asks for a middle rational. No new pairs follows from transitivity. No lost pairs follows by choosing \(y=(x+z)/2\) whenever \(x<z\). Thus \(R\circ R=R\), even though no rational is less than itself. This midpoint proof is an editorial derivation, not a worked source example.[^ref-6d3afcc72d07]

Congruence modulo \(n\ge2\). Its carrier is ordered pairs of integers equivalent modulo the fixed \(n\). Composition links congruent pairs through an intermediary. No new pairs follows from transitivity; no lost pairs follows by choosing one endpoint as intermediary using reflexivity. The modular instance is an editorial application of Kahl's reflexive-and-transitive theorem.[^{ref-e84b823f8b71][}ref-6d3afcc72d07]

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 proves only the no-new-pairs half. Reflexivity can prove factorability but is not required. Equivalence relation is one sufficient family, not the whole class, since rational strict order is irreflexive. General idempotence covers operations on many kinds of objects; this entry concerns a binary endorelation under relational composition. There is no intrinsic tradeoff between the two required containments: both must hold.[^{ref-e84b823f8b71][}ref-6d3afcc72d07]

References¶

[^ref-e84b823f8b71]: 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

[^ref-6d3afcc72d07]: 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