Skip to content

DA6. Equivalence, Partial Ordering, and Congruence mod m

Task1

Consider the relation R defined on the states of the United Kingdom. State A is related to B if and only if they are connected by roadways, assuming that each state is connected to the other, and to itself by roadways. Explain whether this relation is a partial order or an equivalence relation. Also, discuss the difference between a partial order and an equivalence relation.

Let’s define our relation R, We’ll denote the set of all states in the United Kingdom as S.

\(R = \{(a,b) \in S | a \text{ is connected to } b \text{ by roadways}\}\)

  • Equivalence requires the relation R on set S to be, reflexive, symmetric, and transitive (Neso Academy, 2022).
  • Partial ordering requires the relation R on set S to be, reflexive, antisymmetric, and transitive (Neso Academy, 2022).

Let’s discuss each one of these properties:

  • Reflexive:
    • For each element a in the set S, the pair (a,a) is in the relation.
    • That is, each state is connected to itself by roadways.
    • By the statement of the problem, each state is connected to itself by roadways, so the relation is reflexive.
  • Symmetric:
    • For each pair (a,b) in the relation, the pair (b,a) is also in the relation.
    • That is, if state a is connected to state b by roadways, then state b is also connected to state a.
    • It is true, assuming that those roadways are two-way; then the relation is symmetric.
  • Antisymmetric:
    • For each pair (a,b) in the relation, the pair (b,a) is not in the relation unless a=b.
    • That is, if state a is connected to state b by roadways, then state b is not connected to state a unless it is the same state.
    • This is not true, as it contradicts the symmetric property which is proven true; then the relation is Not antisymmetric.
  • Transitive:
    • If the pair (a,b) and the pair (b,c) are in the relation, then the pair (a,c) is also in the relation.
    • That is, if state a is connected to state b by roadways, and state b is connected to state c, then state a is also connected to state c.
    • This is true, as you can go from state a to state b and then to state c; then the relation is transitive.

By the discussion above, we have proven that the relation R is reflexive, symmetric, and transitive; thus, it is an equivalence relation.

We also proved that the relation R is Not antisymmetric; thus, it is Not a partial ordering.

Task2

How do you define congruence modulo n, where n is any positive integer? Explain with any two examples for n and determine if the congruence relation is a partial ordering.

Two integers a and b are said to be congruent modulo m if a%m = b%m and denoted by \(a \equiv b (mod m)\) iff m divides (a-b).

For any two integers a and b, if a and b are congruent modulo m, then a and b have the same remainder when divided by m and m divides (a-b) which indicates that a-b must be a multiple of m.

So this will generate the following classes:

for m=2, we denote the reminder r

  • for r=0, the class is C0 = {0,2,4,6,8,...}
  • for r=1, the class is C1 = {1,3,5,7,9,...}

In general terms, for any m, and reminder r, The class is C[r] = {r, r+m, r+2m, r+3m, r+4m, ...} where m,r are integers and 0 <= r < m (Mathispower4u, 2022).

References