Reflexive closure

In mathematics, the reflexive closure of a binary relation R {\displaystyle R} on a set X {\displaystyle X} is the smallest reflexive relation on X {\displaystyle X} that contains R {\displaystyle R} , i.e. the set R ∪ { ( x , x ) ∣ x ∈ X } {\displaystyle R\cup \{(x,x)\mid x\in X\}} .

For example, if X {\displaystyle X} is a set of distinct numbers and x R y {\displaystyle xRy} means " x {\displaystyle x} is less than y {\displaystyle y} ", then the reflexive closure of R {\displaystyle R} is the relation " x {\displaystyle x} is less than or equal to y {\displaystyle y} ".

Definition

The reflexive closure S {\displaystyle S} of a relation R {\displaystyle R} on a set X {\displaystyle X} is given by S = R ∪ { ( x , x ) ∣ x ∈ X } {\displaystyle S=R\cup \{(x,x)\mid x\in X\}}

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

Example

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

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

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