Dobrze zamów - Well-order

W matematyce , A oraz rzędu (a oraz zamawiania lub dobrze celu związek ) w zbiorze S jest całkowita celu na S z właściwości, co nie jest pusty podzbiór z S ma najmniejszy element, w tej kolejności. Zbiór S razem z relacją uporządkowaną nazywamy wtedy zbiorem uporządkowanym . W niektórych artykułach akademickich i podręcznikach terminy te są zamiast tego zapisywane jako uporządkowane , uporządkowane i uporządkowane lub dobrze uporządkowane , dobrze uporządkowane i dobrze uporządkowane .

Każdy niepusty, dobrze uporządkowany zestaw ma najmniej elementu. Każdy element s od uporządkowanego zbioru, z wyjątkiem możliwie największego elementu , ma unikalną następcy (NEXT), a mianowicie elementu najmniej element podzbiorze wszystkich elementów większe niż s . Oprócz najmniejszego elementu mogą istnieć elementy, które nie mają poprzednika (patrz przykład w § Liczby naturalne poniżej). Dobrze uporządkowanym S zawiera dla każdego podzbioru T z górną związaną z co najmniej górne ograniczenie , a mianowicie co najmniej element podzbiorze wszystkich górnych granic T w S .

Jeśli ≤ jest nieścisłym uporządkowaniem dobrze, to <jest ścisłym uporządkowaniem dobrze. Relacja jest ściśle uporządkowanym porządkiem wtedy i tylko wtedy, gdy jest dobrze ugruntowanym ścisłym porządkiem całkowitym . Często ignoruje się rozróżnienie między ścisłymi i nieścisłymi porządkami studni, ponieważ są one łatwo wymienialne.

Każdy dobrze uporządkowany zestaw jest unikatowo uporządkowany izomorficznie do unikalnej liczby porządkowej , zwanej typem porządku dobrze uporządkowanego zbioru. Twierdzenie o dobrym uporządkowaniu , które jest równoważne z aksjomatem wyboru , stwierdza, że ​​każdy zbiór można dobrze uporządkować. Jeśli zbiór jest dobrze uporządkowany (lub nawet jeśli po prostu dopuszcza dobrze uzasadnioną relację ), można zastosować metodę dowodzenia indukcji pozaskończonej, aby udowodnić, że dane zdanie jest prawdziwe dla wszystkich elementów zbioru.

Spostrzeżenie, że liczby naturalne są dobrze uporządkowane przez zwykłą relację mniej niż, jest powszechnie nazywane zasadą porządku (dla liczb naturalnych).

Liczby porządkowe

Każdy dobrze uporządkowany zestaw jest unikatowo uporządkowany izomorficznie do unikalnej liczby porządkowej , zwanej typem porządku dobrze uporządkowanego zbioru. Pozycję każdego elementu w uporządkowanym zbiorze określa również liczba porządkowa. W przypadku zbioru skończonego podstawową operacją liczenia , aby znaleźć liczbę porządkową danego obiektu lub znaleźć przedmiot o określonej liczbie porządkowej, jest przypisanie poszczególnym przedmiotom liczb porządkowych. Rozmiar (liczba elementów, liczba kardynalna ) skończonego zbioru jest równy rodzajowi zamówienia. Liczenie w codziennym sensie zwykle zaczyna się od jedynki, więc przypisuje każdemu obiektowi rozmiar początkowego segmentu z tym obiektem jako ostatnim elementem. Zauważ, że te liczby są o jeden więcej niż formalne liczby porządkowe zgodnie z porządkiem izomorficznym, ponieważ są one równe liczbie wcześniejszych obiektów (co odpowiada liczeniu od zera). Zatem dla skończonego n wyrażenie „ n- ty element” dobrze uporządkowanego zbioru wymaga, aby kontekst wiedział, czy liczy się od zera, czy od jednego. W notacji „β-ten element”, gdzie β może być również nieskończoną liczbą porządkową, będzie on zazwyczaj liczony od zera.

