Editing Binary relation (section)

== Operations ==
=== Union ===
<!---This definition should appear before the closure defs, which refer to it:--->
If <math>R</math> and <math>S</math> are binary relations over sets <math>X</math> and <math>Y</math> then <math>R \cup S = \{ (x, y) \mid xRy \text{ or } xSy \}</math> is the {{em|union relation}} of <math>R</math> and <math>S</math> over <math>X</math> and <math>Y</math>.

The identity element is the empty relation. For example, <math>\leq</math> is the union of < and =, and <math>\geq</math> is the union of > and =.

=== Intersection ===
If <math>R</math> and <math>S</math> are binary relations over sets <math>X</math> and <math>Y</math> then <math>R \cap S = \{ (x, y) \mid xRy \text{ and } xSy \}</math> is the {{em|intersection relation}} of <math>R</math> and <math>S</math> over <math>X</math> and <math>Y</math>.

The identity element is the universal relation. For example, the relation "is divisible by 6" is the intersection of the relations "is divisible by 3" and "is divisible by 2".

=== Composition ===
{{main|Composition of relations}}
If <math>R</math> is a binary relation over sets <math>X</math> and <math>Y</math>, and <math>S</math> is a binary relation over sets <math>Y</math> and <math>Z</math> then <math>S \circ R = \{ (x, z) \mid \text{ there exists } y \in Y \text{ such that } xRy \text{ and } ySz \}</math> (also denoted by <math>R; S</math>) is the {{em|composition relation}} of <math>R</math> and <math>S</math> over <math>X</math> and <math>Z</math>.

The identity element is the identity relation. The order of <math>R</math> and <math>S</math> in the notation <math>S \circ R,</math> used here agrees with the standard notational order for [[composition of functions]]. For example, the composition (is parent of)<math>\circ</math>(is mother of) yields (is maternal grandparent of), while the composition (is mother of)<math>\circ</math>(is parent of) yields (is grandmother of). For the former case, if <math>x</math> is the parent of <math>y</math> and <math>y</math> is the mother of <math>z</math>, then <math>x</math> is the maternal grandparent of <math>z</math>.

=== Converse ===
{{main|Converse relation}}
{{see also|Duality (order theory)}}
If <math>R</math> is a binary relation over sets <math>X</math> and <math>Y</math> then <math>R^\textsf{T} = \{ (y, x) \mid xRy \}</math> is the {{em|converse relation}},<ref>[[Garrett Birkhoff]] & Thomas Bartee (1970) ''Modern Applied Algebra'', page 35, McGraw-Hill</ref> also called {{em|inverse relation}},<ref>[[Mary P. Dolciani]] (1962) ''Modern Algebra: Structure and Method'', Book 2, page 339, Houghton Mifflin</ref> of <math>R</math> over <math>Y</math> and <math>X</math>.

For example, <math>=</math> is the converse of itself, as is <math>\neq</math>, and <math><</math> and <math>></math> are each other's converse, as are <math>\leq</math> and <math>\geq.</math> A binary relation is equal to its converse if and only if it is [[Symmetric relation|symmetric]].

=== Complement ===
{{main|Complementary relation}}
If <math>R</math> is a binary relation over sets <math>X</math> and <math>Y</math> then <math>\bar{R} = \{ (x, y) \mid \neg xRy \}</math> (also denoted by <math>\neg R</math>) is the {{em|complementary relation}} of <math>R</math> over <math>X</math> and <math>Y</math>.

For example, <math>=</math> and <math>\neq</math> are each other's complement, as are <math>\subseteq</math> and <math>\not \subseteq</math>, <math>\supseteq</math> and <math>\not \supseteq</math>, <math>\in</math> and <math>\not \in</math>, and for [[total order]]s also <math><</math> and <math>\geq</math>, and <math>></math> and <math>\leq</math>.

The complement of the [[converse relation]] <math>R^\textsf{T}</math> is the converse of the complement: <math>\overline{R^\mathsf{T}} = \bar{R}^\mathsf{T}.</math>

If <math>X = Y,</math> the complement has the following properties:
* If a relation is symmetric, then so is the complement.
* The complement of a reflexive relation is irreflexive—and vice versa.
* The complement of a [[strict weak order]] is a total preorder—and vice versa.

=== Restriction ===
{{main|Restriction (mathematics)}}
If <math>R</math> is a binary [[homogeneous relation]] over a set <math>X</math> and <math>S</math> is a subset of <math>X</math> then <math>R_{\vert S} = \{ (x, y) \mid xRy \text{ and } x \in S \text{ and } y \in S \}</math> is the {{em|{{visible anchor|restriction relation|Restriction relation|Restriction of a homogeneous relation}}}} of <math>R</math> to <math>S</math> over <math>X</math>.

