Supporto matematico



Introduzione

In questa pagina intendiamo fornire alcuni strumenti matematici di base utili per la comprensione dei teoremi presenti nel resto del documento.
I quattro capitoli che la compongono trattano rispettivamente le relazioni e le loro proprietà, necessarie alla definizione degli insiemi parzialmente ordinati; le principali strutture algebriche, fino ad arrivare alla definizione di reticolo; ed infine viene presentata una relazione sui matroidi, struttura utile quando si ha a che fare con grafi non planari.

1. Relazioni
1.1 Definizioni
1.2 Rappresentazione delle relazioni
1.3 Operazioni sulle relazioni
1.4 Proprietà delle relazioni
2. Principali strutture algebriche
2.1 Semigruppo
2.2 Monoide
2.3 Gruppo
2.4 Anello
2.5 Campo
2.6 Reticolo
2.7 Algebra di Boole
3. Matroidi
3.1 Matroidi separabili
3.2 Matroide duale
3.3 Ulteriori interpretazioni
4. Reticoli geometrici (e loro relazione con i matroidi)


1. Relazioni

1.1 Definizioni

Dati due insiemi A e B, si dice prodotto cartesiano di A e B, e si indica con A x B, l'insieme di tutte le coppie ordinate (a,b) con aA e bB
A x B = { (a,b) : aA, bB }

Il prodotto cartesiano non è commutativo, tranne nel caso in cui A = B.
|A x B| = |A| x |B|

Una relazione binaria tra l'insieme A e l'insieme B è un sottoinsieme R(A,B) del prodotto cartesiano A x B.

Fissati A e B, si ha:
dom(R) = {aA: (bB) (a,b)R}
= elementi di A che sono in relazione con elementi di B

Se dom(R) = A allora R si dice relazione totale

rango(R) = {bB: (a A) (a,b)R}
= elementi di B che sono in relazione con elementi di A



1.2 Rappresentazione delle relazioni

1) Grafo bipartito
(a,b)R

2) Rappresentazione cartesiana
(a,b)R

3) Grafo orientato
(a,b)R

4) Matrice di adiacenza

È una matrice di ordine |A| x |B| di valori booleani nella quale l'elemento aij vale 1 se i è in relazione con j, 0 altrimenti.



1.3 Operazioni sulle relazioni

Data una relazione R fra A e B si dice relazione trasposta di R la relazione
R t = {(b,a) | (a,b)R}

Date due relazioni R A x B e S B x C, si dice prodotto o composizione di R ed S la relazione
RS = {(a,c) A x C | bB , (a,b)R e (b,c)S}

Si dice relazione identica I su A la relazione
I = {(a,a) | aA}

La relazione I è l'elemento neutro rispetto alla composizione: R = IR = RI

Inoltre si ha: RR t =I


1.4 Proprietà delle relazioni

Sia R una relazione sull'insieme A.

R è riflessiva se a A, (a,a) R

R è simmetrica se (a,b) R (b,a) R

R è antisimmetrica se (a,b)R, (b,a)R a = b

R è transitiva se (a,b)R, (b,c)R (a,c)R

La relazione R si dice di precedenza se gode delle proprietà transitiva e antisimmetrica
La relazione R si dice di equivalenza se gode delle proprietà transitiva, simmetrica e riflessiva
La relazione R si dice di copertura se gode delle proprietà antisimmetrica e antitransitiva
La relazione R si dice di ordine parziale se gode delle proprietà transitiva, antisimmetrica e riflessiva

(se la relazione di ordine parziale vale per ogni coppia di elementi di A allora la relazione si dice di ordine totale)

Un insieme A su cui è definita una relazione d'ordine parziale R si dice insieme parzialmente ordinato (IPO) e lo indichiamo con ( A, R )

Si dice catena (o insieme linearmente ordinato) un insieme parzialmente ordinato tale che ogni coppia di suoi elementi sia confrontabile

