Midterm

1

\begin{matrix} Let A be a finite set \\ Let R be a relation on A \\ R^{0} = R \\ R^{i + 1} = R^{i} \cup {(a, b) \in A \times A | \exists c \in A : (a, c), (b, c) \in R^{i}} \\ 1. Prove or disprove: R^{1} is transitive \\ 2. Prove: \forall k \in N_{0} : R^{k} is symmetric ⟹ R^{k + 1} is symmetric \\ 3. Prove: \exists n \in N_{0} : R^{n} is transitive \end{matrix}

\begin{matrix} Let A, B be non-empty sets \\ Let ≼ be an order relation on B \\ Let R be a relation on B^{A} \\ \forall f, g \in B^{A} : f R g ⟺ \forall a \in A : f (a) ≼ g (a) \\ 1. Prove: R is an order relation \\ 2. Prove: ≼ has a maximum ⟺ R has a maximum \\ Let h \in B^{A} be surjective \\ Let F :≼ \to B^{A} : F ((b, b^{'})) = g \\ Where g (a) = {\begin{cases} b & h (a) ≼ b \\ b^{'} & otherwise \end{cases} \\ 3. Prove: ≼ is a total order ⟹ F is injective \end{matrix}