Relacja częściowego porządku ma właściwości. Własności relacji na zbiorze

Ostatni przykład wprowadza koncepcję porządku alfabetycznego.

Alfabet jest krotką parami odrębnych znaków zwanych literami alfabetu. Przykładem jest alfabet dowolnego języka europejskiego, a także alfabet składający się z 10 cyfr arabskich.Na komputerze klawiatura i niektóre narzędzia pomocnicze określają alfabet prawidłowych znaków.

Słowo w alfabecieA - krotka znaków alfabetu A. Słowo zapisywane jest symbolami alfabetycznymi w rzędzie, od lewej do prawej, bez spacji.Liczba naturalna jest słowem w alfabecie cyfrowym.Formuła nie zawsze jest słowem ze względu na nieliniowy układ symboli, obecność indeks górny (wykładniki) i dolny (indeksy zmiennych, podstawy logarytmów), symbole, kreski ułamkowe, rodniki znaków itp.; jednakże według niektórych konwencji można go zapisać w postaci ciągu znaków, który wykorzystuje się np. w programowaniu komputerów (np. znak potęgowania zapisuje się jako 2 znaki mnożenia pod rząd: 5**3 oznacza trzecią potęgę liczby numer 5.

Porządek leksykograficzny (alfabetyczny) - dla różnych słów w alfabecie z uporządkowanym

symbole ustalają kolejność: , if

możliwość prezentacji , przy którym albo

(podsłowo może być puste) lub - puste podsłowo

W tej definicji - przedrostek (podsłowo początkowe) taki sam dla obu słów - lub pierwsze z lewej strony są różne

znaków, albo - ostatni znak w słowie - ogon

słowa podrzędne.

Zatem o kolejności alfabetycznej słów decyduje pierwszy symbol z lewej strony, który je odróżnia (na przykład słowo KONUS poprzedza słowo COSINUS, ponieważ różnią się one najpierw trzecią literą, a N poprzedza S w alfabecie rosyjskim). Uważa się również, że znak spacji poprzedza dowolny znak alfabetu - w przypadku, gdy jedno ze słów jest przedrostkiem innego (na przykład CON i CONE)

Ćwiczenia. Sprawdź, czy porządek alfabetyczny liczb naturalnych mających tę samą liczbę miejsc po przecinku pokrywa się z ich porządkiem według wielkości.

Pozwalać A - częściowo zamówiony zestaw. Element nazywa się maksymalny V A, jeśli nie ma elementu dla którego A< b. Element A zwany największy V A, jeśli dla każdego innego niż A element ukończony B<а-

Ustalane symetrycznie minimalne i najmniejsze elementy. Pojęcia największych i maksymalnych (odpowiednio najmniejszych i minimalnych) elementów są różne - patrz. przykład na ryc. 14. Zestaw na rys. 14,a ma największy element R, jest to również maksimum, istnieją dwa minimalne elementy: si i t, nie ma najmniejszego. Natomiast na rys. 14b mamy do czynienia ze zbiorem mającym dwa elementy maksymalne / i J, nie ma największego, minimalnego, czyli najmniejszego - jednego: T.

Ogólnie rzecz biorąc, jeśli zbiór ma największy (odpowiednio najmniejszy) element, to jest tylko jeden (może nie być żadnego).

Elementów maksymalnych i minimalnych może być kilka (może ich w ogóle nie być – w nieskończonym zbiorze; w ostatecznym przypadku – musi być).

Spójrzmy na jeszcze dwa przykłady. - relacja na planie N:

„Y dzieli X", Lub "X jest dzielnikiem liczby Y”(Na przykład,

) jest zwrotny i przechodni. Rozważmy to na skończonym zestawie dzielników liczby 30.

Relacja jest relacją częściowego porządku (nieścisłą)

i jest reprezentowany przez następującą macierz rzędu 8, zawierającą 31 znaków

Odpowiedni obwód z 8 wierzchołkami musi zawierać 31 ogniw. . Jednak wygodniejsze będzie przeglądanie, jeśli wykluczymy 8

łączniki-pętle obrazujące zwrotność relacji (elementy diagonalne macierzy) oraz spójniki przechodnie, tj. więzadła

Jeśli istnieje liczba pośrednia Z taka, że

(na przykład łącznik od). Następnie w schemacie

Pozostanie 12 więzadeł (ryc. 15); brakujące ogniwa są sugerowane „przez przechodniość”. Liczba 1 jest najmniejsza, a liczba 30

największe elementy w . Jeśli wykluczymy z liczby 30 i

rozważ zatem ten sam częściowy porządek w zestawie

nie ma elementu maksymalnego, ale są 3 elementy maksymalne: 6, 10, 15

Teraz zbudujmy ten sam obwód dla relacji opartej na wartości logicznej

(zbiór wszystkich podzbiorów) zbioru trzyelementowego

Zawiera 8 elementów:

Sprawdź, czy pasujesz do elementów a, b, c, odpowiednio liczby 2, 3, 5 oraz operacje łączenia zbiorów to mnożenie odpowiednich liczb (tj. np. podzbiór odpowiada

iloczyn 2 5 = 10), to macierz relacji będzie dokładnie taka

tak samo jak w przypadku relacji ; schematy tych dwóch zależności z opisanymi

skróty pętli i spójników przechodnich pokrywają się aż do zapisu (patrz ryc. 16). Najmniejszym elementem jest

I największy -

Relacje binarne R na zestawie A I S na zestawie W są nazywane izomorficzny, jeśli pomiędzy A i B możliwe jest nawiązanie korespondencji jeden do jednego, w której, jeśli (tj.

elementy są ze sobą powiązane R), następnie (zdjęcia

te elementy są ze sobą powiązane S).

Zatem zbiory częściowo uporządkowane są izomorficzne.

Rozważany przykład pozwala na uogólnienia.

Relacja logiczna jest porządkiem częściowym. Jeśli

Te. pęczek mi zawiera P elementy, a następnie każdy

odpowiada podzbiorze P-wymiarowy wektor z

składowe , gdzie jest funkcją charakterystyczną

ustaw A/ . Zbiór wszystkich takich wektorów można uznać za zbiór punktów P-wymiarowa przestrzeń arytmetyczna o współrzędnych 0 lub 1, czyli inaczej mówiąc, jako wierzchołki P-wymiarowy

sześcian jednostkowy, oznaczony jako , tj. sześcian o krawędziach o jednostkowej długości. Dla n = 1, 2, 3 wskazane punkty reprezentują odpowiednio końce odcinka, wierzchołki kwadratu i sześcianu – stąd potoczna nazwa. Dla /7=4 graficzną reprezentację tej zależności przedstawiono na ryc. 17. W pobliżu każdego wierzchołka 4-wymiarowego sześcianu odpowiedni

podzbiór zbioru 4-elementowego i czterowymiarowy

wektor reprezentujący funkcję charakterystyczną tego podzbioru. Wierzchołki odpowiadające podzbiorom różniącym się obecnością dokładnie jednego elementu są ze sobą połączone.

Na ryc. 17 czterowymiarowy sześcian jest przedstawiony w taki sposób, że na jednym

poziomie nieporównywalne elementy układają się w pary zawierające w rekordzie tę samą liczbę jednostek (od 0 do 4), czyli inaczej mówiąc tę ​​samą liczbę elementów w reprezentowanych podzbiorach.

Na ryc. 18a, b - inne wizualne reprezentacje 4-wymiarowego sześcianu;

na ryc. 18a oś pierwszej zmiennej OH skierowany w górę (celowe odchylenie od pionu, aby różne krawędzie sześcianu nie połączyły się):

w tym przypadku trójwymiarowy podsześcian odpowiadający X= 0 znajduje się poniżej i dla X= 1 - wyższy. Na ryc. 186 tej samej osi OH skierowany od wewnątrz sześcianu na zewnątrz; odpowiada wewnętrznemu podsześcianowi X= Aha, i ten zewnętrzny jest X = 1.

W
Plik materiałów przedstawia obraz 5-wymiarowego sześcianu jednostkowego (s. 134).

2) relację na zbiorze X nazywamy relacją ściśle w porządku, jeśli jest antysymetryczny i przechodni. Związek nazywa się antysymetryczny, jeśli z tego, że a jest w relacji do c, nie wynika, że ​​b jest w relacji do a (a, w ∈ X i R w → w Ra a) R – być w relacji. Związek nazywa się przechodni, jeśli dla dowolnych elementów a, b, c z faktu, że a R w i w R c → że a R c, a, b, c ∈ X. Np.: relacja „więcej, mniej”. Zbiór, na którym zdefiniowana jest relacja ścisłego porządku, nazywa się zamówione wiele.

