Discrete-math 6

\begin{matrix} Let B \subseteq P (A) \\ Then \\ s u p (B) = ⋃_{X \in B} X \\ i n f (B) = ⋂_{X \in B} X \\ Proof for supremum: \\ By properties of inclusion: X \subseteq X \cup Y ⟹ ⋃_{X \in B} X is an upper bound \\ Let A^{'} \subset ⋃_{X \in B} X such that A^{'} is an upper bound of B \\ Then \exists a \in (⋃_{X \in B} X) ∖ A^{'} ⟹ \exists A_{i} \in B : a \in A_{i} \land a \notin A^{'} \\ ⟹ a \in A_{i} ∖ A^{'} ⟹ A^{'} ⊉ A_{i} \in B ⟹ A^{'} is not an upper bound of B - Contradiction! \\ ⟹ s u p (B) = ⋃_{X \in B} X \end{matrix}

\begin{matrix} Let A, B be finite sets, | A | = n, | B | = m \\ [\exists f : A \to B : f is surjective] ⟺ m \leq n \\ Proof: \\ A = {a_{1}, a_{2}, \dots, a_{n}}, B = {b_{1}, b_{2}, \dots, b_{m}} \\ Let m \leq n \\ Let f = {(a_{i}, b_{i}) | \forall i \in [1, m]} ⟺ f (a_{i}) = b_{i} \\ \forall i \in [1, m] : a_{i} \in A \land b_{i} \in B ⟹ \forall b \in B \exists a \in A : f (a) = b \\ m \leq n ⟹ \exists f : f is surjective (1) \\ Let \exists f : A \to B : f is surjective \\ f is surjective ⟹ I m (f) = B = {f (a_{1}), f (a_{2}), \dots, f (a_{n})} \\ ⟹ {\begin{cases} | B | = | A | & f is one-to-one \\ | B | < | A | & otherwise \end{cases} ⟹ m \leq n \\ \exists f : A \to B : f is surjective ⟹ m \leq n (2) \\ (1) and (2) ⟹ \exists f : A \to B : f is surjective ⟺ m \leq n \end{matrix}