closure of a relation with respect to a property


Introduction

Fix a set A. A property 𝒫 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 relationMathworldPlanetmathPlanetmath is just a subset of An, 𝒫P(An), the powerset of An. An n-ary relation is said to have property 𝒫 if R𝒫.

For example, the transitive property is a property of binary relations on A; it consists of all transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath binary relations on A. ReflexiveMathworldPlanetmathPlanetmath 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 closureMathworldPlanetmath of an n-ary relation R with respect to property 𝒫, or the 𝒫-closure of R for short, we mean the smallest relation S𝒫 such that RS. In other words, if T𝒫 and RT, then ST. We write Cl𝒫(R) for the 𝒫-closure of R.

Given an n-ary relation R on A, and a property 𝒫 on n-ary relations on A, does Cl𝒫(R) always exist? The answer is no. For example, let 𝒫 be the anti-symmetric property of binary relations on A, and R=A2. For another example, take 𝒫 to be the irreflexiveMathworldPlanetmath property, and R=Δ, the diagonal relation on A.

However, if An𝒫 and 𝒫 is closed underPlanetmathPlanetmath arbitrary intersectionsMathworldPlanetmath, then 𝒫 is a complete latticeMathworldPlanetmath according to this fact (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice), and, as a result, Cl𝒫(R) exists for any RAn.

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 𝒳 the reflexive property, 𝒮 the symmetric property, and 𝒯 be the transitive property on the binary relations on A.

Proposition 1.

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

  • R=:=Cl𝒳(R)=RΔ, where Δ is the diagonal relation on A,

  • R:=Cl𝒮(R)=RR-1, where R-1 is the converseMathworldPlanetmath of R, and

  • R+:=Cl𝒯(R) is given by

    nRn=R(RR)(RR)n-fold power,

    where is the relational compositionPlanetmathPlanetmath operator.

  • R*:=R=+=R+=.

R=, R, R+, and R* are called the reflexive closureMathworldPlanetmath, the symmetric closure, the transitive closureMathworldPlanetmath, and the reflexive transitive closure of R respectively. The last item in the propositionPlanetmathPlanetmath permits us to call R* the transitive reflexive closure of R as well (there is no differencePlanetmathPlanetmath 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 A={a,b}, and R={(a,b)}. Then R+=A2{(a,b),(b,a)}=R+.

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