Definizione

$R \subseteq S \times S$ è d’ordine se è:

• Riflessiva: $\forall x \in S, xRx$
• Antisimmetrica: $\forall x, y \in S, xRy,yRx \Rightarrow x = y$
• Transitiva: $\forall x,y,z \in S, xRy,yRz \Rightarrow xRz$

Ordine stretto, insieme ordinato, ordine totale, omomorfismo d’ordine

Se invece è Antisimmetrica e Transitiva ma non Riflessiva, è di ordine stretto

Un insieme ordinato è una coppia $(S, \le)$ con $\le$ relazione d’ordine binaria su $S$

Siano $(S, \le)$, $(T, \preceq)$ due insiemi ordinati, $f: S \rightarrow T$ è omomorfismo d’ordine se $\forall x,y \in S, x \le y \Rightarrow f(x) \preceq f(y)$

Se $\le$ è totale, cioè $\forall x,y \in S$ si ha $x \le y$ oppure $y \le x$ allora $S$ si dirà totalmente ordinato o catena

Minimo, massimo

Un minimo per $(S, \le)$ è un elemento $a \in S$ tale che $a \le x, \forall x \in S$

Un massimo per $(S, \le )$ è un elemento $a \in S$ tale che $x \le a, \forall x \in S$

Lemma: massimo e minimo, se esistono, sono unici

Minimale, massimale

Un elemento $c \in S$ è detto minimale se $\nexists a \in S: a \le c$

Un elemento $c \in S$ è detto massimale se $\nexists a \in S : c \le a$