Discrete-math 5

1

\begin{matrix} Let A be a set. B \subseteq A \\ R \subseteq P (A) \times P (A) \\ (C, D) \in R ⟺ C \cap B = D \cap B \end{matrix}

1a

\begin{matrix} Prove: R is an equivalence relation \\ Proof: \\ \forall C \in P (A) : C \cap B = C \cap B ⟹ (C, C) \in R ⟹ R is reflexive \\ Let (C, D) \in R ⟹ C \cap B = D \cap B ⟹ D \cap B = C \cap B \\ ⟹ (D, C) \in R ⟹ R is symmetric \\ Let (C, D) \in R, (D, E) \in R \\ ⟹ C \cap B = D \cap B \land D \cap B = E \cap B ⟹ C \cap B = E \cap B \\ ⟹ (C, E) \in R ⟹ R is transitive \\ R is reflexive, symmetric and transitive ⟹ R is an equivalence relation \end{matrix}

1b

\begin{matrix} Prove: \forall C, D \subseteq B : C \neq D ⟹ [C]_{R} \neq [D]_{R} \\ Proof: \\ C \subseteq B ⟹ C \cap B = C \\ D \subseteq B ⟹ D \cap B = D \\ C \neq D ⟹ C \cap B \neq D \cap B ⟹ (C, D) \notin R \\ ⟹ D \in [D]_{R} \land D \notin [C]_{R} ⟹ [D]_{R} \neq [C]_{R} \end{matrix}

1c

\begin{matrix} Prove: \forall C \subseteq A : \exists D \subseteq B : [C]_{R} = [D]_{R} \\ Proof: \\ [C]_{R} = {X | X \cap B = C \cap B} \\ [D]_{R} = {X | X \cap B = D \cap B = D} \\ ⟹ [C]_{R} = [D]_{R} ⟺ C \cap B = D \\ By properties of inclusion: C \cap B \subseteq B \\ ⟹ \forall C \subseteq A : \exists D \subseteq B : D = C \cap B ⟺ [C]_{R} = [D]_{R} \end{matrix}

1d

\begin{matrix} A = {1, 2, 3, 4}, B = {1, 4} \\ [\emptyset]_{R} = {X \in P (A) | X \cap B = \emptyset \cap B = \emptyset} \\ X \cap B = \emptyset ⟺ 1 \notin X \land 4 \notin X \\ ⟹ [\emptyset]_{R} = {\emptyset, {2}, {3}, {2, 3}} \\ [X]_{R} = {Y \in P (A) | X \cap B = Y \cap B} \\ What equivalence classes are there? \\ Let us take all possible values of X \cap B, they are all possible subsets of B : \\ \emptyset \subseteq {1, 4} \\ {1} \subseteq {1, 4} \\ {4} \subseteq {1, 4} \\ {1, 4} \subseteq {1, 4} \\ ⟹^{P (A)} /_{R} = {[X]_{R} | X \in P (A)} = {[\emptyset]_{R}, [{1}]_{R}, [{4}]_{R}, [{1, 4}]_{R}} \end{matrix}

2

\begin{matrix} A = {1, 2, 3, 4} \\ R_{1} = I_{A} ⟹^{A} /_{R_{1}} = {{1}, {2}, {3}, {4}} \\ R_{2} = I_{A} \cup {(1, 2), (2, 1)} ⟹^{A} /_{R_{2}} = {{1, 2}, {3}, {4}} \\ R_{3} = I_{A} \cup {(1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1)} \\ ⟹^{A} /_{R_{3}} = {{1, 2, 3}, {4}} \end{matrix}

3a

\begin{matrix} R on R \times R \\ (x_{1}, y_{1}) R (x_{2}, y_{2}) ⟺ x_{1}^{2} + y_{1}^{2} = x_{2}^{2} + y_{2}^{2} \\ [(1, 1)]_{R} = {(x, y) | x^{2} + y^{2} = 2} \\ (\frac{1}{2}, \frac{\sqrt{7}}{2}) R (1, 1) ⟺ \frac{1}{4} + \frac{7}{4} = 1 + 1 ⟹ (\frac{1}{2}, \frac{\sqrt{7}}{2}) \in [(1, 1)]_{R} \\ Equation of a circle: (x - a)^{2} + (y - b)^{2} = r^{2} \\ ⟹ The geometric interpretation of the partition would be \\ all different circles with the center at (0, 0) \end{matrix}

3b

