Relations

Definition. A relation R on a set S is a subset of S x S, that is, a set of ordered pairs. If (a, b) ∈ R, we write a R b.

R is a relation from A to B iff R is a subset of the Cartesian product A x B,written as R ⊆ A x B.

Examples: {(USA, Washington), (China, Beijing), (France, Paris), …}, =, >, ≥, ≤, … {(x, y) ∈ ℝ²: x < y}, {(m, n) ∈ ℕ²: m divides n}. Typically, in these last two examples, we write m < n and m|n instead of m R n if (m, n) ∈ R.

Properties of relations

Given a set S, a relation R on S, and x, y, z ∈ S.

• (i) R is reflexive if x R x for every x in S; otherwise R is nonreflexive. The relations = and ≤ are both reflexive.
• (ii) R is symmetric if whenever x R y then y R x; otherwise, R is nonsymmetric. Equality is symmetric, but ≤ is not (3 ≤ 4 but 4 ≤ 3 is False)
• (iii) R is anti-symmetric if whenever x R y and y R x then x = y. The “less than” relation < is antisymmetric because if a < b, b is not less than a, so the premise of the definition is never satisfied. ≤ is also antisymmetric, too.
• (iv) R is transitive if whenever x R y and y R z then x R z; otherwise, R is nontransitive. The relations =, <, and ≤ are all transitive.

A relation is a partial order or poset when it is reflexive, antisymmetric, and transitive. For example, divisibility, {(m, n) ∈ ℕ²: m divides n} is a partial order: Reflexive (a|a ∀a∈ ℕ), Antisymmetric (if a|b and b|a then a = b), and Transitive (a|b and b|c, then a|c).

A partial order relation that provides a way to compare between any two elements of a set is called a total order relation, that is, ∀ x, y ∈ S, either x R y or y R x (or both). For example, the set of integers over the relation “less than or equal to” is a totally ordered set because for every element a and b in the set of integers, either a ≼ b or b ≼ a.

Equivalence relations

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. It is generally represented by the symbol “∼”.

Examples.

• Let n ∈ ℤ, n ≥ 2, {(a, b) ∈ ℤⁿ: n divides (a-b)} = {(a, b) ∈ ℤⁿ: n | (a-b)} is an equivalence relation, you may often see it as a ∼ b and expressed as “a = b mod n”. Proof. Reflexive property. a R a because n (n ≥ 2) divides 0.
  Symmetric property. a R b ⇨ ∃k ∈ Z: a - b = kn ⇨ b - a = -kn, and therefore, b R a.
  Transitive property. a R b and b R c ⇨ ∃k,l ∈ ℤ: a - b = kn, b - c = ln ⇨ a - c = (a - b) + (b - c) = (k+l)n, and therefore, a R c.

• “is equal to” is an equivalent relation on ℝ as ∀a, b, c ∈ ℝ, ⇨ Reflexive property (a = a), Symmetric property (a = b ⇒ b = a), and Transitive property (a = b, b = c ⇒ a = c).

• ‘Has the same absolute value’ is an equivalence relation on ℂ. More formally, S = ℂ, with z ∼ w ⇔ |z| = |w|.

Proof: ∀a, b, c ∈ ℂ, Reflexivity property (|a| = |a|), Symmetric property (|a| = |b| ⇒ |b| = |a|), and Transitive property (|a| = |b| and |b| = |c| ⇒ |a| = |c|).

• Let S = M_n(ℝ), the set of n × n matrices with real coefficients. We define ∼ on M_n(ℝ) by saying A ∼ B if and only if there exists an invertible matrix P such that A = P^-1BP.

  In linear algebra, an n-by-n square matrix is called invertible if the product of the matrix and its inverse is the identity matrix, that is, AA^-1=I_n. If A and B are two invertible matrices of the same order then (AB)^-1 = B^-1A^-1.

