In matematica , una relazione ben fondata (chiamata anche relazione noetheriana o relazione artiniana ) è una relazione binaria che soddisfa una delle due condizioni seguenti, equivalente secondo l' assioma della scelta dipendente (una versione debole dell'assioma della scelta ):
Un ordine ben fondato (chiamato anche ordine noetheriano o ordine artiniano ) è una relazione d'ordine di cui l' ordine stretto associato è una relazione ben fondata.
Ogni relazione ben fondata è strettamente aciclica , cioè la sua chiusura transitiva è un ordine rigoroso. Una relazione R è ben fondata se è la sua chiusura transitiva , o se R è antiriflesso e se la sua chiusura riflessiva transitiva è un ordine ben fondato.
Indichiamo con R −1 [ x ] l'insieme degli R -antecedenti di x .
Il seguente teorema (nella teoria degli insiemi di Zermelo ) offre sia una terza definizione equivalente del buon fondamento sia una generalizzazione del principio di dimostrazione per induzione transfinita (su un buon ordine o su un ordinale ), che a sua volta estende l' assioma di Peano n ° 5 o il principio di induzione (corrispondente al solito ordine sui numeri naturali):
Teorema (buon fondamento e induzione ben fondata) - Una relazione R su un insieme E è ben fondata se e solo se, affinché una parte di E sia uguale a E nel suo insieme, è sufficiente che contenga ogni elemento di cui contiene tutti gli antecedenti R.
Formalmente: R è fondato se e solo se, per qualsiasi parte P di E ,se ∀ x ∈ E ( R -1 [ x ] ⊂ P ⇒ x ∈ P ) allora P = E . DimostrazionePassando al complementare , la condizione dell'enunciato equivale all'implicazione
per qualsiasi parte X di E , se ∀ x ∈ E ( R −1 [ x ] ∩ X = ∅ ⇒ x ∉ X ) allora X = ∅o ancora, al contrario :
per ogni parte non vuota X di E , ∃ x ∈ X ( R −1 [ x ] ∩ X = ∅),che esprime pure per tutti non vuota sottoinsieme X di E , esiste un elemento x di X senza R -antécédent in X .
Analogamente, un secondo teorema (in teoria degli insiemi di Zermelo-Fraenkel , quindi con sostituzione ) generalizza il principio di definizione per induzione di una sequenza e più in generale, di definizione di una funzione transfinite ricorsione :
Teorema (funzione definita da ricorsione ben fondata) - Sia R una relazione fondata su un insieme E e G una classe funzionale definita ovunque. Allora, esiste una funzione f ed una sola (nel senso: un unico grafo di funzione ), di dominio D f = E , tale che per ogni x ∈ E , f ( x ) = G ( x , f | R - 1 [ x ] ), dove f | P denota la restrizione di f per P .
DimostrazioneDefiniamo il predicato rec ( h ) da: h è una funzione di dominio D h ⊂ E , tale che per ogni z ∈ D h , R -1 [ z ] ⊂ D h ed h ( z ) = G ( z , h | R −1 [ z ] ), quindi il predicato F ( x , y ) di: ∃ h (rec ( h ) e h ( x ) = y ).
Per induzione ben fondata, la classe F è funzionale (che già dimostra, per estensionalità , che la possibile funzione f annunciata nel teorema è unica), ma il suo dominio è quindi compreso nell'insieme E (secondo il diagramma degli assiomi di sostituzione ) esiste una funzione f tale che F ( x , y ) ⇔ f ( x ) = y . Inoltre, per costruzione, il punto rec ( f ) è soddisfatto.
Infine, D f = E , sempre per induzione ben fondata: per ogni x ∈ E tale che R −1 [ x ] ⊂ D f , l'insieme delle coppie h : = f ∪ {( x , G ( x , f | R −1 [ x ] ))} soddisfa rec ( h ) quindi x ∈ D f .
Questi due teoremi si estendono alle classi, come le loro controparti nel caso particolare della ricorrenza transfinita . Più precisamente: si possono sostituire, in queste due affermazioni, gli insiemi E , R ed f con classi (relazionali per R e funzionali per f ), a condizione che per ogni insieme x , la classe R −1 [ x ] sia un insieme ( nel caso dell'induzione transfinita, è inutile aggiungere questa assunzione perché ∈ −1 [ x ] = x ).
In un insieme E dotato di una relazione ben fondata R , ogni elemento x ammette un rango ρ ( x ), che è un numero ordinale . La funzione di rango è definita su E da ricorsione ben fondata da:
ρ ( x ) = ∪ {α + 1 | α ∈ im (ρ | R −1 [ x ] ) } = ∪ {ρ ( y ) + 1 | y R x }(l'unione di un insieme di ordinali è un ordinale). Pertanto, il rango di x è il più piccolo ordinale strettamente maggiore dei ranghi degli antecedenti di x .
La lunghezza della relazione R , spesso annotata | R |, è il più piccolo ordinale contenente tutto ρ ( x ).
L'induzione e la ricorsione ben fondate ( vedi sopra ) si applicano a R , ma a volte è più conveniente applicarle al pullback di ρ dell'ordine rigoroso sull'ordinale | R |, cioè alla relazione T definita da: xTy ⇔ ρ ( x ) <ρ ( y ).
La funzione rango consente di organizzare E in modo ovvio in una gerarchia, ampiamente utilizzata nella teoria degli insiemi con la relazione di appartenenza per R (cfr. " Rango di un insieme ").
Un caso speciale di ricorrenza fondata è la ricorrenza strutturale . Un algoritmo , quando costruisce una serie di elementi assicurando che un elemento costruito sia strettamente inferiore al suo predecessore, ne assicura anche la terminazione , non appena l'ordine rigoroso è ben fondato.
Le strutture utilizzate negli algoritmi (tipi costruiti) sono spesso ordini rigorosi ben fondati, quindi abbiamo un metodo molto generale per provare la conclusione di un programma per computer .