Processing math: 100%

Zbiory uporządkowane

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 RX2 jest relacją:

  1. zwrotną,
  2. przechodnią,
  3. 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,yX(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 xy oraz xy.

Definicja 1.2.

Element a nazywamy maksymalnym w porządku (X,), gdy xXaxa=x.

Element a nazywamy minimalnym w porządku (X,), gdy xXxaa=x.

Element a nazywamy największym w porządku (X,), gdy xXxa.

Element a nazywamy najmniejszym w porządku (X,), gdy xXax.

Definicja 1.3.

Niech AX oraz bX. Mówimy, że b jest majorantą zbioru A, gdy aAab.

Niech AX oraz bX. Mówimy, że b jest minorantą zbioru A, gdy aAba.

Definicja 1.4.

AX. Element a0X nazywamy supremum zbioru A, gdy:

  1. aAaa0,
  2. (aAab)a0b.

Ł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.

AX. Element b0X nazywamy infimum zbioru A, gdy:

  1. aAb0a
  2. (aAba)bb0

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 AP(X). Zdefiniujmy relację ⊑⊂A×A następująco:

abab.

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 rP(A) istnieje supremum i infimum?


Ćwiczenie 1.9

W zbiorze liczb naturalnych zdefiniujemy relację |N2 następująco:

a,bN[a|bcNca=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,gNN[fRghNNhf=gh].

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,gII[fRgxIf(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,gII[fRGxIf(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 AX 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 APfin(N) mamy APfin(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 APfin(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

LX 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,RL×L) jest porządkiem liniowym.

Definicja 1.20.

Zbiór AX 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,bA(aba=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|bc7ac=b). Wypisz wszystkie łańcuchy maksymalne w sensie inkluzji. Wypisz wszystkie antyłańcuchy maksymalne w sensie inkluzji.