Velbegrundet forhold

I matematik er en velbegrundet relation (også kaldet en Noetherian-relation eller Artinian-relation ) en binær relation, der opfylder en af ​​de to følgende betingelser, svarende til aksiomet af afhængigt valg (en svag version af valgets aksiom ):

En velbegrundet orden (også kaldet en Noetherian orden eller Artinian orden ) er en orden forhold, hvoraf den tilknyttede strenge orden er en velbegrundet relation.

Ethvert velbegrundet forhold er strengt acyklisk , det vil sige dets transitive lukning er en streng ordre. En relation R er velbegrundet, hvis dens transitive lukning er den, eller hvis R er antirefleksiv, og hvis dens transitive refleksive lukning er en velbegrundet rækkefølge.

Eksempler

I den sidste rækkefølge har træet ( ¤ ) ¤ en uendelig træ mindre end sig selv.

Ingen æterisk eller velbegrundet gentagelse

Vi betegner ved R −1 [ x ] sættet med R- fortilfælde af x .

Følgende sætning (i Zermelos sætteori ) tilbyder både en tredje ækvivalent definition af det gode fundament og en generalisering af bevisprincippet ved transfinit induktion (i god orden eller på en ordinal ), som i sig selv udvider aksiomet af Peano n o  5 eller induktionsprincippet (svarende til den sædvanlige rækkefølge på naturlige tal):

Sætning (godt fundament og velbegrundet induktion )  -  En relation R på et sæt E er velbegrundet, hvis og kun hvis det for en del af E er lig med E som helhed, det er nok, at det indeholder hvert element, af hvilket den indeholder alle R- antecedenter.

Formelt: R er velbegrundet, hvis og kun hvis, for en hvilken som helst del P af E ,hvis ∀ x ∈ E ( R -1 [ x ] ⊂ P ⇒ x ∈ P ) derefter P = E . Demonstration

Ved at videregive til det komplementære svarer erklæringens tilstand til implikationen

for en hvilken som helst del X af E , hvis ∀ x ∈ E ( R −1 [ x ] ∩ X = ∅ ⇒ x ∉ X ) så X = ∅

eller igen, i modsat retning  :

for enhver nonempty del X af E , ∃ x ∈ X ( R -1 [ x ] ∩ X = ∅),

som udtrykker såvel som for alle nonempty delmængde X af E , der findes et element x af X uden R -antécédent i X .

Ligeledes generaliserer en anden sætning (i Zermelo-Fraenkels teori om sæt , derfor med udskiftning ) definitionen af definitionen ved induktion af en sekvens og mere generelt af definitionen af ​​en funktion ved transfinit rekursion  :

Sætning (funktion defineret af velbegrundet rekursion )  -  Lad R være en relation, der er funderet på et sæt E og G en funktionel klasse defineret overalt. Derefter findes der en funktion f og kun en (i betydningen: en enkelt funktionsgraf ) af domæne D f = E , således at for alle x ∈ E , f ( x ) = G ( x , f | R - 1 [ x ] ), hvor f | P betegner begrænsning af f til P .

Demonstration

Lad os definere prædikatet rec ( h ) ved: h er en funktion af domæne D h ⊂ E , således at for alle z ∈ D h , R −1 [ z ] ⊂ D h og h ( z ) = G ( z , h | R −1 [ z ] ), derefter predikatet F ( x , y ) ved: ∃ h (rec ( h ) og h ( x ) = y ).

Ved velbegrundet induktion er klassen F funktionel (hvilket allerede ved ekstensionalitet beviser, at den mulige funktion f, der er annonceret i sætningen, er unik), men dens domæne er derfor inkluderet i sæt E (ifølge diagrammet over erstatningsaksiomer ) der findes en funktion f sådan at F ( x , y ) ⇔ f ( x ) = y . Desuden er rek ( f ) opfyldt ved konstruktion .

Endelig er D f = E , igen ved velbegrundet induktion: for alle x ∈ E således, at R −1 [ x ] ⊂ D f , sæt af par h  : = f ∪ {( x , G ( x , f | R −1 [ x ] ))} opfylder rec ( h ) så x ∈ D f .

Disse to sætninger strækker sig til klasser, ligesom deres kolleger i det særlige tilfælde af transfinit gentagelse . Mere præcist: man kan i disse to udsagn erstatte sætene E , R og f med klasser (relationelt for R og funktionelt for f ), forudsat at for ethvert sæt x er klassen R −1 [ x ] en sammen ( i tilfælde af transfinit induktion er det nytteløst at tilføje denne antagelse, fordi ∈ −1 [ x ] = x ).

Rangfunktion

I et sæt E forsynet med et velbegrundet forhold R indrømmer hvert element x en rang ρ ( x ), som er et ordinalt tal . Rangfunktionen er defineret på E ved velbegrundet rekursion af:

ρ ( x ) = ∪ {α + 1 | α ∈ im (ρ | R −1 [ x ] ) } = ∪ {ρ ( y ) + 1 | y R x }

(foreningen af ​​et sæt ordener er en ordinal). Således er rangeringen af x den mindste ordinær strengt større end rækken af ​​fortilfælde af x .

Den længde af relationen R , ofte bemærket | R |, er den mindste ordinal, der indeholder alle ρ ( x ).

Velbegrundet induktion og rekursion ( se ovenfor ) gælder for R , men det er undertiden mere praktisk at anvende dem på tilbagetrækningen ved ρ af den strenge rækkefølge på ordinær | R |, dvs. til forholdet T defineret af: xTy ⇔ ρ ( x ) <ρ ( y ).

Rangfunktionen gør det muligt at organisere E på en indlysende måde i et hierarki, der er meget udbredt i sætteori med medlemsforholdet for R (jf. “  Rang af et sæt  ”).

Algoritmisk brug

Et specielt tilfælde af velbegrundet gentagelse er strukturel gentagelse . Når en algoritme konstruerer en række elementer, samtidig med at det sikres, at et konstrueret element er strengt ringere end dets forgænger, sikrer det også dets afslutning , så snart den strenge orden er velbegrundet.

De strukturer, der anvendes i algoritmer (konstruerede typer), er ofte velbegrundede strenge ordrer. Vi har således en meget generel metode til at bevise afslutningen af ​​et computerprogram .

Noter og referencer

  1. Jean-Pierre Ramis , André Warusfel et al. , All-in-one matematik til licensen: Niveau L1 , Dunod ,2013, 2 nd  ed. ( læs online ) , s.  38.
  2. (in) Kees Doets, fra logik til logisk programmering , MIT Press ,1994( læs online ) , s.  7.
  3. (i) András Hajnal og Peter Hamburger Set Theory , Cambridge University Press ,1999( læs online ) , s.  202 og 280.
  4. (i) Michael Holz, Karsten Steffens og Edmund Weitz Introduktion til kardinal Aritmetik , Birkhauser ,1999( læs online ) , s.  20-23.

Relaterede artikler