Dobrze ugruntowana relacja - Well-founded relation

W matematyce , A binarny stosunek R jest zwany wellfounded (lub wellfounded ) na klasy X , jeśli każdy niepusty podzbiór S ⊆ X ma minimalny elementu w odniesieniu do R , to znaczy w elemencie m niezwiązanego przez SRM (na przykład " a nie jest mniejszy, niż m ") dla każdego s ∈ s . Innymi słowy, relacja jest dobrze uzasadniona, jeśli

${\ Displaystyle (\ forall S \ subseteq X) \; [S \ neq \ emptyset \ implikuje (\ istnieje m \ in S) (\ forall s \ in S) \ lnot (sRm)].}$

Niektórzy autorzy zawierają dodatkowy warunek, że R jest podobny do zbioru , tj. Że elementy mniejsze niż jakikolwiek dany element tworzą zbiór.

Równoważnie, zakładając aksjomat wyboru zależnego , relacja jest dobrze ugruntowana, jeśli nie zawiera policzalnych nieskończonych zstępujących łańcuchów : to znaczy nie ma nieskończonego ciągu x ₀ , x ₁ , x ₂ , ... elementów X takich, że x _{n +1} R x _n dla każdej liczby naturalnej n .

W teorii zlecenia , o częściowy porządek nazywany jest uzasadnione, jeżeli odpowiada ścisły porządek jest dobrze założona relacja. Jeśli zamówienie jest porządkiem całkowitym, nazywa się je porządkiem dobrego .

W teorii mnogości , zbiór x nazywany jest dobrze założony zestaw jeśli przynależność zestaw relacja jest dobrze założony na przechodniego zamknięcia z x . Aksjomat regularności , który jest jednym z aksjomatów Zermelo-Fraenkel teorii mnogości , twierdzi, że wszystkie zestawy są dobrze uzasadnione.

Relacja R jest odwrotna uzasadnione , w górę uzasadnione lub Noetherian na X , jeśli odwrotnej relacji R ^-1 jest dobrze założona X . W tym przypadku mówi się również, że R spełnia warunek wstępującego łańcucha . W kontekście systemów przepisywania relacja Noetherian jest również nazywana zakończeniem .

Indukcja i rekurencja

Ważnym powodem, dla którego dobrze ugruntowane relacje są interesujące, jest to, że można na nich zastosować wersję indukcji pozaskończonej : jeśli ( X , R ) jest relacją dobrze ugruntowaną, P ( x ) jest pewną własnością elementów X , a my chcę to pokazać

P ( x ) odnosi się do wszystkich elementów x w X ,

wystarczy wykazać, że:

Jeśli x jest elementem X, a P ( y ) jest prawdziwe dla wszystkich y, tak że y R x , to P ( x ) również musi być prawdziwe.

To jest,

${\ Displaystyle (\ forall x \ w X) \; [(\ forall y \ w X) \; [YRx \ implikuje P (y)] \ oznacza P (x)] \ quad {\ tekst {implikuje}} \ quad (\ forall x \ in X) \, P (x).}$

Dobrze ugruntowana indukcja jest czasami nazywana indukcją Noetherian, po Emmy Noether .

Na równi z indukcją, dobrze ugruntowane relacje wspierają konstruowanie obiektów przez rekurencję pozaskończoną . Niech ( X , R ) będzie dobrze ugruntowaną relacją podobną do zbioru, a F funkcją, która przypisuje obiekt F ( x , g ) każdej parze elementu x ∈ X i funkcją g na początkowym odcinku { y : y R x } z X . Wtedy istnieje unikalna funkcja G taka, że ​​dla każdego x ∈ X ,

${\ Displaystyle G (x) = F \ lewo (x, G \ vert _ {\ lewo \ {y: \, yRx \ prawo \}} \ prawo).}$

To znaczy, jeśli chcemy skonstruować funkcję G na X , możemy zdefiniować G ( x ) używając wartości G ( y ) dla y R x .

Jako przykład rozważmy dobrze ugruntowaną relację ( N , S ), gdzie N jest zbiorem wszystkich liczb naturalnych , a S jest wykresem funkcji następczej x ↦ x +1. Wtedy indukcja na S jest zwykłą indukcją matematyczną , a rekursja na S daje rekursję pierwotną . Jeśli weźmiemy pod uwagę relację porządku ( N , <), otrzymamy pełną indukcję i rekursję przebiegu wartości . Stwierdzenie, że ( N , <) jest dobrze uzasadnione, jest również znane jako zasada dobrego uporządkowania .

Istnieją inne interesujące, szczególne przypadki dobrze uzasadnionej indukcji. Kiedy dobrze ugruntowaną relacją jest zwykle porządkowanie w klasie wszystkich liczb porządkowych , technika ta nazywana jest indukcją pozaskończoną . Gdy dobrze ugruntowany zbiór jest zbiorem rekurencyjnie zdefiniowanych struktur danych, technika ta nazywana jest indukcją strukturalną . Gdy dobrze ugruntowana relacja jest przypisana członkostwu do klasy uniwersalnej, technika ta nazywana jest indukcją ind . Więcej informacji znajdziesz w tych artykułach.

