Relazione ben fondata
In matematica, una relazione binaria R si dice ben fondata su una classe X se ogni sottoinsieme non vuoto S ⊆ X ha un elemento minimale rispetto a R, cioè un elemento m per cui, per ogni s ∈ S, non valga s R m. In altre parole, una relazione è ben fondata se:
Alcuni autori includono un'ulteriore condizione, vale a dire che R sia simile ad un insieme, cioè che gli elementi minori di un qualunque elemento dato formino a loro volta un insieme.
In modo analogo, assumendo l'assioma della scelta dipendente, una relazione è fondata quando non contiene infinite catene discendenti, il che può essere dimostrato quando non esiste una sequenza infinita x0, x1, x2, ...di elementi di X tale che xn+1 R xn per ogni numero naturale n.[1][2]
Nella teoria degli ordini, un ordine parziale si dice ben fondato se l'ordine parziale in senso stretto corrispondente è una relazione ben fondata. Se l'ordine è un ordine totale, la relazione si dice ben fondata.
Nella teoria degli insiemi, un insieme X è chiamato insieme ben fondato se la relazione di appartenenza all'insieme è ben fondata sulla chiusura transitiva di X. L'assioma di regolarità, che è uno degli assiomi della teoria degli insiemi di Zermelo-Fraenkel, afferma che tutti gli insiemi sono ben fondati.
Una relazione R è inversamente fondata, ascendente o noetheriana su X, se la relazione inversa R−1 è ben fondata su X . In questo caso, si dice anche che R soddisfi la condizione della catena ascendente. Nel contesto dei sistemi di riscrittura, una relazione noetheriana è anche chiamata terminazione.
Induzione e ricorsione
Un motivo importante per cui le relazioni ben fondate sono interessanti è perché su di esse può essere utilizzata una versione dell'induzione transfinita: se (X , R) è una relazione ben fondata, P (x) è una proprietà degli elementi di X , tesi che si dimostra come segue:
P (x) vale per tutti gli elementi x di X, è sufficiente dimostrare che: Se x è un elemento di X e P (y) è vero per ogni y tale che y R x, allora anche P ( x ) deve essere vera.
In simboli, si ha:
L'induzione ben fondata è talvolta chiamata induzione noetheriana da Emmy Noether.[3]
Al pari dell'induzione, anche le relazioni ben fondate supportano la costruzione di oggetti matematici mediante la ricorsione transfinita.
Sia ( X , R ) una relazione insiemistica ben fondata e F una funzione che assegna un oggetto ‘’F=F( x , g )’’ a ciascuna coppia di un elemento x ∈ X e di una funzione g sul segmento iniziale {y : y R x} di X. Allora esiste una funzione unica G tale che per ogni x ∈ X,
Ciò significa che, se si desidera costruire una funzione G su X, è possibile definire G ( x ) utilizzando i valori di G ( y ) per y R x.
A titolo di esempio, si consideri la relazione ben fondata (N , S ), dove N è l'insieme di tutti i numeri naturali e S è il grafico della funzione successore x ↦ x +1. Allora l'induzione su S è la solita induzione matematica, e la ricorsione su S è la ricorsione primitiva. Se consideriamo la relazione d'ordine ( N , <), otteniamo l'induzione completa. L'affermazione che ( N , <) è ben fondata è anche nota come principio del buon ordinamento.
Esistono altri casi speciali interessanti di induzione ben fondata. Quando la relazione ben fondata è il solito ordinamento sulla classe di tutti i numeri ordinali, la tecnica è chiamata induzione transfinita. Quando l'insieme ben fondato è un insieme di strutture di dati definite in modo ricorsivo, la tecnica è chiamata induzione strutturale. Quando la relazione ben fondata è impostata sull'appartenenza alla classe universale, la tecnica è nota come induzione-epsilon.
Esempi
Le relazioni ben fondate che non sono del tutto ordinate includono:
- Gli interi positivi {1, 2, 3, ...}, con l'ordine definito da a < b se e solo se a divide b e a ≠ b;
- L'insieme di tutte le stringhe finite su un alfabeto fisso, con l'ordine definito da s < t se e solo se s è una sottostringa propria di t;
- L'insieme N × N di coppie di numeri naturali, ordinato per (n1, n2) < (m1, m2 se e solo se n1 < m1 and n2 < m2;
- Ogni classe i cui elementi sono insiemi, con la relazione ("è un elemento di"). Questo è l'assioma di regolarità.
- I nodi di qualsiasi grafo aciclico orientato finito, con la relazione R definita tale che a R b se e solo se esiste un arco da a a b.
Esempi di relazioni non ben fondate includono:
- Gli interi negativi {−1, −2, −3, ...}, con il solito ordine, poiché ogni sottoinsieme illimitato non ha alcun elemento minimo.
- L'insieme delle stringhe su un alfabeto finito con più di un elemento, nell'ordine consueto (lessicografico), poiché la sequenza "B" > "AB" > "AAB" > "AAAB" > ... è una catena discendente infinita. Questa relazione non è ben fondata anche se l'intero insieme ha un elemento minimo, ovvero la stringa vuota
- L'insieme dei numeri razionali (o di quelli reali) non negativi nell'ordinamento standard, poiché, ad esempio, il sottoinsieme dei razionali positivi (o reali) manca di un minimo.
Altre proprietà
Se ( X , <) è una relazione ben fondata e x è un elemento di X, allora le catene discendenti che iniziano da x sono tutte finite, ma ciò non significa che le loro lunghezze siano necessariamente limitate. Si consideri il seguente esempio: Sia X l'unione degli interi positivi con un nuovo elemento ω maggiore di qualsiasi intero. Allora X è un insieme ben fondato, ma esistono catene discendenti che iniziano da ω di lunghezza arbitraria grande (finita); la catena ω, n − 1, n − 2, ..., 2, 1 ha lunghezza n per ogni n.
Il lemma di collasso di Mostowski implica che l'appartenenza agli insiemi è un universale tra le relazioni estensionali ben fondate: per ogni relazione ben fondata di tipo insiemistico R su una classe X che è estensionale, esiste una classe C tale che ( X , R ) è isomorfo a (C , ∈).
Riflessività
Una relazione R si dice riflessiva se a R a è vero per ogni a nel dominio della relazione. Ogni relazione riflessiva su un dominio non vuoto ha catene discendenti infinite, perché ogni sequenza costante è una catena discendente. Ad esempio, nei numeri naturali con il loro solito ordine ≤, abbiamo Per evitare queste banali sequenze discendenti, quando si lavora con un ordine parziale ≤, è comune applicare la definizione di relazione ben fondata (forse implicitamente) alla relazione alternativa < definita tale che a < b se e solo se a ≤ b e a ≠ b. Più in generale, quando si lavora con un preordine ≤, è comune utilizzare la relazione < definita tale che a < b se e solo se a ≤ b e b ≰ a. Nel contesto dei numeri naturali, ciò significa che viene utilizzata la relazione <, che è ben fondata, al posto della relazione ≤, che non lo è. In alcuni testi, la definizione di relazione ben fondata viene modificata rispetto alla definizione precedente per includere queste convenzioni.
Note
- ^ Infinite Sequence Property of Strictly Well-Founded Relation, su proofwiki.org.
- ^ R. Fraisse, Theory of Relations, Volume 145 - 1st Edition, 1ª ed., Elsevier, 15 dicembre 2000, p. 46, ISBN 9780444505422.
- ^ Bourbaki, N. (1972) Elements of mathematics. Commutative algebra, Addison-Wesley.
Bibliografia
- Just, Winfried e Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society ISBN 0-8218-0266-6.
- Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", pp. 251–5, Marcel Dekker ISBN 0-8247-7915-0
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)