3) relację na zbiorze X nazywamy relacją nie w ścisłej kolejności, jeśli jest zwrotny, asymetryczny i przechodni. Na przykład: relacja ≥ ≤. Jeśli relacja porządku ma właściwość powiązania, to nazywa się ją relacją porządek liniowy. Związek nazywa się powiązany na zbiorze X, jeżeli dla dowolnych elementów x i y spełniony jest warunek: z faktu, że x ≠ y wynika, że ​​x R y lub y R x. Jeśli na zbiorze dana jest liniowa relacja porządku, to porządkuje ona dany zbiór liniowo.

5. Zbiór liczb rzeczywistych. Jego właściwości. Ekspansja zbioru liczb wymiernych wynikała z konieczności pomiaru długości odcinków, obszarów itp. Podstawą każdego pomiaru jest ta sama zasada: mierzony obiekt porównuje się ze wzorcem (obiektem lub zjawiskiem), którego wartość ma wartość liczbową równą 1, ale segment jednostkowy nie zawsze jest osadzony w mierzonym przedmiocie. Dlatego przy pomiarze przyjmuje się dwa założenia, które w matematyce określa się jako aksjomaty: 1) Pojedynczy standard można podzielić na dowolną liczbę równych udziałów lub części. 2) Wybrany standard może zostać użyty do pomiaru dowolnego obiektu o dowolnej wielkości. Dla segmentów Archimedes sformułował następujące aksjomaty: Niezależnie od tego, jak mały jest odcinek AB i jak duży jest segment CD, istnieje liczba naturalna N taka, że ​​N*AB>CD, jeśli zmierzony odcinek CD zawiera równą liczbę odcinków AB, wówczas długość odcinka CD wyraża się liczbą naturalną. Jeżeli w mierzonym odcinku CD odcinek AB zostanie umieszczony nierówną liczbę razy, wówczas AB dzieli się na 10 identycznych odcinków, zwanych dziesiątkami wzorca. W razie potrzeby dziesiątą część można podzielić na 10 równych części itp. Jeśli równa liczba 10, 100 itd. mieści się w segmencie CD. ułamki odcinków AB, wówczas długość odcinka CD wyraża się liczbą wymierną. Jednak długość odcinka nie zawsze można wyrazić jako liczbę naturalną lub wymierną. Istnieją segmenty niewspółmierne, tj. segmenty, których długość nie jest wyrażona liczbą wymierną. (twierdzenia patrz pytanie 32)

