> *Definition*: a relation $\sqsubseteq$ on a set $P$ is called an **order** if it is reflexive, antisymmetric and transitive.
>
>* The pair $(P, \sqsubseteq)$ is called a **partially ordered set** or for short **poset**.
>* Two elements $x$ and $y$ in a poset $(P, \sqsubseteq)$ are called comparable if $x \sqsubseteq y$ or $y \sqsubseteq x$. The elements are incomparable if $x \not\sqsubseteq y$ and $y \not\sqsubseteq x$.
>* If any two elements are comparable then the relation is called a linear order.
For example on the set of real numbers $\mathbb{R}$ the relation $\leq$ is an order relation. For any two numbers $x,y \in \mathbb{R}$ we have $x \leq y$ or $y \leq x$. This makes $\leq$ into a linear order.
> *Definition* **- Hasse diagram**: let $(P, \sqsubseteq)$ be a poset. The graph with vertex set $P$ and two vertices $x,y \in P$ adjacent if and only if $x \sqsubseteq y$ and there is no $z \in P$ different from $x$ and $y$ with $x \sqsubseteq z$ and $z \sqsubseteq y$.
## Maximal and minimal elements
> *Definition*: let $(P, \sqsubseteq)$ be a partially ordered set and $A \subseteq P$. An element $a \in A$ is called the **maximum** ($\top$) of $A$, if for all $a' \in A$ we have $a' \sqsubseteq a$. An element $a \in A$ is called **maximal** if for all $a' \in A$ we have that either $a' \sqsubseteq a$ or $a$ and $a'$ are incomparable.
>
> Similarly we can define the notion of **minimum** ($\bot$) and **minimal** element.
If we consider the poset of all subsets of a set $S$ then the empty set $\varnothing$ is the minimum of the poset, whereas the whole set $S$ is the maximum. The atoms are the subsets of $S$ containing just a single element.
> *Definition*: if a poset $(P, \sqsubseteq)$ has a minimum $\bot$, then the minimal elements of $P\backslash \{\bot\}$ are called the atoms of $P$.
> *Lemma*: let $(P, \sqsubseteq)$ be a partially ordered set. Then $P$ contains at most one maximum and one minimum.
??? note "*Proof*:"
Suppose $p,q \in P$ are maxima. Then $p \sqsubseteq q$ as $q$ is a maximum. Similarly $q \sqsubseteq p$ as $p$ is a maximum. By antisymmetry of $\sqsubseteq$ we have $p = q$.
> *Lemma*: let $(P, \sqsubseteq)$ be a finite poset then $P$ contains a minimal and a maximal element.
??? note "*Proof*:"
Consider the directed graph associated to $(P, \sqsubseteq)$ and pick a vertex in this graph. If the vertex is not maximal, then there is an edge leaving it. Move along this edge to the neighbour. Repeat this as long as no maximal element is found. Since the graph contains no cycles, a vertex will never be met twice. Hence, as $P$ is finite, the procedure has to stop. Implying a maximal element has been found. A minimal element of $(P, \sqsubseteq)$ is a maximal element of $(P, \sqsupseteq)$ and thus also exists.
> *Definition*: if $(P, \sqsubseteq)$ is a poset and $A \subseteq P$ then an **upperbound** for $A$ is an element $u$ with $a \sqsubseteq u$ for all $a \in A$. A **lowerbound** for $A$ is an element $u$ with $u \sqsubseteq a$ for all $a \in A$.
>
> If the set of all upperbounds of $A$ has a minimal element then this element is called the **least upperbound** or **supremum** of $A$. Such an element is denoted by $\mathrm{sup} A$.
>
> If the set of all lowerbounds of $A$ has a maximal element then this element is called the **largest lowerbound** or **infimum** of $A$. Such an element is denoted by $\mathrm{inf} A$.
For example let $S$ be a set. In $(\wp(S), \subseteq)$ any set $A$ of subsets of $S$ has a least upperbound and an largest lowerbound. Indeed
$$
\mathrm{sup} A = \bigcup_{X \in A} X \;\text{ and }\; \mathrm{inf} A = \bigcap_{X \in A} X.
$$
If $(P, \sqsubseteq)$ is a finite poset then the elements from $P$ can be ordered as $p_1, p_2, \dots, p_n$ such that $p_i \sqsubseteq p_j$ implies $i <j$.Thisimpliesthattheadjacencymatrixof$\sqsubseteq$isuppertriangular,whichmeansthatithasonlynonzeroentriesonorabovethemaindiagonal.
> *Definition*: an **ascending chain** in a poset $(P, \sqsubseteq)$ is a sequence $p_1 \sqsubseteq p_2 \sqsubseteq \dots$ of elements $p_i \in P,i \in \mathbb{N}$. A **descending chain** in $(P, \sqsubseteq)$ is a sequence $p_1 \sqsupseteq p_2 \sqsupseteq \dots$ of elements $p_i \in P, i \in \mathbb{N}$.
>
> The poset $(P, \sqsubseteq)$ is called **well founded** if any descending chain is finite.