If <math>R</math> is a binary relation over sets <math>X</math> and <math>Y</math> and if <math>S</math> is a subset of <math>X</math> then <math>R_{\vert S} = \{ (x, y) \mid xRy \text{ and } x \in S \}</math> is the {{em|{{visible anchor|left-restriction relation|Left-restriction relation}}}} of <math>R</math> to <math>S</math> over <math>X</math> and <math>Y</math>.{{clarify|reason=Introduce notational distinction between restriction and left restriction.|date=November 2022}}

If a relation is [[Reflexive relation|reflexive]], irreflexive, [[Symmetric relation|symmetric]], [[Antisymmetric relation|antisymmetric]], [[Asymmetric relation|asymmetric]], [[Transitive relation|transitive]], [[Serial relation|total]], [[Trichotomy (mathematics)|trichotomous]], a [[partial order]], [[total order]], [[strict weak order]], [[Strict weak order#Total preorders|total preorder]] (weak order), or an [[equivalence relation]], then so too are its restrictions.

However, the transitive closure of a restriction is a subset of the restriction of the transitive closure, i.e., in general not equal. For example, restricting the relation "<math>x</math> is parent of <math>y</math>" to females yields the relation "<math>x</math> is mother of the woman <math>y</math>"; its transitive closure does not relate a woman with her paternal grandmother. On the other hand, the transitive closure of "is parent of" is "is ancestor of"; its restriction to females does relate a woman with her paternal grandmother.

Also, the various concepts of [[Completeness (order theory)|completeness]] (not to be confused with being "total") do not carry over to restrictions. For example, over the [[real number]]s a property of the relation <math>\leq</math> is that every [[Empty set|non-empty]] subset <math>S \subseteq \R</math> with an [[upper bound]] in <math>\R</math> has a [[Supremum|least upper bound]] (also called supremum) in <math>\R.</math> However, for the rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation <math>\leq</math> to the rational numbers.

<!---This definition is needed by the closure defs, too, but maybe should better given in an earlier section(?):--->
A binary relation <math>R</math> over sets <math>X</math> and <math>Y</math> is said to be {{em|{{visible anchor|contained in|Containment of relations}}}} a relation <math>S</math> over <math>X</math> and <math>Y</math>, written <math>R \subseteq S,</math> if <math>R</math> is a subset of <math>S</math>, that is, for all <math>x \in X</math> and <math>y \in Y,</math> if <math>xRy</math>, then <math>xSy</math>. If <math>R</math> is contained in <math>S</math> and <math>S</math> is contained in <math>R</math>, then <math>R</math> and <math>S</math> are called {{em|equal}} written <math>R = S</math>. If <math>R</math> is contained in <math>S</math> but <math>S</math> is not contained in <math>R</math>, then <math>R</math> is said to be {{em|{{visible anchor|smaller|Smaller relation}}}} than <math>S</math>, written <math>R \subsetneq S.</math> For example, on the [[rational number]]s, the relation <math>></math> is smaller than <math>\geq</math>, and equal to the composition <math>> \circ ></math>.

=== Matrix representation ===
Binary relations over sets <math>X</math> and <math>Y</math> can be represented algebraically by [[Logical matrix|logical matrices]] indexed by <math>X</math> and <math>Y</math> with entries in the [[Boolean semiring]] (addition corresponds to OR and multiplication to AND) where [[matrix addition]] corresponds to union of relations, [[matrix multiplication]] corresponds to composition of relations (of a relation over <math>X</math> and <math>Y</math> and a relation over <math>Y</math> and <math>Z</math>),<ref>{{cite newsgroup |title=quantum mechanics over a commutative rig |author=John C. Baez |author-link=John C. Baez |date=6 Nov 2001 |newsgroup=sci.physics.research |message-id=9s87n0$iv5@gap.cco.caltech.edu |url=https://groups.google.com/d/msg/sci.physics.research/VJNPMCfreao/TMKt9tFYNwEJ |access-date=November 25, 2018}}</ref> the [[Hadamard product (matrices)|Hadamard product]] corresponds to intersection of relations, the [[zero matrix]] corresponds to the empty relation, and the [[matrix of ones]] corresponds to the universal relation. Homogeneous relations (when <math>X = Y</math>) form a [[matrix semiring]] (indeed, a [[matrix semialgebra]] over the Boolean semiring) where the [[identity matrix]] corresponds to the identity relation.<ref name="droste">Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. {{doi|10.1007/978-3-642-01492-5_1}}, pp. 7-10</ref>