Discrete-math 6

1

\begin{matrix} \forall (n_{1}, m_{1}), (n_{2}, m_{2}) \in N \times N \\ (n_{1}, m_{1}) R (n_{2}, m_{2}) ⟺ n_{1} \leq n_{2} \land m_{1} \leq m_{2} \end{matrix}

1a

\begin{matrix} Prove: R is an ordering relation \\ Proof: \\ Let (n, m) \in N \times N \\ n = n \land m = n ⟹ n \leq n \land m \leq m ⟹ (n, m) R (n, m) \\ ⟹ R is reflexive \\ Let (n_{1}, m_{1}) R (n_{2}, m_{2}), (n_{2}, m_{2}) R (n_{1}, m_{1}) \\ ⟹ {\begin{matrix} n_{1} \leq n_{2} \\ m_{1} \leq m_{2} \\ n_{2} \leq n_{1} \\ m_{2} \leq m_{1} \end{matrix} ⟹ n_{1} = n_{2} \land m_{1} = m_{2} ⟺ (n_{1}, m_{1}) = (n_{2}, m_{2}) \\ ⟹ R is anti-symmetric \\ Let (n_{1}, m_{1}) R (n_{2}, m_{2}), (n_{2}, m_{2}) R (n_{3}, m_{3}) \\ ⟹ {\begin{matrix} n_{1} \leq n_{2} \leq n_{3} \\ m_{1} \leq m_{2} \leq m_{3} \end{matrix} ⟹ n_{1} \leq n_{3} \land m_{1} \leq m_{3} ⟹ (n_{1}, m_{1}) R (n_{3}, m_{3}) \\ ⟹ R is transitive \\ ⟹ R is an ordering relation \end{matrix}

1b

\begin{matrix} Prove or disprove: (N \times N, R) is a total order (R is linear) \\ Disproof: \\ Let x = (1, 3) \in N \times N \\ Let y = (5, 2) \in N \times N \\ 3 > 2 ⟹ x R̸ y \\ 5 > 1 ⟹ y R̸ x \\ ⟹ \exists (n_{1}, m_{1}), (n_{2}, m_{2}) : \neg [(n_{1}, m_{1}) R (n_{2}, m_{2}) \land (n_{2}, m_{2}) R (n_{1}, m_{1})] \\ ⟹ (N \times N, R) is not a total order \end{matrix}

1c

\begin{matrix} B = {(1, n) | n \in N} \\ Find i n f (B) and s u p (B) \\ Solution: \\ Let (x, y) \in N \times N \\ \forall b \in B : (x, y) R b ⟺ \forall n \in N : x \leq 1 \land y \leq n ⟺ x \leq 1 \land y \leq 1 \\ ⟹ L_{B} = {(x, y) \in N \times N | x \leq 1 \land y \leq 1} ⟹ m a x (L_{B}) = (1, 1) ⟹ i n f (B) = (1, 1) \\ \forall b \in B : b R (x, y) ⟺ \forall n \in N : 1 \leq x \land n \leq y ⟺ 1 \leq x \land \underset{False}{\underset{⏟}{\exists s u p (N)}} \\ ⟹ U_{B} = \emptyset ⟹ ∄ s u p (B) \end{matrix}

1d

\begin{matrix} B = {(n, 1) | n \in N} \\ Find i n f (B) and s u p (B) \\ Solution: \\ Let (x, y) \in N \times N \\ \forall b \in B : (x, y) R (n, 1) ⟺ \forall n \in N : x \leq n \land y \leq 1 ⟺ x \leq 1 \land y \leq 1 \\ ⟹ L_{B} = {(x, y) \in N \times N | x \leq 1 \land y \leq 1} ⟹ m a x (L_{B}) = (1, 1) ⟹ i n f (B) = (1, 1) \\ \forall b \in B : b R (x, y) ⟺ \forall n \in N : n \leq x \land 1 \leq y ⟺ \underset{False}{\underset{⏟}{\exists s u p (N)}} \land 1 \leq y \\ ⟹ U_{B} = \emptyset ⟹ ∄ s u p (B) \end{matrix}

2

\begin{matrix} Let (A, ≼) be a poset, | A | \geq 2 \\ (a_{1}, b_{1}) R (a_{2}, b_{2}) ⟺ a_{1} ≼ a_{2} \land b_{1} ≼ b_{2} \\ Prove: R is a non-linear relation on A \times A \\ Proof: \\ Let a_{1} \neq a_{2}, a_{1} ≼ a_{2} \land b_{2} ≼ b_{1}, b_{1} \neq b_{2} \\ ⟹ (a_{1}, b_{1}) R̸ (a_{2}, b_{2}) \land (a_{2}, b_{2}) R̸ (a_{1}, b_{1}) \\ ⟹ \exists (a_{1}, b_{1}), (a_{2}, b_{2}) \in A \times A : \neg [(a_{1}, b_{1}) R (a_{2}, b_{2}) \lor (a_{2}, b_{2}) R (a_{1}, b_{1})] \\ ⟹ R is a non-linear relation \end{matrix}

3

\begin{matrix} Let (A, \leq), (B, ≼) be posets, A, B \neq \emptyset \\ Lexicographic order L on A \times B : \\ (a_{1}, b_{1}) L (a_{2}, b_{2}) ⟺ (a_{1} < a_{2} \lor (a_{1} = a_{2} \land b_{1} ≼ b_{2})) \end{matrix}

3a

\begin{matrix} Find posets (A, \leq), (B, ≼) such that L is non-linear \\ Solution: \\ (A, \leq) = ({2, 3}, ∣) \\ (B, ≼) = ({5, 7}, ∣) \\ 2 ∤ 3 \lor (2 \neq 3 \land 5 ∤ 7) \equiv F ⟹ (2, 5) L̸ (3, 7) \\ 3 ∤ 2 \lor (3 \neq 2 \land 7 ∤ 5) \equiv F ⟹ (3, 7) L̸ (2, 5) \\ ⟹ L is non-linear \end{matrix}

3b

\begin{matrix} Prove: L is linear ⟺ \leq, ≼ are linear \\ Proof: \\ Let a_{1}, a_{2} \in A, b_{1}, b_{2} \in B ⟹ (a_{1}, b_{1}), (a_{2}, b_{2}) \in A \times B \\ Let \leq, ≼ be linear \\ {\begin{matrix} a_{1} \leq a_{2} \lor a_{2} \leq a_{1} \\ b_{1} ≼ b_{2} \lor b_{2} ≼ b_{1} \end{matrix} ⟹ {\begin{matrix} [\begin{matrix} a_{1} < a_{2} \\ a_{2} < a_{1} \\ a_{1} = a_{2} \end{matrix} \\ b_{1} ≼ b_{2} \lor b_{2} ≼ b_{1} \end{matrix} ⟹ {\begin{matrix} [\begin{matrix} (a_{1}, b_{1}) L (a_{2}, b_{2}) \\ (a_{2}, b_{2}) L (a_{1}, b_{1}) \\ a_{1} = a_{2} \end{matrix} \\ b_{1} ≼ b_{2} \lor b_{2} ≼ b_{1} \end{matrix} \\ ⟹ [\begin{matrix} (a_{1}, b_{1}) L (a_{2}, b_{2}) \\ (a_{2}, b_{2}) L (a_{1}, b_{1}) \\ a_{1} = a_{2} \land (b_{1} ≼ b_{2} \lor b_{2} ≼ b_{1}) \end{matrix} ⟹ [\begin{matrix} (a_{1}, b_{1}) L (a_{2}, b_{2}) \\ (a_{2}, b_{2}) L (a_{1}, b_{1}) \\ a_{1} = a_{2} \land b_{1} ≼ b_{2} \\ a_{1} = a_{2} \land b_{2} ≼ b_{1} \end{matrix} ⟹ [\begin{matrix} (a_{1}, b_{1}) L (a_{2}, b_{2}) \\ (a_{2}, b_{2}) L (a_{1}, b_{1}) \\ (a_{1}, b_{1}) L (a_{2}, b_{2}) \\ (a_{2}, b_{2}) L (a_{1}, b_{1}) \end{matrix} \\ ⟹ L is linear & (1) \\ Let L be linear \\ [\begin{matrix} (a_{1}, b_{1}) L (a_{2}, b_{1}) \\ (a_{2}, b_{1}) L (a_{1}, b_{1}) \end{matrix} ⟹ [\begin{matrix} a_{1} < a_{2} \lor (a_{1} = a_{2} \land b_{1} ≼ b_{1}) \\ a_{2} < a_{1} \lor (a_{2} = a_{1} \land b_{1} ≼ b_{1}) \end{matrix} ⟹ a_{1} \leq a_{2} \lor a_{2} \leq a_{1} \\ ⟹ \leq is linear & (2) \\ [\begin{matrix} (a_{1}, b_{1}) L (a_{1}, b_{2}) \\ (a_{1}, b_{2}) L (a_{1}, b_{1}) \end{matrix} ⟹ [\begin{matrix} a_{1} < a_{1} \lor (a_{1} = a_{1} \land b_{1} ≼ b_{2}) \\ a_{1} < a_{1} \lor (a_{1} = a_{1} \land b_{2} ≼ b_{1}) \end{matrix} ⟹ b_{1} ≼ b_{2} \lor b_{2} ≼ b_{1} \\ ⟹ ≼ is linear & (3) \\ (1) \land (2) \land (3) ⟹ L is linear ⟺ \leq, ≼ are linear \end{matrix}

4

\begin{matrix} Let (A, ≼) be a poset, assume \exists m i n (A) = a, let B \subseteq A \end{matrix}

4a

\begin{matrix} Prove or disprove: a \in B ⟸ i n f (B) = a \\ Proof: \\ B \subseteq A ⟹ \forall b \in B : b \in A ⟹ \forall b \in B : a ≼ b \\ a \in B ⟹ a = m i n (B) \\ \exists m i n (B) ⟹ i n f (B) = m i n (B) \\ ⟹ i n f (B) = a \end{matrix}

4b

\begin{matrix} Prove or disprove: i n f (B) = a ⟹ a \in B \\ Disproof: \\ Let A = {x \in R | x \geq 0} \\ Let a_{1} ≼ a_{2} ⟺ a_{1} \leq a_{2} \\ ⟹ m i n (A) = 0 \\ Let B = {\frac{1}{n} | n \in N} \\ i n f (B) = 0 \land 0 \notin B Disproved \end{matrix}

5a

\begin{matrix} Find a function f : N \to N that is injective but not surjective \\ Solution: \\ f (n) = n + 1 \\ \forall n_{1}, n_{2} \in N : f (n_{1}) = f (n_{2}) ⟹ n_{1} + 1 = n_{2} + 1 ⟹ n_{1} = n_{2} ⟹ f is injective \\ \forall n \in N : f (n) \neq 1 ⟹ f is not surjective \end{matrix}

5b

\begin{matrix} Find a function f : N \to N that is surjective but not injective \\ Solution: \\ f (n) = {\begin{cases} n & n = 1 \\ n - 1 & otherwise \end{cases} \\ f (1) = f (2) ⟹ f is not injective \\ \forall n \in N : \exists n + 1 \in N : f (n + 1) = n + 1 - 1 = n ⟹ f is surjective \end{matrix}

5c

\begin{matrix} Let f : R \to R, f (x) = m x + b \\ For which values of m, b \in R, function f is bijective? \\ Solution: \\ \forall m, b, x_{1}, x_{2} \in R : f (x_{1}) = f (x_{2}) ⟹ m x_{1} + b = m x_{2} + b ⟹ [\begin{matrix} m = 0 \\ x_{1} = x_{2} \end{matrix} \\ ⟹ m \neq 0 ⟹ f is injective \\ Let y \in R \\ y = m x + b ⟺ x = \frac{y - b}{m} \\ \frac{y - b}{m} \in R ⟺ m \neq 0 \\ ⟹ [\forall y \in R \exists x \in R : f (x) = y] ⟺ m \neq 0 \\ ⟹ f is bijective ⟺ m \neq 0 \end{matrix}

6

\begin{matrix} Define and prove whether the functions are injective, surjective or bijective \end{matrix}

6a

\begin{matrix} f : Z \to Z, f (n) = | n | \\ Also find I m (f) \\ Solution: \\ f (1) = f (- 1) = 1 ⟹ f is not injective \\ \forall n \in Z : f (n) \neq - 1 ⟹ f is not surjective \\ I m (f) = {z \in Z | z \geq 0} \end{matrix}

6b

\begin{matrix} f : R \to {0, 1}, f (x) = {\begin{cases} 1 & x \in Q \\ 0 & x \notin Q \end{cases} \\ Solution: \\ f (1) = f (2) = 1 ⟹ f is not injective \\ f (1) = 1, f (\sqrt{2}) = 0 ⟹ I m (f) = {0, 1} ⟹ f is surjective \end{matrix}

6c

\begin{matrix} f : P (A) \to P (A), f (B) = A ∖ B \\ Solution: \\ If there are no two different elements in P (A), then f is obviously injective \\ Let B_{1}, B_{2} \subseteq A, B_{1} \neq B_{2} \\ \underset{b can be in B_{1} or in B_{2}}{⟹} \exists b \in B_{1} : b \notin B_{2} \\ b \in B_{1} ⟹ b \in A ⟹ b \in A ∖ B_{2} \\ b \in B_{1} ⟹ b \notin A ∖ B_{1} ⟹ A ∖ B_{1} \neq A ∖ B_{2} \\ ⟹ [B_{1} \neq B_{2} ⟹ f (B_{1}) \neq f (B_{2})] ⟹ \forall A : f is injective \\ Let C \subseteq A \\ \exists B \subseteq A : B = A ∖ C \\ f (B) = A ∖ (A ∖ C) = C \\ ⟹ \forall A : f is surjective \end{matrix}

6d

\begin{matrix} A \neq \emptyset, B \subset A \\ f : P (A) \to P (B), f (C) = C \cap B \\ Solution: \\ A \cap B = B = B \cap B \\ f (A) = f (B) = B ⟹ f is not injective \\ Let B_{1} \subseteq B \\ B_{1} \subseteq B \subset A ⟹ B_{1} \in P (A) \\ f (B_{1}) = B_{1} \cap B = B_{1} \\ ⟹ f is surjective \end{matrix}

6e

\begin{matrix} A \neq \emptyset, B \subset A \\ f : P (B) \to P (A), f (C) = C \cup (A ∖ B) \\ Solution: \\ Let C_{1}, C_{2} \subseteq B, C_{1} \neq C_{2} \\ \underset{c can be in C_{1} or in C_{2}}{⟹} \exists c \in C_{1} : c \notin C_{2} \\ c \in C_{1} ⟹ c \in B ⟹ c \notin A ∖ B \\ c \notin C_{2} ⟹ c \notin C_{2} \cup (A ∖ B) \\ c \in C_{1} ⟹ c \in C_{1} \cup (A ∖ B) \\ ⟹ C_{1} \cup (A ∖ B) \neq C_{2} \cup (A ∖ B) \\ ⟹ [C_{1} \neq C_{2} ⟹ f (C_{1}) \neq f (C_{2})] ⟹ f is injective \\ B \subset A ⟹ A ∖ B \neq \emptyset ⟹ \forall X : X \cup (A ∖ B) \neq \emptyset \\ \emptyset \subseteq A \land \forall C \subseteq B : f (C) \neq \emptyset ⟹ f is not surjective \end{matrix}

7

\begin{matrix} Let A be a set \\ Let f : A \to N \\ Let R be a relation on A \\ a R b ⟺ f (a) \leq f (b) \\ Prove: R is an order relation ⟺ f is injective \\ Proof: \\ Let a, b, c \in A \\ R is reflexive : a R a ⟺ f (a) \leq f (a) \equiv T \\ R is transitive : a R b \land b R c ⟺ f (a) \leq f (b) \leq f (c) ⟹ f (a) \leq f (c) ⟹ a R c \\ Let a \neq b, f (a) = f (b) \\ f (a) = f (b) \land a \neq b ⟹ f (a) \leq f (b) \land f (b) \leq f (a) \land a \neq b ⟹ a R b \land b R a \land a \neq b \\ ⟹ R is not an order relation \\ ⟹ [f is not injection ⟹ R is not an order relation] \\ ⟹ R is an order relation ⟹ f is injective & (1) \\ Let a \neq b, a R b, b R a \\ a R b \land b R a \land a \neq b ⟹ f (a) \leq f (b) \land f (b) \leq f (a) \land a \neq b ⟹ f (a) = f (b) \land a \neq b \\ ⟹ f is not injective ⟹ [R is not an order relation ⟹ f is not injective] \\ ⟹ f is injective ⟹ R is an order relation & (2) \\ (1) \land (2) ⟹ R is an order relation ⟺ f is injective \end{matrix}

8

\begin{matrix} Let A, B be finite sets \end{matrix}

8a

\begin{matrix} Let f : A \to B \\ Prove: | A | = | B | ⟹ [f is injective ⟺ f is surjective] \\ Proof: \\ Let | A | = | B | = n \\ Let f be injective \\ \forall a_{1}, a_{2} \in A : a_{1} \neq a_{2} ⟹ f (a_{1}) \neq f (a_{2}) \\ There are n unique sources in A ⟹ there are n unique images in B \\ ⟹ | I m (f) | = | A | = n \\ I m (f) \subseteq B \land | I m (f) | = n ⟹ I m (f) = B ⟹ f is surjective & (1) \\ Let f be surjective \\ \forall b \in B : \exists a \in A : f (a) = b \\ Let a_{1}, a_{2} \in A : a_{1} \neq a_{2} \land f (a_{1}) = f (a_{2}) \\ Let b \in B : b = f (a_{1}) = f (a_{2}) \\ | A ∖ {a_{1}, a_{2}} | = n - 2 \\ | B ∖ {b} | = n - 1 \\ \forall b_{1} \in B ∖ {b} : b_{1} \neq b ⟹ f (a_{1}) \neq b_{1} \neq f (a_{2}) \\ ⟹ There are n - 1 distinct images that have at least one source each, \\ however there are only n - 2 distinct sources \\ ⟹ \exists a \in A, \exists b_{1}, b_{2} \in B : f (a) = b_{1} = b_{2} ⟹ f is not to one - Contradiction! \\ ⟹ [\forall a_{1}, a_{2} \in A : a_{1} \neq a_{2} ⟹ f (a_{1}) \neq f (a_{2})] ⟹ f is injective & (2) \\ (1) \land (2) ⟹ f is injective ⟺ f is surjective \end{matrix}

8b

\begin{matrix} Let f : A \to B \\ Prove: [\exists f : f is injective ⟺ f is surjective] ⟺ | A | = | B | \\ Proof: \\ As proved in 8a, \forall f : | A | = | B | ⟹ [f is injective ⟺ f is surjective] \\ ⟹ | A | = | B | ⟹ [\exists f : f is injective ⟺ f is surjective] & (1) \\ Let \exists f : f is injective ⟺ f is surjective \\ Let | A | > | B | = n \\ A = {a_{1}, a_{2}, \dots, a_{n}, a_{n + 1}, \dots}, B = {b_{1}, b_{2}, \dots, b_{n}} \\ Let \forall i \in [1, n] : f (a_{i}) = b_{i} ⟹ f is surjective \\ By our assumption, f is also injective, but there is no b_{n + 1} \\ ⟹ \exists i \in [1, n] : f (a_{n + 1}) = b_{i} ⟹ \exists i \in [1, n] : a_{i} \neq a_{n + 1} \land f (a_{i}) = f (a_{n + 1}) \\ ⟹ f is not injective - Contradiction! \\ ⟹ | A | ≯ | B | \\ Let n = | A | < | B | \\ A = {a_{1}, a_{2}, \dots, a_{n}}, B = {b_{1}, b_{2}, \dots, b_{n}, b_{n + 1}, \dots} \\ Let \forall i \in [1, n] : f (a_{i}) = b_{i} ⟹ f is injective \\ By our assumption, f is also surjective, but there is no a_{n + 1} \\ ⟹ ∄ i \in [1, n] : f (a_{i}) = b_{n + 1} ⟹ f is not surjective - Contradiction! \\ ⟹ | A | ≮ | B | \\ | A | ≯ | B | \land | A | ≮ | B | ⟹ | A | = | B | \\ ⟹ [\exists f : f is injective ⟺ f is surjective] ⟹ | A | = | B | & (2) \\ (1) \land (2) ⟹ [\exists f : f is injective ⟺ f is surjective] ⟺ | A | = | B | \end{matrix}

9

\begin{matrix} Let X = P (N \times N) \\ S on X is defined as following: \\ R_{1} S R_{2} ⟺ R_{1} \cup R_{2} is an equivalence relation \end{matrix}

9a

\begin{matrix} Is S an equivalence relation on X ? \\ Solution: \\ Let R_{1} \in X \\ R_{1} S R_{1} ⟺ R_{1} \cup R_{1} is an equivalence relation \\ R_{1} \cup R_{1} = R_{1} ⟹ [S is reflexive ⟺ R_{1} is an equivalence relation] \\ X is a set of all relations on N \\ Let R = {(n, m) \in N \times N | n < m} \\ R \subseteq N \times N ⟹ R \in P (N \times N) \\ R is not reflexive ⟹ R is not an equivalence relation \\ ⟹ S is not reflexive ⟹ S is not an equivalence relation \end{matrix}

9b

\begin{matrix} Prove: (S \circ S) is an equivalence relation \\ Proof: \\ Let us define (S \circ S) \\ R_{1} (S \circ S) R_{2} ⟺ \exists R_{3} : R_{1} S R_{3} \land R_{3} S R_{2} \\ ⟺ \exists R_{3} : R_{1} \cup R_{3} is an equivalence relation \land R_{3} \cup R_{2} is an equivalence relation \\ \forall R_{1}, R_{2} \in P (N \times N) : R_{1} \cup N \times N = R_{2} \cup N \times N = N \times N - an equivalence relation \\ ⟹ \forall R_{1}, R_{2} \in P (N \times N) : R_{1} (S \circ S) R_{2} ⟹ S is full \\ ⟹ (S \circ S) is an equivalence relation \end{matrix}