# 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

[https://en.wikipedia.org/wiki/Binary\_relation](https://en.wikipedia.org/wiki/Binary_relation)

[https://en.wikipedia.org/wiki/Lattice\_(order](https://en.wikipedia.org/wiki/Lattice_\(order)) [https://en.wikipedia.org/wiki/Finitary\_relation](https://en.wikipedia.org/wiki/Finitary_relation) [https://en.wikipedia.org/wiki/Heterogeneous\_relation](https://en.wikipedia.org/wiki/Heterogeneous_relation)
