Editing Binary relation (section)

== Particular relations ==
* ''Proposition'': If <math>R</math> is a [[surjective relation]] and <math>R^\mathsf{T}</math> is its transpose, then <math>I \subseteq R^\textsf{T} R</math> where <math>I</math> is the <math>m \times m</math> identity relation.
* ''Proposition'': If <math>R</math> is a [[serial relation]], then <math>I \subseteq R R^\textsf{T}</math> where <math>I</math> is the <math>n \times n</math> identity relation.

=== 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.

=== Ferrers type ===
A [[strict order]] on a set is a homogeneous relation arising in [[order theory]].
In 1951 [[Jacques Riguet]] adopted the ordering of an [[integer partition]], called a [[Ferrers diagram]], to extend ordering to binary relations in general.<ref>J. Riguet (1951) "Les relations de Ferrers", [[Comptes Rendus]] 232: 1729,30</ref>

The corresponding logical matrix of a general binary relation has rows which finish with a sequence of ones. Thus the dots of a Ferrer's diagram are changed to ones and aligned on the right in the matrix.

An algebraic statement required for a Ferrers type relation R is
<math display="block">R \bar{R}^\textsf{T} R \subseteq R.</math>

If any one of the relations <math>R, \bar{R}, R^\textsf{T}</math> is of Ferrers type, then all of them are.
<ref name="Schmidt p.77">{{cite book|last1=Schmidt|first1=Gunther|last2=Ströhlein|first2=Thomas|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url={{google books |plainurl=y |id=ZgarCAAAQBAJ|paged=277}}|date=2012|publisher=Springer Science & Business Media|isbn=978-3-642-77968-8|authorlink1=Gunther Schmidt |page=77}}</ref>

=== Contact ===
Suppose <math>B</math> is the [[power set]] of <math>A</math>, the set of all [[subset]]s of <math>A</math>. Then a relation <math>g</math> is a '''contact relation''' if it satisfies three properties: 
# <math>\text{for all } x \in A, Y = \{ x \} \text{ implies } xgY.</math>
# <math>Y \subseteq Z \text{ and } xgY \text{ implies } xgZ.</math>
# <math>\text{for all } y \in Y, ygZ \text{ and } xgY \text{ implies } xgZ.</math>
The [[set membership]] relation, <math>\epsilon = </math> "is an element of", satisfies these properties so <math>\epsilon</math> is a contact relation. The notion of a general contact relation was introduced by [[Georg Aumann]] in 1970.<ref>{{cite journal | url=https://www.zobodat.at/publikation_volumes.php?id=56359 | author=Georg Aumann | title=Kontakt-Relationen | journal=Sitzungsberichte der mathematisch-physikalischen Klasse der Bayerischen Akademie der Wissenschaften München | volume=1970 | number=II | pages=67&ndash;77 | year=1971 }}</ref><ref>Anne K. Steiner (1970) [https://mathscinet.ams.org/mathscinet-getitem?mr=0309040 Review:''Kontakt-Relationen''] from [[Mathematical Reviews]]</ref>

In terms of the calculus of relations, sufficient conditions for a contact relation include
<math display="block">C^\textsf{T} \bar{C} \subseteq \ni \bar{C} \equiv C \overline{\ni \bar{C}} \subseteq C,</math> 
where <math>\ni</math> is the converse of set membership (<math>\in</math>).<ref name=GS11/>{{rp|280}}