Permutation

A permutation of a set \(A\) is a bijection from \(A\) to itself.

Equivalence relation

Let \(A\) be a nonempty set. The relation \(\sim\) on \(A\) is said to be:

• reflexive if \(a \sim a\) for all \(a \in A\)
• symmetric if \(a \sim b\) implies \(b \sim a\) for all \(a,b \in A\)
• transitive if \(a \sim b\) and \(b \sim c\) implies \(a \sim c\) for all \(a,b,c \in A\)

A relation is an equivalence relation if it is reflexive, symmetric, and transitive.

Equivalence class

Let \(A\) be a nonempty set. If \(\sim\) is an equivalence relation on \(A\), then the equivalence class of \(a \in A\) is defined to be \(\{x \in A \mid x \sim a\}\). Elements of the equivalence class of \(a\) are said to be equivalent to \(a\). If \(C\) is an equivalence class, any element of \(C\) is called a representative of the class \(C\).

Partition

A partition of \(A\) is any collection \(\{A_i \mid i \in I\}\) of nonempty subsets of \(A\), where \(I\) is some indexing set, such that

1. \(A = \bigcup_{i=1} A_i\), and
2. \(A_i \cap A_j = \emptyset\) for all \(i,j \in I\) with \(i \ne j\)

i.e., \(A\) is the disjoint union of the sets in the partition.

Proposition 2

Let \(A\) be a nonempty set.

1. If \(\sim\) defines an equivalence relation on \(A\), then the set of equivalence classes of \(\sim\) form a partition of \(A\).
2. If \(\{A_i \mid i \in I\}\) is a partition of \(A\), then there is an equivalence relation on \(A\) whose equivalence classes are precisely the sets \(A_i\), \(i\in I\).

Proof

(1)

By reflexivity, any element \(a \in A\) belongs to an equivalence class of itself.

Now suppose that \(a \in A\) belongs to 2 equivalence classes \(A_1\) and \(A_2\). Let \(x\) and \(y\) be an arbitrary representative of \(A_1\) and \(A_2\), respectively. Then, \(a \sim x\) and \(a \sim y\). By symmetricity and transitivity, \(x \sim y\). Therefore, \(A_1 = A_2\).

Hence, the set of equivalence classes of \(\sim\) form a partition of \(A\). $$\tag*{$\blacksquare$}$$

(2)

For each \(A_i\), define a relation \(\sim_i\) on \(A_i\) so that \(x \sim_i a_i\) if and only if \(x \in A_i\), where \(a_i\) is some element of \(A_i\). \(\sim_i\) is an equivalence relation where the equivalence class is precisely the set \(A_i\).

$$\tag*{$\blacksquare$}$$

Euler \(\varphi\)-function

The Euler \(\varphi\)-function is defined as follows: for \(n \in \mathbb{Z}^+\), let \(\varphi(n)\) be the number of positive integers \(a \le n\) with \(a\) relatively prime to \(n\), i.e., \(gcd(a,n) = 1\).