Rapporto fondato

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.

Esempi

Nell'ultimo ordine, l'albero ( ¤ ) ¤ ha un'infinità di alberi più piccoli di lui.

Ricorrenza noetheriana o fondata

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 . Dimostrazione

Passando 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 .

Dimostrazione

Definiamo 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 ).

Funzione di rango

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  ").

Uso algoritmico

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 .

Note e riferimenti

  1. Jean-Pierre Ramis , André Warusfel et al. , Matematica all-in-one per la licenza: Livello L1 , Dunod ,2013, 2 °  ed. ( leggi in linea ) , p.  38.
  2. (in) Kees Doets, Dalla logica alla programmazione logica , MIT Press ,1994( leggi in linea ) , p.  7.
  3. (a) András Hajnal e Peter Hamburger, Set Theory , Cambridge University Press ,1999( leggi in linea ) , p.  202 e 280.
  4. (a) Michael Holz, Karsten Steffens e Edmund Weitz Introduzione all'aritmetica cardinale , Birkhauser ,1999( leggi in linea ) , p.  20-23.

Articoli Correlati