Discrete-math 10

Ordering relations

\begin{matrix} Let (A, ≼) be a partially ordered set \end{matrix}

\begin{matrix} a is called the smallest element of A iff \\ \forall b \in A : a ≼ b \\ Sometimes the smallest element is called minimum of the set \end{matrix}

\begin{matrix} a \in A is called a minimal element of A iff \\ \neg (\exists b \in A : b \neq a \land b ≼ a) \\ \equiv \forall b \in A : b = a \lor \neg (b ≼ a) \\ \equiv \forall b \in A : (b ≼ a) \to (b = a) \end{matrix}

\begin{matrix} a is called the greatest element of A iff \\ \forall b \in A : b ≼ a \\ Sometimes the biggest element is called maximum of the set \end{matrix}

\begin{matrix} a \in A is called a maximal element of A iff \\ \neg (\exists b \in A : b \neq a \land a ≼ b) \\ \equiv \forall b \in A : b = a \lor \neg (a ≼ b) \\ \equiv \forall b \in A : (a ≼ b) \to (b = a) \end{matrix}

graph TD;

8---4
9---3
4---2
6---3
6---2
5---1
7---1
2---1
3---1

\begin{matrix} Let (A, ≼) be a partially ordered set \\ 1. & If A has a smallest element, then it is unique \\ 2. & If A has a smallest element, then it is minimal and the only minimal element of the set \\ 3. & If in addition, (A, ≼) is a totally ordered set and a is a minimal element, \\ then a is also the smallest \end{matrix}

\begin{matrix} Proof for 1. \\ Let a = m i n (A), b = m i n (A) \\ a = m i n (A) \land b \in A ⟹ a ≼ b \\ b = m i n (A) \land a \in A ⟹ b ≼ a \\ a ≼ b \land b ≼ a \underset{By anti-symmetry of ordering relation}{⟹} a = b \\ ⟹ \exists! a \in A : a = m i n (A) \end{matrix}

\begin{matrix} Proof for 2. \\ Let a = m i n (A), b \in A : b ≼ a \\ a = m i n (A) ⟹ a ≼ b \\ a ≼ b \land b ≼ a ⟹ a = b ⟹ \forall b \in A : (b ≼ a) \to (b = a) \\ ⟹ a is a minimal element \\ Let c \in A, such that c is a minimal element \\ a = m i n (A) ⟹ a ≼ c \\ c is minimal ⟹ \forall x \in A : (x ≼ c) \to x = c \\ a ≼ c ⟹ a = c ⟹ a is the only minimal element \end{matrix}

\begin{matrix} Proof for 3. \\ Proof in lecture 11 \end{matrix}