Discrete-math 3

Let A, B, C be sets. Prove or disprove the following statements:

1a

\begin{matrix} A △ (B \cap C) = (A △ B) \cap (A △ C) \\ Disproof: \\ Let A = C \neq \emptyset, B \cap C \neq C \\ Then: \\ A △ (B \cap C) \neq \emptyset \\ (A △ B) \cap (A △ C) = (A △ B) \cap \emptyset = \emptyset \\ ⟹ A △ (B \cap C) \neq (A △ B) \cap (A △ C) \\ An example of such sets: A = {1, 2}, B = {1}, C = {1, 2} \end{matrix}

1b

\begin{matrix} A △ B = A^{c} △ B^{c} \\ Proof: \\ A^{c} △ B^{c} = {x ∣ x \in (A^{c} ∖ B^{c}) \lor x \in (B^{c} ∖ A^{c})} = \\ = {x ∣ (x \in A^{c} \land x \notin B^{c}) \lor (x \in B^{c} \land x \notin A^{c})} = \\ = {x \in U ∣ (x \notin A \land x \in B) \lor (x \notin B \land x \in A)} = \\ = {x \in U ∣ x \in (B ∖ A) \lor x \in (A ∖ B)} = {x ∣ x \in (B ∖ A) \lor x \in (A ∖ B)} = A △ B \\ ⟹ A △ B = A^{c} △ B^{c} \end{matrix}

1c

\begin{matrix} A \cap ((B \cup A^{c}) \cap B^{c}) = \emptyset \\ Proof: \\ A \cap ((B \cup A^{c}) \cap B^{c}) = A \cap ((B \cap B^{c}) \cup (A^{c} \cap B^{c})) = A \cap (\emptyset \cup (A^{c} \cap B^{c})) = \\ = A \cap (A^{c} \cap B^{c}) = (A \cap A^{c}) \cap B^{c} = \emptyset \cap B^{c} = \emptyset \\ ⟹ A \cap ((B \cup A^{c}) \cap B^{c}) = \emptyset \end{matrix}

1d

\begin{matrix} B \subseteq A ⟹ A △ B = A ∖ B \\ Proof: \\ B \subseteq A ⟹ \forall x : x \in B \to x \in A \\ B ∖ A = {x | x \in B \land x \notin A} \underset{B \subseteq A}{\subseteq} {x | \underset{F}{\underset{⏟}{x \in A \land x \notin A}}} = \emptyset \\ B ∖ A \subseteq \emptyset ⟹ B ∖ A = \emptyset \\ ⟹ A △ B = (A ∖ B) \cup (B ∖ A) = (A ∖ B) \cup \emptyset = A ∖ B \\ ⟹ A △ B = A ∖ B \end{matrix}

1e

\begin{matrix} A ∖ (B ∖ C) = (A ∖ B) ∖ C \\ Disproof: \\ Let A \neq \emptyset, A \neq B, B = C \neq \emptyset \\ For example: A = {1, 2}, B = {1}, C = {1} \\ A ∖ (B ∖ C) = A ∖ \emptyset = A \\ (A ∖ B) ∖ C = {2} ∖ {1} = {2} \\ ⟹ A ∖ (B ∖ C) \neq (A ∖ B) ∖ C \end{matrix}

2a

\begin{matrix} Prove: For any sets X, Y : if X \cap Y = \emptyset, then X △ Y = X \cup Y \\ Proof: \\ X △ Y = (X \cup Y) ∖ (X \cap Y) = (X \cup Y) ∖ \emptyset = X \cup Y \\ ⟹ X △ Y = X \cup Y \end{matrix}

2b

\begin{matrix} Prove: For any sets X, Y : if X \subseteq Y, then X \cup (Y ∖ X) = Y \\ Proof: \\ X \cup (Y ∖ X) = {a ∣ a \in X \lor (a \in Y \land a \notin X)} = \\ = {a ∣ (a \in X \lor a \in Y) \land \underset{T}{\underset{⏟}{(a \in X \lor a \notin X)}}} = {a ∣ a \in X \lor a \in Y} \\ X \subseteq Y ⟺ \forall a : (a \in X ⟹ a \in Y) \\ ⟹ {a ∣ (a \in X \lor a \in Y)} = {a ∣ a \in Y \cup a \in Y} = Y \cup Y = Y \\ ⟹ X \cup (Y ∖ X) = Y \end{matrix}

2c

