1.5 Equivalence classes (Infinite sets)

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$

$-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}.$