PlanetMath: closure of a relation with respect to a property

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (191)
Orphanage
Unclass'd
Unproven (496)
Corrections (10)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

closure of a relation with respect to a property

(Definition)

Introduction

Let be an -ary relation on a set . Recall that a property is just a subset of some set. A property $\mathcal{P}$ of an -ary relation on is then a subset of the set of all -ary relations on . Thus, $\mathcal{P}\subseteq P(A^n)$ , the powerset of .

For example, the transitive property is a property of binary relations on some set, and so are the reflexive and symmetric properties.

By the closure of with respect to property $\mathcal{P}$ , or the $\mathcal{P}$ -closure of 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 . This is just a special case of the closure of a subset $B\subseteq A$ under a set $\mathcal{R}$ of relations on . The special case here deals with the situation where () is a subset of , and $\mathcal{R}$ ( $=\mathcal{P}$ ) is a set of unary relations on . See the parent entry “closure of a set via relations” for more detail.

According to the parent entry (Proposition 2), for an arbitray -ary relation on , the closure of exists iff $\mathcal{P}$ is closed under arbitrary intersection. This means that given any subset $\mathcal{Q}$ of relations with property $\mathcal{P}$ , including the case when $\mathcal{Q}=\varnothing$ , $\bigcap \mathcal{Q}$ has property $\mathcal{P}$ . In particular, this implies that has property $\mathcal{P}$ .

So the first thing to check if has a $\mathcal{P}$ -closure is to determine if has property $\mathcal{P}$ . For example, let $\mathcal{P}$ be the anti-symmetric property of a binary relation on . Then $A\times A$ clearly does not have $\mathcal{P}$ , and thus it is not possible to find $\mathcal{P}$ -closure for an arbitrary on . Obviously, if contains both and , then it is not possible to find the $\mathcal{P}$ -closure of . Similarly, if $\mathcal{P}$ is the irreflexive property, then $\mathcal{P}$ -closures may not exist for every $R\subseteq A\times A$ .

Reflexive, Symmetric, and Transitive Closures

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

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

$R^=:=\operatorname{Cl}_{\mathcal{X}}(R)=R\cup \Delta$ , where $\Delta$ is the diagonal relation on ,
$R^{\leftrightarrow}:=\operatorname{Cl}_{\mathcal{S}}(R)=R\cup R^{-1}$ , where $R^{-1}$ is the converse of , and
$R^+:=\operatorname{Cl}_{\mathcal{T}}(R)$ is given by
$\displaystyle \bigcup_{n\in \mathbb{N}} R^n = R\cup (R\circ R) \cup \cdots \cup... ...ace{(R\circ \cdots \circ R)}_{\displaystyle{n}\mbox{-fold power}} \cup \cdots ,$
where $\circ$ is the relational composition operator.
$R^*:=R^{=+}=R^{+=}$ .

, $R^{\leftrightarrow}$ ,

, and

are called the reflexive closure, the symmetric closure, the transitive closure, and the reflexive transitive closure of

respectively. The last item in the proposition permits us to call

the transitive reflexive closure of

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=\lbrace a,b\rbrace$ , and $R=\lbrace (a,b)\rbrace$ . Then $R^{\leftrightarrow +}=A^2\ne \lbrace (a,b),(b,a)\rbrace = R^{+ \leftrightarrow}$ .

"closure of a relation with respect to a property" is owned by CWoo.

(view preamble)

See Also: property

Also defines:

reflexive closure, symmetric closure, transitive closure, reflexive transitive closure

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: closures, order, difference, transitive, operator, relational composition, converse, diagonal relation, closed, fix, irreflexive, contains, anti-symmetric, implies, intersection, closed under, iff, unary relations, mean, symmetric, Reflexive, binary relations, transitive property, powerset, subset, property, relation
There are 8 references to this entry.

This is version 6 of closure of a relation with respect to a property, born on 2007-10-29, modified 2007-10-31.
Object id is 10023, canonical name is ClosureOfARelationWithRespectToAProperty.
Accessed 1483 times total.

Classification:

AMS MSC:

08A02 (General algebraic systems :: Algebraic structures :: Relational systems, laws of composition)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact