Discrete-math 4

Subset and intersection #lemma

Prove: A \subseteq B \leftrightarrow A \cap B = A

\begin{matrix} 1. Prove: A \subseteq B \to A \cap B = A \\ 1.a By properties of inclusion: A \cap B \subseteq A \\ 1.b Prove: A \subseteq A \cap B \\ \forall x \in A : x \in A \equiv x \in A \land x \in A \equiv x \in A \land x \in B \equiv x \in A \cap B \\ ⟹ \forall x \in A : x \in A \cap B \equiv A \subseteq A \cap B \\ 2. Prove: A \cap B = A \to A \subseteq B \\ \forall x \in A : x \in A \equiv x \in A \land x \in B \equiv T r u e \land x \in B \equiv x \in B \\ ⟹ A \subseteq B \end{matrix}

\begin{matrix} {A_{i}}_{i \in I} is a family (ccollection) of sets \\ For example: \\ A_{1} = {1, 2, 3}; A_{2} = {3, 5}; A_{3} = {3, 10} \\ {A_{i}}_{i \in {1, 2, 3}} = {A_{1}, A_{2}, A_{3}} \end{matrix}

⋂_{i \in I} A_{i} = {x | \forall i \in I : x \in A_{i}}

⋃_{i \in I} A_{i} = {x | \exists i \in I : x \in A_{i}}

\begin{matrix} Let’s define the family of sets {A_{i}}_{i \in N} as following: \\ \forall i \in N : A_{i} = {i \in N | i \leq x} \end{matrix}

\begin{matrix} A_{1} = N \\ A_{2} = N ∖ {1} \\ \dots \end{matrix}

Let’s prove: ⋃_{i \in N} A_{i} = N

\begin{matrix} \forall x \in ⋃_{i \in N} A_{i} : \exists i \in N : x \in A_{i} \to x \in N ⟹ ⋃_{i \in N} A_{i} \subseteq N \\ \forall x \in N : \exists i = 1 : A_{i} = N \land x \in A_{i} ⟹ N \subseteq ⋃_{i \in N} A_{i} \end{matrix}

Let’s prove: ⋂_{i \in N} A_{i} = \emptyset

\begin{matrix} Suppose: \exists x : x \in ⋂_{i \in N} A_{i} \\ By definition of {A_{i}} : x \notin A_{x + 1} ⟹ x \notin ⋂_{i \in N} A_{i} \end{matrix}

P (A) = {X | X \subseteq A}

\forall X : X \in P (A) \leftrightarrow X \subseteq A

P ({1, 2}) = {\emptyset, {1}, {2}, {1, 2}}

P (\emptyset) = {\emptyset}

P ({\emptyset}) = {\emptyset, {\emptyset}}

Prove: A \subseteq B \leftrightarrow P (A) \subseteq P (B)

\begin{matrix} Let A \subseteq B : \\ \forall D \in P (A) : D \subseteq A \to D \subseteq B \equiv D \in P (B) ⟹ P (A) \subseteq P (B) \\ Let P (A) \subseteq P (B) : \\ \forall x \in A : {x} \subseteq A \equiv {x} \in P (A) \to {x} \in P (B) \equiv {x} \subseteq B \equiv x \in B ⟹ A \subseteq B \end{matrix}