Discrete-math 8

Equivalence relations

Quotient set is a partition #theorem

\begin{matrix} Let R be an equivalence relation on A \\ Then^{A} /_{R} is a partition of A \end{matrix}

\begin{matrix} Proof: \\ 1. & \forall X \in^{A} /_{R} : A_{R} \neq \emptyset \\ Let X \in^{A} /_{R} \\ Then \exists a \in A : X = [a]_{R} \\ R is reflexive ⟹ (a, a) \in R ⟹ a \in [a]_{R} ⟹ [a]_{R} \neq \emptyset ⟹ X \neq \emptyset \\ ⟹ \forall X \in^{A} /_{R} : A_{R} \neq \emptyset \\ 2. & \forall X, Y \in^{A} /_{R} : X \neq Y \to X \cap Y = \emptyset \\ Let X, Y \in^{A} /_{R} \\ Then \exists x, y \in A : X = [x]_{R}, Y = [y]_{R} \\ Let also X \neq Y, X \cap Y \neq \emptyset \\ Then \exists z \in X \cap Y ⟺ z \in [x]_{R} \land z \in [y]_{R} \\ z \in [x]_{R} ⟹ [z]_{R} = [x]_{R} \\ z \in [y]_{R} ⟹ [z]_{R} = [y]_{R} \\ z \in [x]_{R} \land z \in [y]_{R} ⟹ [x]_{R} = [y]_{R} ⟹ X = Y - Contradiction! \\ ⟹ \forall X, Y \in^{A} /_{R} : X \neq Y \to X \cap Y = \emptyset \\ 3. & ⋃^{A} /_{R} = A \\ 3.1 & ⋃^{A} /_{R} \subseteq A \\ Let X \in ⋃^{A} /_{R} \\ Then \exists a \in A : X = [a]_{R} \\ By definition: [a]_{R} \subseteq A ⟹ X \subseteq A \\ ⟹ \forall X \in ⋃^{A} /_{R} : X \subseteq A ⟹ ⋃^{A} /_{R} \subseteq A \\ 3.2 & A \subseteq ⋃^{A} /_{R} \\ Let x \in A \\ R is reflexive ⟹ (x, x) \in R ⟹ x \in [x]_{R} \\ [x]_{R} \in ⋃^{A} /_{R} ⟹ x \in ⋃^{A} /_{R} ⟹ A \subseteq ⋃^{A} /_{R} \\ 3.1 and 3.2 ⟹ ⋃^{A} /_{R} = A \\ 1., 2. and 3. ⟹^{A} /_{R} is a partition of A \end{matrix}

Existence of equivalence relation based on partition #theorem

\begin{matrix} Let {A_{i}}_{i \in I} be a partition of A \\ Then there is an equivalence relation R :^{A} /_{R} = {A_{i}}_{i \in I} \\ Proof: \\ Let’s define R as following: \\ R = {(a, b) ∣ \exists i \in I : a \in A_{i} \land b \in A_{i}} \\ Let us rephrase: R = ⋃_{i \in I} (A_{i} \times A_{i}) \\ Let us prove that R is an equivalence relation: \\ Let x \in A \\ By definition of partition: x \in ⋃_{i \in I} A_{i} ⟺ \exists i \in I : x \in A_{i} \\ ⟹ \exists i \in I : (x, x) \in (A_{i} \times A_{i}) ⟹ \forall x \in A : (x, x) \in R ⟺ R is reflexive \\ Let x, y \in A : (x, y) \in R \\ Then (x, y) \in R ⟹ \exists i \in I : (x, y) \in (A_{i} \times A_{i}) ⟹ \exists i \in I : x \in A_{i} \land y \in A_{i} \\ ⟹ \exists i \in I : y \in A_{i} \land x \in A_{i} ⟹ \exists i \in I : (y, x) \in (A_{i} \times A_{i}) \\ ⟹ (y, x) \in R ⟹ R is symmetric \\ Let x, y, z \in A : (x, y) \in R \land (y, z) \in R \\ Then \exists i \in I : (x, y) \in (A_{i} \times A_{i}) ⟺ \exists i \in I : x \in A_{i} \land y \in A_{i} \\ And also \exists j \in I : (y, z) \in (A_{j} \times A_{j}) ⟺ \exists j \in I : y \in A_{j} \land z \in A_{j} \\ By definition of partition: y \in A_{i} \land y \in A_{j} ⟹ A_{i} = A_{j} \\ ⟹ \exists i \in I : x \in A_{i} \land y \in A_{i} \land z \in A_{i} ⟹ \exists i \in I : x \in A_{i} \land z \in A_{i} \\ ⟺ \exists i \in I : (x, z) \in (A_{i} \times A_{i}) ⟹ (x, z) \in R ⟹ R is transitive \\ R is reflexive, symmetric and transitive ⟺ R is an equivalence relation \end{matrix}

\begin{matrix} Let us now prove that^{A} /_{R} = {A_{i}}_{i \in I} \\ Proof in lecture 9 \end{matrix}