The Cartesian Product

The Cartesian product of two sets $A$ and $B$, denoted $A \times B$, is the set of all possible ordered pairs $(a, b)$, where the first element $a$ belongs to $A$, and the second element $b$ belongs to $B$.

Formally, we write: $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$. Example: Let $A = \{1, 2\}$ and $B = \{\text{Red, Blue}\}$. $A \times B = \{(1, \text{Red}), (1, \text{Blue}), (2, \text{Red}), (2, \text{Blue})\}$

The Order Matters: Because these are ordered pairs, $A \times B \neq B \times A$ (unless $A = B$ or one is empty). For instance, $(\text{Red}, 1)$ is an element of $B \times A$, but it is not an element of $A \times B$.

We can generalize this to the Cartesian product of $n$ sets: $\prod_{i=1}^n A_i = A_1 \times A_2 \times \dots \times A_n = \{(a_1, a_2, \dots, a_n) \mid a_i \in A_i\}$

When we multiply a set by itself $n$ times, we use exponential notation: $A^n$.

Geometric Intuition: René Descartes invented this concept to link algebra to geometry. The 2D coordinate plane is simply $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$, which is the set of all $(x, y)$ coordinate pairs!

$\vert{} A \times B\vert{} = \vert{}A\vert{} \vert{}B\vert{} = 3 \times 2 = 6.$

It is written in latex as \prod_{i=1}^n A_i.

Mathematical Relations

A Cartesian product generates every possible pairing. But what if we only care about pairs that share a specific property?

Definition: A relation $R$ from set $A$ to set $B$ is any subset of the Cartesian product $A \times B$. If the relation is strictly within a single set $S$, we say $R$ is a relation on $S$ (meaning $R \subseteq S \times S$).

If an ordered pair $(a, b)$ belongs to the relation $R$, we write $aRb$ or $a \sim b$, read as “$a$ is related to $b$”.

Examples of Relations:

Country/Capital: $S = \{(\text{USA}, \text{Washington}), (\text{China}, \text{Beijing}), (\text{France}, \text{Paris}), (\text{Spain}, \text{Madrid}), \cdots \}$.
$S = \mathbb{N}$. The relation “$<$” (less than). $R = \{(x, y) \in \mathbb{N}^2 \mid x < y\}$. Thus, $2 \sim 5$ because $(2, 5) \in R$.
$S = \mathbb{N}$. The relation “$\le$” (less than or equal). $R = \{(x, y) \in \mathbb{N}^2 \mid x \le y\}$. Thus, $2 \sim 2$ because $(2, 2) \in R$.
The relation “$\vert{}$” (divides). $R = \{(m, n) \in \mathbb{Z}^2 \mid \exists k \in \mathbb{Z} \text{ such that } n = mk\}$. Thus, $3 \sim 12$, but $3 \nsim 14$.

Typically, in these last examples, we write $m \gt n$, $m \ge n$ and $m \vert{} n$ instead of $m \sim n$ if $(m, n) \in R$.

Properties of Relations on a Set $S$

Let $R$ be a relation on a set $S$. We can classify $R$ based on how elements interact:

Reflexive: Every element of the set $S$ is related or linked to itself. $\forall x \in S$, $x \sim x$. Otherwise, $R$ is said to be non-reflexive.
Example: “$\le$” is reflexive because $3 \le 3$. “$<$” is NOT reflexive because 3 is not strictly less than 3.
Symmetric: Order can be reversed. If when a first element is related to a second then the reverse is also true, that is, the second element is related to the first. If $x \sim y$, then $y \sim x$.
Examples: Equality “$=$” is symmetric. “Is the sibling of” is symmetric. “$<$” is NOT symmetric because $2 < 5$ does not mean $5 < 2$.
Antisymmetric: If two elements relate in both directions, they must be the exact same element. If $x \sim y$ and $y \sim x$, then $x = y$.
Example: “$\le$” is antisymmetric. If $a \le b$ and $b \le a$, then $a=b$. The divides relation in a set of positive integer is anti-symmetric, too.
Transitive: Chain links hold. If $x \sim y$ and $y \sim z$, then $x \sim z$.
Example: “$=$”, “$<$”, and “$\le$” are all transitive.