W przypadku nieskończonego zestawu typ porządku określa liczność , ale nie odwrotnie: dobrze uporządkowane zbiory o określonej liczności mogą mieć wiele różnych typów kolejności. Prosty przykład można znaleźć w sekcji # Liczby naturalne . Dla policzalnie nieskończonego zbioru zbiór możliwych typów zleceń jest nawet niepoliczalny.

Przykłady i kontrprzykłady

Liczby naturalne

Standardowe uporządkowanie ≤ liczb naturalnych jest porządkiem dobrze i ma dodatkową właściwość polegającą na tym, że każda niezerowa liczba naturalna ma unikalnego poprzednika.

Inną dobrą kolejnością liczb naturalnych jest zdefiniowanie, że wszystkie liczby parzyste są mniejsze niż wszystkie liczby nieparzyste, a zwykła kolejność ma zastosowanie w liczbach parzystych i kursach:

0 2 4 6 8 ... 1 3 5 7 9 ...

Jest to uporządkowany zestaw typu ω + ω. Każdy element ma następcę (nie ma elementu największego). Brakuje dwóch elementów poprzednika: 0 i 1.

Liczby całkowite

W przeciwieństwie do standardowego uporządkowania ≤ liczb naturalnych , standardowe uporządkowanie ≤ liczb całkowitych nie jest dobrym porządkiem, ponieważ na przykład zbiór ujemnych liczb całkowitych nie zawiera najmniejszego elementu.

Następująca relacja R jest przykładem dobrego uporządkowania liczb całkowitych: x R y wtedy i tylko wtedy, gdy zachodzi jeden z następujących warunków:

  1. x = 0
  2. x jest dodatnie, a y jest ujemne
  3. x i y są dodatnie, a x y
  4. x i y są ujemne, a | x | ≤ | y |

Relację R można wizualizować następująco:

0 1 2 3 4 ... −1 −2 −3 ...

R jest izomorficzna z liczbą porządkową ω + ω.

Inną relacją do porządkowania liczb całkowitych jest następująca definicja: x  ≤ z   y wtedy i tylko wtedy, gdy (| x | <| y | lub (| x | = | y | i x  ≤  y )). Ten porządek studni można wizualizować w następujący sposób:

0 −1 1 −2 2 −3 3 −4 4 ...

Ma to typ zamówienia ω.

Reals

Standardowe uporządkowanie ≤ dowolnego rzeczywistego przedziału nie jest porządkiem dobrze, ponieważ na przykład przedział otwarcia (0, 1) ⊆ [0,1] nie zawiera najmniejszego elementu. Z aksjomatów ZFC teorii mnogości (w tym aksjomatu wyboru ) można wykazać, że istnieje dobry porządek liczb rzeczywistych. Również Wacław Sierpiński udowodnił, że ZF + GCH ( uogólniona hipoteza kontinuum ) implikuje aksjomat wyboru, a tym samym porządek liczb rzeczywistych. Niemniej jednak można wykazać, że same aksjomaty ZFC + GCH nie wystarczają do udowodnienia istnienia dającego się zdefiniować (za pomocą wzoru) dobrze uporządkowania liczb rzeczywistych. Jednak jest zgodne z ZFC, że istnieje definiowalny porządek liczb rzeczywistych - na przykład jest zgodny z ZFC, że V = L , a z ZFC + V = L wynika, że ​​konkretna formuła dobrze porządkuje liczby rzeczywiste, a nawet zestaw.

Niezliczony podzbiór liczb rzeczywistych ze standardowym porządkiem ≤ nie może być porządkiem dobrze: załóżmy, że X jest podzbiorem R uporządkowanym przez ≤. Dla każdego x w X niech s ( x ) będzie następcą x w kolejności ≤ na X (chyba że x jest ostatnim elementem X ). Niech A = {( x , s ( x )) | x X }, których elementami są niepuste i rozłączne przedziały. Każdy taki przedział zawiera co najmniej jeden numer racjonalne, więc nie jest to za pomocą wstrzyknięć funkcja od A do Q . Istnieje wstrzyknięcie z X do A (z wyjątkiem być może ostatniego elementu X, który można później zamapować na zero). I dobrze wiadomo, że istnieje zastrzyk z Q do liczb naturalnych (które można wybrać, aby uniknąć trafienia zera). W ten sposób występuje zastrzyk z X do liczb naturalnych, co oznacza, że X jest policzalny. Z drugiej strony, policzalnie nieskończony podzbiór liczb rzeczywistych może, ale nie musi, być dobrym porządkiem ze standardem „≤”. Na przykład,

  • Liczby naturalne są dobrze uporządkowane zgodnie ze standardowym porządkiem ≤.
  • Zbiór {1 / n: n = 1,2,3, ...} nie ma najmniejszego elementu i dlatego nie jest dobrym porządkiem w standardowym uporządkowaniu ≤.

