Exam 2023 (C)

5

\begin{matrix} Let A be a set \\ Let R be a relation on A \\ Let α be some property of relations on A \\ S is called α -closure of R if: \\ 1. S satisfies property α \\ 2. R \subseteq S \\ 3. \forall relations K on A that satisfy α : R \subseteq K ⟹ S \subseteq K \\ α is called saved under intersecion in A if \\ \forall K \subseteq {R | R satisfies α on A} \neq \emptyset : ⋂_{R \in K} R satisfies α \end{matrix}

\begin{matrix} Let A = {1, 2, 3, 4} \\ Let R = {(1, 2), (2, 3), (3, 4)} \\ Find transitivity-closure of R \\ Solution: \\ S = {(1, 2), (2, 3), (1, 3), (3, 4), (1, 4), (2, 4)} \end{matrix}

\begin{matrix} Let A be a set \\ Let α be a property of relations on A \\ Let R be a relation satisfying α \\ Prove: α -closure of R is R itself \\ Proof: \\ Let S \neq R be an α -closure of R \\ ⟹ R \subseteq S ⟹ R \subset S \\ R satisfies α and R \subseteq R ⟹ S \subseteq R - Contradiction! \\ ⟹ R is an α -closure of R \end{matrix}

\begin{matrix} Let A be a set \\ Let α be a property of relations on A \\ Let R be a relation on A \\ Let T = {S | R \subseteq S : S satisfies α}, T \neq \emptyset \\ Prove: α is saved under intersection in A ⟹ ⋂_{S \in T} S is an α -closure of R \\ Proof: \\ α is saved under intersection in A \\ ⟹ \forall K \subseteq {R | R satisfies α} \neq \emptyset : ⋂_{R \in K} R satisfies α \\ T \subseteq {R | R satisfies α} ⟹ ⋂_{S \in T} S satisfies α \\ Let x \in R \\ \forall S \in T : R \subseteq S ⟹ x \in S ⟹ x \in ⋂_{S \in T} S ⟹ R \subseteq ⋂_{S \in T} S \\ Let X : R \subseteq X and X satisfies α \\ ⟹ X \in T ⟹ ⋂_{S \in T} S \subseteq X \\ ⟹ ⋂_{S \in T} S is an α -closure of R \end{matrix}

\begin{matrix} f, g : N \to N \\ f (n) = n + 1 ⟹ f is injective \\ g (n) = {\begin{cases} n - 1 & n > 1 \\ 1 & n = 1 \end{cases} \\ g (1) = g (2) = 1 ⟹ g is not injective \\ g (f (n)) = g (n + 1) = n + 1 - 1 = n ⟹ (g \circ f) is injective \end{matrix}