\begin{matrix} Prove: For any sets A, B : (A △ B) \cap (A \cap B) = \emptyset \\ Proof: \\ (A △ B) \cap (A \cap B) = ((A \cup B) ∖ (A \cap B)) \cap (A \cap B) = \\ = {x ∣ (x \in (A \cup B) \land x \notin (A \cap B)) \land x \in (A \cap B)} = \\ = {x ∣ x \in (A \cup B) \land (x \notin (A \cap B) \land x \in (A \cap B))} = \\ = {x ∣ x \in (A \cup B) \land F} = {x ∣ F} = \emptyset \\ ⟹ (A △ B) \cap (A \cap B) = \emptyset \end{matrix}

2d

\begin{matrix} Prove: For any sets A, B : (A △ B) △ (A \cap B) = A \cup B \\ Proof: \\ (A △ B) △ (A \cap B) = ((A △ B) \cup (A \cap B)) ∖ \underset{\emptyset, proved in 2c}{\underset{⏟}{((A △ B) \cap (A \cap B))}} = \\ = (A △ B) \cup (A \cap B) = ((A \cup B) ∖ (A \cap B)) \cup (A \cap B) \\ Let X = A \cap B, Y = A \cup B \\ ((A \cup B) ∖ (A \cap B)) \cup (A \cap B) = (Y ∖ X) \cup X \\ By properties of inclusion: \\ X = A \cap B \subseteq A \cup B = Y ⟹ X \subseteq Y \\ ⟹ (Y ∖ X) \cup X \underset{Proved in 2b}{=} Y \\ ⟹ ((A \cup B) ∖ (A \cap B)) \cup (A \cap B) = A \cup B \\ ⟹ (A △ B) △ (A \cap B) = A \cup B \end{matrix}

3a

\begin{matrix} Prove: {(⋂_{i \in I} A_{i})}^{c} = ⋃_{i \in I} A_{i}^{c} \\ Proof: \\ {(⋂_{i \in I} A_{i})}^{c} = {x \in U ∣ x \notin ⋂_{i \in I} A_{i}} = {x \in U ∣ \neg (\forall i \in I : x \in A_{i})} = \\ = {x \in U ∣ \exists i \in I : x \notin A_{i}} = {x ∣ \exists i \in I : x \in A_{i}^{c}} = ⋃_{i \in I} A_{i}^{c} \\ ⟹ {(⋂_{i \in I} A_{i})}^{c} = ⋃_{i \in I} A_{i}^{c} \end{matrix}

3b

\begin{matrix} Prove: {(⋃_{i \in I} A_{i})}^{c} = ⋂_{i \in I} A_{i}^{c} \\ Proof: \\ {(⋃_{i \in I} A_{i})}^{c} = {x \in U ∣ x \notin ⋃_{i \in I} A_{i}} = {x \in U ∣ \neg (\exists i \in I : x \in A_{i})} = \\ = {x \in U ∣ \forall i \in I : x \notin A_{i}} = {x ∣ \forall i \in I : x \in A_{i}^{c}} = ⋂_{i \in I} A_{i}^{c} \\ ⟹ {(⋃_{i \in I} A_{i})}^{c} = ⋂_{i \in I} A_{i}^{c} \end{matrix}

\begin{matrix} For all n \in N, define: \\ A_{n} = {n - 1, n, n + 1} \end{matrix}

4a

\begin{matrix} N_{0} - according to Wikipedia, this denotion is a set of natural numbers and 0 \\ ⋃_{n \in N} A_{n} = N_{0} \\ Proof: \\ 1. ⋃_{n \in N} A_{n} \subseteq N_{0} \\ Let x \in ⋃_{n \in N} A_{n} \\ Then, \exists n \in N : x \in A_{n} ⟺ \exists n \in N : (x = n - 1) \lor (x = n) \lor (x = n + 1) \\ 1.1 x = n - 1, x is a difference between a natural number and 1, \\ therefore it is either a natural number, or 0 \\ 1.2 x = n, x is a natural number \\ 1.3 x = n + 1, x is a sum of two natural numbers, \\ therefore it is a natural number \\ 1.1, 1.2 and 1.3 ⟹ x \in N_{0} ⟹ ⋃_{n \in N} A_{n} \subseteq N_{0} \\ 2. N_{0} \subseteq ⋃_{n \in N} A_{n} \\ Let x \in N_{0} \\ 2.1 x = 0, then \exists n = 1 : x \in A_{1} ⟹ x \in ⋃_{n \in N} A_{n} \\ 2.2 x \in N, then \exists n = x : x \in A_{n} ⟹ x \in ⋃_{n \in N} A_{n} \\ 2.1 and 2.2 ⟹ x \in ⋃_{n \in N} A_{n} ⟹ N_{0} \subseteq ⋃_{n \in N} A_{n} \\ 1. and 2. ⟹ ⋃_{n \in N} A_{n} = N_{0} \end{matrix}

