Zbiory uporządkowane
Definicja 1.1. Porządkiem (w wielu podręcznikach jest używana jest również nazwa poset, pochodząca od angielskiego skrótu
partially ordered set) nazywamy parę
(X,R), gdzie
X jest zbiorem, a
R⊂X2 jest relacją:
- zwrotną,
- przechodnią,
- antysymetryczną, to znaczy jeżeli (x,y)∈R oraz (y,x)∈R, to x=y.
Jeżeli dodatkowo relacja R jest spójna (to znaczy taka, że ∀x,y∈X(x,y)∈R lub (y,x)∈R ), to porządek nazywamy liniowym.
Często oznaczamy relacje porządkującą jako ≤. Oznaczamy też x<y, gdy x≤y oraz x≠y.
Definicja 1.2.
Element a nazywamy maksymalnym w porządku (X,≤), gdy ∀x∈Xa≤x⇒a=x.
Element a nazywamy minimalnym w porządku (X,≤), gdy ∀x∈Xx≤a⇒a=x.
Element a nazywamy największym w porządku (X,≤), gdy ∀x∈Xx≤a.
Element a nazywamy najmniejszym w porządku (X,≤), gdy ∀x∈Xa≤x.
Definicja 1.3.
Niech A⊂X oraz b∈X. Mówimy, że b jest majorantą zbioru A, gdy ∀a∈Aa≤b.
Niech A⊂X oraz b∈X. Mówimy, że b jest minorantą zbioru A, gdy ∀a∈Ab≤a.
Definicja 1.4.
A⊂X. Element a0∈X nazywamy supremum zbioru A, gdy:
- ∀a∈Aa≤a0,
- (∀a∈Aa≤b)⇒a0≤b.
Łatwo zauważyć, że supremum, o ile istnieje, jest jedyne i jest najmniejszą z majorant. Jeżeli istnieje supremum dla A będziemy je oznaczać ⋁A.
Definicja 1.5.
A⊂X. Element b0∈X nazywamy infimum zbioru A, gdy:
- ∀a∈Ab0≤a
- (∀a∈Ab≤a)⇒b≤b0
Tak jak w przypadku supremum infimum, o ile istnieje, jest jedyne i jest największą z minorant zbioru. Jeżeli istnieje infimum dla A, będziemy je oznaczać ⋀A.
Ćwiczenie 1.6
Niech X będzie ustalonym zbiorem i niech A⊂P(X). Zdefiniujmy relację ⊑⊂A×A następująco:
a⊑b⇔a⊆b.
Udowodnij, że (A,⊑) jest zbiorem uporządkowanym.
Uwaga 1.7.
Nadużywając notacji, będziemy czasem używać symbolu ⊂ dla oznaczenia relacji ⊑ zdefiniowanej w poprzednim ćwiczeniu. Zwracamy przy tym uwagę, że nie ma czegoś takiego jak relacja ⊂, gdyż musiałaby ona być określona w zbiorze wszystkich zbiorów, który nie istnieje. W przypadku jednak, gdy rozważamy jedynie podzbiory ustalonego zbioru X, możemy mówić o relacji bycia podzbiorem. Czasem dla podkreślenia, że mówimy o podzbiorach ustalonego zbioru, będziemy pisać ⊂X.
Ćwiczenie 1.8
Dla dowolnego zbioru A, jego zbiór potęgowy P(A) jest uporządkowany przez inkluzję. Czy dla dowolnej niepustej rodziny r⊂P(A) istnieje supremum i infimum?
Ćwiczenie 1.9
W zbiorze liczb naturalnych zdefiniujemy relację |⊂N2 następująco:
∀a,b∈N[a|b⇔∃c∈Nc⋅a=b].
Udowodnij, że relacja ta porządkuje zbiór N. Czy w tak uporządkowanym zbiorze istnieją elementy najmniejszy i największy?
Ćwiczenie 1.10
W zbiorze funkcji z N w N (czyli NN) zdefiniujmy relację R następująco:
∀f,g∈NN[fRg⇔∃h∈NNh∘f=g∘h].
Sprawdź, czy relacja ta jest zwrotna, przechodnia i antysymetryczna.
Ćwiczenie 1.11
Niech I=[0,1]⊂R. W zbiorze II zdefiniujemy relację R następująco:
∀f,g∈II[fRg⇔∃x∈If(x)≤g(x)].
Sprawdź, czy relacja R jest zwrotna, przechodnia i antysymetryczna.
Ćwiczenie 1.12
Niech I=[0,1]⊂R. W zbiorze II zdefiniujemy relację R następująco:
∀f,g∈II[fRG⇔∀x∈If(x)≤g(x)].
Udowodnij, że relacja R porządkuje zbiór I. Czy w porządku istnieją elementy najmniejszy i największy?
Ćwiczenie 1.13
Podaj przykład przeliczalnego porządku, w którym istnieje element najmniejszy i największy.
Ćwiczenie 1.14
Podaj przykład porządku, w którym istnieje element maksymalny, który nie jest elementem największym. Czy istnieje taki porządek, żeby element maksymalny był jedyny?
Ćwiczenie 1.15
Podaj przykład zbioru liniowo uporządkowanego (X,≤), w którym istnieje podzbiór niemający supremum.
Takim zbiorem jest N uporządkowany naturalną relacją ≤. Wtedy cały zbiór N nie ma supremum, gdyż takie supremum musiałoby być największą liczbą naturalną, a taka nie istnieje.
Ćwiczenie 1.16
Udowodnij, że zbiorze uporządkowanym (X,≤) istnieje ⋁∅ wtedy i tylko wtedy, gdy w X istnieje element najmniejszy.
Ćwiczenie 1.17
Udowodnij, że zbiorze uporządkowanym (X,≤), jeśli każdy podzbiór ma supremum, to każdy podzbiór ma infimum.
Ćwiczenie 1.18
Podaj przykład porządku (X,≤) takiego, że podzbiór A⊂X ma supremum wtedy i tylko wtedy, gdy jest skończony.
Przykładem takiego porządku są skończone podzbiory liczb naturalnych, uporządkowane przez inkluzję; oznaczymy ten porządek przez (Pfin(N),⊂). Dla dowolnego skończonego zbioru A⊂Pfin(N) mamy ⋃A∈Pfin(N), a więc zbiór ten ma supremum w Pfin(N). Jeśli zbiór A jest nieskończony, to ⋃A jest nieskończony, a więc ⋃A∉Pfin(N), co oznacza, że w Pfin(N) nie istnieje supremum zbioru A (gdyby istniało, to w zbiorze (P(N),⊂) istniałyby dwa suprema zbioru A, co jest niemożliwe).
Definicja 1.19
L⊂X jest łańcuchem w porządku (X,≤), gdy każde dwa elementy L są porównywalne w sensie ≤. Oznacza to, że porządek indukowany na zbiorze L, czyli (L,R∩L×L) jest porządkiem liniowym.
Definicja 1.20.
Zbiór A⊂X jest antyłańcuchem w porządku (X,≤), gdy żadne dwa różne elementy A nie są porównywalne w sensie ≤. Formalnie, jeśli następująca formuła jest prawdziwa:
∀a,b∈A(a≤b⇒a=b).
Ćwiczenie 1.21
Sprawdź, czy suma antyłańcuchów musi być antyłańcychem oraz czy suma łańcuchów musi być łańcuchem.
Ćwiczenie 1.22
Czy antyłańcuch może być łańcuchem?
Ćwiczenie 1.23
Podaj przykład porządku, w których nie istnieje największy w sensie inkluzji łańcuch ani antyłańcuch.
Ćwiczenie 1.24
Kiedy w porządku (X,≤) istnieje największy w sensie inkluzji łańcuch.
Ćwiczenie 1.25
Kiedy w porządku (X,≤) istnieje największy w sensie inkluzji antyłańcuch.
Ćwiczenie 1.26
Czy porządek, w którym każdy łańcuch jest skończony, musi być skończony? Czy taki porządek może zawierać łańcuchy o dowolnie dużej skończonej mocy?
Ćwiczenie 1.27
Rozważmy zbiór 7={0,1,2,3,4,5,6} uporządkowany relacją podzielności (czyli a|b⇔∃c∈7a⋅c=b). Wypisz wszystkie łańcuchy maksymalne w sensie inkluzji. Wypisz wszystkie antyłańcuchy maksymalne w sensie inkluzji.