CalculusofRelations

v 0.10 Author @Prathyvsh

Closures of Relations

A closure of a relation Rel is the most minimal relation with respect to some property Prop that contains the source relation Rel.

Thinking computationally, the closure operation takes a relation and adds the least number of relations needed so that the resulting relation fulfills the property Prop.

If we think about the relationship between any closure to the source relation Rel, one might note the following rule holds:

Extensivity

Rel ⊆ Closure(Rel)

Structural Interpretation

Closure (with respect to any property) contains the source relation as a subset.

Information Interpretation

Closure is more information rich than the source relation.

Shows the image of a relation with three dots say a → b, a → c with transitive closure applied to it which adds a new ivory arrow b → c in the closure. The source relation Rel A is connected to its closure Closure(Rel A, Transitivity) and the arrow connecting them is labelled “Transitive Closure” and ⊆ relation.

There are also two other neat properties closures have:

Idempotence

Closure(Closure(Rel)) = Closure(Rel)
Shows the image of a relation with three dots say a → b, a → c with transitive closure applied to it which adds a new ivory arrow b → c in the closure. The source relation Rel A is connected to its closure Closure(Rel A, Transitivity) and the arrow connecting them is labelled “Transitive Closure” and ⊆ relation.

Structural Interpretation

Applying a closure on a relation which already has closure results in the same relation.

Informational Interpretation

Repeated application of closure produces no new information.

Monotonicity

Rel1 ⊆ Rel2 => Closure(Rel1) ⊆ Closure(Rel2)
Shows the image of a relation with three dots say a → b, a → c with transitive closure applied to it which adds a new ivory arrow b → c in the closure. The source relation Rel A is connected to its closure Closure(Rel A, Transitivity) and the arrow connecting them is labelled “Transitive Closure” and ⊆ relation.

Structural Interpretation

Closure operation respects the underlying containment relations or that “the diagram commutes”.

Informational Interpretation

Information gained by applying a transitive closure on a subset SubRel C would be a subset of the one gained by applying it on its superset Rel C.

Note that since the closure property is extensive, once a closure relation is applied to a relation, one might need to apply the reverse process called kernel operation to make it acquire arbitrary desired properties. Otherwise, if closure operation is the only one we have in our repertoire, we would be left with operations that only increase the information but not reduce it. This aspect will be explored in a later outing in this blog post.

Order 0

Type

(Empty * Empty) -> Bool

State Space

(0 * 0) -> 2 = 2⁰ = 1 Configuration
Empty relation showing a circle with thin grey stroke

Original Relation

Empty matrix showing a square with thin grey stroke
Empty relation showing a circle with thin grey stroke

All Operations

Empty matrix showing a square with thin grey stroke

Order 1

Type

(Unit * Unit) -> Bool

State Space

(1 * 1) -> 2 = 2¹ = 2 Configurations
Unit relation showing a slate grey color filled circle

Original Relation

Unit matrix showing a square with thin grey stroke
Reflexive unit relation showing a grey color filled circle with ivory colored arrow

All Operations

Reflexive unit matrix showing an ivory color filled square

Order 2

Type

(Set(2) * Set(2)) -> Bool

State Space

(2 * 2) -> 2 = 2⁴ = 16 Configurations
Order two source relation that connects one slate gray circle to another

Original Relation

Order two source matrix showing a 2 * 2 matrix with top right column colored
Same order two source relation for transitive closure

Transitive Closure

Same order two source matrix for transitive closure
Source relation with two ivory arrows between the circles

Reflexive and Reflexive Transitive Closure

Source matrix with the left diagonal colored in ivory
Source relation with a symmetric arrow from the other circle

Symmetric and Symmetric Transitive Closure

Source matrix with the bottom right block colored in ivory
Same order two source relation for transitive closure

All Others

Same order two source matrix for transitive closure

Leibniz’ Theory of Concepts

Leibniz on Intension and Extension

The Algebra of Logic Tradition

Stanley Burris

Origins of the Calculus of Relations

Vaughan Pratt

The Origins of Relation Algebras in the Development and Axiomatization of the Calculus of Relations

Roger D. Maddux

2009

Normal Forms and Reduction for Theories of Binary Relations

Dan Dougherty, Claudio Gutiérrez

First Steps in Pointfree Dependency Theory

J. N. Oliveira

2005

Discovering regularities in databases using canonical decomposition of binary relation

Ali Jaoua, Samir Elloumi, A Hasnah, J Jaam, I Nafkha