JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

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) ∈ ℝ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.

Properties of relations

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.

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.

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

Proof: ∀A, B, C ∈ Mn(ℝ) 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.

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:

Partitions

A partition of a set S is a grouping of its elements into non-empty subsets Ai ≠ ∅, 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 Ai which are exhaustive and mutually exclusive. More formally, {Ai ⊆ S : i ∈ I} where I is an indexing set, with satisfies,

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 {Xi}i∈I is a partition of S. Let’s define a relation on S by saying x ∼ y if and only if x, y∈Xi for some i∈I.

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

Bitcoin donation

JustToThePoint Copyright © 2011 - 2023 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.