Przykłady

Dobrze ugruntowane relacje, które nie są całkowicie uporządkowane, obejmują:

• dodatnie liczby całkowite {1, 2, 3, ...}, w kolejności określonej przez a < b wtedy i tylko wtedy, gdy a dzieli b i a ≠ b .
• zbiór wszystkich skończonych ciągów w ustalonym alfabecie, z porządkiem zdefiniowanym przez s < t wtedy i tylko wtedy, gdy s jest właściwym podciągiem t .
• Zestaw N x N z parami z liczb naturalnych , na zlecenie ( n- ₁ , n- ₂ ) <( m ₁ , m ₂ ), wtedy i tylko wtedy, gdy n ₁ < m ₁ i n ₂ < m ₂ .
• zbiór wszystkich wyrażeń regularnych w ustalonym alfabecie, z porządkiem zdefiniowanym przez s < t wtedy i tylko wtedy, gdy s jest właściwym podwyrażeniem t .
• dowolna klasa, której elementy są zbiorami, z relacją („jest elementem”). To jest aksjomat regularności . ${\ displaystyle \ in}$
• węzły dowolnego skończonego skierowanego grafu acyklicznego , z relacją R zdefiniowaną tak, że a R b wtedy i tylko wtedy, gdy istnieje krawędź od a do b .

Przykłady relacji, które nie są uzasadnione:

• ujemne liczby całkowite {−1, −2, −3,…}, w zwykłej kolejności, ponieważ każdy nieograniczony podzbiór nie ma najmniejszego elementu.
• Zbiór łańcuchów nad skończonym alfabetem z więcej niż jednym elementem, w zwykłym ( leksykograficznym ) porządku, ponieważ sekwencja „B”> „AB”> „AAB”> „AAAB”>… jest nieskończonym łańcuchem opadającym. Ta relacja nie jest dobrze ugruntowana, mimo że cały zbiór ma minimalny element, a mianowicie pusty łańcuch.
• z liczbami wymiernymi (lub reals ) w ramach standardowej kolejności, ponieważ, na przykład zbiór dodatnich liczb wymiernych (lub liczb rzeczywistych) brakuje minimum.

Inne właściwości

Jeśli ( X , <) jest dobrze ugruntowaną relacją, a x jest elementem X , to zstępujące łańcuchy zaczynające się od x są wszystkie skończone, ale nie oznacza to, że ich długości są koniecznie ograniczone. Rozważmy następujący przykład: Niech X będzie sumą dodatnich liczb całkowitych i nowego elementu ω, który jest większy niż dowolna liczba całkowita. Wtedy X jest zbiorem dobrze ugruntowanym, ale istnieją zstępujące łańcuchy zaczynające się od ω o dowolnej dużej (skończonej) długości; łańcuch ω, n - 1, n - 2, ..., 2, 1 ma długość n dla dowolnego n .

Kolaps mostowskiego oznacza, że członkostwo zestaw jest uniwersalnym wśród ekstensjonalnych stosunków zasadną: dla każdego zbioru, jak dobrze założonej relacji R na klasy X , który jest ekstensjonalny, istnieje klasa C takie, że ( X , R ) jest izomorficzny do ( C , ∈).

Refleksyjność

Relacja R jest uważane za zwrotny jeśli R zachodzi dla każdego A w dziedzinie relacji. Każda relacja zwrotna na niepustej domenie ma nieskończone zstępujące łańcuchy, ponieważ każda stała sekwencja jest zstępującym łańcuchem. Na przykład w liczbach naturalnych z ich zwykłą kolejnością ≤, musimy uniknąć tych trywialnych ciągów malejących, pracując z porządkiem częściowym ≤, często stosuje się definicję zasadności (być może pośrednio) do relacji alternatywnej <zdefiniowane takie, że a < b wtedy i tylko wtedy, gdy a ≤ b i a ≠ b . Mówiąc bardziej ogólnie, podczas pracy z zamówieniem w przedsprzedaży ≤, często używa się relacji <zdefiniowanej w taki sposób, że a < b wtedy i tylko wtedy, gdy a ≤ b i b ≰ a . W kontekście liczb naturalnych oznacza to, że relacja <, która jest dobrze uzasadniona, jest używana zamiast relacji ≤, która nie jest. W niektórych tekstach definicja dobrze ugruntowanej relacji została zmieniona z powyższej definicji, aby uwzględnić te konwencje. ${\ displaystyle 1 \ geq 1 \ geq 1 \ geq \ cdots.}$

Bibliografia

• Just, Winfried and Weese, Martin (1998) Odkrywanie nowoczesnej teorii mnogości. Ja , American Mathematical Society ISBN   0-8218-0266-6 .
• Karel Hrbáček i Thomas Jech (1999) Wprowadzenie do teorii mnogości , 3. wydanie, „Dobrze ugruntowane relacje”, strony 251–5, Marcel Dekker ISBN   0-8247-7915-0