Przykłady zamówień studni:

  • Zbiór liczb {- 2 - n | 0 ≤ n <ω} ma typ zamówienia ω.
  • Zbiór liczb {- 2 - n - 2 - m - n | 0 ≤ m , n <ω} ma typ zlecenia ω 2 . Poprzedni zestaw to zbiór punktów granicznych w zestawie. W zbiorze liczb rzeczywistych, czy to w zwykłej topologii, czy w topologii porządku, 0 jest również punktem granicznym zbioru. Jest to również punkt graniczny zbioru punktów granicznych.
  • Zbiór liczb {- 2 - n | 0 ≤ n <ω} ∪ {1} ma typ zlecenia ω + 1. W topologii porządku tego zbioru, 1 jest punktem granicznym zbioru. W przypadku zwykłej topologii (lub równoważnie topologii porządku) liczb rzeczywistych tak nie jest.

Równoważne sformułowania

Jeśli zestaw jest całkowicie zamówiony , następujące elementy są sobie równoważne:

  1. Zestaw jest dobrze uporządkowany. Oznacza to, że każdy niepusty podzbiór ma najmniejszy element.
  2. Indukcja nieskończona działa dla całego zamówionego zestawu.
  3. Każdy ściśle malejący ciąg elementów zbioru musi kończyć się po zaledwie skończonej liczbie kroków (przy założeniu aksjomatu wyboru zależnego ).
  4. Każde podporządkowanie jest izomorficzne z początkowym segmentem.

Zamów topologię

Każdy uporządkowany zestaw można przekształcić w przestrzeń topologiczną , nadając mu topologię kolejności .

W odniesieniu do tej topologii mogą istnieć dwa rodzaje elementów:

  • pojedyncze punkty - to minimum i elementy z poprzednikiem.
  • punkty graniczne - ten typ nie występuje w zbiorach skończonych i może, ale nie musi, występować w zestawie nieskończonym; nieskończone Zestawy bez punktu granicznego są zestawy typu celu co, na przykład N .

W przypadku podzbiorów możemy wyróżnić:

  • Podzbiory z maksimum (to znaczy podzbiory, które są ograniczone sobą); może to być pojedynczy punkt lub punkt graniczny całego zestawu; w tym drugim przypadku może, ale nie musi, być również punktem granicznym podzbioru.
  • Podzbiory, które same w sobie są nieograniczone, ale ograniczone w całym zbiorze; nie mają maksimum, ale supremum poza podzbiorem; jeśli podzbiór nie jest pusty, to supremum jest punktem granicznym podzbioru, a zatem także całego zbioru; jeśli podzbiór jest pusty, to supremum jest minimum całego zbioru.
  • Podzbiory, które są nieograniczone w całym zbiorze.

Podzbiór jest kumulatywny w całym zbiorze wtedy i tylko wtedy, gdy jest nieograniczony w całym zbiorze lub ma maksimum, które jest jednocześnie maksimum całego zbioru.

Uporządkowany zbiór jako przestrzeń topologiczna jest przestrzenią policzalną jako pierwszy wtedy i tylko wtedy, gdy ma typ porządku mniejszy lub równy ω 1 ( omega-jeden ), to znaczy wtedy i tylko wtedy, gdy zbiór jest policzalny lub ma najmniejszy niepoliczalny rodzaj zamówienia.

Zobacz też

Bibliografia

  1. ^ Feferman, S. (1964). „Niektóre zastosowania pojęć wymuszania i zbiorów rodzajowych” . Fundamenta Mathematicae . 56 (3): 325–345. doi : 10.4064 / fm-56-3-325-345 .