Exam 2023 (B)

5

\begin{matrix} Sets A, B are called equivalent if \exists f : A \to B : f is bijective \end{matrix}

\begin{matrix} Are these sets equivalent? \\ A = {n \in N | n is even} \\ B = {n \in N | n is odd} \\ Solution: \\ Let f : A \to B, f (n) = n - 1 \\ Let n \neq m \in A \\ Let n < m WLOG \\ ⟹ f (m) = m - 1 > f (n) = n - 1 ⟹ f is injective \\ Let k \in B \\ k \in N ⟹ k + 1 \in N \\ k is odd ⟹ k + 1 is even ⟹ k + 1 \in A \\ f (k + 1) = k + 1 - 1 = k ⟹ f is surjective \\ ⟹ f is bijective ⟹ A, B are equivalent \end{matrix}

\begin{matrix} Let A be a set \\ Let R be a relation on P (A) \\ \forall B, C \in P (A) : (B, C) \in R ⟺ B is equivalent to C \\ Prove: R is an equivalence relation \\ Proof: \\ Let B \in P (A) \\ I_{B} : B \to B is biejctive \\ ⟹ B is equivalent to B ⟹ (B, B) \in R ⟹ R is reflexive \\ Let B, C \in P (A) \\ (B, C) \in R ⟹ \exists f : B \to C : f is bijective ⟹ \exists f^{- 1} : C \to B : f^{- 1} bijective \\ ⟹ C is equivalent to B ⟹ (C, B) \in R ⟹ R is symmetric \\ Let B, C, D \in P (A) \\ (B, C), (C, D) \in R ⟹ \exists f : B \to C : f is bijective, \exists g : C \to D : g is bijective \\ f is bijective ⟹ (g \circ f) : B \to D is bijective \\ ⟹ (B, D) \in R ⟹ R is transitive \\ ⟹ R is an equivalence relation \end{matrix}

\begin{matrix} Prove: {0, 1}^{A}, P (A) are equivalent \\ Proof: \\ Let F : P (A) \to {0, 1}^{A}, F (X) = {(x, f_{X} (x)) | x \in A} \\ Where f_{X} : A \to {0, 1}, f_{X} (x) = {\begin{cases} 1 & x \in X \\ 0 & x \notin X \end{cases} \\ Let X \neq Y \in P (A) \\ X \neq Y ⟹ \exists x \in X : x \notin Y (WLOG) \\ ⟹ (x, 1) \in F (X), (x, 1) \notin F (Y) ⟹ F (X) \neq F (Y) \\ ⟹ F is injective \\ Let g \in {0, 1}^{A} \\ \forall x \in A : \exists y \in {0, 1} : (x, y) \in g \\ Let X = {x \in A | (x, 1) \in g} \\ F (X) = {(x, f_{X} (x)) | x \in A} = {(x, 1) | x \in X} \cup {(x, 0) | x \in A ∖ X} = g \\ ⟹ F is surjective ⟹ F is bijective \\ ⟹ {0, 1}^{A}, P (A) are equivalent \end{matrix}