Discrete-math 7

Equivalence relation #definition

Relation R is called equivalence relation if it is Reflexive, Symmetric and Transitive

\begin{matrix} \forall a, b, c \in Z : a \equiv_{c} b ⟺ c ∣ (b - a) ⟺ k = \frac{b - a}{c} \in Z \\ Reflexive? \\ a \equiv_{c} a ⟺ c ∣ (a - a) ⟺ c ∣ 0 ⟺ T \\ Symmetric? \\ a \equiv_{c} b ⟺ c ∣ (b - a) ⟺ k_{1} = \frac{b - a}{c} \in Z ⟺ k_{2} = - k_{1} = \frac{a - b}{c} \in Z ⟺ b \equiv_{c} a \\ Transitive? \\ a \equiv_{c} b \land b \equiv_{c} d ⟺ c ∣ (b - a) \land c ∣ (d - b) ⟺ k_{1} = \frac{b - a}{c} \in Z, k_{2} = \frac{d - b}{c} \in Z \\ ⟺ k = k_{1} + k_{2} = \frac{d - a}{c} \in Z ⟺ a \equiv_{c} d \end{matrix}

\begin{matrix} Let R be an equivalence relation on set A, and a \in A \\ [a]_{R} = {b \in A ∣ (a, b) \in R} \end{matrix}

\begin{matrix} ^{A} /_{R} = {[a]_{R} ∣ a \in A} \end{matrix}

\begin{matrix} Define^{Z} /_{\equiv_{3}} \\ [0]_{\equiv_{3}} = {b \in Z ∣ 0 \equiv_{3} b} = {b \in Z ∣ \frac{b - 0}{3} = k \in Z} = {3 k ∣ k \in Z} \\ [1]_{\equiv_{3}} = {3 k + 1 ∣ k \in Z} \\ [2]_{\equiv_{3}} = {3 k + 2 ∣ k \in Z} \\ ⟹^{Z} /_{\equiv_{3}} = {[0]_{\equiv_{3}}, [1]_{\equiv_{3}}, [2]_{\equiv_{3}}} \end{matrix}

\begin{matrix} x \in [y]_{R} ⟺ [x]_{R} = [y]_{R} \\ Proof: \\ 1. x \in [y]_{R} \\ 1.1 Let z \in [x]_{R} \\ Then (x, z) \in R \\ x \in [y]_{R} ⟹ (y, x) \in R \\ (y, x) \in R \land (x, z) \in R \underset{Transitive}{⟹} (y, z) \in R ⟺ z \in [y]_{R} \\ 1.2 Let z \in [y]_{R} \\ Then (y, z) \in R \\ x \in [y]_{R} ⟹ (y, x) \in R \underset{Symmetric}{⟹} (x, y) \in R \\ (x, y) \in R \land (y, z) \in R \underset{Transitive}{⟹} (x, z) \in R ⟺ z \in [x]_{R} \\ 2. [x]_{R} = [y]_{R} \\ [x]_{R} = [y]_{R} \underset{Reflexive}{⟹} x \in [x]_{R} = [y]_{R} ⟹ x \in [y]_{R} \\ 1. and 2. ⟹ x \in [y]_{R} ⟺ [x]_{R} = [y]_{R} \end{matrix}

\begin{matrix} Family {A_{i}}_{i \in I} is a partition of a set A if: \\ 1. & \forall i \in I : A_{i} \neq \emptyset \\ 2. & \forall i, j \in I : A_{i} \neq A_{j} \to A_{i} \cap A_{j} = \emptyset \\ 3. & ⋃_{i \in I} A_{i} = A \end{matrix}

\begin{matrix} ^{Z} /_{\equiv_{3}} = {[0]_{\equiv_{3}}, [1]_{\equiv_{3}}, [2]_{\equiv_{3}}} \\ ^{Z} /_{\equiv_{3}} is a partition of Z \end{matrix}