4b

\begin{matrix} ⋂_{n \in N} A_{n} = \emptyset \\ Proof: \\ \emptyset is a subset of any set ⟹ \emptyset \subseteq ⋂_{n \in N} A_{n} \\ ⋂_{n \in N} A_{n} \subseteq \emptyset \\ Let x \in ⋂_{n \in N} A_{n} \\ Then \forall n \in N : x \in A_{n} \\ Let n = 1, then x \in A_{1} = {0, 1, 2} \\ Now let n = 4, then x \in A_{4} = {3, 4, 5} \\ ⟹ x \in A_{1} \land x \in A_{4} ⟹ x \in (A_{1} \cap A_{4}) ⟹ x \in \emptyset \\ ⟹ ⋂_{n \in N} A_{n} \subseteq \emptyset \\ (\emptyset \subseteq ⋂_{n \in N} A_{n}) \land (⋂_{n \in N} A_{n} \subseteq \emptyset) ⟺ ⋂_{n \in N} A_{n} = \emptyset \end{matrix}

5a

\begin{matrix} Prove or disprove: P (A) ∖ P (B) \neq P (A ∖ B) \\ Proof: \\ \forall C : \emptyset \in P (C) ⟹ \emptyset \notin (P (A) ∖ P (B)) \\ \forall C : \emptyset \in P (C) ⟹ \emptyset \in P (A ∖ B) \\ ⟹ P (A) ∖ P (B) \neq P (A ∖ B) \end{matrix}

5b

\begin{matrix} Prove or disprove: P (A) △ P (B) = P (A △ B) \\ Disproof: \\ \emptyset \notin (P (A) △ P (B)) \\ \emptyset \in P (A △ B) \\ Example: \\ A = \emptyset, B = \emptyset \\ P (A) = P (B) = {\emptyset} \\ P (A) △ P (B) = \emptyset \\ P (A △ B) = P (△) = {\emptyset} \\ ⟹ P (A) △ P (B) \neq P (A △ B) \end{matrix}

5c

\begin{matrix} Prove or disprove: A \cap P (A) = \emptyset \\ Disproof: \\ Example: \\ A = {\emptyset} \\ P (A) = {\emptyset, {\emptyset}} \\ A \cap P (A) = {\emptyset} \neq \emptyset \\ ⟹ A \cap P (A) \neq \emptyset \end{matrix}

5d

\begin{matrix} Prove or disprove: P (A) \cap P (P (A)) \neq \emptyset \\ Proof: \\ \forall C : \emptyset \in P (C) ⟹ \emptyset \in P (A) \land \emptyset \in P (P (A)) \\ ⟹ \emptyset \in P (A) \cap P (P (A)) ⟹ P (A) \cap P (P (A)) \neq \emptyset \end{matrix}

5e

\begin{matrix} Prove or disprove: A \subseteq B ⟺ P (A) \subseteq P (B) \\ Proof: \\ 1. Let A \subseteq B : \\ D \in P (A) ⟺ D \subseteq A ⟹ D \subseteq B ⟺ D \in P (B) \\ (D \in P (A) ⟹ D \in P (B)) ⟹ P (A) \subseteq P (B) \\ 2. Let P (A) \subseteq P (B) : \\ x \in A ⟺ {x} \subseteq A ⟺ {x} \in P (A) ⟹ {x} \in P (B) ⟺ {x} \subseteq B ⟺ x \in B \\ (x \in A ⟹ x \in B) ⟹ A \subseteq B \\ 1. and 2. ⟹ A \subseteq B ⟺ P (A) \subseteq P (B) \end{matrix}

5f