Proof: ∀A, B, C ∈ M_n(ℝ) Reflexive property (A = I^-1AI, I is the identity matrix, that is, a square matrix having 1s on the main diagonal, and 0s everywhere else.), Symmetric property (A = P^-1BP ⇒ B = PAP^-1 = (P^-1)^-1AP^-1, i.e., B ∼ A for P^-1), and Transitive Property (A = P^-1BP and B = Q^-1CQ for some P, Q ⇒ A = P^-1Q^-1CQP = QP^-1CQP).

Remember that P and Q are invertible matrices of the same order, then (PQ)^-1 = Q^-1P^-1.

• Let S be the set of all triangles in a plane, a, b ∈ S, a ∼ b if a and b are similar. Then, ∼ is an equivalence relation on S.

  Two triangles are similar if their corresponding angles are equal.

• Let S = {(a, b) | a, b ∈ ℤ, b ≠ 0}, (a, b), (c, d) ∈ S, (a, b) ∼ (c, d) if their fractions are equal, i.e., ^a⁄_b = ^c⁄_d, that is ad = bc. Then, ∼ is an equivalence relation.

Proof: It is trivially true: reflexivity (a, b) ∼ (a, b) because ab = ba [∴ Commutativity of multiplication]. Symmetric (a, b) ∼ (c, d). ad = bc, then cb = da [∴ Commutativity of multiplication] ⇒ (c, d) ∼ (a, b). Transitivity (a, b) ∼ (c, d) and (c, d) ∼ (e, f). ad = bc and cf = de ⇒ adf = bcf = bde ⇒ afd = bed [∴ Commutativity of multiplication] ⇒ af = be [∴ We can cancel d because d ≠ 0] ⇒ (a, b) ∼ (e, f)

Equivalence Class

Definition. An equivalence class is the name that we give to the subset of S which includes all elements that are equivalent to each other. More formally, give an equivalent relation ∼ on S, and an element x ∈ S, the equivalence class of x, typically denoted by x or [x] is the subset x = {y ∈ S : y ∼ x}.

Examples:

• Suppose that S is the set of all children playing in a garden. Then, if ~ is the equivalent relation ‘of the same age’ children, one equivalence class would be the set of all 7-year-olds, and another the set of all 5-year-olds.

• Suppose that S is the set of all polygons. Then, if ~ is the equivalent relation defined as polygons with the same number of sides. Then, a few examples of equivalences classes would be the set of all triangles, the set of all quadrilaterals, the set of all pentagons, and so on.

• If ~ is the equivalent relation “congruence module n”, n ∈ ℤ, n ≥ 2, {(a, b) ∈ ℤ²: n divides (a-b)}, the equivalence class of 1, 1 = {. . . , −n + 1, 1, n + 1, 2n + 1, . . .};  

• Let S be the set of all polynomials with real coefficients. If f, g ∈ S, let’s define f ~ g if f’ = g’. Then, ~ is an equivalence relation on S. f = {f + c | c ∈ ℝ}.

Partitions

A partition of a set S is a grouping of its elements into non-empty subsets A_i ≠ ∅, in such a way that every element is included in exactly one subset. In other words, it is a collection of non-empty subsets or parts A_i which are exhaustive and mutually exclusive. More formally, {A_i ⊆ S : i ∈ I} where I is an indexing set, with satisfies,

• (i) A_i ≠ ∅, ∀i ∈ I, that is, all the subsets are non-empty. The subsets are the cells of the partition.
• (ii) ∪_i∈I A_i = S, that is, every member of S lies in one of the subsets (exhaustive).
• (iii) A_i ∩ A_j = ∅ ∀i,j∈ I, i≠j, that is, the subsets are disjoint (no overlap). Figure 1.a.  

Examples.

