Insieme parzialmente ordinato
Un insieme in cui è definito un ordine parziale è detto insieme parzialmente ordinato (A,≤).
Cos'è un ordine parziale?
Dato un insieme A, un ordine parziale è una relazione
$$ ≤:AxA \rightarrow \{ vero, falso \}. $$
tale che dati due elementi dell'insieme (x,y) di A è possibile affermare se la relazione ≤ è vera oppure è falsa.
Un esempio pratico
Ho un insieme finito A composto da 7 elementi
$$ A = \{ a, b, c, d, e, f \} $$
Definisco una relazione ≤ tra le coppie AxA degli elementi dell'insieme.
$$ ≤ \{ (a,c,) , (a,e) , (b,d) , (b,f) , (c,g) , (d,g) , (e,g) , (f,g) \} $$
L'insieme (A,≤) è un insieme parzialmente ordinato.
Nota. Non sono le relazioni tra tutti gli elementi dell'insieme ma soltanto tra alcuni. Ad esempio, non ci sono relazioni (a,b) , (a,d) , ecc.
Posso rappresentare graficamente le relazioni dell'insieme parzialmente ordinato (A,≤) in questo modo.
Ogni relazione è rappresentata da un arco che congiunge gli elementi.
Gli estremi inferiori e superiori
Dato un insieme parzialmente ordinato (A,≤) e un sottoinsieme B di A
- il sottoinsieme B ha un estremo inferiore inf(B) se esiste un elemento k ∈ A che è il massimo dei minoranti dell'insieme B.
- il sottoinsieme B ha un estremo superiore sup(B) se esiste un elemento k ∈ A che è il minimo dei maggioranti dell'insieme B.
Esempio
Il sottoinsieme B ha sia un estremo inferiore (3) che un estremo superiore (4).
Nota. Non è detto che il sottoinsieme abbia un estremo inferiore o superiore. Tuttavia, se esistono sono unici.
I minoranti e i maggioranti
Dato un insieme parzialmente ordinato (A,≤) e un sottoinsieme B di A
- un elemento k ∈ A è detto minorante del sottoinsieme B se è minore o uguale a ogni elemento del sottoinsieme B.
Esempio. Dato l'insieme A = {1, 2, 3, 4, 5, 6} e il sottoinsieme B = { 3, 4 }. I minoranti di B sono { 1, 2, 3 }
- un elemento k ∈ A è detto maggiorante del sottoinsieme B se è maggiore o uguale a ogni elemento del sottoinsieme B.
Esempio. Dato l'insieme A = {1, 2, 3, 4, 5, 6} e il sottoinsieme B = { 3, 4 }. I maggioranti di B sono { 4, 5, 6 }
I massimali e i minimali
Dato un insieme parzialmente ordinato (A,≤)
- un elemento k ∈ A è detto minimale di A se non c'è un altro elemento di A che lo precede.
Esempio. Dato l'insieme A = {1, 2, 3, 4, 5, 6} il minimale di A è 1.
- un elemento k ∈ A è detto massimale di A se non precede un altro elemento di A.
Esempio. Dato l'insieme A = {1, 2, 3, 4, 5, 6} il massimale di A è 6.
Un insieme parzialmente ordinato potrebbe anche avere più massimali o più minimali.
Esempio
In questo esempio ci sono tre massimali e un minimale.
Le relazioni dell'insieme parzialmente ordinato sono le seguenti
$$ ≤ \{ (1,2,) , (1,3), (2,4) , (2,6) , (3,6) , (3,9) \} $$
Posso affermare che
- 4,6,9 non precedono un altro elemento di A. Quindi sono massimali.
- 1 non è preceduto da altri elementi di A. Quindi è minimale.
Nota. Gli insiemi parzialmente ordinati composti da infiniti elementi non è detto che abbiano degli elementi massimali e minimali. Gli insiemi parzialmente ordinati finiti, invece, hanno sempre almeno un elemento massimale e un elemento minimale.
Il massimo e minimo
Dato un insieme parzialmente ordinato (A,≤)
- un elemento k ∈ A è detto minimo di A se è minore o uguale a tutti gli elementi dell'insieme A.
- un elemento k ∈ A è detto massimo di A se è maggiore o uguale a tutti gli elementi dell'insieme A.
Non è detto che gli insiemi parzialmente ordinati abbiano un minimo o un massimo.
Esempio
In questo esempio c'è un minimo (1) ma non un massimo.
Le relazioni dell'insieme parzialmente ordinato sono le seguenti
$$ ≤ \{ (1,2,) , (1,3) , (2,4) , (2,6) , (3,6) , (3,9) \} $$
Posso affermare che 1 è il minimo perché per ogni elemento k di A vale 1≤k.
$$ 1 \le 2 \\ 1 \le 3 \\ 1 \le 4 \\ 1 \le 6 \\ 1 \le 9 $$
Viceversa non posso affermare che 9 sia il massimo perché mancano le relazioni tra le coppie (2,9), (4,9), (6,9).
$$ 1 \le 9 \\ 3 \le 9 \\ 2 \: ? \: 9 \\ 4 \: ? \: 9 \\ 6 \: ? \: 9 $$
Lo stesso discorso vale per gli altri massimali 4 e 6.
Non posso affermare che 4 sia il massimo perché mancano le relazioni tra le coppie (4,9), (4,6), (4,3).
$$ 1 \le 4 \\ 2 \le 4 \\ 4 \: ? \: 3 \\ 4 \: ? \: 6 \\ 4 \: ? \: 9 $$
Non posso affermare che 6 sia il massimo perché mancano le relazioni tra le coppie (6,4), (6,9).
$$ 1 \le 6 \\ 2 \le 6 \\ 3 \le 6 \\ 4 \: ? \: 6 \\ 9 \: ? \: 6 $$
E così via.