\begin{matrix} Prove or disprove: P (A) \cap P (B) = {\emptyset} ⟺ A △ B = A \cup B \\ Proof: \\ 1. Let A △ B = A \cup B \\ P (A) \cap P (B) = {X ∣ X \subseteq A \land X \subseteq B} \\ A △ B = (A \cup B) ∖ (A \cap B) = A \cup B \\ ⟹ A \cap B = \emptyset \\ Let X \subseteq A, X \subseteq B \\ \forall x \in X : (x \in A \land x \in B) \\ \forall x \in X : x \in A \cap B \\ \forall x \in X : x \in \emptyset ⟹ X = \emptyset ⟹ P (A) \cap P (B) = {\emptyset} \\ 2. Let P (A) \cap P (B) = {\emptyset} \\ Let X = A \cap B \\ X \subseteq A \land X \subseteq B ⟹ X \in P (A) \land X \in P (B) \\ ⟹ X \in (P (A) \cap P (B)) ⟹ X = \emptyset \\ A △ B = (A \cup B) ∖ (A \cap B) = (A \cup B) ∖ X = (A \cup B) ∖ \emptyset = A \cup B \\ ⟹ A △ B = A \cup B \\ 1. and 2. ⟹ P (A) \cap P (B) = {\emptyset} ⟺ A △ B = A \cup B \end{matrix}

\begin{matrix} {A_{n}}_{n \in N} \\ A_{n} = {k \in N ∣ 2 \leq k \leq 3 n - 2} \\ B_{n} = A_{n + 1} ∖ A_{n} \end{matrix}

6a

\begin{matrix} A_{n + 1} = {k \in N ∣ 2 \leq k \leq 3 n + 1} = A_{n} \cup {3 n - 1, 3 n, 3 n + 1 ∣ n \in N} \\ ⟹ B_{n} = {3 n - 1, 3 n, 3 n + 1 ∣ n \in N} \\ ⋃_{n \in N} B_{n} = N ∖ {1} \\ Proof: \\ 1. ⋃_{n \in N} B_{n} \subseteq (N ∖ {1}) \\ Let x \in ⋃_{n \in N} B_{n} \\ Then, \exists n \in N : x \in B_{n} ⟺ \exists n \in N : (x = 3 n - 1) \lor (x = 3 n) \lor (x = 3 n + 1) \\ 1.1 x = 3 n - 1, x is a difference between a natural number \\ bigger than 2, and 1, therefore it is a natural number bigger than 1 \\ 1.2 x = 3 n, x is a natural number bigger than 1 \\ 1.3 x = 3 n + 1, x is a sum of two natural numbers, \\ therefore it is a natural number bigger than 1 \\ 1.1, 1.2 and 1.3 ⟹ x \in (N ∖ {1}) ⟹ ⋃_{n \in N} B_{n} \subseteq (N ∖ {1}) \\ 2. (N ∖ {1}) \subseteq ⋃_{n \in N} B_{n} \\ Let x \in N ∖ {1} \\ 2.1 If x \equiv 0 \mod 3, then \exists n \in N : x = 3 n \\ ⟹ x \in B_{n} ⟹ x \in ⋃_{n \in N} B_{n} \\ 2.2 If x \equiv 1 \mod 3, then \exists n \in N : x = 3 n + 1 \\ ⟹ x \in B_{n} ⟹ x \in ⋃_{n \in N} B_{n} \\ 2.3 If x \equiv 2 \mod 3, then \exists n \in N : x = 3 n + 2 = 3 (n + 1) - 1 \\ ⟹ x \in B_{n + 1} ⟹ x \in ⋃_{n \in N} B_{n} \\ 2.1, 2.2 and 2.3 ⟹ x \in ⋃_{n \in N} B_{n} ⟹ (N ∖ {1}) \subseteq ⋃_{n \in N} B_{n} \\ 1. and 2. ⟹ ⋃_{n \in N} B_{n} = N ∖ {1} \end{matrix}

6b

\begin{matrix} Let D_{n} = N ∖ B_{n} \\ ⋂_{n \in N} D_{n} = {1} \\ Proof: \\ Let domain of the complement be N \\ Then D_{n}^{c} = (N ∖ B_{n})^{c} = B_{n} \\ Given that ⋃_{n \in N} B_{n} = N ∖ {1} \\ As proved in 3a: ⋃_{n \in N} B_{n} = ⋃_{n \in N} D_{n}^{c} = {(⋂_{n \in N} D_{n})}^{c} \\ ⟹ {(⋂_{n \in N} D_{n})}^{c} = N ∖ {1} ⟹ {({(⋂_{n \in N} D_{n})}^{c})}^{c} = (N ∖ {1})^{c} = {1} \\ ⟹ ⋂_{n \in N} D_{n} = {1} \end{matrix}