Heterogeneous relation

From Wikipedia, the free encyclopedia
  (Redirected from Difunctional)
Jump to navigation Jump to search

In mathematics, a heterogeneous relation is a subset of a Cartesian product A × B, where A and B are distinct sets. A common example is an incidence structure (P, L, I) where P is a set of points, L a set of lines, and I is relation that holds when a point is on a line. Another example arises in concept analysis where A is a set of "objects" and B is a set of "attributes", and where the meaning of relation RA × B is that object a has attribute b when aRb. A heterogeneous relation has been called a rectangular relation,[1] suggesting that it does not have the square-symmetry of a relation on a set where A = B.

Jacques Riguet wrote of rectangular relations depending on two logical vectors

and . The logical outer product of them generates an n × m logical matrix

Evidently a re-arrangement of rows and columns of a can result in a matrix where all the 1s are in an upper-left rectangle. Some authors write that matrix a corresponds to a rectangle in any relation that contains it.[2] A concept in a relation RA × B is a rectangle in R such that it is not contained in any larger rectangle.

Visualization of heterogeneous relations leans on graph theory: For relations on a set (homogeneous relations), a graph illustrates a corresponding relation. A bipartite graph is used to illustrate a heterogeneous relation. Just as the clique is integral to relations on a set, so bicliques are used to describe heterogeneous relations; indeed, the rectangles in a heterogeneous relation are illustrated through bicliques in the corresponding bipartite graph.

Calculus of relations

Developments in algebraic logic have facilitated usage of binary relations. The calculus of relations includes the algebra of sets, extended by composition of relations and the use of converse relations. The inclusion RS, meaning that aRb implies aSb, sets the scene in a lattice of relations. But since the inclusion symbol is superfluous. Nevertheless, composition of relations and manipulation of the operators according to Schröder rules, provides a calculus to work in the power set of A × B.

  • Proposition: If R is a total relation and RT is its transpose, then where I is the m × m identity relation.
  • Proposition: If R is a surjective relation, then where I is the n × n identity relation.


A difunctional (or regular) relation, defined as a relation R such that


To understand this notion better, it helps to consider a relation as mapping every element xX to a set xR = { yY | xRy }.[3] This set is sometimes called the successor neighborhood of x in R; one can define the predecessor neighborhood analogously.[4] Synonymous terms for these notions are afterset and respectively foreset.[5]

A difunctional relation can then be equivalently characterized as a relation R such that wherever x1R and x2R have a non-empty intersection, then these two sets coincide; formally x1Rx2R ≠ ∅ implies x1R = x2R.[3]

As examples, any function or any functional (right-unique) relation is difunctional; the converse doesn't hold. If one considers a relation R from set to itself (X = Y), then if R is both transitive and symmetric (i.e. a partial equivalence relation), then it is also difunctional.[6] The converse of this latter statement also doesn't hold.

A characterization of difunctional relations, which also explains their name, is to consider two functions f: AC and g: BC and then define the following set which generalizes the kernel of a single function as joint kernel: ker(f, g) = { (a, b) ∈ A × B | f(a) = g(b) }. Every difunctional relation RA × B arises as the joint kernel of two functions f: AC and g: BC for some set C.[7]

Difunctional relations were introduced by Jacques Riguet in 1950.[8]

In automata theory, the term rectangular relation has also been used to denote a difunctional relation. This terminology is justified by the fact that when represented as a logical matrix, the columns and rows of a difunctional relation can be arranged as a block diagonal matrix with rectangular blocks of true on the (asymmetric) main diagonal.[9]

Ferrers type

A strict order on a set is a homogeneous relation arising in order theory. For heterogeneous relations one requires that its logical matrix can be re-arranged to a staircase block form. An algebraic statement required for a Ferrers type relation R is

If any one of the relations is of Ferrer’s type, then all of them are. [10]

Relations of this type were named after N. M. Ferrers by Jacques Riguet[11]

See also


  1. ^ Michael Winter (2007). Goguen Categories: A Categorical Approach to L-fuzzy Relations. Springer. pp. x–xi. ISBN 978-1-4020-6164-6. 
  2. ^ Ali Jaoua, Rehab Duwairi, Samir Elloumi, and Sadok Ben Yahia (2009) "Data mining, reasoning and incremental information retrieval through non enlargeable rectangular relation coverage", pages 199 to 210 in Relations and Kleene algebras in computer science, Lecture Notes in Computer Science 5827, Springer MR2781235
  3. ^ a b c Chris Brink; Wolfram Kahl; Gunther Schmidt (1997). Relational Methods in Computer Science. Springer Science & Business Media. p. 200. ISBN 978-3-211-82971-4. 
  4. ^ Yao, Y. (2004). "Semantics of Fuzzy Sets in Rough Set Theory". Transactions on Rough Sets II. Lecture Notes in Computer Science. 3135. p. 309. doi:10.1007/978-3-540-27778-1_15. ISBN 978-3-540-23990-1. 
  5. ^ Christodoulos A. Floudas; Panos M. Pardalos (2008). Encyclopedia of Optimization (2nd ed.). Springer Science & Business Media. pp. 299–300. ISBN 978-0-387-74758-3. 
  6. ^ William Craig (2006). Semigroups Underlying First-order Logic. American Mathematical Soc. p. 72. ISBN 978-0-8218-6588-0. 
  7. ^ Gumm, H. P.; Zarrad, M. (2014). "Coalgebraic Simulations and Congruences". Coalgebraic Methods in Computer Science. Lecture Notes in Computer Science. 8446. p. 118. doi:10.1007/978-3-662-44124-4_7. ISBN 978-3-662-44123-7. 
  8. ^ J. Riguet (1950) "Quelques proprietes des relations difonctionelles", Comptes Rendus 230: 1999–2000
  9. ^ Julius Richard Büchi (1989). Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions. Springer Science & Business Media. pp. 35–37. ISBN 978-1-4613-8853-1. 
  10. ^ Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. p. 77. ISBN 978-3-642-77968-8. 
  11. ^ J. Riguet (1951) "Les relations de Ferrers", Comptes Rendus 232: 1729,30
  • Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). "Chapter 3: Heterogeneous relations". Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. ISBN 978-3-642-77968-8. 
Retrieved from "https://en.wikipedia.org/w/index.php?title=Heterogeneous_relation&oldid=850125924#Difunctional"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Difunctional
This page is based on the copyrighted Wikipedia article "Heterogeneous relation"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA