closure of a relation with respect to a property
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 .
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 .
, , , 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|
|Date of creation||2013-03-22 17:36:26|
|Last modified on||2013-03-22 17:36:26|
|Last modified by||CWoo (3771)|
|Defines||reflexive transitive closure|