\( n \)-ary relation
An \( n \)-ary relation on the sets \( X_{1} , X_{2} , \ldots , X_{n} \) is a subset \( R \) of their cartesian product, where we say that the relation holds between \( x_{1} , x_{2} , \ldots , x_{n} \) when \( \left ( x_{1} , x_{2} , \ldots , x_{n} \right ) \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 \( \left ( x , y \right ) \in R \), then we write \( x R y \) 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 \[ \operatorname{ rev } \left( R \right) := \left\{ \left( y, x \right) : \left( x, y \right) \in R \right\} \]
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} := \left \lbrace a \in X : a \in R \right \rbrace \)
reflexive relation
Given a binary relation \( R \) on \( X \), we say it is reflexive when every element of \( X \) is related to itself. Symbolically \( \forall x \in X , x R x \)
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 \( x R y \) then \( y R x \)
Anti-Symmetric Relation
Given a binary relation \( R \) on \( X \), we say it is anti-symmetric when for any \( x , y \in X \), if \( x R y \) and \( y R x \) 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 \( x R y \) then it's false that \( y R x \).
Transitive Relation
Given a binary relation \( R \) on \( X \), we say it is transitive if for any \( x , y , z \in X \) if \( x R y \) and \( y R z \) then \( y R x \)
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 \neq y \) then \( x R y \) or \( y R x \)
Strongly Connected Relation
Given a binary relation \( R \) on \( X \), we say it is strongly connected if for any \( x, y \in X \) \( x R y \) or \( y R x \)
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 \( \left \lbrace y \in X : y \sim x \right \rbrace \)
Congruences induce a Equivalence Relation
Fix \( n \in \mathbb{N}_{1} \), then relation on \( \mathbb{Z} \) by \( a R b \) if and only if \( a \% n = b \% n \) defines an equivalence relation

Given any \( a \in G \), then clearly \( a \% n = a \% n \) so that \( a R a \), if \( a R b \), then \( a \% n = b \% n \) and then \( b \% n = a \% n \), finally if \( a \% n = b \% n \) and \( b \% n = c \% n \) therefore \( a \% n = c \% 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 \( \lt \) on a set \( X \) such that \( \lt \) is transitive and asymmetric.
Every Partial Order Admits a Strict Partial Order
Suppose that \( \left( X , \le \right) \) is a partial order, then there exists a relation \( \lt \) such that \( \left( X, \lt \right) \) is a partial order such that \[ a \lt b \iff \left( a \le b \land a \neq b \right) \]
Consider the partial order \( \left( X, \le \right) \), since \( \le \) is a collection of tuples we just need to consider \( \lt = \le \setminus \left\{ \left( x, x \right) : x \in X \right\} \)
Comparable
Suppose \( R \) is a partial order, then elements \( a, b \in R \) are said to be comparable if \( a R b \) or \( b R a \), 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
well ordering
Every set \( X \) can be well ordered
TODO
The Smallest Element of a Set is Unique
Supose that \( \left( S, \le \right) \) 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.