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.

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.Bourbaki, N. (1972) Elements of mathematics. Commutative algebra, Addison-Wesley.

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

Bibliografia Just, Winfried e Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society . Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", pp. 251–5, Marcel Dekker

Collegamenti esterni

Categoria:Analisi matematica Categoria:Logica proposizionale Categoria:Logica matematica Categoria:Logica classica