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) ∈ ℝ^{2}: x < y}, {(m, n) ∈ ℕ^{2}: 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.
Given a set S, a relation R on S, and x, y, z ∈ S.
A relation is a partial order or poset when it is reflexive, antisymmetric, and transitive. For example, divisibility, {(m, n) ∈ ℕ^{2}: 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.
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}: n divides (a-b)} = {(a, b) ∈ ℤ^{n}: 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|).
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^{-1}A^{-1}.
Proof: ∀A, B, C ∈ M_{n}(ℝ) Reflexive property (A = I^{-1}AI, I is the identity matrix, that is, a square matrix having 1s on the main diagonal, and 0s everywhere else.), Symmetric property (A = P^{-1}BP ⇒ B = PAP^{-1} = (P^{-1})^{-1}AP^{-1}, i.e., B ∼ A for P^{-1}), and Transitive Property (A = P^{-1}BP and B = Q^{-1}CQ for some P, Q ⇒ A = P^{-1}Q^{-1}CQP = QP^{-1}CQP).
Remember that P and Q are invertible matrices of the same order, then (PQ)^{-1} = Q^{-1}P^{-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)
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) ∈ ℤ^{2}: 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 ∈ ℝ}.
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,
Examples.
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∈X}S(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∈Y}S(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.
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|.