closure of a relation with respect to a property
Introduction
Fix a set . A property of -ary relations on a set may be thought of as some subset of the set of all -ary relations on . Since an -ary relation is just a subset of , , the powerset of . An -ary relation is said to have property if .
For example, the transitive property is a property of binary relations on ; it consists of all transitive binary relations on . Reflexive and symmetric properties are sets of reflexive and symmetric binary relations on correspondingly.
Let be an -ary relation on . By the closure of an -ary relation with respect to property , or the -closure of for short, we mean the smallest relation such that . In other words, if and , then . We write for the -closure of .
Given an -ary relation on , and a property on -ary relations on , does always exist? The answer is no. For example, let be the anti-symmetric property of binary relations on , and . For another example, take to be the irreflexive property, and , the diagonal relation on .
However, if and is closed under arbitrary intersections, then is a complete lattice according to this fact (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice), and, as a result, exists for any .
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 the reflexive property, the symmetric property, and be the transitive property on the binary relations on .
Proposition 1.
Arbitrary intersections are closed in , , and . Furthermore, if is any binary relation on , then
-
•
, where is the diagonal relation on ,
-
•
, where is the converse of , and
- •
-
•
.
, , , 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 is transitive.
Remark. In general, however, the order of taking closures of a relation is important. For example, let , and . Then .
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 |