Editing Binary relation (section)

=== Difunctional ===
{{anchor|difunctional}}
The idea of a difunctional relation is to partition objects by distinguishing attributes, as a generalization of the concept of an [[equivalence relation]]. One way this can be done is with an intervening set <math>Z = \{ x, y, z, \ldots \}</math> of [[Indicator (research)|indicator]]s. The partitioning relation <math>R = F G^\textsf{T}</math> is a [[composition of relations]] using {{em|functional}} relations <math>F \subseteq A \times Z \text{ and } G \subseteq B \times Z.</math> [[Jacques Riguet]] named these relations '''difunctional''' since the composition <math>F G^\mathsf{T}</math> involves functional relations, commonly called ''partial functions''.

In 1950 Riguet showed that such relations satisfy the inclusion:<ref>{{cite journal |last1=Riguet |first1=Jacques|author-link=Jacques Riguet|journal=Comptes rendus |date=January 1950 |url=https://gallica.bnf.fr/ark:/12148/bpt6k3182n/f2001.item |language=fr|title=Quelques proprietes des relations difonctionelles|volume=230|pages=1999–2000}}</ref>
: <math display=block>R R^\textsf{T} R \subseteq R</math>

In [[automata theory]], the term '''rectangular relation''' has also been used to denote a difunctional relation. This terminology recalls the fact that, when represented as a [[logical matrix]], the columns and rows of a difunctional relation can be arranged as a [[block matrix]] with rectangular blocks of ones on the (asymmetric) main diagonal.<ref name="Büchi1989">{{cite book|author=Julius Richard Büchi|title=Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions|year=1989|publisher=Springer Science & Business Media|isbn=978-1-4613-8853-1|pages=35–37|author-link=Julius Richard Büchi}}</ref> More formally, a relation <math>R</math> on <math>X \times Y</math> is difunctional if and only if it can be written as the union of Cartesian products <math>A_i \times B_i</math>, where the <math>A_i</math> are a partition of a subset of <math>X</math> and the <math>B_i</math> likewise a partition of a subset of <math>Y</math>.<ref>{{cite journal |last1=East |first1=James |last2=Vernitski |first2=Alexei |title=Ranks of ideals in inverse semigroups of difunctional binary relations |journal=Semigroup Forum |date=February 2018 |volume=96 |issue=1 |pages=21–30 |doi=10.1007/s00233-017-9846-9|arxiv=1612.04935|s2cid=54527913 }}</ref>

Using the notation <math>\{y \mid xRy\} = xR</math>, a difunctional relation can also be characterized as a relation <math>R</math> such that wherever <math>x_1 R</math> and <math>x_2 R</math> have a non-empty intersection, then these two sets coincide; formally <math>x_1 \cap x_2 \neq \varnothing</math> implies <math>x_1 R = x_2 R.</math><ref name="BrinkKahl1997">{{cite book|author1=Chris Brink|author2=Wolfram Kahl|author3=Gunther Schmidt|title=Relational Methods in Computer Science|year=1997|publisher=Springer Science & Business Media|isbn=978-3-211-82971-4|page=200}}</ref>

In 1997 researchers found "utility of binary decomposition based on difunctional dependencies in [[database]] management."<ref>Ali Jaoua, Nadin Belkhiter, Habib Ounalli, and Theodore Moukam (1997) "Databases", pages 197–210 in ''Relational Methods in Computer Science'', edited by Chris Brink, Wolfram Kahl, and [[Gunther Schmidt]], [[Springer Science & Business Media]] {{isbn|978-3-211-82971-4}}</ref> Furthermore, difunctional relations are fundamental in the study of [[bisimulation]]s.<ref>{{Cite book | doi = 10.1007/978-3-662-44124-4_7
| chapter = Coalgebraic Simulations and Congruences| title = Coalgebraic Methods in Computer Science| volume = 8446| pages = 118| series = [[Lecture Notes in Computer Science]]| year = 2014| last1 = Gumm | first1 = H. P. | last2 = Zarrad | first2 = M. | isbn = 978-3-662-44123-7}}</ref>

In the context of homogeneous relations, a [[partial equivalence relation]] is difunctional.