\begin{matrix} S on R \times R \\ (x_{1}, y_{1}) S (x_{2}, y_{2}) ⟺ x_{1} = x_{2} \\ [(1, 1)]_{S} = {(x, y) | x = 1} \\ (1, - 1) S (1, 1) ⟺ 1 = 1 ⟹ (1, - 1) \in [(1, 1)]_{S} \\ Equation of a vertical line: x = a \\ ⟹ The geometric interpretation of the partition would be \\ all different vertical lines \end{matrix}

3c

\begin{matrix} [(x, y)]_{R \cap S} = {(a, b) | a^{2} + b^{2} = x^{2} + y^{2} \land a = x} = {(a, b) | b^{2} = y^{2} \land a = x} = \\ = {(a, b) | b = \pm y \land a = x} \\ ⟹ [(x, y)]_{R \cap S} = {\begin{cases} {(x, y)} & y = 0 \\ {(x, y), (x, - y)} & y \neq 0 \end{cases} \\ ⟹ | [(x, y)]_{R \cap S} | = {\begin{cases} 1 & y = 0 \\ 2 & y \neq 0 \end{cases} \\ Geometrically this can be explained as: \\ A vertical line can either touch the circle in one point or cross it in two points \end{matrix}

4

\begin{matrix} S on A = (R ∖ {0}) \times (R ∖ {0}) \\ (x_{1}, y_{1}) S (x_{2}, y_{2}) ⟺ x_{1} \cdot x_{2} > 0 \land y_{1} \cdot y_{2} > 0 \\ x_{1} \cdot x_{2} > 0 ⟺ {\begin{cases} x_{1} < 0 \land x_{2} < 0 \\ x_{1} > 0 \land x_{2} > 0 \end{cases} \\ y_{1} \cdot y_{2} > 0 ⟺ {\begin{cases} y_{1} < 0 \land y_{2} < 0 \\ y_{1} > 0 \land y_{2} > 0 \end{cases} \\ ⟹ (x_{1}, y_{1}) S (x_{2}, y_{2}) ⟺ {\begin{cases} x_{1}, x_{2}, y_{1}, y_{2} < 0 \\ x_{1}, x_{2} < 0 \land y_{1}, y_{2} > 0 \\ x_{1}, x_{2}, y_{1}, y_{2} > 0 \\ x_{1}, x_{2} > 0 \land y_{1}, y_{2} < 0 \end{cases} \\ ⟹^{A} /_{S} = {[(1, 1)]_{S}, [(1, - 1)]_{S}, [(- 1, 1)]_{S}, [(- 1, - 1)]_{S}} \\ ⟹ |^{A} /_{S} | = 4 \\ Geometrical interpretation of S are quadrants, not including the axes \end{matrix}

Let A = {1, 2, 3}

5a

\begin{matrix} Nor symmetric, nor anti-symmetric \\ R = {(1, 2), (2, 1), (3, 1)} \end{matrix}

5b

\begin{matrix} Anti-symmetric, but not symmetric \\ R = {(1, 2)} \end{matrix}

5c

\begin{matrix} Symmetric, but not anti-symmetric \\ R = {(1, 2), (2, 1)} \end{matrix}

5d

\begin{matrix} Symmetric and anti-symmetric \\ R = I_{A} \end{matrix}

6a

\begin{matrix} R \subseteq R \times R \\ R = {(a, b) | a^{2} \leq b^{2}} \\ R is reflexive: a^{2} \leq a^{2} ⟹ (a, a) \in R \\ R is not anti-symmetric: a^{2} \leq b^{2} \land b^{2} \leq a^{2} ⟹ a^{2} = b^{2} ⟹ ⧸ a = b \\ Example: (a, - a) \in R, (- a, a) \in R, a \neq - a \\ ⟹ R is not a partially ordering relation \end{matrix}

6b

\begin{matrix} (A, R) is a partially ordered set (poset) \\ Let B \subseteq A, S = R \cap (B \times B) \\ Let a \in B ⟹ (a, a) \in B \times B \\ (a, a) \in R ⟹ (a, a) \in S ⟹ S is reflexive on B \\ Let a, b \in B ⟹ (a, b), (b, a) \in B \times B \\ (a, b) \in S ⟹ (a, b) \in R ⟹ [(b, a) \in R \to b = a] ⟹ [(b, a) \in S \to b = a] \\ ⟹ S is anti-symmetric on B \\ Let a, b, c \in B ⟹ (a, b), (b, c), (a, c) \in B \times B \\ (a, b), (b, c) \in S ⟹ (a, b), (b, c) \in R ⟹ (a, c) \in R ⟹ (a, c) \in S \\ ⟹ S is transitive on B \\ ⟹ S is a partially ordering relation on B \end{matrix}

6c

\begin{matrix} A = {(a_{1}, a_{2}, \dots, a_{n}) | \forall k \in [1, n] : a_{k} \in {0, 1}} \\ R = {((a_{1}, a_{2}, \dots, a_{n}), (b_{1}, b_{2}, \dots, b_{n})) | \sum_{k = 1}^{n} a_{k} < \sum_{k = 1}^{n} b_{k}} \\ Note: I will use notation 00, 010, 1011, e t c . \\ to denote sequences (0, 0), (0, 1, 0), (1, 0, 1, 1), e t c . \\ so that the solution is not too flooded with extra characters \\ e . g . 10 in this case is not a number, but a sequence of length 2 \\ Let n = 1 \\ A = {(0), (1)}, R = {((0), (1))} \\ Let n = 2 \\ A = {00, 01, 10, 11} \\ R = {(00, 01), (00, 10), (00, 11), (01, 11), (10, 11)} \\ R is a relation comparing the number of 1s in two sequences \\ R is not a partial ordering relation, because any sequence is not in relation R with itself \\ Let S = R \cup I_{A} \\ I_{A} \subseteq S ⟹ S is reflexive \\ (a, b) \in S \land (b, a) \in S is always false ⟹ S is anti-symmetric \\ a S b, b S c ⟺ \sum a < \sum b < \sum c ⟹ \sum a < \sum c ⟹ a S c ⟹ S is transitive \\ ⟹ S is a partially ordering relation \\ Sequence 0_{A} = (0, 0, \dots, 0)_{n} is a minimum of set A : \\ \forall x \in A : (0_{A}, x) \in S as all x will have at least one 1 or be equal to 0_{A} \\ Set A has a minimum ⟹ the only minimal element is 0_{A} \\ Sequence 1_{A} = (1, 1, \dots, 1)_{n} is a maximum of set A : \\ \forall x \in A : (x, 1_{A}) \in S as all x will have at least one 0 or be equal to 1_{A} \\ Set A has a maximum ⟹ the only maximal element is 1_{A} \end{matrix}

7

\begin{matrix} A = {2, 3, \dots, 99, 100} \\ R = {(a, b) | \exists k \in N : b = a k} \end{matrix}

7a

\begin{matrix} How many maximal elements are there in this set? \\ Element is going to be maximal if it doesn’t divide any member of set A except for itself \\ \forall x \in A : x \leq 50 ⟹ 4 \leq 2 x \leq 100 ⟹ 2 x \in A ⟹ x ∣ 2 x \\ ⟹ Any element less or equal to 50 is not maximal \\ \forall x \in A : x > 50, k \geq 2 ⟹ x k > 100 ⟹ {\begin{cases} x k = x & k = 1 \\ x k \notin A & k \geq 2 \end{cases} \\ ⟹ \forall x > 50 \in A : \neg (\exists b \in A : b \neq x \land x ∣ b) \\ ⟹ All elements of A greater than 50 are maximal, there are 50 of them \end{matrix}

7b

\begin{matrix} Is there a smallest element? \\ 2 ∤ 3 ⟹ 2 is not the smallest \\ \forall x \in [3, 100] : x ∤ 2 \\ ⟹ \forall a \in A \exists x \in A : a ∤ x \\ ⟹ There is no smallest element \end{matrix}

7c

\begin{matrix} Add two elements to the set such that it has a smallest and a largest elements \\ First element to add would be 1, as it divides all elements of set A ⟹ 1 is a minimum \\ Second element to add would be \prod_{k = 2}^{100} k, as it is divided by all elements of set A \\ ⟹ \prod_{k = 2}^{100} k is a maximum \end{matrix}

8

\begin{matrix} A is a finite set, (A, R) is a partially ordered set \\ Prove: If there is exactly one minimal element, then it is also a minimum \\ Proof: \\ Let m be a unique minimal element, but not a minimum of set A \\ ⟹ \exists x \in A : m S̸ x \\ m S m ⟹ x \neq m ⟹ x S̸ m \\ Let B = {b \in A | b S x} \\ x \in B ⟹ B \neq \emptyset \\ B \subseteq A ⟹ B is finite \\ ⟹ \exists z \in B : z is a minimal element of B \\ [m S b \land b S x \to m S x] ⟹ \forall b \in B : m S̸ b ⟹ m S̸ z ⟹ m \neq z \\ m is a unique minimal of A ⟹ z is not minimal in A ⟹ \exists a \in A : a \neq z \land a S z \\ a S z \land z S x \underset{By transitivity}{⟹} a S x ⟹ a \in B \\ a \in B \land a S z ⟹ a = z - Contradiction! \\ ⟹ m is a minimum of A \end{matrix}