> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/220-relation-theory/terms/binary-relations.md). # Binary relations $$ \begin{align} & reflexivity & \forall & x . & & xRx \\ & irreflexivity & \forall & x . & & \lnot xRx \\ & symmetry & \forall & xy . & & xRy \to yRx \\ & asymmetry & \forall & xy . & & xRy \to (\lnot yRx) \\ & antisymmetry & \forall & xy . & & xRy \land yRx \to x = y \\ & transitivity & \forall & xyz . & & xRy \land yRz \to xRz \\ & intransitivity & \forall & xyz . & & xRy \land yRz \to \lnot xRz \\ & linearity & \forall & xy . & & xRy \land yRx \to x = y \end{align} $$ A binary relation on a set is a collection of ordered pairs of the set's elements. A binary relation on a set $$X$$ is a set of ordered pairs of elements of $$X$$; it is a subset of the Cartesian product $$X^2 = X \times X$$. > A binary relation between sets $$X$$ and $$Y$$ is a subset of $$X \times Y$$. The terms *correspondence*, *dyadic relation* and *2-place relation* are synonyms for binary relation. Binary relations are used to model concepts like "is greater than", "is equal to", and similar. The concept of function is defined as a special kind of binary relation. A binary relation is the special case n = 2 of an n-ary relation R ⊆ A1 × … × An, that is, a set of n-tuples where the jth component of each n-tuple is taken from the jth domain Aj of the relation. An example for a ternary relation on Z×Z×Z is " ... lies between ... and ...", containing e.g. the triples (5,2,8), (5,8,2), and (−4,9,−7). The Cartesian product, $$X \times Y$$, from set $$X$$ to set $$Y$$ represents the **full relation** between two sets, where every ordered pair participates in the relation. Any subset of $$X \times Y$$ is called a relation between $$X$$ and $$Y$$. On the other side of the extreme is the **empty relation**, which is an empty set since no elements, let alone ordered pairs, participate. Despite being empty, it is still considered as a relation between two sets. In between these two extremes are all other relations, therefore, any relation $$R$$ from set $$X$$ to $$Y$$ is a subset of the Cartesian product, $$X \times Y$$. Relations may also exist between objects of the same set or between objects of two or more sets. Any subset of $$X \times X$$ is called a relation on $$X$$. Most of these relations are anonymous, some popular ones have a name, and the most popular come with a name and a special symbol attached. Since a relation $$R$$ on $$X$$ is a subset of $$X \times X$$, it is an element of the powerset of $$X \times X$$ i.e. $$R\subseteq \mathcal{P}(X \times X)$$ If $$R$$ is a relation on $$X$$ and $$(x,y)\in R$$ then we also write $$xRy$$ and read it as "*x is in R-relation to y*", or simply, "*x is in relation to y*", if R is understood. A binary relation $$R$$ on the sets $$X$$ and $$Y$$ is an element in their power set: $$R \in \mathfrak{P}(X \times Y)$$ If $$X = Y$$ then we simply say that the binary relation is over $$X$$, or that it is an **endorelation** over $$X$$. $$Rxy$$ or $$xRy$$ denotes a **homogeneous** relation when $$X = Y$$ and a **heterogeneous** relation when $$X \not = Y$$. Binary relations (all relations are transitive and reflexive) | Relation | Sy | vS | Cx | Wf | Jn | Mt | | --------------------- | -- | -- | -- | -- | -- | -- | | Equivalence relation | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | | Preorder (Quasiorder) | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | | Partial order | ✗ | ✓ | ✗ | ✗ | ✗ | ✗ | | Total preorder | ✗ | ✗ | ✓ | ✗ | ✗ | ✗ | | Total order | ✗ | ✓ | ✓ | ✗ | ✗ | ✗ | | Prewellordering | ✗ | ✗ | ✓ | ✓ | ✗ | ✗ | | Well-quasi-ordering | ✗ | ✗ | ✗ | ✓ | ✗ | ✗ | | Well-ordering | ✗ | ✓ | ✓ | ✓ | ✗ | ✗ | | Lattice | ✗ | ✓ | ✗ | ✗ | ✓ | ✓ | | Join-semilattice | ✗ | ✓ | ✗ | ✗ | ✓ | ✗ | | Meet-semilattice | ✗ | ✓ | ✗ | ✗ | ✗ | ✓ | Legend: * Sy: Symmetric * vS: Anti-symmetric * Cx: Connex * Wf: Well-formed * Jn: has join * Mt: has meet ## Reference )