n -ary relation
An n -ary relation on the sets X 1 , X 2 , … , X n is a subset R of their cartesian product, where we say that the relation holds between x 1 , x 2 , … , x n when ( x 1 , x 2 , … , x n ) ∈ 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 ) ∈ R , then we write x R y to say that x is related to y .

Note: A binary relation on X × X is stated simply as a relation on X

The Reverse of a Binary Relation
Suppose that R is a binary relation then rev ⁡ ( R ) := { ( y , x ) : ( x , y ) ∈ 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 ∈ X : a ∈ 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 ∀ x ∈ 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 ∈ 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 ∈ 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 ∈ 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 ∈ 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 ∼ instead of R

Connected Relation
Given a binary relation R on X , we say it is connected if for any x , y ∈ X if x ≠ 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 ∈ X x R y or y R x
Equivalence Class
Given an equivalence relation ∼ an equivalence class is a complete set of equivalent elements, which we denote by [ x ] which is defined to be the set { y ∈ X : y ∼ x }
Congruences induce a Equivalence Relation
Fix n ∈ N 1 , then relation on Z by a R b if and only if a % n = b % n defines an equivalence relation

Given any a ∈ 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 ≤ on a set X such that ≤ 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 , ≤ ) is a partial order, then there exists a relation < such that ( X , < ) is a partial order such that a < b ⟺ ( a ≤ b ∧ a ≠ b )
Consider the partial order ( X , ≤ ) , since ≤ is a collection of tuples we just need to consider <=≤ ∖ { ( x , x ) : x ∈ X }
Comparable
Suppose R is a partial order, then elements a , b ∈ 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 ⊂ we can see that { 1 } and { 2 } 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 ( S , ≤ ) is a partial order, then the smallest element is unique
Suppose that there are two smallest elements a , b ∈ S since a is the smallest then a ≤ b and since b is the smallest then b ≤ a by transitivity a = b and so the smallest element is unique.