Zbiory uporządkowane
Zbiorem uporządkowanym (częściowo) nazywamy parę , gdzie jest zbiorem, a jest relacją:
1. Zwrotną, tzn. dla dowolnego zachodzi
2. Antysymetryczną, tzn. spełnia warunek
3. Przechodnią, tzn. spełnia warunek
Jeżeli dodatkowo relacja jest spójna, tzn. dla dowolnych zachodzi lub , to wtedy parę , nazywamy zbiorem liniowo uporządkowanym. Mówimy wtedy, że jest liniowym porządkiem na , oraz że zbiór jest liniowo uporządkowany przez . Podobnie dla zbioru uporządkowanego, relację nazywamy porządkiem (częściowym) na zbiorze
Często oznaczamy relację porządku przez ( lub symbolami podobnymi np.). Dla zbioru uporządkowanego , dla dowolnego zachodzi bo relacja porządku jest zwrotna. Zatem dla elementów , oznaczamy gdy i i mówimy, że jest silnie mniejszy od Podobnie dla innych oznaczeń relacji porządku. W zbiorze uporządkowanym , będziemy czasem pisać zamiast , oraz zamiast
Warto zobaczyć jaką postać przyjmują wymagania stawiane zbiorom liniowo uporządkowanym, gdy relację liniowego porządku oznaczymy przez , (i gdy będziemy pisać zamiast będziemy pisać O zwrotności już pisałem, jako , dla dowolnego Antysymetria przyjmuję postać: jeżeli i , to . Przechodniość przyjmuję postać: jeżeli i , to Spójność zapisujemy jako: dla dowolnych ma zachodzić lub . Nietrudno więc zauważyć, że te własności są spełnione w zbiorach liczbowych z naturalnym porządkiem. Nasza definicja zbioru liniowego uporządkowanego jest więc uogólnieniem znanych własności porządkowych na zbiorach liczbowych. Nie zapominajmy jednak, że formalnie jest to zbiór wraz z relacją, która ma dokładnie wymienione własności.
Niech będzie zbiorem uporządkowanym. niech . Element nazywamy elementem najmniejszym zbioru względem porządku , gdy , oraz gdy dla dowolnego , zachodzi
Tzn. element najmniejszy zbioru , to taki element , który jest mniejszy lub równy (względem rozpatrywanego porządku) od każdego elementu tego zbioru .
Analogicznie możemy zdefiniować element największy zbioru , jako taki element , który jest większy lub równy od każdego elementu tego zbioru, tzn. dla dowolnego zachodzi
Niech zbiory uporządkowane. Porządek nazywamy rozszerzeniem porządku , gdy dla dowolnych spełniony jest warunek:
Tzn. jeśli jest mniejszy ( lub równy) od względem danego porządku (na ),to tymbardziej musi być mniejsze(lub równe) od względem porządku rozszerzającego. Dla liniowych porządków wygląda to tak, że porządek rozszerzający jest szerszy- zobacz ilustrację obok.
Twierdzenie:
Niech będzie dowolnym ustalonym zbiorem. Niech będzie pewnym zbiorem złożonym z liniowych porządków( samych relacji) określonych na pewnych podzbiorach , takim, że dla dowolnych dwóch liniowych porządków w jeden jest rozszerzeniem drugiego, to wtedy dla relacji , zachodzi i jest liniowym porządkiem na tym zbiorze.
Tzn. suma rodziny liniowych porządków na podzbiorach , i jeśli wiemy, że dla dowolnych dwóch takich liniowych porządków jeden jest rozszerzeniem drugiego, to wtedy suma rodziny takich liniowych porządków jest liniowym porządkiem na swoim polu- zobacz ilustrację obok.
Dowód:
Aby wykazać, że wykażemy inkluzję w obydwie strony.
Aby pokazać, że , to niech . Oznacza to , że przy pewnym . To z kolei zapisujemy a więc dla pewnego liniowego porządku z . Porządek taki jest zwrotny, więc , a więc otrzymujemy, że , lub inaczej , i ponieważ jest prawą współrzędna pary z relacji , to , i
Dowód inkluzji w drugą stronę jest analogiczny. A więc Oznaczmy ten zbiór jako . Wykażemy, że jest liniowym porządkiem na tym zbiorze.
Zwrotność. Niech . Należy pokazać, że , lub inaczej że czyli, że dla pewnego liniowego porządku z . Ale każdy liniowy porządek jest zwrotny, więc powyższy fakt jest prawdziwy. Relacja jest więc zwrotna.
Antysymetria. Niech i . Pokażemy, że . Równoważnie możemy zapisać nasze założenia jako i Pierwszy warunek oznacza, że dla pewnego liniowego porządku z Drugi warunek oznacza, że dla pewnego liniowego porządku z ( niekoniecznie tego samego). Ale wiemy, że dla dowolnych dwóch liniowych porządków z jeden jest rozszerzeniem drugiego, więc jeśli jest rozszerzeniem , to z warunku wynika, że mamy , i ponieważ liniowy porządek jest antysymetryczny, to dostajemy , co należało pokazać. W drugim przypadku jest rozszerzeniem , i wtedy z warunku wynika, że , mamy , i ponieważ liniowy porządek jest antysymetryczny, to dostajemy , co należało pokazać. Antysymetria jest więc pokazana.
Przechodniość. Niech Pokażemy, że Nasze założenia możemy inaczej zapisać jako: oraz Wnioskujemy, że dla pewnego liniowego porządku z , oraz, że dla pewnego liniowego porządku z . Dla porządków , jeden jest rozszerzeniem drugiego, więc jeśli jest rozszerzeniem , to z faktu wynika, że , mamy, że , więc z przechodniości liniowego porządku otrzymujemy, że , a więc , czyli W pozostałym przypadku musi być rozszerzeniem , a wtedy z faktu wynika, że , mamy założenie, że , więc z przechodniości liniowego porządku , dostajemy, że , i również w tym przypadku Relacja jest więc przechodnia.
Dowód spójności jest niestety bardzo żmudny, więc go pomijamy. Wykazaliśmy, że jest porządkiem na swoim polu. Tego twierdzenia użyjemy tylko chyba raz w dowodzie twierdzenia Zermelo. To, że ten porządek jest liniowy nie będzie nam wtedy konieczne.