A relation is a partial order when it is reflexive, antisymmetric, and transitive. For example, $(\mathbb{R}, \le)$ and $(\mathbb{N}, \text{ divisibility}) = \{(m, n) \in \mathbb{N}^2: m \text{ divides } n\}$ are good examples. The set of subsets of a given set (its power set, say $P(S)$) ordered by inclusion is another example.

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, $\forall x, y \in S$, either $x \sim y$ or $y \sim 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 \le b$ or $b \le a$.

Equivalence Relations

In mathematics, we frequently want to group different things together if they share a core property. We do this using a specific type of relation.

Definition: An equivalence relation is a binary relation that is Reflexive, Symmetric, and Transitive. It acts as a generalized version of “equals”.

Deep Algebraic Examples

1. Constructing Integers and Rational Numbers

We could define an equivalence relation on the set of all ordered pairs of natural numbers $(a, b), a, b \in \mathbb{N}$ as follows: $(a, b) \sim (c, d) \iff a + d = c + b$. The set of integers is the set of all equivalence classes of such ordered pairs. $\mathbb{Z} = \{ [a, b]: (a, b) \in \mathbb{N}^2\}$

We can define integer addition and multiplication as two maps $+: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}, \cdot: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$,: $[(a, b)] + [(c, d)] = [(a + c, b + d)], [(a, b)] \cdot [(c, d)] = [(ac + bd, ad + bc)]$.

Fractions like $\frac{1}{2}$, $\frac{2}{4}$, and $\frac{50}{100}$ look visually different, but they represent the exact same mathematical quantity. In formal mathematics, we define the rational numbers by creating an equivalence relation on pairs of integers.

Let $S = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$. This is the set of all ordered pairs of integers where the second integer (the denominator) is not zero. We define our relation as follows: $(a, b) \sim (c, d) \iff ad = bc$

Intuition: We are simply formalizing cross-multiplication. We want $\frac{a}{b} = \frac{c}{d}$, which algebraically means $ad = bc$. By defining it this way, we avoid division entirely and rely strictly on integer multiplication!

Proof that this is an equivalence relation:

Reflexive: $(a, b) \sim (a, b)$ because $ab = ba$ (integer multiplication is commutative).
Symmetric: If $(a, b) \sim (c, d)$, then $ad = bc$. By commutativity, we can rewrite this as $cb = da$, which exactly means $(c, d) \sim (a, b)$.
Transitive: Suppose $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$. This gives us two equations:$ad = bc$ and $cf = de$

Multiply the first equation by $f$ and the second equation by $b$: $adf = bcf \quad \text{and} \quad bcf = bde$

Because both equal $bcf$, we can set them equal to each other: $adf = bde$

Since $d \neq 0$ (by our initial definition of the set $S$), we can divide both sides by $d$ to yield $af = be$. This proves that $(a, b) \sim (e, f)$.

Because it satisfies all three properties, it is an equivalence relation. The rational numbers ($\mathbb{Q}$) are defined strictly as the set of all equivalence classes of these ordered pairs. Typically, we choose the fully simplified irreducible fraction (where $a$ and $b$ share no common factors) as the “representative” of the class.

2. Matrix Similarity in Linear Algebra

Let $M_n(\mathbb{R})$ be the set of all $n \times n$ square matrices with real coefficients. We say that matrix $A$ is similar to matrix $B$ ($A \sim B$) if there exists an invertible matrix $P$ such that: $A = P^{-1}BP$

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}$.

Geometric Intuition: Why do we care about similar matrices? In linear algebra, two similar matrices represent the exact same linear transformation (like a rotation or a sheer) occurring in space, just viewed from the perspective of two different coordinate systems (basis vectors). The matrix $P$ acts as the “translator” between the two perspectives.

Proof of Equivalence:

For any matrices $A, B, C \in M_n(\mathbb{R})$:

Reflexive: $A = I^{-1}AI$, where $I$ is the identity matrix. Since $I$ is invertible, $A \sim A$.
Symmetric: If $A = P^{-1}BP$, we can multiply on the left by $P$ and on the right by $P^{-1}$ to isolate $B$: $B = PAP^{-1} = (P^{-1})^{-1} A (P^{-1})$. Since $P^{-1}$ is also an invertible matrix, $B \sim A$.
Transitive: If $A = P^{-1}BP$ and $B = Q^{-1}CQ$ for some invertible matrices $P$ and $Q$, substitute $B$ into the first equation: $A = P^{-1}(Q^{-1}CQ)P = (P^{-1}Q^{-1})C(QP)$

Because the inverse of a matrix product reverses the order ($(QP)^{-1} = P^{-1}Q^{-1}$), we get: $A = (QP)^{-1} C (QP)$. Since the product of two invertible matrices ($QP$) is also an invertible matrix, $A \sim C$.

3. Calculus: Functions and Derivatives

Let $S$ be the set of all differentiable functions mapping $\mathbb{R} \to \mathbb{R}$. Let’s define a relation where two functions are related if their derivatives are identical: $f \sim g \iff f'(x) = g'(x)$

This is trivially an equivalence relation (since equality of derivatives is reflexive, symmetric, and transitive). But what do the equivalence classes look like?

If $f'(x) = g'(x)$, it means the difference between their derivatives is zero: $\frac{d}{dx}[f(x) - g(x)] = 0$

In calculus, if a derivative is zero everywhere, the function must be a constant. Therefore, $f(x) - g(x) = C$, or $f(x) = g(x) + C$.

This means the equivalence class of a function $f$ is the family of all functions that are vertical shifts of $f$. This is the rigorous foundation of the indefinite integral! When you evaluate $\int f'(x) dx = f(x) + C$, you are not returning a single function; you are returning an entire equivalence class of functions.

4. Other Standard Equivalence Relations

Trivial Relations: For any set $A$, equality ($a = b$) is the strictest equivalence relation. Conversely, the universal relation ($A \times A$), where everything is related to everything, is the loosest.
Absolute Value: On the set of complex numbers ($\mathbb{C}$), having the same absolute value ($z \sim w \iff \vert{}z\vert{} = \vert{}w\vert{}$) is an equivalence relation. Geometrically, the equivalence classes form concentric circles centered at the origin of the complex plane.
Geometric Similarity: On the set of all triangles in a plane, two triangles are related if they are similar (corresponding angles are equal and sides are proportional).
Congruence Modulo $n$: On the integers $\mathbb{Z}$, for any $n \ge 2$, we define $a \sim b \iff n \mid (a-b)$. This is written as $a \equiv b \pmod{n}$. It groups integers into exactly $n$ distinct equivalence classes based on their remainders when divided by $n$. This is the basis of “clock arithmetic”.

Proof.

Reflexive. $a \sim a$ because $n \text{ divides } 0$.
Symmetric. $a \sim b \implies \exist k \in \mathbb{Z}: a - b = kn \implies b - a = -kn$, and therefore, $b \sim a$.
Transitive. Suppose $a \sim b$ and $b \sim c$. Then, $\exist k, l \in \mathbb{Z}: a - b = kn, b - c = ln \implies a - c = (a - b) + (b - c) = (k+l)n$, and therefore, $a \sim c$.

5. Counterexamples: When Relations Fail

To truly understand equivalence relations, we must look at relations that fail the test.

Inequalities ($<$ and $>$): The relation “greater than” on $\mathbb{R}$ is transitive, but it is neither reflexive nor symmetric. $2 \ngtr 2$, and $5 > 3$ does not imply $3 > 5$.
Weak Inequalities ($\le$ and $\ge$): These are reflexive and transitive, but they fail to be symmetric. $2 \ge 1$ is true, but $1 \ge 2$ is false. These form Partial Orders, not Equivalence Relations.
Human Relationships - “Is the brother of”: Let $S$ be the set of all humans. It is not reflexive: John cannot be his own brother. It is not symmetric: If John is the brother of Eva, Eva is not the brother of John (she is his sister). “Is the sibling of” is not transitive: If John is the brother of Eva, and Eva is the sister of John, John is not the brother of John.
Human Relationships - “Loves”: The relation $x \sim y \iff \text{x loves y}$ fails on all accounts. People do not always love themselves (Some people do not love themselves), unrequited love exists (fails symmetry), and if Alice loves Bob, and Bob loves Charlie, Alice does not necessarily love Charlie (fails transitivity).