1. {1, 2} and {3} forms a partition of the set {1, 2, 3}.
2. The set of naturals can be partitioned into two sets based on parity. {n ∈ ℕ : n is divisible by 2} and {n ∈ ℕ : n + 1 is divisible by 2}} form a partition of ℕ into odds and evens.
3. Congruence mod n partitions ℤ⁺ into n equivalence classes or partitions. These cells are the residue classes modulo n in ℤ⁺, e.g., congruence mod 3 partitions the integers into 3 equivalence clases: {0, ±3, ±6, ±9, ±12…}, {1±3, 1±6, 1 ±9, ±12…}, and {2±3, 2±6, 2±9, ±12…}.
4. The set of integers can be partitioned into three disjoint sets, Z = −ℕ ∪ {0} ∪ ℕ, where ℕ = {1, 2, 3,… } = Natural Numbers = Positive Integers.

Equivalence Classes Partition.

For any equivalence relation ∼ on a set S, the equivalence classes of the equivalence relation on a set S form or constitute a partition of S. Conversely, for any partition P of S, there is an equivalence relation on S by relating elements if they lie in the same part or subset of the partition.

Basically, we can define an equivalence relation on S by saying x ~ y if and only if x and y are elements in the same part or subset of the partition P. Thus, the notions of equivalence relation and partition are essentially equivalent.

Proof: Suppose that ∼ is an equivalent relation on S. If x∈S, let $\bar{x}$ = S(x) = {y ∈ X | y ∼ x}. Thus, S(x) is the equivalence class of x. By the reflexive property, x ∼ x, so x ∈ S(x) ⇨ S = ∪_x∈XS(x). However, some of the S(x)’s may be identical, so let’s throw out the duplicates.

In other words, we have S = ∪_x∈YS(x) and Y is a subset of S. If x, y∈Y and x≠y, then S(x)≠S(y). ¿Do the remaining S(x), x∈Y intersect?

Suppose x, y∈Y, x≠y, but z∈ S(x)∩S(y). z∈ S(x) ⇨ z ∼ x, and z∈ S(y) ⇨ z ∼ y. x ∼ z (by symmetry) and z ∼ y ⇨ x ∼ y (by transitivity).

Let’s see that S(x)=S(y). First, let’s prove that S(x) ⊆ S(y). Suppose w ∈ S(x), w ∼ x, but we already know that x ∼ y ⇨ w ∼ y (by transitivity) ⇨ w ∈ S(y). Secondly, let’s prove that S(y) ⊆ S(x). Suppose w ∈ S(y), w ∼ y, y ∼ x (by symmetry) ⇨ w ∼ x (by transitivity) ⇨ w ∈ S(x), and by double inclusion, S(x)=S(y) that is a contradiction because we threw out all the duplicates earlier.

Conversely, suppose {X_i}_i∈I is a partition of S. Let’s define a relation on S by saying x ∼ y if and only if x, y∈X_i for some i∈I.

1. (i) Reflexive. If x∈S ⇨ x ∈X_i for some i∈I (every member of S lies in one of the subsets -Partition’s definition ii-). Obviously, x is in the same X_i than itself ⇨ x, x ∈X_i so x ∼ x.
2. (ii) If x ∼ y, then x, y ∈X_i for some i∈I, and obviously y, x ∈X_i, so y ∼ x.
3. (iii) If x ∼ y and y ∼ z, then x, y∈X_i and y, z ∈X_j ⇨ y ∈ X_i∩X_j, but the partition’s subsets are disjoint (Partition’s definition iii) ⇨ X_i = X_j ⇨ x, z ∈X_i ⇨ x ∼ z.

Let r ∈ ℤ, r ≥ 1. We know that n∼m iff r |(n-m) is a equivalent relation. We call $\frac{ℤ}{rℤ}$ = { equivalent classes [n] for r}, and define addition on $\frac{ℤ}{rℤ}$ by [n] + [m] = [n+m]. This operation is well-defined.

Proof. If n ∼ n’ and m ∼ m’ ⇒ n+m ∼ n’+m’. In other words, if r|(n-n’) and r|(m-m’) ⇒ r|(n+m -(n’+m’)) that is evident.

$\frac{ℤ}{rℤ}$ is an Abelian group with this operation, |0| is the neutral element, and -|n|=|-n|.