Discrete-math 3

Empty set is a subset of any set #lemma

Prove: \emptyset \subseteq A

Formalized statement: \forall x : x \in \emptyset \to x \in A

x \in \emptyset \equiv F a l s e

\forall x : F a l s e \to x \in A

\forall x : T r u e ⟹ \emptyset \subseteq A

Prove: A \subseteq B and B \subseteq C ⟹ A \subseteq C

Formalized statement: \forall x : x \in A \to x \in C

$x \notin A ⟹ \forall x : x \in A \to x \in C \equiv \forall x : F a l s e \to x \in C \equiv T r u e$
$x \in A ⟹ x \in B ⟹ x \in C ⟹ \forall x : x \in A \to x \in C \equiv T r u e \to T r u e \equiv T r u e$

⟹ A \subseteq C

A = B \leftrightarrow ((A \subseteq B) \land (B \subseteq A))

\begin{matrix} Let A = {2 k - 1 | k \in Z} \\ Let B = {2 k + 1 | k \in Z} \\ Prove: A = B \end{matrix}

\begin{matrix} Let x \in A ⟹ \exists k \in Z : x = 2 k - 1 = 2 (k - 1) + 1 \\ k \in Z ⟹ k - 1 \in Z ⟹ \exists k^{'} = k - 1 \in Z : x = 2 k^{'} + 1 ⟹ \exists k^{'} \in Z : x \in B ⟹ A \subseteq B \end{matrix}

\begin{matrix} Let x \in B ⟹ \exists k \in Z : x = 2 k + 1 = 2 (k + 1) - 1 \\ k \in Z ⟹ k + 1 \in Z ⟹ \exists k^{'} = k + 1 \in Z : x = 2 k^{'} - 1 ⟹ \exists k^{'} \in Z : x \in A ⟹ B \subseteq A \end{matrix}

(A \subseteq B) \land (B \subseteq A) ⟹ A = B

A \cap B = \forall x : x \in A \land x \in B

A \cup B = \forall x : x \in A \lor x \in B

A ∖ B = \forall x : x \in A \land x \notin B

A △ B = \forall x : x \in (A ∖ B) \lor x \in (B ∖ A)

\begin{matrix} Domain: U (universal set) \\ A^{c} = {x \in U | x \notin A} \end{matrix}

A \cup A = A = A \cap A

\begin{matrix} A \cup A = {x | x \in A \lor x \in A} = {x | x \in A} ⟹ A \cup A = A \\ A \cap A = {x | x \in A \land x \in A} = {x | x \in A} ⟹ A \cap A = A \end{matrix}

A \cap \emptyset = \emptyset

A \cap \emptyset = {x | x \in A \land x \in \emptyset} = {x | x \in A \land F a l s e} = {x | F a l s e} = \emptyset

A \cup \emptyset = A

A \cup \emptyset = {x | x \in A \lor x \in \emptyset} = {x | x \in A \lor F a l s e} = {x | x \in A} = A

\begin{matrix} A \cup B = B \cup A \\ A \cap B = B \cap A \\ A △ B = B △ A \end{matrix}

\begin{matrix} A \cup (B \cup C) = (A \cup B) \cup C \\ A \cap (B \cap C) = (A \cap B) \cap C \\ A △ (B △ C) = (A △ B) △ C \end{matrix}

\begin{matrix} A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \\ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \end{matrix}

\begin{matrix} A \cap B \subseteq A \subseteq A \cup B \\ \emptyset \subseteq A \\ A \subseteq A \\ (A \subseteq C \land B \subseteq C) \to A \cup B \subseteq C \end{matrix}

(A \subseteq B \land B \subseteq C) \to A \subseteq C

A △ B = (A \cup B) ∖ (A \cap B)