Equivalence Class

Definition. An equivalence class is a subset of S which includes all elements that are related or equivalent to each other by some equivalence relation. More formally, give an equivalent relation ∼ on S, and an element x \in S, the equivalence class of x, typically denoted by x or [x] is the subset x = {y \in S : y ∼ x}, and each element of the set is called a representative of the equivalence class.

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.
Let A be any set and let be R the equality =. \forall a \in A, [a] = {b \in A | a = b} = {a}
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 \in \mathbb{Z}, n ≥ 2, {(a, b) \in \mathbb{Z}^2: n divides (a-b)}, the equivalence class of 1, 1 = {. . . , −n + 1, 1, n + 1, 2n + 1, . . .}; 2 = {. . . , −n + 2, 2, n + 2, 2n + 2, . . .};
Let S be the set of all polynomials with real coefficients. If f, g \in S, let’s define f ~ g ↭ f’ = g’. Then, ~ is an equivalence relation on S. f = [f] = {g \in S : f’ = g’} = {g \in S : (f - g)’ = 0} = {f + c | c \in ℝ}.

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 (whose union is the entire set) and mutually exclusive (they are disjoint subsets). More formally, {A_i ⊆ S : i \in I} where I is an indexing set, with satisfies,

A_i ≠ ∅, \forall i \in I, that is, all the subsets are non-empty. The subsets are the cells of the partition.
∪_i\inI A_i = S, that is, every member of S lies in one of the subsets. They are exhaustive, i.e., their union is the entire set.
A_i ∩ A_j = ∅ \forall i,j\in I, i≠j, that is, they are disjoint subsets (they do no overlap). Figure 1.a.

Examples.

{1, 2} and {3} forms a partition of the set {1, 2, 3}. {1, 2}, {3, 5, 7}, {4, 6} forms a partition of the set {1, 2, 3, 4, 5, 6, 7}. Finally, {A, E, I, O, U}, {B, C, D, F, G, J, K, L, M, N, P, Q, S, T, V, X, Z} and {H, R, W, Y} forms a partition of the English alphabet.
The set of naturals can be partitioned into two sets based on parity. {n \in ℕ : n is divisible by 2} and {n \in ℕ : n + 1 is divisible by 2} form a partition of ℕ into odds and evens.
Congruence mod n partitions \mathbb{Z} into n equivalence classes or partitions. These cells are the residue classes modulo n in \mathbb{Z}, 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…}.
The set of integers can be partitioned into three disjoint sets, Z = −ℕ ∪ {0} ∪ ℕ, where ℕ = {1, 2, 3,… } = Natural Numbers = Positive Integers.

Equivalence Classes and Partitions

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 the same thing.

Proof:

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

In other words, we have S = ∪_x\inYS(x) and Y is a subset of S. If x, y\inY and x≠y, then by construction, S(x)≠S(y). ¿Do they intersect?

For the sake of contradiction, suppose x, y\inY, x≠y, but z\in S(x)∩S(y). z\in S(x) ⇨ z ∼ x, and z\in 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 \in S(x) ⇒ w ∼ x, but we already know that x ∼ y ⇨ w ∼ y (by transitivity) ⇨ w \in S(y). Secondly, let’s prove that S(y) ⊆ S(x). Suppose w \in S(y), w ∼ y, y ∼ x (by symmetry) ⇨ w ∼ x (by transitivity) ⇨ w \in 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\inI is a partition of S. Let’s define a relation on S by saying x ∼ y if and only if x, y\inX_i for some i\inI.

Reflexive. If x\inS ⇨ x \inX_i for some i\inI (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 \inX_i so x ∼ x.
If x ∼ y, then x, y \inX_i for some i\inI, and obviously y, x \inX_i, so y ∼ x.
If x ∼ y and y ∼ z, then x, y\inX_i and y, z \inX_j ⇨ y \in X_i∩X_j, but the partition’s subsets are disjoint (Partition’s definition iii) ⇨ X_i = X_j ⇨ x, y, z \in X_i and in particular, x, z \in X_i ⇨ x ∼ z.

An important example

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

Cartesian Products, Relations, and Partitions