1st Class
Equivalence Relation
Let \( X (
e \emptyset) \) be a set. A relation \( \sim \) on \( X \) is called an equivalence relation if:
- Reflexivity: \( x \sim x \) for all \( x \in X \).
- Symmetry: For all \( x, y \in X \), if \( x \sim y \) then \( y \sim x \).
- Transitivity: For all \( x, y, z \in X \), if \( x \sim y \) and \( y \sim z \) then \( x \sim z \).
Equivalence Class
Let \( \sim \) be an equivalence relation on a set \( X (\ne \emptyset) \).
For any \( x \in X \), the equivalence class of \( x \) is defined as:
\[
[x] := \{y \in X \mid x \sim y\}
\]
Example 1: If \( a \in [x] \), then \( [x] = [a] \).
Solution:
- If \( a \in [x] \), then by definition, \( x \sim a \). By symmetry, \( a \sim x \).
- To show \( [x] \subseteq [a] \): Let \( b \in [x] \Rightarrow x \sim b \). Since \( a \sim x \) and \( x \sim b \), by transitivity \( a \sim b \Rightarrow b \in [a] \).
- To show \( [a] \subseteq [x] \): Let \( c \in [a] \Rightarrow a \sim c \). Since \( x \sim a \) and \( a \sim c \), by transitivity \( x \sim c \Rightarrow c \in [x] \).
Hence, \( [a] = [x] \).
Example 2: For any \( x, y \in X \), either \( [x] = [y] \) or \( [x] \cap [y] = \emptyset \).
Solution:
- If \( [x] \cap [y] = \emptyset \), done.
- Otherwise, \( \exists z \in [x] \cap [y] \Rightarrow x \sim z \) and \( y \sim z \Rightarrow z \sim y \). Since \( x \sim z \) and \( z \sim y \), by transitivity \( x \sim y \Rightarrow [x] = [y] \).
Construction of Natural Numbers (Von Neumann Ordinals)
On the class of sets, define the successor operation by \( S(A) = A \cup \{A\} \). Starting from \( \emptyset \):
-
\( S(\emptyset) = \{\emptyset\} \)
-
\( S(\{\emptyset\}) = \{\emptyset, \{\emptyset\}\} \)
-
\( S(\{\emptyset, \{\emptyset\}\}) = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\} \)
Define natural numbers:
\[
0 := \emptyset, \quad 1 := S(0), \quad 2 := S(1), \quad \dots
\]
-
\( 1 = \{0\} \)
-
\( 2 = \{0, 1\} \)
-
\( 3 = \{0, 1, 2\} \)
Every natural number is the set of all its predecessors.
Peano Axioms
The set \( \mathbb{N} \) satisfies:
-
\( 0 \) is a natural number.
-
The successor of any natural number is also a natural number.
-
\( 0 \) is not the successor of any natural number.
-
If \( S(n) = S(m) \), then \( n = m \).
-
Induction: If true for 0 and holds from \( n \Rightarrow S(n) \), then true for all \( \mathbb{N} \).
Operations on \( \mathbb{N} \)
Addition
-
\( n + 0 = n \)
-
\( n + S(m) = S(n + m) \)
This makes \( (\mathbb{N}, +) \) a cancellative abelian monoid:
-
Identity: \( n + 0 = 0 + n = n \)
-
Associativity: \( n + (m + p) = (n + m) + p \)
-
Commutativity: \( n + m = m + n \)
-
Cancellation: If \( n + m = n + p \), then \( m = p \)
Motivation for Integers (\( \mathbb{Z} \))
The equation \( 2 + x = 1 \) has no solution in \( \mathbb{N} \). Using Peano Axiom 3, this motivates extending to integers.
Extending \( \mathbb{N} \) to Integers (\( \mathbb{Z} \))
Let \( X = \mathbb{N} \times \mathbb{N} \), and define:
\[
(a, b) \sim (c, d) \iff a + d = c + b
\]
This is an equivalence relation. Define:
\[
\mathbb{Z} := \{[(a, b)] \mid a, b \in \mathbb{N}\}
\]
Addition: \( [(a, b)] + [(c, d)] = [(a + c, b + d)] \)
Embedding: \( \phi(a) = [(a, 0)] \)
Interpretation: \( [(a, b)] = a - b \)
Extending \( \mathbb{Z} \) to Rational Numbers (\( \mathbb{Q} \))
Let \( X = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\}) \), define:
\[
(a, b) \sim (c, d) \iff ad = cb
\]
Define:
\[
\mathbb{Q} := \{[(a, b)] \mid a \in \mathbb{Z}, b \in \mathbb{Z} \setminus \{0\}\}
\]
-
Addition: \( [(a, b)] + [(c, d)] = [(ad + bc, bd)] \)
-
Multiplication: \( [(a, b)] \cdot [(c, d)] = [(ac, bd)] \)
Embedding: \( \phi(a) = [(a, 1)] \)
Every non-zero element has an inverse → \( (\mathbb{Q}, +, \cdot) \) is a field.
Fraction notation: \( \frac{m}{n} \)
Further Extensions
-
Equation \( x^2 = 2 \) has no solution in \( \mathbb{Q} \) → Extend to \( \mathbb{R} \) (Dedekind cuts or Cauchy sequences).
-
Equation \( x^2 = -1 \) has no solution in \( \mathbb{R} \) → Extend to \( \mathbb{C} \) via \( \mathbb{R}[x]/(x^2 + 1) \).