Liczby, które można przedstawić w postaci nieskończonych ułamków dziesiętnych nieokresowych, nazywane są niewymiernymi. Suma zbioru liczb wymiernych i zbioru liczb niewymiernych to zbiór liczb rzeczywistych ().

Własności zbioru liczb rzeczywistych. 1). Zbiór punktów na osi liczbowej jest równy zbiorowi liczb rzeczywistych.

0 M 1 Weźmy dowolny punkt M na odcinku od 0 do 1,

D narysuj półkole ze środkiem w punkcie

Środek tego odcinka i promień

K O S równy połowie. Narysujmy prostopadłą z M, aż przetnie się z półokręgiem. Otrzymujemy D. Ten punkt jest wyjątkowy, ponieważ półkole i prosta przecinają się tylko w jednym punkcie. Ze środka tego odcinka poprowadź linię prostą przez D, aż przetnie się ona z osią liczb. Otrzymujemy K, które wyznacza się w sposób unikalny, gdyż proste przecinają się tylko w jednym punkcie. Wybierając inny, dowolny punkt na danym odcinku i powtarzając cały proces, otrzymujemy, że dowolnemu punktowi na odcinku od 0 do 1 odpowiada pojedynczy punkt na osi liczbowej. Rozumując w odwrotnej kolejności, możemy wykazać, że dowolnemu punktowi na osi liczbowej odpowiada również pojedynczy punkt od 0 do 1. Jeśli dowolny punkt E należy do osi liczbowej, to przez punkty M i E można poprowadzić tylko jedną prostą który przecina półkole. Z półokręgu można obniżyć prostopadłą do danego odcinka. W ten sposób ustalane jest wzajemnie identyczne odwzorowanie pomiędzy punktami odcinka od 0 do 1 a punktami osi liczbowej, tj. są równie potężni.

