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.
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 . DemonstrasjonVed å 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 .
DemonstrasjonDefiner 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 ).
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 ”).
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 .