Reflexive closure

In mathematics, the reflexive closure of a binary relation [math]\displaystyle{ R }[/math] on a set [math]\displaystyle{ X }[/math] is the smallest reflexive relation on [math]\displaystyle{ X }[/math] that contains [math]\displaystyle{ R. }[/math] A relation is called reflexive if it relates every element of [math]\displaystyle{ X }[/math] to itself. For example, if [math]\displaystyle{ X }[/math] is a set of distinct numbers and [math]\displaystyle{ x R y }[/math] means "[math]\displaystyle{ x }[/math] is less than [math]\displaystyle{ y }[/math]", then the reflexive closure of [math]\displaystyle{ R }[/math] is the relation "[math]\displaystyle{ x }[/math] is less than or equal to [math]\displaystyle{ y }[/math]".

Definition

The reflexive closure [math]\displaystyle{ S }[/math] of a relation [math]\displaystyle{ R }[/math] on a set [math]\displaystyle{ X }[/math] is given by [math]\displaystyle{ S = R \cup \{(x, x) : x \in X\} }[/math]

In plain English, the reflexive closure of [math]\displaystyle{ R }[/math] is the union of [math]\displaystyle{ R }[/math] with the identity relation on [math]\displaystyle{ X. }[/math]

Example

As an example, if [math]\displaystyle{ X = \{1, 2, 3, 4\} }[/math] [math]\displaystyle{ R = \{(1,1), (2,2), (3,3), (4,4)\} }[/math] then the relation [math]\displaystyle{ R }[/math] is already reflexive by itself, so it does not differ from its reflexive closure.

However, if any of the pairs in [math]\displaystyle{ R }[/math] was absent, it would be inserted for the reflexive closure. For example, if on the same set [math]\displaystyle{ X }[/math] [math]\displaystyle{ R = \{(1,1), (2,2), (4,4)\} }[/math] then the reflexive closure is [math]\displaystyle{ S = R \cup \{(x,x): x \in X\} = \{(1,1), (2,2), (3,3), (4,4)\} . }[/math]

See also

• Symmetric closure
• Transitive closure – Smallest transitive relation containing a given binary relation

References

• Franz Baader and Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1998, p. 8