Discrete-math 5

\begin{matrix} Let (A, R) be a partially ordered finite set \\ Prove: \exists a \in A : a is a minimal element \\ Proof: \\ Base case. Let | A | = 1 \\ A = {a} ⟹ a is a minimal element \\ Induction step. Let | A | = n + 1 \\ Let a \in A, B = A ∖ {a} \\ Let S = (B \times B) \cap R ⟹ S is a parital ordering relation (proved in HW 5) \\ | B | = n, by induction assumption \exists b \in B : b is a minimal element of B \\ If a R b, let a be not minimal in A : \exists x \in A : x R a \land x \neq a \\ x \neq a ⟹ x \in B \\ x R a \land a R b ⟹ x R b \land x \in B ⟹ x = b ⟹ b R a \land a R b ⟹ a = b - Contradiction! \\ ⟹ a is a minimal element of A \\ If a R̸ b, let b be not minimal in A : \exists x \in A : x R b \land x \neq b \\ x R b ⟹ x \neq a ⟹ x \in B ⟹ [x R b \to x = b] ⟹ x = b - Contradiction! \\ ⟹ b is a minimal element of A \\ Base case + Induction step ⟹ Proved by induction \end{matrix}