2) zbiór liczb rzeczywistych jest nieprzeliczalny, tj. nie jest równy zbiorowi liczb naturalnych.

3). Zbiór liczb rzeczywistych jest zbiorem ciągłym. Ciągłość zbioru liczb rzeczywistych polega na tym, że pomiędzy dowolnymi dwiema liczbami rzeczywistymi znajduje się nieskończony zbiór tylko liczb rzeczywistych

6. Podział zbioru na klasy. Przykłady klasyfikacji. Relacja równoważności, jej własności. Związek relacji równoważności z podziałem zbioru na klasy. Spójrzmy na przykład. Niech dany będzie zbiór M (zbiór wielokątów wypukłych), tworzymy wszystkie podzbiory tego zbioru: A 1 – zbiór trójkątów; A2 – zbiór czworokątów; A3 – zestaw pięciokątów; Ak jest zbiorem k-gonów. Zbiór M uważa się za podzielony na klasy, jeżeli spełnione są następujące warunki:

1. każdy podzbiór A nie jest pusty
2. przecięcie dowolnych dwóch podzbiorów jest zbiorem pustym
3. suma wszystkich podzbiorów to dany zbiór M

Nazywa się dzielenie zbioru na klasy Klasyfikacja.

Postawa na zbiorze X nazywa się równowartość , jeśli jest zwrotny, symetryczny i przechodni. Związek nazywa się odblaskowy, jeśli dowolny element ze zbioru X jest w relacji sam ze sobą a ∈ X i Ra (R jest w relacji). Związek nazywa się symetryczny, jeśli dla dowolnych dwóch elementów zbioru X (aib) z faktu, że a jest w relacji z b, wynika, że ​​b jest w relacji z a (a, b ∈ X i R b → w Ra). Związek nazywa się przechodni, jeśli dla dowolnych elementów a, b, c z faktu, że a R w i w R c → że a R c, a, b, c ∈ X. Na wykresie relacji równoważności znajdują się pętle, wzajemnie odwrotne strzałki i trójkąt strzałki. Relacja równoważności i tylko ona związana jest z podziałem zbioru na klasy. Stwierdzenie to można sformułować jako twierdzenia: Jeżeli na zbiorze X jest określona relacja równoważności, to relacja ta dzieli zbiór X na klasy i odwrotnie, jeśli zbiór X dzieli się na klasy, to relacja równoważności jest spełniona na danym zbiorze. Na przykład. Niech będzie postawa - mieszkać w tym samym domu. Pokażmy, że zbiór mieszkańców domu zostanie podzielony na klasy. A każda klasa to osobne mieszkanie. Dla tego podziału zostaną spełnione wszystkie warunki konieczne do podzielenia zbioru na klasy: a) każda klasa nie jest pusta, ponieważ w każdym mieszkaniu zarejestrowana jest co najmniej 1 osoba, b) zajęcia nie nakładają się na siebie (1 osoba nie jest zameldowana w dwóch różnych mieszkaniach), c) połączenie wszystkich klas, tj. mieszkańców każdego mieszkania i stanowi zbiór mieszkańców domu.

18 . Teoretyczne podejście do konstruowania teorii nieujemnych liczb całkowitych. Relacje równości, więcej (mniej). Dwa zbiory A i B nazywane są równoważnymi lub równie potężnymi, jeśli można między nimi ustalić zgodność jeden do jednego, to znaczy, jeśli każdy element zbioru A jest powiązany z pojedynczym elementem zbioru B i odwrotnie. Potęga lub liczba kardynalna to właściwość właściwa każdemu zbiorowi B, która jest równoważna zbiorowi A i nie jest nieodłączna żadnemu innemu zbiorowi, który nie jest równy zbiorowi A. A~B n (A) = a to potęga. Relacja równej mocy jest relacją równoważności, tj. spełnione są dla niego właściwości zwrotności, symetrii i przechodniości. Relacja równoważności dzieli zbiór wszystkich zbiorów na klasy równoważności. Aby zdefiniować pojęcie liczby naturalnej i zera, rozważmy podział wszystkich zbiorów skończonych.

