Algebra di incidenza

In matematica, e più specificamente in teoria degli ordini, per algebra di incidenza si intende un'algebra associativa definita opportunamente per un qualsiasi insieme parzialmente ordinato localmente finito e un qualsiasi anello commutativo (dotato di unità).

Definizione

Denotiamo con $\mathbf {R} =\langle R,+,\cdot ,0,1\rangle$ un anello commutativo; i suoi elementi qui verranno detti scalari.

Un poset $\mathbf {P} =\langle P,\leq \rangle$ si dice localmente finito se ciascuno dei suoi intervalli

[a, b] = {x : a ≤ x ≤ b}

ha cardinalità finita.

L'algebra di incidenza di P ed R ha come sostegno l'insieme delle funzioni f che associano ad ogni intervallo non vuoto [a, b] di P uno scalare f(a, b); denoteremo questo insieme con F. Su questo insieme definiamo la somma e la moltiplicazione per uno scalare componente per componente. Munita di tali operazioni F costituisce un modulo. Per avere un'algebra occorre definire una "moltiplicazione" tra due elementi f e g di F; per questa operazione binaria si assume una convoluzione definendo

$(f*g)(a,b)=\sum _{a\leq x\leq b}f(a,x)g(x,b).$

Va osservato che il carattere localmente finito di P rende sempre possibile effettuare la precedente somma. Un'algebra di incidenza risulta finito-dimensionale se e solo se P è un insieme finito.

Concetti collegati

Un'algebra di incidenza è analoga a un'algebra di gruppo; in effetti sia l'algebra di gruppo che l'algebra di incidenza sono casi particolari di un'algebra categorica, definita analogamente; essendo gruppi e poset tipi particolari di categorie.

Elementi speciali

L'elemento identità moltiplicativa dell'algebra di incidenza è la funzione delta, definita da

$\delta (a,b)=\left\{{\begin{matrix}\,1,&{\mbox{se }}a=b\\\,0,&{\mbox{se }}a\neq b\end{matrix}}\right.$

La funzione zeta di un'algebra di incidenza è la funzione costante ζ(a, b) = 1 per ogni intervallo [a, b]. La moltiplicazione per ζ è analoga all'integrazione.

Si può mostrare che ζ è invertibile nell'algebra di incidenza (rispetto alla convoluzione definita sopra). Generalmente un membro h dell'algebra di incidenza è invertibile se e solo se h(x, x) è invertibile per ogni x. L'inverso moltiplicativo della funzione zeta è la funzione di Möbius μ(a, b); ogni valore di μ(a, b) è un multiplo intero di 1 nell'anello base.

La funzione di Möbius può essere anche definita direttamente, dalla seguente relazione:

$\mu (x,y)=\left\{{\begin{array}{cc}1,&{\textrm {se}}\quad x=y\\-\sum _{x\leq z<y}\mu (x,z),&{\textrm {se}}\quad x<y\\0,&{\textrm {altrimenti}}\end{array}}\right.$

Moltiplicare per μ è analogo alla differenziazione ed è chiamata inversione di Möbius.

Esempi

• Interi positivi ordinati dalla divisibilità

La funzione di Möbius è μ(a, b) = μ(b/a), dove la seconda "μ" è la classica funzione di Möbius introdotta in teoria dei numeri nel XIX secolo.

• Sottoinsiemi finiti di un insieme E, ordinati dall'inclusione

La funzione di Möbius è

$\mu (S,T)=(-1)^{\left|T\setminus S\right|}$

quando S e T sono sottoinsiemi finiti di E con S ⊆ T, e l'inversione di Möbius è chiamata principio di inclusione-esclusione.

Geometricamente questo è un ipercubo: $2^{E}=\{0,1\}^{E}.$

• Numeri naturali con l'ordine consueto

La funzione di Möbius è

$\mu (x,y)=\left\{{\begin{matrix}1&{\mbox{se }}y-x=0,\\-1&{\mbox{se }}y-x=1,\\0&{\mbox{se }}y-x>1.\end{matrix}}\right.$

e l'inversione di Möbius è chiamata operatore differenza (inversa). Geometricamente questo corrisponde alla retta numerica discreta.

La convoluzione di successioni corrisponde alla moltiplicazione di serie formali di potenze.

La funzione di Möbius corrisponde alla sequenza (1, −1, 0, 0, 0, ... ) di coefficienti della serie formale di potenze 1 − z, e la funzione zeta in questo caso corrisponde alla sequenza di coefficienti (1, 1, 1, 1, ... ) della serie formale di potenze $(1-z)^{-1}=1+z+z^{2}+z^{3}+\cdots$, che è l'inverso. La funzione delta in questa algebra di incidenza corrisponde alla serie formale di potenze 1.

• Partizioni di un insieme

Si può ordinare (parzialmente) l'insieme di tutte le partizioni di un insieme finito ponendo σ ≤ τ se σ è una partizione più fine di τ. La funzione di Möbius è

$\mu (\sigma ,\tau )=(-1)^{n-r}(2!)^{r_{3}}(3!)^{r_{4}}\cdots ((n-1)!)^{r_{n}}$

dove n è il numero di blocchi nella partizione più fine σ, r è il numero di blocchi nella partizione meno fine τ, e r_i è il numero di blocchi di τ che contengono esattamente i blocchi di σ.

Caratteristica di Eulero

Un poset si dice limitato se e solo se possiede un elemento minimo ed un elemento massimo; qui li denotiamo con 0 ed 1 rispettivamente, in modo da non confonderli con gli elementi 0 e 1 dell'anello degli scalari. La caratteristica di Eulero di un poset finito e limitato è μ(0,1); questo scalare è sempre un intero. Questa nozione generalizza quella di caratteristica di Eulero classica.

Algebre di incidenza ridotte

Ogni membro di un'algebra di incidenza che assegna lo stesso valore a due intervalli che siano isomorfi tra di loro è un membro dell'algebra di incidenza ridotta. Essa è una sottoalgebra dell'algebra di incidenza che chiaramente contiene l'identità dell'algebra e la funzione zeta.

Ogni elemento dell'algebra ridotta che sia invertibile nell'algebra originale ha il suo inverso nell'algebra ridotta. Conseguentemente, la funzione di Möbius è sempre un elemento dell'algebra ridotta. Le algebre ridotte aiutano la comprensione della teoria delle funzioni generatrici, come si allude nell'esempio precedente sui numeri naturali.

Letteratura

• Gian-Carlo Rota, On the Foundations of Combinatorial Theory I: Theory of Möbius Functions, in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 2, pp. 340–368.