closure of a relation with respect to a property

Introduction

Fix a set $A$ . A property $\mathcal{P}$ of $n$ -ary relations on a set $A$ may be thought of as some subset of the set of all $n$ -ary relations on $A$ . Since an $n$ -ary relation is just a subset of $A^{n}$ , $\mathcal{P}\subseteq P(A^{n})$ , the powerset of $A^{n}$ . An $n$ -ary relation is said to have property $\mathcal{P}$ if $R\in\mathcal{P}$ .

For example, the transitive property is a property of binary relations on $A$ ; it consists of all transitive binary relations on $A$ . Reflexive and symmetric properties are sets of reflexive and symmetric binary relations on $A$ correspondingly.

Let $R$ be an $n$ -ary relation on $A$ . By the closure of an $n$ -ary relation $R$ with respect to property $\mathcal{P}$ , or the $\mathcal{P}$ -closure of $R$ for short, we mean the smallest relation $S\in\mathcal{P}$ such that $R\subseteq S$ . In other words, if $T\in\mathcal{P}$ and $R\subseteq T$ , then $S\subseteq T$ . We write $\operatorname{Cl}_{\mathcal{P}}(R)$ for the $\mathcal{P}$ -closure of $R$ .

Given an $n$ -ary relation $R$ on $A$ , and a property $\mathcal{P}$ on $n$ -ary relations on $A$ , does $\operatorname{Cl}_{\mathcal{P}}(R)$ always exist? The answer is no. For example, let $\mathcal{P}$ be the anti-symmetric property of binary relations on $A$ , and $R=A^{2}$ . For another example, take $\mathcal{P}$ to be the irreflexive property, and $R=\Delta$ , the diagonal relation on $A$ .

However, if $A^{n}\in\mathcal{P}$ and $\mathcal{P}$ is closed under arbitrary intersections, then $\mathcal{P}$ is a complete lattice according to this fact (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice), and, as a result, $\operatorname{Cl}_{\mathcal{P}}(R)$ exists for any $R\subseteq A^{n}$ .

Reflexive, Symmetric, and Transitive Closures

From now on, we concentrate on binary relations on a set $A$ . In particular, we fix a binary relation $R$ on $A$ , and let $\mathcal{X}$ the reflexive property, $\mathcal{S}$ the symmetric property, and $\mathcal{T}$ be the transitive property on the binary relations on $A$ .

Proposition 1.

Arbitrary intersections are closed in $\mathcal{X}$ , $\mathcal{S}$ , and $\mathcal{T}$ . Furthermore, if $R$ is any binary relation on $A$ , then

•

$R^{=}:=\operatorname{Cl}_{\mathcal{X}}(R)=R\cup\Delta$ , where $\Delta$ is the diagonal relation on $A$ ,
•

$R^{\leftrightarrow}:=\operatorname{Cl}_{\mathcal{S}}(R)=R\cup R^{-1}$ , where $R^{-1}$ is the converse of $R$ , and

•

$R^{+}:=\operatorname{Cl}_{\mathcal{T}}(R)$ is given by

$\bigcup_{n\in\mathbb{N}}R^{n}=R\cup(R\circ R)\cup\cdots\cup\underbrace{(R\circ% \cdots\circ R)}_{\displaystyle{n}\mbox{-fold power}}\cup\cdots,$

where $\circ$ is the relational composition operator.

•

$R^{*}:=R^{=+}=R^{+=}$ .

$R^{=}$ , $R^{\leftrightarrow}$ , $R^{+}$ , and $R^{*}$ are called the reflexive closure, the symmetric closure, the transitive closure, and the reflexive transitive closure of $R$ respectively. The last item in the proposition permits us to call $R^{*}$ the transitive reflexive closure of $R$ as well (there is no difference to the order of taking closures). This is true because $\Delta$ is transitive.

Remark. In general, however, the order of taking closures of a relation is important. For example, let $A=\{a,b\}$ , and $R=\{(a,b)\}$ . Then $R^{\leftrightarrow+}=A^{2}\neq\{(a,b),(b,a)\}=R^{+\leftrightarrow}$ .

Title	closure of a relation with respect to a property
Canonical name	ClosureOfARelationWithRespectToAProperty
Date of creation	2013-03-22 17:36:26
Last modified on	2013-03-22 17:36:26
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	15
Author	CWoo (3771)
Entry type	Definition
Classification	msc 08A02
Related topic	Property2
Defines	reflexive closure
Defines	symmetric closure
Defines	transitive closure
Defines	reflexive transitive closure