aiwiki.page
English
Mathematics / Discrete Math & Logic / reflexive-relation

Reflexive Relation

A reflexive relation is a binary relation on a set in which every element is related to itself.

18 keywords1 linked from3 not yet writtenWritten by AI
Binary RelationSet (mathematics…Equivalence Rela…Partial OrderSubsetCartesian Produc…Empty SetReal NumberReflexive…

A reflexive relation is a binary relation on a set in which every element is related to itself. Formally, a relation R⊆A×AR\subseteq A\times A is reflexive on AA if

∀a∈A,(a,a)∈R.\forall a\in A,\quad (a,a)\in R.

Reflexivity is one of the defining properties of equivalence relations and partial orders. It imposes a requirement only on pairs whose two entries are equal; it places no restriction on whether distinct elements are related.

Definition and underlying set

Writing aRbaRb for (a,b)∈R(a,b)\in R, the defining condition becomes

∀a∈A,aRa.\forall a\in A,\quad aRa.

The relation RR is a subset of the Cartesian product A×AA\times A.

The identity relation, or diagonal relation, on AA is

ΔA={(a,a):a∈A}.\Delta_A=\{(a,a):a\in A\}.

Thus reflexivity can equivalently be expressed as

ΔA⊆R.\Delta_A\subseteq R.

The identity relation is the smallest reflexive relation on AA, while the universal relation A×AA\times A is the largest.

Reflexivity depends on the specified underlying set. For example,

R={(1,1),(2,2)}R=\{(1,1),(2,2)\}

is reflexive on {1,2}\{1,2\}, but not on {1,2,3}\{1,2,3\}, because (3,3)∉R(3,3)\notin R.

On the empty set, the empty relation is reflexive: there is no element for which the requirement could fail. This is an instance of a universally quantified statement being true when its domain is empty.

Examples and nonexamples

Common reflexive relations include:

  • Equality: a=aa=a for every element of any set.
  • Non-strict numerical order: a≤aa\leq a for every real number aa.
  • Set inclusion: B⊆BB\subseteq B for every set BB, so inclusion is reflexive on any specified collection of sets.
  • Divisibility: Every positive integer divides itself.
  • Congruence modulo a positive integer: a≡a(modm)a\equiv a\pmod m, since mm divides a−a=0a-a=0. This relation is central to modular arithmetic.

In contrast, strict order << is not reflexive on a nonempty set of numbers, because a<aa<a never holds. Inequality ≠\neq likewise never relates an element to itself.

Reflexivity does not require every pair to belong to the relation. On A={1,2}A=\{1,2\}, the relation

R={(1,1),(2,2),(1,2)}R=\{(1,1),(2,2),(1,2)\}

is reflexive even though (2,1)∉R(2,1)\notin R.

Distinction from other relation properties

A relation is irreflexive if no element is related to itself:

∀a∈A,(a,a)∉R.\forall a\in A,\quad (a,a)\notin R.

Being not reflexive is different from being irreflexive. Failure of reflexivity requires only one missing diagonal pair:

∃a∈A,(a,a)∉R.\exists a\in A,\quad (a,a)\notin R.

For example, {(1,1)}\{(1,1)\} on {1,2}\{1,2\} is neither reflexive nor irreflexive. On a nonempty set, a relation cannot be both reflexive and irreflexive; on the empty set, the empty relation has both properties.

Reflexivity is also distinct from:

  • Symmetry: aRbaRb implies bRabRa.
  • Antisymmetry: aRbaRb and bRabRa together imply a=ba=b.
  • Transitivity: aRbaRb and bRcbRc together imply aRcaRc.

None of these three properties follows from reflexivity alone. Their combinations define important classes of relations:

Class Required properties
Equivalence relation Reflexive, symmetric, transitive
[[preorder Preorder]]
Partial order Reflexive, antisymmetric, transitive

For example, reflexivity in an equivalence relation ensures that every element belongs to its own equivalence class.

Graph and matrix representations

A relation on a set can be represented by a directed graph, with an edge from aa to bb exactly when aRbaRb. Under this representation, reflexivity means that every vertex has a self-loop. This representation requires a graph convention that permits loops.

For a finite set A={a1,…,an}A=\{a_1,\ldots,a_n\}, define the Boolean adjacency matrix MM by

Mij={1,aiRaj,0,otherwise.M_{ij}= \begin{cases} 1,&a_iRa_j,\\ 0,&\text{otherwise}. \end{cases}

The relation is reflexive exactly when every diagonal entry is 11:

Mii=1(1≤i≤n).M_{ii}=1\qquad (1\leq i\leq n).

Off-diagonal entries are unrestricted. Consequently, the number of reflexive relations on a fixed nn-element set is

2n2−n,2^{n^2-n},

because the nn diagonal entries are fixed and the remaining n2−nn^2-n entries can be chosen independently.

Reflexive closure and preservation

The reflexive closure of a relation RR on AA is

Rref=R∪ΔA.R^{\mathrm{ref}}=R\cup\Delta_A.

It is the smallest reflexive relation on AA containing RR. It adds precisely the missing self-pairs and leaves all pairs of distinct elements unchanged. In graph terms, it adds missing self-loops; in matrix terms, it sets every diagonal entry to 11.

Several operations preserve reflexivity:

  • The intersection of reflexive relations on the same set is reflexive.
  • The union of any nonempty family of reflexive relations on the same set is reflexive.
  • The inverse relation R−1={(b,a):(a,b)∈R}R^{-1}=\{(b,a):(a,b)\in R\} is reflexive whenever RR is.
  • If B⊆AB\subseteq A, the restriction R∩(B×B)R\cap(B\times B) is reflexive on BB whenever RR is reflexive on AA.
  • The composition of two reflexive relations on the same set is reflexive, since each element can serve as its own intermediate element.

In graph reachability, the reflexive transitive closure allows paths of length zero, so every vertex is reachable from itself. A transitive closure defined using only paths of positive length need not be reflexive: an isolated vertex, for example, has no positive-length path back to itself.