Let’s find the equivalence classes of the following finite set S:

Given \(S = \{ -1, 1, 2, 3, 4 \},\) we can form the following relation \(R = \{ (-1, -1), (1,1), (2,2), (3,3), (4,4), (1,3), (3,1), (2,4), (4,2) \}.\)

Note: writing the relation \(R\) on set \(S\) in the following ways is equivalent:

\[-1R-1, 1R1, 2R2, 3R3, 4R4, 1R3, 3R1, 2R4, 4R2\]

or

\[-1\le -1, 1 \le1, 2 \le2, 3  \le3, 4 \le4, 1 \le 3, 3 \le 1, 2 \le 4, 4 \le 2\]

This relation, \(R\) has been given the symbol \(\le\) but it means “the same sign and parity” in this case. For instance, \((1,3)\) or \(1 \le 3\) tells us that one and three are both odd and both have the same sign in set \(A\) (both positive).

The equivalence classes for this relation are the following sets:

\[\{ -1 \}, \{ 1, 3\} \text{ and } \{2, 4 \}\]

We obtained the above equivalence classes by asking ourselves:

• How is the element \(-1\) related to any other element in the set \(S\) under the definition of \(R?\)

Since R is defined as “the same sign and same parity,” then we’re really asking ourselves whether \(-1\) has the same sign as any other element in \(S.\) Since all the other elements are positive, then \(-1\) has the equivalence class containing only itself. Another question we would’ve asked ourselves is whether \(-1\) is even or odd.  However, given we already know the other elements don’t have the same parity as \(-1,\) we conclude that it is the only element in this equivalence class.

In general, an element \(a \in A\) will always be in its own equivalence class.

• How is the element \(1\) related to any other element in \(S\) under the relation \(R?\)

Since \(1\) has a positive sign and is odd, then any other positive odd element in \(S\) is related to \(1.\) Hence \(1\) is related to itself and \(3\) only. So \(\{1, 3\}\) is our equivalence class. This is also the equivalence class for \(3\)

• How is \(2\) related to any other element in \(S\) under the \(R?\)

Since \(2\) has a positive sign and is even, then the only other element in S related to this element is \(4.\)

We could’ve chosen to write the above equivalence classes in the following way:

\[[1] = [3] = \{ 1, 3\}\]

\[[2] = [4] = \{ 2, 4\}\]

\[[1] = \{ 1\}\]

Let’s find the equivalence classes of an infinite set.

Let \(P\) be the set of all polynomial functions with real coefficients. Given functions \(f(x), g(x) \in P,\) we define the relation R as \(f(x) R g(x)\) to express that the functions have the same degree.

First, note that the set \(P\) has elements of the following nature:

If \(h(x) \in P,\) then we can write as \(h(x) = a_0 + a_1 x_1  + a_2 x_2 ^ 2 + a_3 x_3 ^3 + .... + a_n x_n ^ n\)

The coefficients are real numbers \(a_0, a_1, a_2, a_3, ..., a_n \in \mathbb{ R }\)

There are variables \(x_1, x_2, x_3, .... , x_n\) such that the exponent of each variable is a positive integer \(n \in \{ 0, 1, 2, ...., n \}\)

The degree of the polynomial function is the highest exponent (power) of the function.

For instance,

\(q(x) = 0\) is a function with degree \(0\)

\(h(x) = \frac{8}{79} + x_1 ^3+ \pi x_2 ^ 7\) is a function in \(P\) degree \(7\)

\(f(x) = x^2 , g(x) = 3 x + \sqrt(7)x^2\) are both functions with the degree \(2.\) So we can write \(f(x) R g(x)\) since that’s how our relation is defined.

To describe the equivalence class for all polynomial functions of degree \(3\) from our set \(P:\)

\[\{ a_0 +a_1 x_1 + a_2 x_2^2 +a_3 x_3^3 : a_0, a_1, a_2 \in \mathbb{R}, a_3 \in \mathbb{ R }- 0 \}\]

This is the set of all polynomials with real coefficients such that the degree of the function is \(3.\) The coefficient attached to the variable with this degree \(x_i ^3\) can have ANY real number EXCEPT zero as its coefficient.

Let’s look at another example of equivalence classes on an infinite set:

We want to find the equivalence classes of the relation \(\equiv \text {(mod) } 4\) on set  \(\mathbb{ Z },\) for natural number \(n \in \mathbb{ N}.\)

Let’s find the equivalence class zero:

\[[0] = \{ x \in \mathbb{ Z} : x \equiv 0 \text {(mod) } 4 \}\]

\[[0] = \{ x \in \mathbb{ Z} : 4 | (x - 0) \}\]

\[[0] = \{ x \in \mathbb{ Z} : 4 | x \}\]

\[[0] = \{ x \in \mathbb{ Z} :  4p = x \text { for some p} \in \mathbb{ Z } \}\]

By substituting different integer values for \(p\) we get the equivalence class \([0] = \{ ..., -12, -8, -4, 0, 4, 8, 12, ...\}\)

So we have that the following equivalence classes are equal:

\[[0] = [4] = [-4] = [8] = [-8] = ....\]

Since the equivalence classes are equal, it doesn’t matter which values from the set \(\{ ..., -12, -8, -4, 0, 4, 8, 12, ...\}\) we choose to represent the equivalence class of \([0].\)

We don’t need to be as explicit when we find the other equivalence classes.

Let’s find the equivalence for \([1]:\)

\[[1] = \{ x \in \mathbb{ Z} : 4 | (x - 1) \}\]

\[[1] = \{ x \in \mathbb{ Z} :  4p = x - 1 \text { for some p} \in \mathbb{ Z } \}\]

\[[1] = \{ ..., -11, -7, -3, 1, 5, 9, 13, ...\}\]

So \([1] = [5] = [9] = [13] = ... = \{ ..., -11, -7, -3, 1, 5, 9, 13, ...\}\) is our desired equivalence class.

Similarly, we can find that the last two equivalence classes \(\equiv \text{ (mod)} 4:\)

\[[2] = \{ ..., -10, -6, -2, 2, 6, 10, 14, ... \}\]

\[[3] = \{ ..., -9, -5, -1, 3, 7, 11, 15, ...\}\]

So in summary, we have exactly four equivalence classes; namely:  \([0], [1], [2], [3]\)

Recall: we can label \([2]\) (for instance) by any other number in the equivalence class. So we can choose to write the above equivalence classes for \(\equiv \text{ (mod)} 4\) as the following\(\text{ : } [4], [-11], [2], [3]\)

This example has focused on the relation \(\equiv \text{ (mod)} 4\) on the set of positive integers, \(\mathbb{ N }.\) We can generalise this result for any natural number \(n \in \mathbb{ N}.\)

\(\equiv \text {(mod) } n\) on set  \(\mathbb{ Z }.\) Hence, there will be \(n\) equivalence classes: \([0], [1], [2], ..., [n-1]\)

Hence there will always be exactly \(n\) equivalence classes for the relation \(\equiv \text{ (mod)}4 \text{ on } \mathbb{ N}.\)

Essentially, we can imagine taking the set of Natural Numbers \(\mathbb{ N}\) and divided it into four sets:

• I put in some of the numbers to expect in each congruence class. Note, however, that in reality these sets are infinite.