$$ n$$-ary relation

An $$ n$$-ary relation on the sets $$ {X}_{1},{X}_{2},\dots ,{X}_{n}$$ is a subset $$ R$$ of their cartesian product, where we say that the relation holds between $$ {x}_{1},{x}_{2},\dots ,{x}_{n}$$ when $$ ({x}_{1},{x}_{2},\dots ,{x}_{n})\in R$$

Unary Relation

A unary relation $$ R$$ on X is a $$ 1$$-ary relation

Binary Relation

A binary relation $$ R$$ is a $$ 2$$-ary relation, when $$ (x,y)\in R$$, then we write $$ xRy$$ to say that $$ x$$ is related to $$ y$$.

Note: *A binary relation on $$ X\times X$$ is stated simply as a relation on $$ X$$*

The Reverse of a Binary Relation

Suppose that $$ R$$ is a binary relation then
$$$\mathrm{rev}\left(R\right):=\{(y,x):(x,y)\in R\}$$$

set filtered by a relation

Suppose that $$ X$$ is a set, and that $$ R$$ is a unary relation on $$ X$$, then we define $$ {X}^{R}:=\{a\in X:a\in R\}$$

reflexive relation

Given a binary relation $$ R$$ on $$ X$$, we say it is reflexive when every element of $$ X$$ is related to itself. Symbolically $$ \mathrm{\forall}x\in X,xRx$$

symmetric relation

Given a binary relation $$ R$$ on $$ X$$, we say it is symmetric if the relation goes both ways, that is for any $$ x,y\in X$$ if $$ xRy$$ then $$ yRx$$

Anti-Symmetric Relation

Given a binary relation $$ R$$ on $$ X$$, we say it is anti-symmetric when for any $$ x,y\in X$$, if $$ xRy$$ and $$ yRx$$ we have that $$ x=y$$

Asymmetric Relation

Given a binary relation $$ R$$ on $$ X$$, we say it is **asymmetric** when for any $$ x,y\in X$$, if $$ xRy$$ then it's false that $$ yRx$$.

Transitive Relation

Given a binary relation $$ R$$ on $$ X$$, we say it is transitive if for any $$ x,y,z\in X$$ if $$ xRy$$ and $$ yRz$$ then $$ yRx$$

Equivalence Relation

An equivalence relation is a reflexive, symmetric and transitive relation

when $$ R$$ is an equivalence relation, we denote it by $$ \sim $$ instead of $$ R$$

Connected Relation

Given a binary relation $$ R$$ on $$ X$$, we say it is **connected** if for any $$ x,y\in X$$ if $$ x\ne y$$ then $$ xRy$$ or $$ yRx$$

Strongly Connected Relation

Given a binary relation $$ R$$ on $$ X$$, we say it is **strongly connected** if for any $$ x,y\in X$$ $$ xRy$$ or $$ yRx$$

Equivalence Class

Given an equivalence relation $$ \sim $$ an equivalence class is a complete set of equivalent elements, which we denote by $$ \left[x\right]$$ which is defined to be the set $$ \{y\in X:y\sim x\}$$

Congruences induce a Equivalence Relation

Fix $$ n\in {\mathbb{N}}_{1}$$, then relation on $$ \mathbb{Z}$$ by $$ aRb$$ if and only if $$ a\mathrm{\%}n=b\mathrm{\%}n$$ defines an equivalence relation

Given any $$ a\in G$$, then clearly $$ a\mathrm{\%}n=a\mathrm{\%}n$$ so that $$ aRa$$, if $$ aRb$$, then $$ a\mathrm{\%}n=b\mathrm{\%}n$$ and then $$ b\mathrm{\%}n=a\mathrm{\%}n$$, finally if $$ a\mathrm{\%}n=b\mathrm{\%}n$$ and $$ b\mathrm{\%}n=c\mathrm{\%}n$$ therefore $$ a\mathrm{\%}n=c\mathrm{\%}n$$

Partial Order

A partial order is a binary relation denoted by $$ \le $$ on a set $$ X$$ such that $$ \le $$ is reflexive, anti-symmetric and transitive relation.

Strict Partial Order

A strict partial order is a binary relation denoted by $$ <$$ on a set $$ X$$ such that $$ <$$ is transitive and asymmetric.

Every Partial Order Admits a Strict Partial Order

Suppose that $$ (X,\le )$$ is a partial order, then there exists a relation $$ <$$ such that $$ (X,<)$$ is a partial order such that
$$$a<b\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}(a\le b\wedge a\ne b)$$$

Consider the partial order $$ (X,\le )$$, since $$ \le $$ is a collection of tuples we just need to consider $$ <=\le \setminus \{(x,x):x\in X\}$$

Comparable

Suppose $$ R$$ is a partial order, then elements $$ a,b\in R$$ are said to be **comparable** if $$ aRb$$ or $$ bRa$$, otherwise they are said to be **incomparable**

With the strict partial order $$ \subset $$ we can see that $$ \left\{1\right\}$$ and $$ \left\{2\right\}$$ are incomparable.

Total Order

A total order is a partial order which is strongly connected.

well order

A well order on a set $$ S$$ is a total order on $$ S$$ along with the property that every non-empty subset of $$ S$$ has a least element under this ordering

The Smallest Element of a Set is Unique

Supose that $$ (S,\le )$$ is a partial order, then the smallest element is unique

Suppose that there are two smallest elements $$ a,b\in S$$ since $$ a$$ is the smallest then $$ a\le b$$ and since $$ b$$ is the smallest then $$ b\le a$$ by transitivity $$ a=b$$ and so the smallest element is unique.