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/Lattice_(order) https://en.wikipedia.org/wiki/Finitary_relation https://en.wikipedia.org/wiki/Heterogeneous_relation