Misplaced Pages

In mathematics, the reflexive closure of a binary relation ${\displaystyle R}$ on a set ${\displaystyle X}$ is the smallest reflexive relation on ${\displaystyle X}$ that contains ${\displaystyle R.}$ A relation is called reflexive if it relates every element of ${\displaystyle X}$ to itself.

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

Definition

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

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

Example

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

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

See also

• Symmetric closure – operation on binary relationsPages displaying wikidata descriptions as a fallback
• 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

${\displaystyle \Gamma \!\vdash }$

This programming language theory or type theory-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Binary relations
• Closure operators
• Rewriting systems
• Programming language theory stubs