Niech M będzie zbiorem wszystkich zbiorów skończonych. M = K 0 Ka Kv, gdzie Ko jest klasą zbiorów pustych, Ka jest zbiorem zawierającym równe zbiory a 1, a 2, a 3 itd., Kv jest zbiorem. Zawierające zbiory o równej liczności w 1, w 2, w 3 itd. Zbiór M może zawierać także inne podzbiory K o różnym charakterze, na które składają się zbiory o jednakowej mocy. Cechą wspólną wszystkich klas równoważności K jest to, że składają się z tej samej liczby elementów, nie ma innych wspólnych właściwości. Z punktu widzenia teorii mnogości nieujemna liczba całkowita jest ogólną własnością klasy zbiorów skończonych o równej mocy. Liczba naturalna jest ogólną własnością klasy niepustych zbiorów skończonych o równej liczności. Każdej klasie przypisana jest liczba kardynalna (liczność). Klasie zbiór pusty przypisany jest numer współrzędnej 0. Klasie składającej się ze zbiorów mających 1 element przypisany jest numer 1. Klasie składającej się ze zbiorów 2 elementów przypisuje się liczbę 2. (n(K 0)=0, n(K 1)=1, n(K 2)=2, n(Ka)=a).

Relacja równości. Mówi się, że nieujemne liczby całkowite a i b są równe, jeśli zbiory A i B, których liczbę wyrażają, są równe (A; n(A)=a, n(B)=b, A ~ B n( A)=n(B) a=c).

Twierdzenie: relacja równości w zbiorze nieujemnych liczb całkowitych jest relacją równoważności. Dowód. Udowodnijmy, że relacja równości ma właściwości symetrii, przechodniości i zwrotności.

Ponieważ właściwości zwrotności, symetrii i przechodniości są spełnione, wówczas relacja równości jest relacją równoważności.

Stosunek jest mniejszy. Nieujemna liczba całkowita a<в, если множество А равномощно собственному подмножеству В 1 множества В. а<в; n(А)=а; n(В)=в; В 1 В n(В 1)

Twierdzenie: Relacja mniejsza niż w zbiorze liczb całkowitych nieujemnych jest relacją ściśle uporządkowaną. Dowód: Udowodnijmy, że relacja mniej ma właściwości antysymetrii i przechodniości.

do 2 do 1 do 2 ~B 1 do 2 ~a n(A)=n(C 2) n(C 2)

A B C 1 C

B 1 C 2

19 . Dodawanie i odejmowanie w ilościowej teorii liczb całkowitych nieujemnych. Ich właściwości. Kwota dwie nieujemne liczby całkowite a i b nazywane są nieujemną liczbą całkowitą c, która jest licznością sumy dwóch rozłącznych zbiorów A i B, których liczebności są odpowiednio równe a i b. a+b=c, n(C)=n(AUB), n(AUB)=n(A)+n(B).

Właściwości dodatku. 1. Dodawanie w zbiorze nieujemnych liczb całkowitych zawsze istnieje i jest definiowane w unikalny sposób. Udowodnimy, że suma zawsze istnieje. Rozważmy A i B w taki sposób, że ich przecięcie jest zbiorem pustym, a liczba elementów A wynosi a, a liczność B wynosi b. znajdźmy sumę A i B. Ponieważ suma dwóch zbiorów rozłącznych zawsze istnieje, oznacza to, że suma również istnieje, a z definicji sumy wynika, że ​​zawsze istnieje dodawanie.

Udowodnijmy, że suma jest wyznaczana w sposób jednoznaczny. Istnieją C 1 i C 2 – liczby całkowite nieujemne. C 1 = a + b i C 2 = a + b. Suma liczb a i b nie zależy od tego, które zbiory A i B wybraliśmy z klasy zbiorów o jednakowej potędze, a zatem suma A i B wziętych z klasy zbiorów o jednakowej potędze nie zależy od wyboru zbiory A i B, ponieważ moce w każdej klasie są takie same, wówczas C 1 = C 2.

