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

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.