Sia (X,) un IPO e sia (a,b) una coppia di elementi di X.
Si dice che un elemento x in X è estremo superiore della coppia (a,b), che indichamo con Sup(a,b), se:

ax e bx.
ac e bc implicano xc , con c elemento in X.

Si dice che un elemento x in X è estremo inferioredella coppia (a,b), che indichiamo con Inf(a,b), se:

xa e xb.
ca e cb implicano cx , con c elemento in X.

Nota:

In generale una coppia (a,b) di elementi di un insieme ordinato (X,) può non ammettere alcun estremo superiore/inferiore in X.
Tuttavia se la coppia (a,b) ammette estremo superiore/inferiore, esso è unico.
Si ha che ab se e solo se Sup(a,b)=b o equivalentemente Inf(a,b)=a.
Due elementi a e b si dicono non confrontabili di X se non si ha né ab e né ba.
Se (X,) è un insieme totalmente ordinato, per ogni coppia (a,b) di elementi di X esistono Sup(a,b) e Inf(a,b), e coincidono con uno degli elementi della coppia.

Sia S un insieme non vuoto costituito da elementi di X, dove (X,) è un insieme ordinato.
Un elemento x in X si dice estremo superiore di S, e si scrive x=Sup(S) ,se:

per ogni elemento s di S si ha sx.
per ogni elemento s di S si ha che sc implica xc, con c elemento in X.

Un elemento x in X si dice estremo inferiore di S, e si scrive x=Inf(S) ,se:

per ogni elemento s di S si ha xs.
per ogni elemento s di S si ha che cs implica cx, con c elemento in X.

Se Sup(S) esiste ed è un elemento di S, si dice che Sup(S) è l'elemento massimo di S.

Se Inf(S) esiste ed è un elemento di S, si dice che Inf(S) è l'elemento minimo di S.

Un insieme ordinato (X,) si dice bene ordinato se ogni sottoinsieme non vuoto di X ammette minimo.
(un insieme ben ordinato è necessariamente totalmente ordinato: infatti ogni coppia (a,b) ammette minimo e quindi ab oppure ba).

2. Principali strutture algebriche

Se X è un insieme e n è un intero positivo , un'applicazione
* : X n X si dice operazione n-aria su X .

Un'operazione n-aria , per un certo n, viene generalmente detta operazione finitaria.

Un insieme finito X e un insieme di operazioni finitarie *1,*2,..su X costituiscono una struttura algebrica, che viene indicata con (X, *1,*2,...).

2.1 Semigruppo

Una struttura algebrica (S,*) costituita da un insieme S e da un'operazione binaria * su S , si dice semigruppo se * è associativa .

2.2 Monoide

Una struttura algebrica (S,*) è un monoide se :

* è associativa.
* ammette unità bilatera u .
(u*a=a*u=a , per ogni elemento a di S)

Se (S,*) è un monoide con unità u , un sottoinsieme H di S si dice sottomonoide se:

u sta in H.
H è chiuso rispetto a *.
(a*b=c ,con c in H ; per ogni elemento a e b di H).

Sia A un sottoinsieme non vuoto di un monoide S.
L'intersezione di tutti i sottomonoidi di S contenenti A si indica con <A>, e prende il nome di sottomonoide generato dal sottoinsieme A.

Nota:

<A> è un sottomonoide.
<A> è il minimo sottomonoide di S contenente A , nel senso che <A> contiene A ed è contenuto in ogni sottomonoide di S che contiene A.
Gli elementi di <A> possono essere espressi in modo esplicito:
r
<A> = { 1s } { ai | r >=1 , ai A }.
i=1

Vale a dire che <A> è costituito dall'unità 1s e dagli elementi di S esprimbili come prodotto di un numero finito di elementi di A.

Se A è costituito da un unico elemento a , il sottomonoide <A> si denota con
<a> = { a n | n>=0 }

