Discrete-math 11

Partial order properties (continued) #theorem

\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}

1. and 2. proved in lecture 10

\begin{matrix} Proof for 3. \\ Let a \in A be a minimal element \\ (A, ≼) is a totally ordered set ⟹ \forall a, b \in A : [\begin{matrix} a ≼ b \\ b ≼ a \end{matrix} \\ Let b \in A \\ 1. b ≼ a \\ a is minimal ⟹ \\ \forall b \in A : (b ≼ a \to b = a) ⟹ b = a \\ \underset{≼ is reflexive}{⟹} a ≼ a ⟹ a ≼ b \\ 2. a ≼ b \\ \forall b \in A : a ≼ b ⟹ a = m i n (A) \end{matrix}

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

\begin{matrix} u \in A is called an upper bound of B iff \\ \forall x \in B : x ≼ u \end{matrix}

\begin{matrix} l \in A is called a lower bound of B iff \\ \forall x \in B : l ≼ x \end{matrix}

\begin{matrix} Let U be set of all upper bounds of B \\ If U has a minimum, this element is called the least upper bound of B \\ \exists u = m i n (U) ⟹ u = s u p (B) \end{matrix}

\begin{matrix} Let L be set of all lower bounds of B \\ If L has a maximum, this element is called the greatest lower bound of B \\ \exists l = m a x (L) ⟹ l = i n f (B) \end{matrix}

Let f \subseteq A \times B

\begin{matrix} f is complete iff \\ \forall a \in A \exists b \in B : (a, b) \in f \end{matrix}

\begin{matrix} f is to one iff \\ \forall a \in A \forall b_{1}, b_{2} \in B : ((a, b_{1}) \in f \land (a, b_{2}) \in f) \to b_{1} = b_{2} \end{matrix}

\begin{matrix} f is onto iff \\ \forall b \in B \exists a \in A : (a, b) \in f \end{matrix}

\begin{matrix} f is one-to-one iff \\ \forall a_{1}, a_{2} \in A \forall b \in B : ((a_{1}, b) \in f \land (a_{2}, b) \in f) \to a_{1} = a_{2} \end{matrix}

\begin{matrix} Let f \subseteq N \times P (N) \\ f = {(n, X) | \forall n \in N, \forall X \in P (N) : n \in X} \\ f is complete: \forall n \in N : n \in N \\ f is not to one: \forall n \in N : n \in N \land n \in {n} \\ f is not onto: \forall n \in N : (n, \emptyset) \notin f \\ f is not one-to-one: (1, N) \in f \land (2, N) \in f \end{matrix}

\begin{matrix} Relation f \subseteq A \times B is called a function iff \\ f is complete and one-to-one \\ In this case: f : A \to B \\ \forall a \in A \exists! b \in B : (a, b) \in f \\ b = f (a) \end{matrix}

\begin{matrix} Let f \subseteq N \times N \\ f = {(x, y) | \forall x, y \in N : y = x - 1} \\ f is not complete: x = 1 ⟹ x - 1 \notin N \end{matrix}

Let f : A \to B

\begin{matrix} f is called a one-to-one function iff f is also a one-to-one relation \\ \forall a_{1}, a_{2} \in A : f (a_{1}) = f (a_{2}) ⟹ a_{1} = a_{2} \end{matrix}

\begin{matrix} f is called an onto function iff f is also an onto relation \\ \forall b \in B \exists a \in A : f (a) = b \end{matrix}

\begin{matrix} Let f : N \to N \\ f (x) = x + 1 \\ f is one-to-one: f (x_{1}) = f (x_{2}) ⟹ x_{1} + 1 = x_{2} + 1 ⟹ x_{1} = x_{2} \\ f is not onto: f (x) \neq 1 \end{matrix}

\begin{matrix} Let f : A \to B \\ A is called a domain of f \\ D o m (f) = A \end{matrix}

\begin{matrix} Let f : A \to B \\ B is called a range of f \\ R a n g e (f) = D \end{matrix}

\begin{matrix} Let f : A \to B \\ Set of all possible values of f (x) is called image of the function \\ I m (f) = {f (x) | x \in A} = {b \in B | \exists a \in A : f (a) = b} \end{matrix}

\begin{matrix} Let f : A \to B, g : B \to C \\ Composition of f with g : (g \circ f) : A \to C \\ \forall x \in A : (g \circ f) (x) = g (f (x)) \end{matrix}