Velbegrunnet forhold

I matematikk er et velbegrunnet forhold (også kalt et noeterisk forhold eller artinsk forhold ) et binært forhold som tilfredsstiller en av de to følgende betingelser, tilsvarende i henhold til aksiomet avhengig valg (en svak versjon av valgaksjonen )

En velbegrunnet orden (også kalt en Noetherian orden eller Artinian orden ) er en orden forhold der den tilhørende strenge orden er en velbegrunnet forhold.

Ethvert velbegrunnet forhold er strengt acyklisk , det vil si at dets transitive lukking er en streng ordre. En relasjon R er velbegrunnet hvis dens transitive lukking er den, eller hvis R er antirefleksiv, og hvis dens transitive refleksive lukking er en velbegrunnet orden.

Eksempler

I den siste rekkefølgen har treet ( ¤ ) ¤ en uendelig mengde trær mindre enn seg selv.

Noetherian eller velbegrunnet gjentakelse

Vi vil betegne R- forekomster av x ved R −1 [ x ] .

Følgende teorem (i Zermelo settteori ) tilbyr både en tredje ekvivalent definisjon av det gode fundamentet og en generalisering av bevisprinsippet ved transfinitt induksjon (i god orden eller på en ordinal ), som i seg selv utvider aksiomet til Peano n o  5 eller induksjonsprinsippet (tilsvarer vanlig rekkefølge på naturlige tall):

Teorem (godt grunnlag og velbegrunnet induksjon )  -  En relasjon R på et sett E er velbegrunnet hvis og bare hvis det for en del av E er lik E som helhet, det er tilstrekkelig at det inneholder hvert element det inneholder alle R- antecedents.

Formelt: R er velbegrunnet hvis og bare hvis, for noen del P av E ,hvis ∀ x ∈ E ( R -1 [ x ] ⊂ P ⇒ x ∈ P ) deretter P = E . Demonstrasjon

Ved å gå til det komplementære tilsvarer uttalelsen tilstanden til implikasjonen

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

eller igjen, i motsatt retning  :

for en hvilken som helst ikke-delaktig del X av E , ∃ x ∈ X ( R −1 [ x ] ∩ X = ∅),

som uttrykker vel som for alle ikke-tom delmengde X fra E , eksisterer det et element X fra X med ingen R -antécédent i X .

På samme måte generaliserer en andre setning (i Zermelo-Fraenkels teori om sett , derfor med erstatning ) prinsippet om definisjon ved induksjon av en sekvens og mer generelt, av definisjon av en funksjon ved transfinitt rekursjon  :

Teorem (funksjon definert av velbegrunnet rekursjon )  -  La R være et forhold godt fundert på et sett E og G en funksjonell klasse definert overalt. Deretter eksisterer en funksjon f og bare en (i betydningen: en enkelt funksjonsgraf ), av domenet D f = E , slik at for alle x ∈ E , f ( x ) = G ( x , f | R - 1 [ x ] ), hvor f | P betegner en begrensning av f til P .

Demonstrasjon

Definer predikatet rec ( h ) ved: h er en funksjon av domenet D h ⊂ E , slik at for alle z ∈ D h , R −1 [ z ] ⊂ D h og h ( z ) = G ( z , h | R −1 [ z ] ), deretter predikatet F ( x , y ) av: ∃ h (rec ( h ) og h ( x ) = y ).

Ved velbegrunnet induksjon er klassen F funksjonell (som allerede ved utvidelse beviser at den mulige funksjonen f kunngjort i teoremet er unik), men dens domene er derfor inkludert i settet E (i henhold til diagrammet over erstatningsaksiomer ) det eksisterer en funksjon f slik at F ( x , y ) ⇔ f ( x ) = y . Videre er rek ( f ) tilfredsstilt ved konstruksjon .

Til slutt, D f = E , igjen ved velbegrunnet induksjon: for alle x ∈ E slik at R −1 [ x ] ⊂ D f , settet med par h  : = f ∪ {( x , G ( x , f | R −1 [ x ] ))} tilfredsstiller rec ( h ) så x ∈ D f .

Disse to setningene strekker seg til klasser, som deres kolleger i det spesielle tilfellet av transfinite gjentakelse . Mer presist: man kan i disse to setningene erstatte settene E , R og f med klasser (relasjonelt for R og funksjonelt for f ), forutsatt at for ethvert sett x er klassen R −1 [ x ] en sammen ( når det gjelder transfinitt induksjon, er det ubrukelig å legge til denne antagelsen fordi ∈ −1 [ x ] = x ).

Rangeringsfunksjon

I et sett E utstyrt med et velbegrunnet forhold R , innrømmer hvert element x en rang ρ ( x ), som er et ordentall . Rangfunksjonen er definert på E ved velbegrunnet rekursjon av:

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

(foreningen av et sett med ordener er en ordinær). Dermed er rangeringen av x den minste ordinæren strengt større enn rekkene til forgjengerne til x .

Den lengden av forholdet R , ofte bemerket | R |, er den minste ordinæren som inneholder alle ρ ( x ).

Velbegrunnet induksjon og rekursjon ( se ovenfor ) gjelder R , men det er noen ganger mer praktisk å bruke dem på tilbaketrekningen med ρ av den strenge ordren på ordinæren | R |, dvs. til forholdet T definert av: xTy ⇔ ρ ( x ) <ρ ( y ).

Rangeringsfunksjonen gjør det mulig å organisere E på en åpenbar måte i et hierarki, mye brukt i mengdeori med medlemsforholdet for R (jf. “  Sett av rang  ”).

Algoritmisk bruk

Et spesielt tilfelle av velbegrunnet gjentakelse er strukturell gjentakelse . En algoritme , når den konstruerer en rekke elementer mens den sørger for at et konstruert element er strengt dårligere enn forgjengeren, sørger også for at det avsluttes , så snart den strenge ordren er velbegrunnet.

Strukturene som brukes i algoritmiske (konstruerte typer) er ofte velbegrunnede strenge ordrer, vi har altså en veldig generell metode for å bevise avslutningen av et dataprogram .

Merknader og referanser

  1. Jean-Pierre Ramis , André Warusfel et al. , Alt-i-ett-matematikk for lisensen: Nivå L1 , Dunod ,2013, 2 nd  ed. ( les online ) , s.  38.
  2. (in) Kees Doets, fra logikk til logisk programmering , MIT Press ,1994( les online ) , s.  7.
  3. (i) András Hajnal og Peter Hamburger, Set Theory , Cambridge University Press ,1999( les online ) , s.  202 og 280.
  4. (i) Michael Holz, Karsten Steffens og Edmund Weitz Introduksjon til kardinalaritmetikk , Birkhauser ,1999( les online ) , s.  20-23.

Relaterte artikler