2. Dodawanie przemienne. Dla dowolnych nieujemnych liczb całkowitych a i b zachodzi własność a+b=b+a. Z teorii mnogości wiemy, że dla АУВ = ВУА. Jeśli zbiory są równe, ich wartości liczbowe są równe. n(АУВ)=n(ВУА). Z teorii mnogości wiemy, że moc sumy jest równa sumie potęg. N(A)+n(B)=n(B)+n(A).

3. Własność łączności. Dla dowolnych liczb a, b, c zachodzi następująca własność: a+(b+c)=(a+b)+c. Z teorii mnogości wiadomo, że do łączenia zbiorów spełniona jest własność asocjatywności: АU(ВУС)=(АУВ)UC, jeśli zbiory są równe, to ich wartości liczbowe są równe, n(АU(ВУС))=n( (АУВ)UC). Z teorii mnogości wiadomo, że potęga sumy jest równa sumie potęg tych zbiorów, n(A)+n(BUC)=n(AUB)+n(C) n(A)+(n (B)+n(C))= (n(A)+n(B))+n(C) a+(b+c)=(a+b)+c.

Przez różnicę nieujemne liczby całkowite aib nazywamy nieujemną liczbą całkowitą c, która jest potęgą uzupełnienia zbioru B do zbioru A tak, że B należy do A, n(A)=a, n(B) =b.

Właściwości różnicowe. 1. Aby istniała różnica nieujemnych liczb całkowitych, konieczne i wystarczające jest, aby a było większe lub równe b.

Udowodnijmy: 1) warunek wystarczający istnienia różnicy. Biorąc pod uwagę: a - b = c, udowodnij: a c. Z definicji różnicy wynika, że ​​istnieje dopełnienie zbioru B do zbioru A i to dopełnienie ma moc, którą można wyprowadzić z równości znanej z teorii mnogości.

n() = n(A)-n(B). Z faktu, że B jest podzbiorem A wynika, że ​​liczba elementów w B jest mniejsza niż liczba elementów A. n (B) V; B wchodzi do A; n(B)

2). Warunek konieczny. Biorąc pod uwagę c. udowodnić istnienie różnicy (a-c). Jeśli a>b, zgodnie z definicją relacji „mniej niż”, istnieje zbiór A 1 taki, że A 1 jest zawarty w A i A 1 ~B. Zróbmy różnicę między A i A 1. Ta różnica zawsze istnieje (A - A 1 = C), dlatego istnieje C, czyli ta różnica. Z tych warunków wynika, że ​​C jest dopełnieniem A 1 do A. C = 1A Potęga C jest potęgą dopełnienia A 1 do A. n (C)=n( 1A)=n(A)- n(A 1), ponieważ A 1 ~ B, wówczas n(A 1)=n(B), zatem n(C)=n(A)-n(B), zatem c=a-b.

2. Różnicę nieujemnych liczb całkowitych stwierdza się w unikalny sposób, ponieważ różnicą jest potęga uzupełnienia podzbiorów do zbioru, a uzupełnienie jest określane w unikalny sposób, wówczas różnica nieujemnych liczb całkowitych wynosi określone w wyjątkowy sposób.

3. W przypadku odejmowania nie są spełnione właściwości przemienności i skojarzenia.

4. Odejmowanie kwoty od liczby. a-(b+c)=(a-c)-c. Z teorii mnogości wiadomo, że A\(BUC)=(A\B)\C i B Ì A; S – A; BUSCA.

n (A\(BUC))=n((A\B)\C)

n(A)-n(BUC)=n(A\B)-n(C)

n(A)-(n(B)+n(C))=(n(A)-n(B))-n(C)

a-(b+c)=(a-c)-c.

5. Odejmowanie liczby od różnicy (a-c)-c=(a-c)-c. Dowód opiera się na własności różnicy zbiorów (A\B)\C=(A\C)\B.

6. Odejmowanie liczby od sumy (a+b)-c=(a-c)+c. Dowód opiera się na własności zbiorów (АУВ)\С=(А\С) УВ.

Wyłącz blokadę reklam!
bardzo potrzebne