Discrete-math 9

Existence of equivalence relation based on partition (continued) #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: \\ Proof in lecture 8 ⟹ R is an equivalence relation \\ Let us prove the following: \\ \forall A_{i} \in {A_{i}}_{i \in I} : \forall a \in A_{i} : [a]_{R} = A_{i} \\ Let y \in [a]_{R}, a \in A_{i} \\ Then (a, y) \in R ⟹ \exists j \in I : (a, y) \in A_{j} \times A_{j} ⟺ \exists j \in I : a \in A_{j} \land y \in A_{j} \\ a \in A_{i} \land a \in A_{j} ⟹ A_{i} \cap A_{j} \neq \emptyset \underset{By definition of partition}{⟹} A_{i} = A_{j} \\ ⟹ y \in A_{i} ⟹ \forall A_{i} \in {A_{i}}_{i \in I} : \forall a \in A_{i} : [a]_{R} \subseteq A_{i} (1) \\ Let y \in A_{i} \\ a \in A_{i} \land y \in A_{i} ⟹ (a, y) \in A_{i} \times A_{i} ⟹ (a, y) \in ⋃_{i \in I} A_{i} \times A_{i} = R \\ ⟹ y \in [a]_{R} ⟹ \forall A_{i} \in {A_{i}}_{i \in I} : \forall a \in A_{i} : [a]_{R} \supseteq A_{i} (2) \\ (1) and (2) ⟹ \forall A_{i} \in {A_{i}}_{i \in I} : \forall a \in A_{i} : [a]_{R} = A_{i} (3) \end{matrix}

\begin{matrix} Let us now prove that^{A} /_{R} = {A_{i}}_{i \in I} \\ Let A_{r} \in {A_{i}}_{i \in I} \\ By definition of partition: A_{r} \neq \emptyset ⟹ \exists a \in A : a \in A_{r} ⟹ A_{r} = [a]_{R} \\ \underset{By definition of quotient set}{⟹} A_{r} \in^{A} /_{R} ⟹ {A_{i}}_{i \in I} \subseteq^{A} /_{R} (4) \\ Let X \in^{A} /_{R} \\ By definition of quotient set: \exists a \in A : X = [a]_{R} \\ By definition of partition: a \in A ⟹ \exists i \in I : a \in A_{i} \\ \underset{(3)}{⟹} A_{i} = [a]_{R} ⟹ X = A_{i} ⟹ X \in {A_{i}}_{i \in I} \\ ⟹ {A_{i}}_{i \in I} \supseteq^{A} /_{R} (5) \\ (4) and (5) ⟹^{A} /_{R} = {A_{i}}_{i \in I} \end{matrix}

\begin{matrix} There is 1-to-1 correspondence from equivalence relations to partitions of some set A \\ ⟹ Number of equivalence relations on A is equal to the number of partitions of A \end{matrix}

\begin{matrix} How many equivalence relations are there on set A = {1, 2, 3} \\ Partitions of A \\ \begin{matrix} 1. & {{1, 2, 3}} \\ 2. & {{1}, {2, 3}} \\ 3. & {{2}, {1, 3}} \\ 4. & {{3}, {1, 2}} \\ 5. & {{1}, {2}, {3}} \end{matrix} \end{matrix}

\begin{matrix} Relation R on set A is called anti-symmetric, \\ if \forall a, b \in A : ((a, b) \in R \land (b, a) \in R) \to a = b \end{matrix}

\begin{matrix} Relation R on set A is called ordering relation, \\ if it is reflexive, anti-symmetric and transitive \end{matrix}

\begin{matrix} R is ordering relation ⟹ (A, R) - partially ordered set \\ And R can also be called partial ordering relation \end{matrix}

\begin{matrix} In addition to partial ordering, \forall a, b \in A : (a, b) \in R \lor (b, a) \in R \\ (A, R) - totally ordered set \end{matrix}

\begin{matrix} \forall a, b \in N : a ∣ b ⟺ \exists k \in N : \frac{b}{a} = k \\ Reflexive: \forall n \in N : n ∣ n \\ Anti-symmetric: \forall a, b \in N : (a ∣ b \land b ∣ a) ⟹ a = b \\ Transitive: \forall a, b, c \in N : (a ∣ b \land b ∣ c) ⟹ a ∣ c \\ Partial: 3 ∤ 5 \land 5 ∤ 3 \end{matrix}

\begin{matrix} \forall (a, b), (c, d) \in A : (a, b) ≼_{l e x} (c, d) ⟺ (a < c) \lor (a = c \land b \leq d) \\ Lexicographic order is a total ordering relation \end{matrix}