\( 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 \)

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 \)
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 \( ~ \) instead of \( R \)

equivalence class
Given an equivalence relation \( ~ \) 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 ~ 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 \( R \) on a set \( X \) such that for any \( a , b , c \in X \) we have that:

  • \( a R a \)
  • if \( a R b \) and \( b R a \) then \( a = b \)
  • if \( a R b \) and \( b R c \) then \( a R c \)
And we say that \( X \) is a partially ordered set.

Note that the above three statements equivalently say that \( \le \) is a reflexive, anti-symmetric and transitive relation.

total order
A total order is a partial order
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