Let’s find the equivalence classes of the following finite set S:
Given we can form the following relation
Note: writing the relation on set in the following ways is equivalent:
This relation, has been given the symbol but it means “the same sign and parity” in this case. For instance, or tells us that one and three are both odd and both have the same sign in set (both positive).
The equivalence classes for this relation are the following sets:
We obtained the above equivalence classes by asking ourselves:
- How is the element related to any other element in the set under the definition of
Since R is defined as “the same sign and same parity,” then we’re really asking ourselves whether has the same sign as any other element in Since all the other elements are positive, then has the equivalence class containing only itself. Another question we would’ve asked ourselves is whether is even or odd. However, given we already know the other elements don’t have the same parity as we conclude that it is the only element in this equivalence class.
In general, an element will always be in its own equivalence class.
- How is the element related to any other element in under the relation
Since has a positive sign and is odd, then any other positive odd element in is related to Hence is related to itself and only. So is our equivalence class. This is also the equivalence class for
- How is related to any other element in under the
Since has a positive sign and is even, then the only other element in S related to this element is
We could’ve chosen to write the above equivalence classes in the following way:
Let’s find the equivalence classes of an infinite set.
Let be the set of all polynomial functions with real coefficients. Given functions we define the relation R as to express that the functions have the same degree.
First, note that the set has elements of the following nature:
If then we can write as
The coefficients are real numbers
There are variables such that the exponent of each variable is a positive integer
The degree of the polynomial function is the highest exponent (power) of the function.
is a function with degree
is a function in degree
are both functions with the degree So we can write since that’s how our relation is defined.
To describe the equivalence class for all polynomial functions of degree from our set
This is the set of all polynomials with real coefficients such that the degree of the function is The coefficient attached to the variable with this degree 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 on set for natural number
Let’s find the equivalence class zero:
By substituting different integer values for we get the equivalence class
So we have that the following equivalence classes are equal:
Since the equivalence classes are equal, it doesn’t matter which values from the set we choose to represent the equivalence class of
We don’t need to be as explicit when we find the other equivalence classes.
Let’s find the equivalence for
So is our desired equivalence class.
Similarly, we can find that the last two equivalence classes
So in summary, we have exactly four equivalence classes; namely:
Recall: we can label (for instance) by any other number in the equivalence class. So we can choose to write the above equivalence classes for as the following
This example has focused on the relation on the set of positive integers, We can generalise this result for any natural number
on set Hence, there will be equivalence classes:
Hence there will always be exactly equivalence classes for the relation
Essentially, we can imagine taking the set of Natural Numbers 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.
[…] 1.5 Relations – Equivalence classes of infinite sets […]