e prende il nome di sottomonoide ciclico generato da a.
Se poi <a>=S , si dice che S è un monoide ciclico generato da a.

Sia S un monoide, e sia A un sottoisieme non vuoto di S.
Si dice che A è un insieme di generatori di S se <A>=S o equivalentemente se ogni elemento di S (diverso dall'unità) si può scrivere in almeno un modo come prodotto di elementi di A.

Se ogni elemento di S (diverso dall'unità) si può scrivere in un unico modo come prodotto di elementi di A , si dice che A è un insieme di generatori liberi di S o anche che S è libero su A.

2.3 Gruppo

Una struttura algebrica (G,*) è un gruppo se:

* è associativa.
* ammette unità bilatera u.
ogni elemento di G è invertibile.
(per ogni elemento g in G , esiste un h in G tale che : g*h=h*g=u)

Nota:

Se * è un'operazione commutativa si dice che (G,*) è un gruppo abeliano.
Ci sono due notazioni generalmente usate per i gruppi :
1. La notazione moltiplicativa , dove l'operazione definita in G viene chiamata prodotto e si indica con il simbolo ·
L'unità u si indica con 1G e l'inverso di g si indica con g(esp -1).
2. La notazione additiva (generalmente usata per i gruppi abeliani) , dove l'operazione definita in G viene chiamata somma e si indica con il simbolo +.
L'unità u si indica 0G e l'inverso di g si indica con -g.
Sia (G,·) un gruppo, e H un sottoinsieme di G.
Si dice che H è un sottogruppo di G se:

1G sta in H.
H è chiuso rispetto a ·
ogni elemento di H è invertibile.

Sia A un sottoinsieme non vuoto di un gruppo G.
L'intersezione di tutti i sottogruppi di G che contengono A si indica con <A> e prende il nome di sottogruppo generato dal sottoinsieme A.

Nota:

<A> è un sottogruppo.
<A> è il minimo sottogruppo di G contenente A, nel senso che <A> contiene A ed è contenuto in ogni sottogruppo contenente A.
Gli elementi di <A> possono essere espressi in modo esplicito:
r
<A> = { ai di | r >=1 , ai A , di {+1 , -1 } }.
i=1

Vale a dire che <A> è costituito dagli elementi di G esprimibili come prodotto di un numero finito di elementi di A e di inversi di elementi di A.

Se <A>=G, si dice che A è un insieme di generatori del gruppo G.
(ogni gruppo ammette almeno un insieme di generatori : ad es. A=G).

Se A è costituito da un unico elemento a, il sottogruppo <A> si indica con
<a> = { a n | n Z }
e prende il nome di sottogruppo ciclico generato da a.

Se poi <a>=G, si dice che G è un gruppo ciclico generato da a.

Sia a un elemento di G.
Se <a> è finito di ordine n, si dice che l'elemento a ha periodo n.
Se <a> è infinito, si dice che a ha periodo infinito.
(l'unità è l'unico elemento di G di periodo 1).

2.4 Anello

Una struttura algebrica (A,+,·) costituita da un insieme A e da due operazioni binarie + e · si dice anello se :

(A,+) è un gruppo abeliano.
(A,·) è un monoide.
per ogni a,b,c in A si ha : a·(b+c) = a·b+a·c
(a+b)·c = a·c+b·c
(proprietà distributive)

Nota:

L'unità 0A del gruppo (A,+) si dice zero dell'anello ; l'unità 1A del monoide (A,·) si dice unità dell'anello.
Se il prodotto definito in A è commutativo , si dice che l'anello A è commutativo.
Un elemento a0 di un anello A si dice divisore dello zero se esiste in A un elemento b tale che a·b=0A o b·a=0A.
Un elemento a di un anello A si dice unitario se ammette inverso rispetto al prodotto : se esiste un elemento b in A tale che a·b=b·a=1A.

2.5 Campo

Un anello commutativo (K,+,·) con almeno due elementi si dice campo se ogni elemento di K, diverso da zero, è unitario.

Nota:

In base ad un noto teorema (che afferma che dati un anello (A,+,·) e l'insieme U degli elementi unitari di A, si ha che (U,·) è un gruppo) si ha che posto H = K - { O } , un anello commutativo (K,+,·) è un campo se e solo se (H,·) è un gruppo.

Un sottoinsieme non vuoto H di un campo K si dice sottocampo se è un campo rispetto alle restrizioni ad H delle operazioni di somma e prodotto definite su K.

Un sottogruppo I del gruppo additivo (A,+) si dice ideale dell'anello (A,+,·) se, per ogni elemento i in I e per ogni elemento a in A, si ha a·i I e i·a I.
(si noti che in particolare un ideale è chiuso rispetto al prodotto definito su A).

2.6 Reticolo

DEF.1

Una struttura algebrica (R,,), costituita da un insieme R e da due operazioni binarie e su R si dice reticolo se valgono i seguenti assiomi per ogni a,b,c in R:

  1. a b=b a , a b=b a
    (proprità commutative)

  2. (a b) c=a (b c) , (a b) c=a (b c)
    (proprietà associative)

  3. a (a b)=a , a (a b)=a
    (proprietà di assorbimento)

DEF.2

Un reticolo R è un ipo dotato di unità e di zero, in cui siano definite le operazioni interne :

/ : R*R in R tale che x/y={max z : zx e zy}
// : R*R in R tale che x//y={min z : xz e yz}
(che determinano rispettivamente l'estremo inferiore e superiore della coppia di elementi (x,y) ).

Nota:

Dalla DEF.1 è sempre possibile passare alla DEF.2, nel senso che:

Sia (R,, ) un reticolo.
Si ponga ab se e solo se a b=a. (o equivalentemente: ab se e solo se a b=b).
Allora (R,) è un ipo tale che per ogni a,b in R si ha : Sup(a,b)=a b e Inf(a,b)=a b

Dalla DEF.2 è sempre possibile passare alla DEF.1 nel senso che:

Sia (R,) un ipo tale che per ogni a,b in R esistano Sup(a,b) e Inf(a,b).
Si definiscano su R le operazioni e ponendo: a b=Sup(a,b) e a b=Inf(a,b) , per ogni a,b in R.
Allora (R, , ) è un reticolo. Inoltre la relazione d'ordine associata al reticolo (R, , ) coincide con .

Sia (R, , ) un reticolo.

Un sottoinsieme non vuoto di R si dice sottoreticolo se è chuso rispetto a e
Se esiste l'elemento neutro rispetto all'unione, tale elemento si dice zero del reticolo.
Se esiste l'elemento neutro rispetto all'intersezione, tale elemento si dice unità del reticolo.
Lo zero di un reticolo R, qualora esista, è l'elemento minimo dell'ipo (R,).
L'unità di un reticolo R, qualora esista, è l'elemento massimo dell'ipo (R,).

2.7 Algebra di Boole

Un reticolo R si dice algebra di Boole o reticolo di Boole se:

è dotato di zero e di unità.
è distributivo: per ogni a,b,c in R si ha
a (b c)=(a b) (a c)
a (b c)=(a b) (a c)
ogni elemento a in R ha complemento: esiste un elemento b in R tale che a b=0 e a b=1
(si noti che in un reticolo avente le prime due proprietà, il complemento di un elemento è unico).

Nota:

In un reticolo di Boole R valgono le seguenti proprietà, dette leggi di De Morgan:
_____ _ _ _____ _ _
a b = a b a b = a b per ogni a,b in R.

Sia R un'algebra di Boole.
Un sottoinsieme S di R si dice sottoalgebra di Boole se:

0R sta in S e 1R sta in S.
S è chiuso rispetto alle operazioni di unione, intersezione e complemento.

3. Matroidi

Sia M un insieme di elementi e1,...,en.
Corrispondentemente ad ogni sottoinsieme N di questi elementi sia associata una funzione rango r a valori interi.
Se i seguenti tre postulati sono soddisfatti, il sistema si dice matroide.

  1. r(0) = 0
  2. per ogni sottoinsieme N e ogni elemento e non in N:
    r(N+e) = r(N)+K ; con K = 0,1
  3. per ogni sottoinsieme N ed elementi e1, e2 non in N:
    se r(N+e1) = r(N+e2) = r(N) allora r(N+e1+e2) = r(N)

Nota:

Ogni sottoinsieme di un matroide è un matroide.
Se M è un matroide, valgono le seguenti definizioni:

(N) = numero di elementi di N.
n(N) = (N) - r(N) = nullità di N.
N è indipendente se n(N) = 0, cioè se ha rango massimo.

Si può dare una definizione alternativa di matroide.

Sia M un insieme di elementi ed N un qualsiasi suo sottoinsieme dipendente o indipendente.
Se M soddisfa i due seguenti postulati allora è un matroide.

  1. Ogni sottoinsieme di un insieme indipendente è indipendente.
  2. Se N = e1+...+ep e H = f1+...+fp+1 sono indipendenti, allora per qualche i tale che fi non è in N si ha che N + fi è indipendente.

Dim.

Sia N un sottoinsieme di M e r(N) il numero di elementi del più grande sottoinsieme indipendente di N.
Allora si ha:

  1. r(0) = numero di elementi del più grande sottoinsieme indipendente di 0
    = numero di elementi di 0 = 0.

  2. Sia e un elemento di M non in N.
    r(N+e) = numero di elementi del più grande sottoinsieme indipendente di N+e
    = r(N)+K , con K=0,1 a seconda che e sia dipendente o meno in N.

  3. Sia r(N+e1) = r(N+e2) = r(N) = r, con e1,e2 elementi in M e non in N.
    Allora r(N+e1+e2) = r oppure r(N+e1+e2) = r+1.
    Nel secondo caso, esiste un insieme indipendente H = f1+...+fr+1 in N+e1+e2.
    Sia K = g1+...+gr un insieme indipendente in N.
    Per la proprietà 2), esiste un i tale che K+fi è un insieme indipendente di r+1 elementi.
    Ma K+fi sta in N+e1 o in N+e2, e quindi r(N+e1) o r(N+e2)>= r+1 , contraddizione. Quindi r(N+e1+e2)=r, come richiesto.
Alcune definizioni:

Elenchiamo alcune proprietà e teoremi di base sui matroidi:

3.1 Matroidi separabili

Se è possibile suddividere gli elementi di un matroide M in due gruppi, M1 ed M2, ognuno contenente almeno un elemento, in maniera tale che r(M) = r(M1)+r(M2) (e quindi n(M) = n(M1)+n(M2), non avendo M1 ed M2 elementi in comune), diciamo che M è separabile.

Ogni singolo elemento in cui abbiamo suddiviso M è un matroide non separabile.

Ogni massima parte non separabile di M si dice componentedi M.

Alcuni teoremi:

3.2 Matroide duale

Supponiamo esista una corrispondenza 1-1 fra gli elementi dei matroidi M ed M', in modo tale che se N è un sottomatroide di M ed N' è la componente del corrispondente matroide di M' allora r(N') = r(M')-n(N). In questo caso diciamo che M' è il duale di M.

Alcune proprietà:

3.3 Ulteriori interpretazioni

Un'ulteriore interpretazione possibile per i matroide è quella matriciale:

Sia M una matrice, con colonne C1,...,C1 e sia N un sottoinsieme di tali colonne, con rango r(N).
Se consideriamo come rango di M il numero di colonne linearmente indipendenti in M, M è un matroide.

Dim.

  1. r(0) = 0.
  2. Sia Ci una generica colonna di M non in N.
    r(N+Ci) = r(N)+k , con k=0,1.
  3. Supponiamo r(N+C1) = r(N+C2) = r(N);
    allora C1 e C2 possono essere espressi come combinazione lineare delle altre colonne di N, e quindi r(N+C1+C2) = r(N).

In questo caso una base in M diventa il minimo sottoisieme di colonne tramite le quali tutte le altre colonne di M possono essere espresse.

M può essere interpretato geometricamente in due modi diversi:

  1. Sia Em lo spazio euclideo ad m dimensioni.
    Corrispondentemente ad ogni colonna Ci di M c'è un punto Xi in Em a coordinate a1i,...,ami (elementi della colonna i-esima di M).
    Il sottoinsieme Ci1,...,Cip di M è linearmente indipendente se e solo se i punti 0 = (0,...,0), Xi1,...,Xip sono linearmente indipendenti in Em; vale a dire se e solo se questi p+1 punti determinano un iperpiano in Em di dimensione p.

    Una base in M corrisponde al minimo insieme di punti Xi1,...,Xip in Em tali che ogni Xj di M sta nell'iperpiano determinato da 0,Xi1,..., Xip.
    Allora p è il rango di M.

  2. Sia En lo spazio euclideo ad n dimensioni.
    Siano R1,...,Rm le righe di M.
    Se Y1,...,Ym sono i corrispondenti punti di En, cioè Yi = (ai1,...,ain), allora i punti 0,Y1,...,Ym determinano l'iperpiano H = H(M), che chiamiamo l'iperpiano associato ad M.
    La dimensione d(H) di H è r(H).
    Sia N = Ci1+...+Cip un sottoinsieme di M, e sia E' il sottospazio p-dimensionale di En contenente gli assi xi1,..., xip.
    La j-esima riga di N corrisponde al punto Yj' in E' di coordinate (aji1,...,ajip); questa è la proiezione di Yj in E'.
    Se H' è l'iperpiano in E' determinato dai punti 0,Y1', ...,Ym', allora H' è la proiezione di H in E' e d(H') = r(N).

    N è indipendente se e solo se d(H') = p, ed è una base se e solo se d(H') = d(H) = p.

Nota:

4. Reticoli geometrici (e loro relazione con i matroidi)

Una geometria combinatoria è una struttura definita su un insieme finito S di punti o atomi.

Consideriamo una famiglia H di sottoinsiemi di S.
Ogni sottoinsieme è detto flat (insieme chiuso) o oggetto della geometria. (ad es. un punto è un flat di rango 1, una linea è un flat di rango 2,...)

Una geometria deve verificare le tre seguenti proposizioni:

  1. S appartiene ad H ed H è chiusa rispetto all'intersezione di flat.
  2. Sia H' la sottofamiglia di H contenente i chiusi che coprono un dato flat F, allora tutti gli elementi che ricavo da F'-F (dove F è contenuto in S e F' appartiene ad H') sono blocchi di una partizione di S-F.
  3. 0 sta in H e (x) sta in H, per ogni x in S.
Una linea è un oggetto che copre un atomo.
Un piano è un oggetto che copre una linea.
Un iperpiano (o coatomo o copunto) è un oggetto coperto da S.
Una colinea è un oggetto coperto da un coatomo.

Fissato F, l'insieme S-F è partizionato nei blocchi F'-F, per ogni F' che copre F.
Se si ordinano per inclusione i flat di H si ottiene un reticolo geometrico.
(cioè un reticolo L è geometrico se gli elementi che coprono x, elemento di L, partiziona l'insieme A - A(X), dove A è l'insieme degli atomi di L e A(x) è l'insieme degli atomi che precedono x).

Una famiglia che soddisfa le proposizioni 1 e 2 e che contiene il vuoto è detta pre-geometria o matroide.

Come passare da un reticolo geometrico alla geometria corrispondente:

Come passare da un reticolo geometrico al grafo corrispondente:


Torna all'indice