plik


ÿþPodstawy matematyki dla informatyków Janusz J. Szuster Wstp do teorii mnogo[ci Literatura [1] Zofia Adamowicz, PaweB Zbierski, Logika matematyczna, PWN W-wa 1991, [2] Wojciech Guzicki, Piotr Zakrzewski, WykBady ze wstpu do matematyki  wprowadzenie do teorii mnogo[ci, Wydawnictwo Naukowe PWN W-wa 2005 [3] Wojciech Guzicki, Piotr Zakrzewski, Wstp do matematyki  zbiór zadaD, Wydawnictwo Naukowe PWN W-wa 2005 [4] Kazimierz Kuratowski, Andrzej Mostowski, Teoria mnogo[ci, Monografie Matematyczne t. XXVII, W-wa 1978, [5] Igor A. Aawrow, Aarisa L. Maksimowa, Zadania z teorii mnogo[ci, logiki matematycznej i teorii algorytmów, PWN W-wa 2004, [6] Janusz Onyszkiewicz, Wiktor Marek, Elementy logiki i teorii mnogo[ci, PWN W-wa 2004. [7] Helena Rasiowa, Wstp do matematyki wspóBczesnej, PWN W-wa 2003, [8] Jerzy Tiuryn, Wstp do teorii mnogo[ci i logiki, WrocBaw 2000, [9] Agnieszka Wojciechowska, Elementy logiki i teorii mnogo[ci, PWN W-wa 1979. 1. ZARYS HISTORII TEORII MNOGOZCI 2 1. Zarys historii teorii mnogo[ci Ewolucja my[li matematycznej przebiega w sposób nieprzerwany od co najmniej 5 000 lat. WiodBa ona od, jak by[my to dzi[ powiedzieli, aplikacji arytmetycznych poprzez rozwój geome- trii i algebry oraz próby formalizacji idei matematycznych z wykorzystaniem dorobku filozofów zwanego od czasów Arystotelesa logik. Wraz ze wzrostem poziomu komplikacji analizowanych obiektów matematycy potrzebowali coraz to nowych narzdzi pozwalajcych na jednoznaczny opis zarówno nowouzyskiwanych wyników jak i tych, które byBy znane stosunkowo dawno, ale jzyk ich opisu byB maBo prezyzyjny. Takie pojcia jak zbiór i zawieranie byBy w przeszBo[ci ro- zumiane intuicyjnie, midzy innymi z uwagi na geometryczne odniesienia, i nie budziBy sporów interpretacje tych poj. KBopoty zaczBy si pojawia w momencie, gdy obiektem rozwa|aD byBy pojcie równoliczno[ci zbiorów, czy te| pojawienia si w kontek[cie zbioru pojcia licz- by czy wielko[ci. Jednym z takich problemów byB problem nieograniczonej  podzielno[ci czy  rozcigliwo[ci badany ju| przez pitagorejczyków. Ten problem prowadziB czsto do kBopotów natury filozoficznej i dotykaB on zarówno eleatów jak Bolzana i Cantora. Po raz pierwszy z zagadniem równoliczno[ci lub bardziej precyzyjnie uogólnionej równolicz- no[ci pojawia si w pracach Galileusza, który wykazuje wzajemnie jednoznaczn odpowiednio[ midzy liczbami naturalnymi i ich drugimi potgami. Dzi[ wydaje si co najmniej niezrozumiaBe, jak przez caBe wieki mogBy by utrzymywane i kultywowane pogldy matematyczne, o których dzi[ wiemy, |e byBy nieprecyzyjne lub caB- kowicie bBdne. WytBumaczenie tego zjawiska wydaje si jednak by do[ nieskomplikowane. Mianowicie, nie istnieBo wewntrzne zapotrzebowanie matematyki na precyzje w tym wzgl- dzie. Rozwój analizy matematycznej jaki dokonaB si w XIX wieku za spraw wielu ówczesnych matematyków w[ród których nale|y wymieni Cauchy ego, Weierstrass a, Bolzano, Riemanna, Poincarégo, Mittag-Leffera, Cantora, Dedekinda, Bernsteina i Peano. Ta lista nie jest oczywi[cie kompletna, ale wymienione nazwiska wskazuj na rang dostrze|onego problemu. Bez wtpienia za ojca teorii mnogo[ci w jej dzisiejszym rozumieniu nale|y uzna matema- tyka niemieckego Georga Ferdynanda Ludwiga Cantora (1845-1918). Wychodzc od analizy prac Riemanna doszedB problemów zwizanych z przeliczalno[ci oraz konstruowaniem liczb rzeczywistych. W latach 1878-1884 Cantor ogBosiB cykl sze[ciu rozpaw po[wiconych proble- mom równoliczno[ci, teorii zbiorów caBkowicie uporzdkowanych, wBasno[ciom topologicznym R i Rn, a tak|e problemom miary. Wprowadzenie w 1882 roku przez Cantora pojcia zbioru dobrze uporzdkowanego daje podstaw do badania liczb kardynalnych oraz pozwala sformu- Bowa  hipotez continuum . Opór matematyków wobec wyników Cantora byB do[ jednolity i twardy. Jedynie Carl Weierstrass byB nastawiony do jego wyników |yczliwie. Opór ten powodo- wany byB rewolucyjnym charakterem tych wyników, burzyBy one bowiem ponad dwutysiczn tradycj matematyczn. Po wynikach Cantora przyszBa kolej na uzupeBniejce je rezultaty Bern- steina i Zermelo. Prawdziwym sojusznikiem Cantora w pracach nad teori mnogo[ci byB Julius Wilhelm Richard Dedekind (1831-1916). Niektóre spo[ród wyników uzyskanych przez Canto- ra i jego kontunuatorów byBy odkryte przez Dedekinda jednak nie zostaBy one opublikowane. Co wicej wiele wyników tego ostatniego pokazaBo jak w peBni nale|y stosowa teorie aksjo- matyczne. Mianowicie, Dedekind rozwa|ajc ogólne przypadki zbiorów, a nie tylko zbiorów LITERATURA 3 caBkowicie uporzdkowanych, dochodzi do zbiorów kratowych i gruntownie analizuje ich wBa- sno[ci. Chocia| w odró|nieniu od wyników Cantora, rezultaty uzyskane przez Dedekinda nie znalazBy natychmiastowego zastosowania, to okazaBy si one niezwykle wa|nie ju| w nieodlegBej przyszBo[ci. Wyniki prac Cantora pozwoliBy na formalizacj matematyki, a jednocze[nie daBy pocztek upowszechnianiu si metod aksjomatycznych. Jednak poza tym osigniciem daBy one pocztek kryzysowi podstaw matematyki. PojawiBy si oto paradoksy teorii mnogo[ci. Wikszo[ z nich byBa blizniaczo podobna, pod wzgldem natury, do tych z jakimi zetknito si wcze[niej przy odkryciu geometrii nieeuklidesowych. Skonstatowa to mo|na sformuBowaniem zaczerpnitym z Elementów historii matematyki Nicolasa Bourbaki, |e pró|ne s próby zbudowania jakiejkolwiek teorii matematycznej za pomoc odwoBywania si (jawnego lub nie) do  intuicji . SzBo zatem o to, by dla teorii mnogo[ci stworzy podstaw aksjomatyczn analogiczn do ukBadu aksjo- matów geometrii elementarnej, bez dociekania co nazywamy zbiorem, w sensie natury obiektu, jak równie| nie jest definiowane przynale|enie do zbioru, a jedynie wyraznie formuBowane s warunki charakteryzujce przynale|no[ do ustalonego zbioru. Pierwszym, który zbudowaB ta- k aksjomatyzacj byB Zermelo i staBo si to w 1908 roku. Próba ta uzupeBniona przez wynki Skolema i Fraenkla pozwoliBa na konstrukcj aksjomatyki teorii mnogo[ci, jednak cen jak nale|aBo za to zapBaci, byBa komieczno[ wprowadzenia tak|e reguB logiki. Literatura [1] N. Bourbaki  Elementy historii matematyki, PWN Warszawa 1980, [2] A.P. Juszkiewicz  Historia matematyki (od czasów najdawniejszych do pocztku czasów nowo|ytnich), Tom 1-3, PWN Warszawa 1975, [3] K.Kuratowski, A. Mostowski  Teoria mnogo[ci, Monografie Matematyczne XXVII, War- szawa 1978, [4] R. Murawski  Filozofia matematyki  zarys dziejów, Wydawnictwo Naukowe PWN 1995 LITERATURA 4 1.1. Wa|ne osoby i daty w rozwoju teorii mnogo[ci Julius Wilhelm Richard DEDEKIND ("1831 Braunschweig w Niemczech  1916 Braun- schweig w Niemczech), nowoczesna teoria liczb algebraicznych, prakroje Dedekinda. Paul David Gustav DU BOIS-REYMOND ("1831 Berlin  1889 Freiburg w Niemczech), badaB szeregi liczbowe, a przy tym wniósB wiele do teorii zbiorów. Georg Ferdynand Ludwig CANTOR ("1845 St Petersburg w Rosji  1918 Halle w Niem- czech), twórca teorii mnogo[ci, która wpBynBa na rozwój caBej matematyki, a w szczególno[- ci na podstawy wspóBczesnej analizy matematycznej, konstrukcja Cantora liczb rzeczywi- stych. Magnus Gösta MITTAG-LEFFLER ("1846 Sztokholm  1927 Sztokholm), twórca skan- dynawskiej szkoBy matematycznej, przyczyniB si do uporzdkowania teorii mnogo[ci. Ernst Friedrich Ferdinand ZERMELO ("1871 Berlin  1953 Freiburg w Niemczech), badaB podstawy matematyki, autor fundamentalnych prac z teorii mnogo[ci w szczególno[ci aksjomatyki teorii mnogo[ci. ´ Julius Henri POINCARE("1854 Nancy we Francji  1912 Pary|), zajmowaB si wieloma dyscyplinami matematycznymi, a tak|e fizyk i filozofi. Jego prace dotyczce podstaw matematyki stanowiBy istotny wkBad w rozwój teorii mnogo[ci. Adolf Abraham Halevi FRAENKEL ("1891 Monachium  1965 Jerozolima), wspólnie z Fraenklem i Cantorem wspóBtworzyB wspóBczesn teori mnogo[ci. Friedriech Ludwig Gottlob FREGE ("1848 Wismar w Mecklenburgii-Schwerinie w Niem- czech  1925 Bad Kleinen w Niemczech), pierwsze ujcie rachunku zdaD jako sformalizo- wanej teorii aksjomatycznej. Giuseppe PEANO ("1858 Cuneo na Sardynii  1932 Turyn we WBoszech), atytmetyka jako teoria aksjomatyczna sformalizowana (Arytmetyka Peano). David HILBERT ("1862 Królewiec w Prusach Wschodnich  1943 Getynga w Niem- czech), jego badania nad podstawami geometrii (1898-1902) zapocztkowaBy nowoczesn, aksjomatyczn budow teorii matematycznych (23 problemy Hilberta, teoria spektralna operatorów liniowych  podstawowy aparat mechaniki kwantowej). Bertrand Arthur William RUSSEL ("1872 Ravenscroft w Walii  1970 Penrhynden- draeth w Walii), w 1902 r analizujc zaproponowany przez Fregego system logicznych podstaw matematyki zauwa|yB w nim sprzeczno[ polegajc na tzw. paradoksie klas (antynomia Russella), w 1903 ogBosiB  Principles of Mathematics , w których staraB si sprowadzi teori mnogo[ci, a nawet caB matematyk do logiki, w 1908 r stworzyB za- sady tzw. teorii typów logicznych. W latach 1910-1913 B.A.W. Russell wraz z Alfredem North Whiteheadem (" 1861 Ramsgate hrabstwo Kent w Anglii  1847 Cambridge w Massachusetts USA) napisali i opublikowali  Principia Mathematica (t. I III), wktórej LITERATURA 5 ide przewodni byBo poszukiwanie podstaw matematyki w zasadach logicznych, rezul- tatem za[ przedstawienie matematyki w postaci systemu sformalizowanego oraz nadanie wspóBczesnego ksztaBtu logice matematycznej. John (Janos) von NEUMANN ("1903 Budapeszt  1957 Waszyngton), matematyk, che- mik, fizyk, informatyk wspóBtwórca broni atomowej. Jego badania z teorii mnogo[ci przy- czyniBy si do wykorzystania uzyskanych przez niego wyników w zastosowaniach prak- tycznych oraz do uszlachetnienia wielu wyników. Henri Leon LEBESGUE ("1875 Beavais we Francji  1941 Pary|), twórca ogólnej teorii miary i caBki. W trakcie badaD nad tymi teoriami uzyskaB wa|ne dla teorii mnogo[ci wyniki. WacBaw SIERPICSKI ("1882 Warszawa  1969 Warszawa), badaB teori liczb, topologi i teori mnogo[ci. W 1912 roku napisaB fundamentaln ksi|k dotyczc tej ostatniej dyscypliny, w której zamie[ciB równie| wiele wBasnych wyników. Kurt GÖDEL ("1906 Brünn w Austrowgrzech obecnie Brno w Czechach  1978 Prin- ceton w stanie Nowy Jork w USA), niepeBno[ teorii aksjomatycznych sformalizowanych zawierajcych arytmetyk. Twierdzenie o niesprzeczno[ci hipotezy continuum zaksjoma- tyk teorii mnogo[ci. Kazimierz KURATOWSKI ("1896 Warszawa  1980 Warszawa), jeden z twórców Lwow- skiej SzkoBy Matematycznej, badacz teorii mnogo[ci, topologii, teorii grafów, analizy mate- matycznej i podstaw matematyki. Jego wyniki badaD z podstaw matematyki przyczyniBy si do uporzdkowania tej dyscypliny (lemat Kuratowskiego-Zorna). StanisBaw Marcin ULAM ("1909 Lwów  1984 Santa Fe w USA), twórca metody Monte Carlo, wszechstronny matematyk o zdolno[ciach przenoszenia wyników matematycznych do innych nauk. Jego prace z teorii procesów stochastycznych, równaD ró|niczkowych czstkowych, analizy funkcjonalnej oraz ich zastosowania w fizyce przyczyniBy si do ba- daD problemów teorii mnogo[ci. Niektóre z jego wyników prac pozostaj utajnione po dzi[ dzieD, ze wzgldu na ich wykorzystanie przy konstrukcji bomby atomowej i wodorowej. Bezspornie StanisBaw Ulam jest uwa|any za twórc koncepcji bomby wodorowej, byB on tak|e staBym konsultantem w trakcie jej budowy. Paul Joseph COHEN ("1934 Long Branch, New Jersey), niezale|no[ hipotezy continuum (1963), medal Fieldsa w 1966. 2. WPROWADZENIE 6 2. Wprowadzenie Warto doda, |e tak jak logika matematyczna korzysta z poj teorii mnogo[ci, tak teoria mnogo[ci wykorzystuje wiele poj logiki. W tej cz[ci wykBadu nie bdziemy formalizowa po- j logiki matematycznej, bdzie to przedmiotem drugiej cz[ci. Jednak z uwagi na u|yteczno[ podstawowych faktów logicznych przedstawimy je w znacznym uproszczeniu. Doda nale|y, |e posBu|ymy si logik znan z nauki w szkole [redniej. Jest to w pewnym sensie klasyczne po- dej[cie do tej dyscypliny, odmienne od podej[cia które zaprezentowane w cz[ci po[wiconej logice. Ten logiczny dualizm jest jednak konieczny ze wzgldu na gradacj trudno[ci. Niech Z oznacza zbiór wszystkich zdaD orzekajcych odnoszcych si do matematyki. Niech ponadto 0 bdzie symbolem faBszu, natomiast 1 symbolem prawdy. Funkcj w : Z ’!{0, 1} nazywamy warto[ciowaniem. Przyjmijmy umow, |e elementy zbioru Z bdziemy oznacza maBymi literami alfabetu: p, q, r, s, p1, q1, r1, s1, p2, q2, r2, s2, . . . , których mo|e by nawet nieskoDczenie wiele. Litery oznacza bd obiekty zwane zmiennymi zdaniowymi. Narzdziem zaczerpnitym z jzyka potocznego s spójniki, zwane w logice równie| funkto- rami zdaniotwórczymi. Pozwalaj one budowa ze zdaD prostych zdania zBo|one. I tak, zamiast pisa  nie u|yjemy symbolu <" (symbolizyje on zdeformowan liter N, od nego, co oznacza przecz), zamiast pisa  je[li ..., to zapiszemy ’!, symbol ”! bdzie zastpowaB zwrot  wtedy i tylko wtedy (lub krótko  wtt ), symbol '" oznacza bdzie  i , za[ symbol (" bdzie zastpowaB spójnik  lub . Oprócz spójników (funktorów zdaniotwórczych) posBugiwa si bdziemy nawiasami: otwie- rajcym  ( oraz zamykajcym  ) . W oparciu o nawiasy, funktory zdaniotwórcze i zmienne zdaniowe tworzy bdziemy formuBy rachunku zdaD. Ka|da z takich formuB staje si zdaniem, gdy w miejsce zmiennych zdaniowych wstawimy zdania  oczywi[cie w miejsce ustalonej litery wstawiamy to samo zdanie. Nawiasy, wymienione jako element skBadowy formuB zdaniowych uBatwiaj, a niekiedy wrcz umo|liwiaj, odczytanie takiej formuBy  gdy w zbiorze funktorów nie zostaBa wprowadzona hierarchia  mocy wizania . W[ród wszystkich formuB rachunku zdaD szczególnie wa|n rol peBni formuBy prawdziwe bez wzgldu na warto[ logiczn wystpujcych w nich zmiennych zdaniowych. FormuBy takie nazywamy tautologiami i w zapisie dla podkre[lenia tego faktu poprzedzamy symbolem . Rola tautologii polega na tym, |e za ich pomoc mo|emy dokonywa operacji logicznych niezale|nie od tre[ci zdaD, które  logicznie przeksztaBcamy. Osobnym zagadnieniem jest sprawdzenie czy dana formuBa jest tautologi. Przedstawimy pochodzc od Ernsta Schrödera metod zerojedynkow, lub inaczej metod tablicow. Polega ona na rozpatrzeniu wszystkich ukBadów warto[ci logicznych zmiennych zdaniowych wystpu- jcych w danym wyra|eniu. Metoda ta nazywana jest niekiedy metod matrycow, ze wzgldu na posBugiwanie si w niej tabelkami matrycowymi, przedstawiajcymi w jaki sposób warto[ logiczna zdania zBo|onego utworzonego przy pomocy danego funktora, lub funktorów, jest wy- 2. WPROWADZENIE 7 znaczona przez warto[ci logiczne zdaD skBadowych. Pozostajc przy dotychczasowych umowach mo|emy zdefiniowa poszczególne funktory. Tym razem definicja ma posta nastpujcej tabeli: w(p) w(q) w(<" p) w(p '" q) w(p (" q) w(p ’! q) w(p ”! q) 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 Metod zerojedynkow zilustrujemy nastpujcym przykBadem. PrzykBad. Sprawdzimy czy formuBa w{(p ’! q) ’! [(q ’! r) ’! (p ’! r)]} jest tautologi (twierdzeniem) rachunku zdaD. w[(q ’! r) ’! w {(p ’! q) ’! w(p) w(q) w(r) w(p ’! q) w(q ’! r) w(p ’! r) ’! (p ’! r)] ’! [(q ’! r) ’! (p ’! r)]} 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 Tabela ta pokazuje w jaki sposób nale|y postpowa dla sprawdzenia czy rozpatrywana for- muBa jest tautologi. Poniewa| ostatnia kolumna skBada si z samych jedynek, to oznacza to, |e dla wszystkich mo|liwych ukBadów warto[ci logicznych zdaD skBadowych, zbudowanych zgodnie z formuB, otrzymujemy zdanie prawdziwe. Zatem badana przez nas formuBa jest tautologi. Przedstawimy teraz kilka wa|niejszych tautologii, których sprawdzenie pozostawiamy do samodzielnego wykonania przy u|yciu obu przedstawionych metod. posta prawa nazwa prawa w(p (" q) =w(q (" p) przemienno[ci alternatywy w(p '" q) =w(q '" p) przemienno[ci koniunkcji w(p (" (q (" r)) = w((p (" q) (" r) Bczno[ci alternatywy w(p '" (q '" r)) = w(p '" q) '" r) Bczno[ci koniunkcji w(p '" (q (" r)) = w((p '" q) (" (p '" r)) rozdzielno[ci koniunkcji wzgldem alternatywy w(p (" (q '" r)) = w((p (" q) '" (p (" r)) rozdzielno[ci alternatywy wzgldem koniunkcji w(p("<"p) =1 wyBczonego [rodka w(p Ð!Ò! p) =1 to|samo[ci w(<" (p'"<"p)) = 1 sprzeczno[ci w(p Ô!<" (<" p)) = 1 podwójnego przeczenia w([(p Ò! q) '" (q Ò! r)] Ò! (p Ò! r)) = 1 sylogizmu w((<" p Ò! p) Ò! p) =1 sprowadzania do niedorzeczno[ci w(p Ò! q) =w(<" q Ò!<" p) kontrapozycji w(p '" (p Ò! q) Ò! q) =1 reguBa odrywania Zajmiemy si teraz bardzo wa|nymi z praktycznego punktu widzenia tautologiami zwanymi 3. ZBIORY I OPERACJE NA ZBIORACH 8 prawami de Morgana. Pozwalaj one przeczy funktorom dwuczBonowym i s czsto wykorzy- stywane w dowodach nie wprost. posta prawa nazwa prawa w(<" (p '" q)) = w(<" p("<"q) prawo de Morgana dla koniunkcji w(<" (p (" q)) = w(<" p'"<"q) prawo de Morgana dla alternatywy Bezpo[redni konsekwencj praw de Morgana dla zdaD s nastpujce tautologie: w(<" (p ’! q)) = w(p'"<"q) w(<" (p ”! q)) = w([(p'"<"q) (" (q'"<"p)]) W matematyce spotykamy si czsto z pojciami warunku koniecznego i warunku wystar- czajcego. Pojcia te wi| si z funktorami implikacji i równowa|no[ci. Rozwa|my implikacj p ’! q, (”) w której zdanie p nazywamy poprzednikiem, a zdanie q nastpnikiem implikacji (”). Mówimy wtedy |e zdanie q jest warunkiem koniecznym dla p, natomiast p jest warunkiem dostatecznym dla q. Dla implikacji (”) implikacj p ! q, (lub inaczej q ’! p)(") nazywamy odwrotn. Je[li prawdziwe s implikacja prosta i implikacja odwrotna, to zdanie p ”! q nazywamy warunkiem koniecznym i wystarczajcym. 3. Zbiory i operacje na zbiorach W teorii mnogo[ci, podobnie jak w ka|dej dyscyplinie matematycznej, korzystamy z po- j przyjmowanych bez definicji tak zwanych poj pierwotnych. Zaliczamy do nich: pojcie zbioru i pojcie przynale|no[ci do zbioru lub inaczej bycie elementem zbioru. Zamiast mówi, |e a jest elementem zbioru A piszemy a " A, je[li natomiast a nie jest elementem zbioru A piszemy a " A. Je[li zajmujemy si ustalon teori matematyczn (w naszym przypadku teori mnogo[ci), to poza pojciami pierwotnymi przyjmuje si bez dowodu pewn liczb wBasno[ci (twierdzeD) odnoszcych si do obiektów teorii (w naszym przypadku zbiorów) zwanych ak- sjomatami i w oparciu o taki zestaw narzdzi formuBowane s dalsze wBasno[ci obiektów tej teorii. Istnienie takiej kolekcji poj pierwotnych i aksjomatów w przypadku ustalonej teorii pozwala nazwa j teori aksjomatyczn. Jak ju| mówili[my w cz[ci po[wiconej historii teorii mnogo[ci dyscyplina ta ma aksjomatyk zwan aksjomatyk Zermelo-Fraenkla. Rozpatrzmy dwa dowolne zbiory A i B. Mówimy, |e A jet równy B wtedy i tylko wtedy, gdy zbiory te maj identyczne elementy. Zwykle fakt ten wyra|amy piszc: A = B wtedy i tylko wtedy, gdy dla ka|dego a zachodzi : a " Awtt a " B. Zale|no[ t nazywamy zasad ekstensjonalno[ci. 3. ZBIORY I OPERACJE NA ZBIORACH 9 Mówimy, |e A jest podzbiorem B lub równowa|nie A jest zawarty w B wtedy i tylko wtedy, gdy ka|dy element zbiotu A jest elementem zbioru B. Piszemy wtedy A †" B. Niekiedy o zbiorze B mówimy, |e jest nadzbiorem zbioru A. Je[li A †" B i A = B, to A nazywamy podzbiorem wBa[ciwym zbioru B i piszemy wtedy A B. Zbiór nie zawierajcy |adnego elementu nazywamy zbiorem pustym i oznaczamy symbolem ". Na mocy zasady ekstensjonalno[ci istnieje dokBadnie jeden zbiór pusty. Zbiór bdziemy uwa|a za okre[lony je[li zostaBo podane kryterium pozwalajce rozstrzyg- n czy dany element nale|y, czy te| nie nale|y do rozpatrywanego zbioru. W zale|no[ci od sposobu okre[lenia i rodzaju zbioru oznaczamy go symbolem {a1, . . . , an}, gdy zbiór jest skoDczony i skBada si z n elementów, albo {x| w(x)}, gdzie w(x) jest warunkiem charakteryzujcym dany zbiór. Zamiast A )"{x| w(x)} bdziemy pisa {x " A| w(x)}. Je|eli A jest zbiorem, którego elementami s zbiory, to A nazywa bdziemy rodzin zbiorów. Je[li A i B s dowolnymi zbiorami, to przez sum tych zbiorów rozumiemy zbiór A *" B, którego elementami s te i tylko te elementy, które nale| do zbioru A lub do zbioru B. Natomiast iloczynem (przeciciem) zbiorów nazywamy zbiór A )" B, którego elementami s te i tylko te elementy, które s równocze[nie elementami zbioru A i zbioru B. Ró|nic zbioru A i B nazywamy zbiór A \ B, zBo|ony z tych i tylko tych elementów, które nale| do A i nie nale| do B. Dla zbioru A symbolem P(A) lub te| 2A oznacza bdziemy zbiór zBo|ony ze wszystkich podzbiorów tego zbioru i nazywa go bdziemy zbiorem potgowym zbioru A. Je|eli w odniesieniu do ustalonego zbioru A rozwa|ania ograniczymy tylko do jego podzbiorów (tj. elementów P(A)), to zbiór A nazywa bdziemy wtedy przestrzeni. DziaBania sumy i iloczynu dwóch zbiorów mo|na rozszerzy na wiksz liczb zbiorów, to znaczy na rodziny zbiorów. Dla rodziny zbiorów A jej sum oznaczamy przez A i mamy wtedy: x " A wtt, gdy istnieje A"A, |e x " A. Podobnie definiujemy iloczyn rodziny zbiorów A. Mamy mianowicie: x " A wtt, dla ka|dego A"A, |e x " A. Rozpatrzmy teraz sytuacj, kiedy element x nie nale|y odpowiednio do sumy zbiorów, ilo- czynu zbiorów oraz ró|nicy zbiorów. A zatem, je[li x " A *" B, to zgodnie z definicj sumy zbiorów x " A i x " B. Z kolei je[li x " A )" B, to x " A lub x " B. Natomiast fakt, |e x " A \ B oznacza na mocy definicji, |e x " A lub x " B. Zatem symbolicznie mo|emy wyrazi te uwagi piszc: x " A *" B a" x " A '" x " B, x " A )" B a" x " A (" x " B, x " A \ B a" x " A (" x " B. Przez formuB rachunku zbiorów rozumiemy wyra|enie utworzone z symboli zbiorów, symboli operacji na zbiorach i nawiasów. Podobnie jak w przypadku formuB rachunku zdaD tautologiami nazywa bdziemy te spo[ród formuB rachunku zdaD, które s prawdziwe niezale|nie od doboru wystpujcych w nich zbiorów. 3. ZBIORY I OPERACJE NA ZBIORACH 10 (1) Prawa przemienno[ci. Je[li A i B s dowolnymi zbiorami to A *" B = B *" A, A )" B = B )" A. D o w ó d. Wyka|emy na wstpie prawdziwo[ przemienno[ci dla sumy. Przypu[my, |e x " B *" A. Na mocy definicji wiemy, |e x " A *" B Ð!Ò! x " A (" x " B. Z drugiej strony na mocy prawa przemienno[ci alternatywy: p (" q a" q (" p, mamy, |e x " A *" B Ð!Ò! x " A *" B Ð!Ò! x " A (" x " B Ð!Ò! x " A *" B Ð!Ò! x " B (" x " A Ð!Ò! x " B *" A. Dowód drugiego z praw przebiega podobnie. (2) Prawa Bczno[ci. Je[li A, B, C s dowolnymi zbiorami, to prawdziwe s równo[ci: A *" (B *" C) = (A *" B) *" C, A )" (B )" C) = (A )" B) )" C. Dla dowodu tych praw wystarczy wykorzysta odpowiednio prawo przemienno[ci dla alter- natywy i dla koniunkcji. (3) Prawa rozdzielno[ci. Je[li A, B, C s dowolnymi zbiorami, to prawdziwe s równo[ci: A )" (B *" C) = (A )" B) *" (B )" C), A *" (B )" C) = (A *" B) )" (A *" C). W tym przypadku równie| wystarczy wykorzysta prawa rachunku zdaD tj. prawa rozdziel- no[ci koniunkcji wzgldem alternatywy i alternatywy wzgldem koniunkcji. (4) Prawa tautologii. Je[li A jest dowolnym zbiorem, to prawdziwe s równo[ci: A *" A = A, A )" A = A. Aatwo udowodni prawa rachunku zdaD: p (" p a" p oraz p '" p a" p, to bezo[rednio z tych praw wynikaj prawa tautologii. (5) Prawa de Morgana. Je[li A, B, C s dowolnymi zbiorami, to prawdziwe s równo[ci: A \ (B )" C) = (A \ B) *" (A \ C), A \ (B *" C) = (A \ B) )" (A \ C). 4. ILOCZYN KARTEZJACSKI ZBIORÓW I RELACJE 11 Prawa de Morgana dla zbiorów s konsekwencj praw de Morgana dla zdaD. Bardziej znana posta praw de Morgana dotyczy dopeBnienia zbioru. Je[li X jest przestrze- ni za[ A " P(X ) i B " P(X ), to przez dopeBnienie zbioru A do przestrzeni X rozumiemy zbiór A = X \ A  podobnie B = X \ B. Przy takich oznaczeniach prawa de Morgana mo|emy zapisa w postaci (A *" B) =A )" B, (A )" B) =A *" B. 4. Iloczyn kartezjaDski zbiorów i relacje Niech A i B bd dowolnymi zbiorami i niech x " A oraz y " B. Wynika std, |e {x} ‚"A oraz {x, y} ‚"A *" B, a zatem {{x}, {x, y}} ‚" P(P(A *" B)). Przyjmujemy umow notacyjn, |e symbol x, y = {{x}, {x, y}} oznacza bdzie par uporzdkowan o poprzedniku x i nastpniku y. Zbiór { x, y | x " A '" y " B} nazywamy iloczyniem kartezjaDskim (produktem kartezjaDskim) zbiorów A i B oraz oznaczamy symbolem A × B. Niech x, y oraz z, t bd elementami zbioru A × B. Pamitamy, |e x, y = {{x}, {x, y}} oraz z, t = {{z}, {z, t}}. Skoro pary te s zbiorami to zbadajmy kiedy s one równe. Przy- pu[my, |e s równe i zastosujmy do nich definicj równo[ci zbiorów. Wynika std, |e {z} "{x, y} oraz {z, t} " x, y , a w konsekwencji, |e (1) {z} = {x} lub {z} = {x, y} (2) oraz (3) {z, t} = {x} lub {z, t} = {x, y} (4) Równo[ (1) ma miejsce jedynie wtedy, gdy x = z = y. W takim przypadku równo[ci (3) oraz (4) s równowa|ne i mamy z = t = x. Mamy wic, |e z = t = x. Prowadzi to do wniosku, |e x = y = z = t. Je[li rozpatrzymy przypadek (3), to równo[ okazuje si tak|e speBniona. Zajmijmy si teraz przypadkiem (4). Wtedy z = x oraz: bdz z = y, bdz t = y. Gdy z = y, to zachodzi równo[ (2) i otrzymujemy rozpatrywany ju| przypadek. Gdy natomiast t = y, to mamy x = z i y = t. Je[li rozpatrzymy teraz implikacj odwrotn do dowiedzionej tzn. je[li przypu[cimy, |e x = z i y = t, to teza jest oczywista, na mocy definicji równo[ci zbiorów. Otrzymali[my zatem nastpujce twierdzenie. 4. ILOCZYN KARTEZJACSKI ZBIORÓW I RELACJE 12 Twierdzenie. Warunkiem koniecznym i wystarczajcym na to, by pary x, y i z, t byBy równe jest, by zachodziBy równo[ci: x = z oraz y = t. Pojcie iloczynu kartezjaDskiego ma Batw interpretacj geometryczn. Je[li A i B s dowol- nie ustalonymi zbiorami, to elementy zbioru A × B nazywamy niekiedy punktami, za[ zbiory A i B osiami wspóBrzdnych. Je[li t = x, y jest punktem w A × B, to x nazywamy odcit, za[ y  rzdn punktu t. Ta intuicja wywodzi si z geometrii pBaszczyzny, gdzie zbiór punk- tów pBaszczyzny mo|e by uto|samiany z iloczynem × , przy czym oznacza zbiór liczb rzeczywistych. Korzystajc bezpo[rednio z definicji produktu kartezjaDskiego mo|emy wyprowadzi wiele praw wi|cych to dziaBanie z dziaBaniami teorii zbiorów. PrzykBad. Wyka|emy to|samo[: (A )" B) × C =(A × C) )" (B × C). Niech (x, y) " (A )" B) × C. Wtedy (x, y) " (A )" B) × C Ð!Ò! (x " A )" B) '" (y " C) Ð!Ò! (x " A '" x " B) '" y " C Ð!Ò! Ð!Ò! x " A '" (y " C '" x " B) Ð!Ò! (x " A '" y " C) '" (x " B '" y " C) Ð!Ò! Ð!Ò! (x, y) " A × C '" (x, y) " B × C Ð!Ò! (x, y) " (A × C) )" (B × C). PosBugujc si podobn technik dowodow mo|emy wykaza prawdziwo[ formuB, o których mówi nastpujce twierdzenie. Twierdzenie. Je[li A1, A2 oraz B s dowolnymi zbiorami, to (A1 *" A2) × B = A1 × B *" A2 × B, (A1 \ A2) × B = A1 × B \ A2 × B, B × (A1 *" A2) = B × A1 *" B × A2, B × (A1 \ A2) = B × A1 \ B *" B × A2, Dowolny podzbiór iloczynu kartezjaDskiego zbioru A × B, tzn. dowolny zbiór par uporzd- kowanych o poprzednikach z A i nastpnikach z B nazywamy relacj (dwuczBonow). Je[li podzbiór taki oznaczymy przez to zamiast pisa a, b " piszemy czesto a b i mówimy, |e  a jest w relacji z b . Dziedzin relacji (dziedzin lewostronn) nazywamy zbiór D zawarty w A i zBo|ony z poprzedników par nale|cych do relacji. Przeciwdziedzin (dziedzin prawostronn) relacji na- zywamy podzbiór R zbioru B zBo|ony z nastpników par nale|cych do relacji . Formalizujc te definicje mo|emy zapisa: D = {a " A| istnieje b " B, |e a b} oraz R = {b " B| istnieje a " A, |e a b} Przez pole relaji rozumiemy zbiór bdcy sum dziedziny i przeciwdziedziny (obu dziedzin) relacji. Niech ‚" A × B. Przez wykres relacji rozumiemy zbiór Gr( ) ={ a, b "A × B| a b}. 4. ILOCZYN KARTEZJACSKI ZBIORÓW I RELACJE 13 Tak wic wykres relacji i relacja speBniaj t sam definicj, zatem jest to ten sam obiekt. Relacja ‚" A × B wyznacza now relacj -1 ‚" B × A w nastpujcy sposób: def (b, a) " -1 Ð!Ò! (a, b) " . Relacj -1 nazywamy relacj odwrotn do relacji . W takim przypadku mamy, |e D -1 = R oraz R -1 = D . Niech ‚" A × B oraz µ ‚" B × C, bd takie, |e D ‚"Rµ. Relacj · ‚" A × C tak, |e x, z "· Ð!Ò! istnieje y " B, |e x y '" y z. nazywamy zBo|eniem (superpozycj) relacji oraz µ i oznaczamy piszc · = µ æ% . PrzykBad. Wezmy pod uwag relacje: ‚"{a, b, c}×{±, ³} i µ ‚"{±, ², ³}×{-2, 0, 1, 5, 8} gdzie = a, ± , b, ± , c, ³ } oraz µ = { ±, -2 , ±, 0 , ², 1 , ³, 5 , ´, 8 }. ZBo|eniem tych relacji jest relacja · ‚"{a, b, c}×{-2, 0, 1, 5, 8} taka, |e · = µ æ% = { a, -2 , a, 0 , b, -2 , b, 0 , c, 5 }. PrzykBad. Dana jest relacja Ç †"{0, 1, 2, 3, . . . , 9}×{0, 1, 2, 3, . . . , 9} zdefiniowana warun- kiem: aÇb Ô! 3a = b (" 3a +1=b. Wyznaczymy relacj Ç-1. Zanim przejdziemy do wyznaczenia relacji Ç-1 na wstpie wypiszmy precyzyjnie pary nale|ce do relacji Ç. Mamy: Ç = { 0, 0 , 0, 1 , 1, 3 , 1, 4 , 2, 6 , 2, 7 , 3, 9 }. Bezpo[rednio z definicji relacji odwrotnej dostajemy, |e Ç-1 = { 0, 0 , 1, 0 , 3, 1 , 4, 1 , 6, 2 , 7, 2 , 9, 3 }. Twierdzenie. Je[li †" A × B, µ †" B × C i ½ †" C × D, to: ½ æ% (µ æ% ) =(½ æ% µ) æ% ; (µ æ% )-1 = µ-1 æ% -1. Dowód. Wyka|emy prawdziwo[ (i). Przypu[my, |e x, z "A×D. Maj miejsce nastpujce fakty: x, z " æ% (µ æ% ½) wtt, gdy istniej t " C, |e x, t "µ æ% ½ oraz t, z " wtt, gdy istniej t " C i y " B, |e x, y " oraz y, t "µ oraz t, z "½ wtt, gdy istnieje y " B, |e a, b oraz y, z "½ æ% µ wtt, gdy x, t "(½ æ% µ) æ% . Rozpatrzmy teraz przypadek (ii). Niech t, x "C × A. Wtedy: 4. ILOCZYN KARTEZJACSKI ZBIORÓW I RELACJE 14 t, x "(µ æ% )-1 wtt, gdy x, t "µ æ% wtt, gdy istnieje y " B, |e x, y " oraz y, t "µ wtt, gdy istnieje y " B, |e y, x " -1 oraz t, y "µ-1 wtt, gdy t, x " -1 æ% µ-1 Przedstawimy teraz kilka przykBadów relacji. PrzykBad. Niech A = B = A bdzie zbiorem wszystkich ludzi |yjcych na Ziemi (w dowolnym okresie jej istnienia). Relacj  bycia przodkiem rozumiemy wtedy jako zbiór par a, b takich, |e osoba a jest przodkiem osoby b  bez wzgldu na czas dzielcy ich daty urodzenia. Niech X = Y = . Rozwa|my nierówno[ y >x + 1. Oznaczmy przez zbiór par x, y , które speBniaj nasz nierówno[. Std piszemy: x, y " Ð!Ò! y >x +1. Niech niepusty zbiór X bdzie przestrzeni, za[ P(X) zbiorem potgowym X. Zgodnie z wprowadzon poprzednio definicj inkluzji i definicj relacji wiemy, |e midzy zbiorami A " P(X) oraz B " P(X) zachodzi inkluzja tylko w pewnych przypadkach. Zatem inkluzja jest wBasno[ci par uporzdkowanych A, B zbiorów  elementów P(X). Jest wic inkluzja  ‚" podzbiorem produktu P(X) ×P(X), a wic relacj. Dotychczas rozwa|ali[my przypadki, gdy produkt kartezjaDski tworzony byB z dwóch zbiorów, a co za tym idzie relacje odnosiBy si do par elementów. W przypadku ogólnym relacjami dwuczBonowymi w produkcie X × Y , gdzie X i Y s dowolnymi zbiorami, nazywamy podzbiory tego produktu. Je[li jest podzbiorem produktu X × X, to miast mówi, |e jest relacj dwuczBonow w w produkcie X × X, czsto mówimy, |e jest relacj dwuczBonow w X. W zbiorze wszystkich relacji dwuczBonowych mo|emy wyró|ni pewne ich klasy. Przedstawimy je w nastpujcej definicji. Relacj dwuczBonow ‚" X × X nazywamy: def zwrotn Ð!Ò! dla ka|dego x " X jest x x; def przeciwzwrotn Ð!Ò! dla ka|dego x " X jest <" (x x); def symetryczn Ð!Ò! dla ka|dego x " X oraz y " X jest x y =Ò! y x; def przeciwsymetryczn Ð!Ò! dla ka|dego x " X oraz y " X jest: x y =Ò!<" (y x); def antysymetryczn Ð!Ò! dla ka|dego x " X oraz y " X jest: (x y) '" (y x) =Ò! (x = y); def przechodni Ð!Ò! dla ka|dych x " X i y " X i ka|dego z " X jest: (x y) '" (y z) Ò! (x z); 5. LICZBY NATURALNE 15 def spójn Ð!Ò! dla ka|dego x " X i ka|dego y " X jest: {(x = y) =Ò! [(x y) (" (y x)]}. PrzykBad. Poszczególne rodzaje relacji zilustrujemy przykBadami Relacja przystawania trójktów jest relacj zwrotn w zbiorze wszystkich trójktów. Relacja  wikszo[ci liczb w zbiorze liczb rzeczywistych jest przeciwzwrotna. PrzykBadem relacji symetrycznej jest relacja podzielno[ci w zbiorze liczb caBkowitych, bo ka|da liczba caBkowita jest podzielna przez sam siebie. PrzykBadem relacji przeciwsymetrycznej jest relacja wikszo[ci w zbiorze liczb rzeczywis- tych. Relacja  niewikszo[ci w zbiorze liczb rzeczywistych jest przykBadem relacji antysymet- rycznej. RównolegBo[ prostych na pBaszczyznie jest relacj przechodni. Niech X bdzie zbiorem liter alfabetu BaciDskigo. Przyjta umowa co do kolejno[ci liter w nim zawartych pozwala ustali relacj  hierarchi wyrazów (haseB) w skorowidzach nazw czy haseB. Tak okre[lona relacja jest relacj spójn. Podobnie relacja  niewikszo[ci ( ) jest relacj spójn. 2 W zbiorze par liczb rzeczywistych mo|emy okre[li relacj tak, |e def x1, y1 x2, y2 Ð!Ò! x1 x2 '" y1 y2. Relacja ta jest jak zauwa|amy; zwrotna, antysymetryczna i przechodnia. Nie jest nato- miast spójna. Jak si niebawem oka|e, relacja jest wygodnym przykBadem sBu|cym ilustrowaniu innych wBasno[ci szczegóBowych odnoszcych si do relacji binarnych. 5. Liczby naturalne Niech A bdzie rodzin zbiorów. Rodzin t nazywamy induktywn wtt, gdy: 1. " "A; 2. dla ka|dego X "A, zbiór X *"{X} "A. 5. LICZBY NATURALNE 16 Operacj nastpnika nazywamy operacj, która ka|demu zbiorowi X przyporzdkowuje zbiór X *"{X}. Nastpnik zbioru X oznaczamy przez X . W aksjomatyce Zermelo-Fraenkla istnienie zbiorów induktywnych gwarantuje aksjomat nieskoDczono[ci. Mówic krótko wyra|a on istnie- nie zbiorów nieskoDczonych. Twierdzenie. Istnieje najmniejszy zbiór induktywny tj. taki zbiór induktywny A , |e dla dowolnego zbioru induktywnego B jest A †"B. Dowód. Przypu[my, |e A jest zbiorem induktywnym . Rozpatrzmy rodzin zbiorów ” tak, |e ”={B †" A| B jest zbiorem induktywnym }. Wynika std, |e równie| zbiór A0 = ” jest zbiorem induktywnym. Pozostaje wykaza, |e A jest najmniejszym zbiorem induktywnym. Je[li B jest zbiorem induktywnym, to B)"A"”. Z kolei z definicji iloczynu zbiorów wynika, |e A0 †"B)"A. Z drugiej strony skoro B )" A †" B, to A0 †" B. Z tego, |e ostatnia inkluzja zachodzi dla wszystkich elementów rodziny ”, to A0 jest najmniejszym zbiorem induktywnym, w sensie relacji zawierania. Przez zbiór liczb naturalnych rozumiemy najmniejszy zbiór induktywny i oznaczamy go przez . Z definicji zbioru induktywnego (warunek 1.), zawiera on zbiór pusty ", który repre- zentuje liczb 0. Z drugiej strony (warunek 2.), zawiera nastpnik 0 (oznaczany symbolem 1), a tak|e nastpnik nastpnika 0 (oznaczany symbolem 2), itd. Twierdzenie. (Zasada indukcji) Je[li M‚" jest zbiorem liczb naturalnych speBniajcym warunki: 0 "M, dla dowolnie wybranej liczby n takiej, |e n "M, zachodzi n "M, to M zawiera wszystkie liczby naturalne tj. M = . Dowód. Teza twierdzenia jest konsekwencj bycia przez najmniejszym zbiorem induktyw- nym. MaBymi literami alfabetu bdziemy oznacza elementy zbioru . Twierdzenie. Dla dowolnych m " oraz n " : 1. je[li m " n, to m †" n; 2. n " n; 3. je[li m = n , to m = n; 4. je[li m †" n oraz m = n, to m " n; 5. LICZBY NATURALNE 17 5. zachodzi: m †" n lub n †" m; 6. zachodzi dokBadnie jedna z mo|liwo[ci: m " n, m = n, n " m. Dowód. Dowód poprowadzimy przez indukcj. Ad 1. Niech M = {n " | dla ka|dego m " n jest m †" n}. Chcemy wykaza induktywno[ zbioru M. Mamy: 0 " M. Przypu[my, |e n " M. Po to by wykaza, |e n " Mobierzmy dowolne m " n . Poniewa| n = n *"{n}, to mamy mo|liwe dwa przypadki. Je[li m " n, to z zaBo|enia indukcyjnego mamy m †" n, a wic m †" n . Je|eli za[ m = n, to m †" n . Wynika std, |e w ka|dym z tych przypadków m †" n , co w konsekwencji dowodzi, |e n "M. Ad 2. Rozpatrzmy zbiór M = {n " | n " n}. W takim przypadku 0 "M. Przypu[my, |e n "Mi zaBó|my, |e n " n *"{n}. Wtedy albo n " n albo n = n. Je[li n " n, to korzystajc z warunku 1. mamy n *"{n} †"n, co oznacza, |e n " n  co przeczy zaBo|eniu indukcyjnemu. Je[li za[ n = n, to otrzymujemy sprzeczno[ z zaBo|eniem indukcyjnym. Zatem przypuszczenie, |e n " n *"{n} jest bBdne. Dowodzi to, |e n "M. Ad 3. Teraz zaBó|my, |e m *"{m} = n *"{n}. Wynika std, |e m musi nale|e do zbioru po prawej stronie znaku równo[ci. Je[li m " n, to na mocy (i) mamy, |e m †" n. Gdy za[ m = n, to tak|e m †" n. Z symetrii zaBo|eD wynika równie| n †" m, co prowadzi do równo[ci m = n. Ad 4. Niech teraz M = {n " | dla ka|dego m †" n, je[li m = n, to m " n}. Na pewno 0 "M bo zbiór pusty nie zawiera podzbiorów wBa[ciwych. Przypu[my, |e n "Mi niech m †" n . (") ZaBó|my, |e m jest podzbiorem wBa[ciwym zbioru n . Poka|emy, |e m " n . Je[li n " m, to na podstawie 1. jest n †" m, zatemn †" m i z zaBo|enia: m †" n , otrzymujemy równo[ n = m  a wic sprzeczno[. Mamy zatem n " m. Z zaBo|enia (") otrzymujemy m †" n. Je[l m = n, to m " n . Niech zatemm = n. Poniewa| m jest podzbiorem wBa[ciwym n, to z zaBo|enia indukcyjnego otrzymujemy, |e m " n, co daje m " n . To za[ oznacza koniec dowodu podpunktu 4. twierdzenia. Ad. 5. Teraz rozpatrzmy zbiór M = {n " | dla ka|dego m " , je[lin †" m, to m †" n}. Dla wykazania induktywno[ci zbioru M zauwa|my, |e 0 " Moraz zaBó|my, |e n " M. Obierzmy dowolny m taki, |e n †" m (e&) Z zaBo|enia indukcyjnego mamy, |e m †" n lub te| n †" m. Gdy m †" n, to m †" n  co koDczy proces dowodowy. Przypu[my zatem, |e n m. Na podstawie 4. mamy, |e n " m. Wynika std, |e n †" m, co przeczy (e&). Dowodzi to, |e zaBo|ony przypadek nie mo|e zaj[. Std n "M. 6. FUNKCJE 18 Ad. 6. Ten podpunkt jest konsekwencj wcze[niejszych podpunktów. Jeden z warunków wynika z 4. i 5., podczas gdy niemo|liwo[ zaj[cia dwóch spo[ród wymienionych przypadków wynika z 2. oraz 1. W zbiorze liczb naturalnych relacja zawierania †" oznaczana jest symbolem , podczas, gdy relacja przynale|no[ci " oznaczana jest symbolem <. Je[li piszemy n " m, to mówimy, |e n jest mniejsze od m oraz, |e m jest wiksze od n. Nastpnik liczby n jest oznaczany poprzez n + 1. Liczba naturalna jest równocze[nie zbiorem wszystkich liczb naturalnych mniejszych od niej, co oznacza, |e n = {k " | k <n}. Twierdzenie. Je[li n jest liczb naturaln, za[ X niepustym zbiorem takim, |e X †" n, to istnieje n0 " X, |e dla ka|dego m " X zachodzi warunek m n0, tj. n0 jest najwiksz liczb w X. Innymi sBowy, ostatnie twierdzenie gBosi, |e ka|dy skoDczony i niepusty podzbiór liczb na- turalnych ma element najwikszy. Dowód. Niech M oznacza zbiór tych wszystkich liczb naturalnych n, |e dla ka|dego niepustego podzbioru X †" n istnieje n0 " X, |e dla ka|dego m " X ma miejsce nierówno[: m n0. Chcemy pokaza, |e M jest zbiorem induktywnym. Z oczywistych powodów 0 "M. Przypu[my, |e n "Moraz niech X †" n bdzie dowolnym niepustym podzbiorem. Roz- patrzmy dwie mo|liwo[ci. Je[li n " X, to szukanym elementem jest n. Gdy za[ n " X, wtedy X †" n i zaBo|enia indukcyjnego mamy, |e istnieje n0 " X o stosownych wBasno[ciach. Twierdzenie. (Zasada minimum) Ka|dy niepusty zbiór liczb naturalnych ma liczb najmniejsz tj. tak, |e je[li X †" oraz X = ", to istnieje n0 " X, |e dla ka|dego m " X zachodzi warunek n0 m. Dowód. Przypu[my, |e X = " jest podzbiorem nie zawierajcym elementu najmniejszego. Niech ponadto M = {n " | n )" X = "}. Chcemy wykaza induktywno[ zbioru M. Aatwo wida, |e 0 " M. Przypu[my, |e n " M oraz, |e n )" X = ". Std n " X oraz dla ka|dego m<n mamy m " X. To za[ oznacza, |e n jest najmniejszym elementem w X. Sprzeczno[ ta dowodzi, |e n )" X = ", co oznacza, |e n "M Na mocy zasady indukcji mamy, |e M = , a wic X = ". Z tej sprzeczno[ci wynika, |e X musi mie element najmniejszy. 6. Funkcje Rozpatrzmy dowolne zbiory A i B. Przez funkcj z A w B rozumiemy uporzdkowan trójk f, A, B tak, |e f †" A × B jest relacj speBniajc nastpujce warunki: 6. FUNKCJE 19 1. dla ka|dego x " A istnieje y " B, |e x, y "f; 2. dla ka|dego x " A oraz ka|dych y1 " b oraz y2 " B, je[li x, y1 "f oraz x, y2 "f, to y1 = y2. Przedstawiona definicja wskazuje na istotno[ ka|dego z elementów trójki f, A, B  a wic nie tylko relacj f, ale w tym samym stopniu zbiory A i B. Zbiór A nazywamy dziedzin, za[ zbiór B przeciwdziedzin funkcji f. Zwykle zamiast pisa f, A, B piszemy f : A ’! B. Zbiór wszystkich funkcji z A w B oznaczamy symbolem AB. Je[li w definicji funkcji zrezygnujemy z warunku (i), to trójk f, A, B speBniajc jedynie warunek (ii) nazywamy funkcj cz[ciow z A w B. Zbiór Dom(f) ={x " A| istnieje b " B, |e x, y "f} nazywamy dziedzin funkcji cz[ciowej f. W przypadku, gdy f †" A × B jest funkcj cz[ciow z A w B, to jest funkcj z Dom(f) wB. Funkcj ze zbioru A wzbiór B nazywamy równowa|nie odwzorowaniem okre[lonym na zbio- rze A i o warto[ciach w zbiorze B. PrzyjBa si niepisana umowa, |e funkcja to odwzorowanie zbioru liczbowego, lub produktu kartezjaDskiego takich zbiorów w inny zbiór liczbowy  my jednak obu nazw bdziemy u|ywa zamiennie. Dla oznaczenia funkcji bdziemy u|ywa na ogóB maBych liter alfabetu BaciDskiego. Symbol f : A ’! B bdzie oznaczaB, |e f odwzorowuje zbiór A w zbiór B, natomiast symbol f : x ’! y, |e f przyporzdkowuje elementowi x " A element y " B. Niekiedy element przyporzdkowany elementowi x " A poprzez funkcj f bdziemy oznacza przez f(x). Wtedy f(x) oznacza warto[ odwzorowania f dla elementu x, lub obraz elementu x poprzez funkcj f. Podzbiór zbioruB zBo|ony z wszystkich tych elementów y, |e dla ka|dego z nich istnieje przynajmniej jeden element x ze zbioru A, |e y jest obrazem x poprzez funkcj f tj. y = f(x) nazywamy obrazem zbioru A poprzez funkcj f. Mamy zatem: f(A) ={y " B : istnieje x " A, |e y = f(x)}. Podobnie, je[li X jest dowolnym podzbiorem zbioru A, to obraz tego zbioru poprzez odwzo- rowanie f oznaczamy przez f(X) i kBadziemy: f(X) ={y " B : istnieje x " A, |e y = f(x)}. Je[li f(A) =B, to mówimy, |e f : A ’! B jest funkcj przeksztaBcajc zbiór A na zbiór B. Odwzorowanie f : A ’! A nazywamy odwzorowaniem zbioru A w siebie, gdy f(A) ‚" A, natomiast odwzorowaniem zbioru A na siebie, gdy f(A) =A. Odwzorowanie i zbioru A na siebie, w którym obrazem ka|dego elementu x " A jest ten sam element tj. dla wszystkich x " A jest i(a) =a nazywamy odwzorowaniem identyczno[ciowym zbioru A na siebie i oznaczamy przez iA. Je|eli dziedzina A funkcji f jest zborem pustym, za[ B jest dowolnym zbiorem, to relacja f †" A × B jest relacj pust (jako podzbiór zbioru pustego). Gdy za[ A = " oraz B = ", to funkcja z A w B nie istnieje. Znów mamy A × B = A ×"= ", jednak teraz relacja pusta jest funkcj cz[ciow, ale nie jest funkcj. 6. FUNKCJE 20 Korzystajc z definicji funkcji wprowadzimy teraz nowe pojcia. Przez indeksowan rodzin zbiorów rozumiemy dowoln funkcj ze zbioru indeksów I w rodzin zbiorów A. Rodzin indeksowan zbiorów oznaczamy zwykle symbolem: {Ai}i"I. Je[li A jest dowolnym zbiorem, to sBowem nad alfabetem A nazywamy ka|dy skoDczony cig elementów zbioru A, tj. funkcj w : {0, 1, 2, . . . , n} ’!A, gdzie (n +1) " nazywamy dBugo[ci sBowa, któr zwykle oznaczamy symbolem |w|. Zbiór wszystkich sBów nad alfabetem A (niezale|nie od ich dBugo[ci) oznaczamy symbolem A". SBowem pustym, oznaczanym zwykle symbolem µ, nazywamy sBowo nad ka|dym alfabetem o dBugo[ci 0. Symbol An oznaczaB bdzie zbiór uporzdkowanych n-tek postaci x0, x1, . . . , xn-1 , które mog by równie| traktowane jako sBowa dBugo[ci n nad alfabetem A. Wtedy x0, x1, . . . , xn-1 mo|e by reprezentowana w przez funkcj w : n ’! A, dla której w(i) =ai, przy i "{0, 1, . . . , n- 1}. Wzbiorze A" mo|emy okre[li operacj skBadania (konkatenacji) sBów w taki sposób, |e je[li w : n ’! A, za[ u : m ’! A, to wu : (m + n) ’! A, przy czym: w(i), gdy i "{0, 1, . . . , n- 1}, (wu)(i) = w(i - n), gdy i "{n, n +1, . . . , m+ n - 1} Dla dowolnie ustalonego zbioru A, przez multizbiór rozumiemy ka|d funkcj M : A ’! . Opisowo, funkcja M z ka|demu elementowi bioru A przypisuje krotno[ jego wystpowania. Oznacza to, |e je|eli element x " A ma przypisan krotno[ 0, to nie wystpuje on w multi- zbiorze, je[li za[ M(x) = 3, to element x pojawia si trzykrotnie. Zbiór wszystkich multizbiorów zbioru A oznaczamy symbolem M(A). Dowolny podzbiór zbioru A, jest multizbiorem, którego ka|dy z elementów ma krotno[ nie przekraczajc 1. Odwzorowanie f : A ’! B nazywamy ró|nowarto[ciowym wtedy i tylko wtedy, gdy dla dowolnych x1 " A oraz x2 " A zachodzi warunek: (x1 = x2 =Ò! f(x1) = f(x2)). Ró|nowarto[ciowe odwzorowanie zbioru A na zbiór B nazywamy te| wzajemnie jednoznacznym odwzorowaniem zbioru A na zbiór B. Je[li odwzorowanie f, A, B jest równocze[nie ró|nowarto[ciowe i  na , to nazywamy je bijekcj. Je[li f : A ’! B, to mo|emy j rozpatrywa w dowolnym podzbiorze X ‚" A i wtedy mówimy, |e rozpatrujemy obcicie funkcji f do zbioru X. Dla podkre[lenia zaw|enia dziedziny funkcji f ze zbioru A do zbioru X u|ywamy symbolu f|X. Funkcj g przeprowadzajc zbiór B na caBy zbiór A nazywamy funkcj odwrotn do funkcji f przeprowadzajcej zbiór A na zbiór B, gdy dla ka|dego x " A oraz ka|dego y " B zachodz równo[ci: g(f(x)) = iA(x) =x oraz f(g(y)) = iB = y. Funkcj odwrotn do funkcji f, dla podkre[lenia jej zwizku z funkcj f bdziemy zwykle oznacza symbolem f-1. Odwzorowania ró|nowarto[ciowe nazywane s niekiedy odwracalny- mi. W[ród wszystkich odwzorowaD wyró|nia si tak|e odwzorowania cz[ciowo odwracalne tj. takie, które zaw|one do pewnego podzbioru dziedziny s ró|nowarto[ciowe. Zwrómy teraz 6. FUNKCJE 21 uwag, |e istnienie dla danej funkcji, funkcji do niej odwrotnej jest obwarowane warunkiem ró|nowarto[ciowo[ci. W przypadku, gdy mówimy o relacji warunek ten nie jest wymagany. Za- tem je[li dla danej funkcji nie istnieje funkcja odwrotna, wskutek jej nieró|nowarto[ciowo[ci, to na pewno istnieje relacja do niej odwrotna. Twierdzenie. Je[li f : A ’! B, g : B ’! C s funkcjami, to: 1. relacja g æ% f ‚" A × c jest funkcj z A w C; 2. gdy f i g s ró|nowarto[ciowe odpowiednio na A i B, to g æ% f jest ró|nowarto[ciowa; 3. gdy f i g s  na , to g æ% f jest  na . Dowód. Ad 1. Z zaBo|enia, |e f jest funkcj z A w B wynika, |e dla dowolnego x " A istnieje y " B speBniajce warunek a, y " f. Z drugiej strony dla funkcji g z podobnych powodów dla ka|dego y " B istnieje z " C, |e y, z " g. Std zgodnie z definicj skBadania relacji dla dowolnego x " A istnieje z " C, |e x, z "g æ% f. Tak wic dla ka|dego x " A istnieje obraz poprzez superpozycj gæ%f. Pozostaje pokaza, |e jest to obraz jedyny. Przypu[my, |e tak nie jest tj., |e istniej dwie pary x, z1 "g æ% f oraz x, z2 "g æ% f. Jednak w takim przypadku musz istnie elementy y1 oraz y2 wzbiorze B takie, |e x, y1 "f oraz x, y2 "f przy czym y1, z1 "g oraz y2, z2 "g. ZaBo|enie o tym, |e f jest funkcj prowadzi do równo[ci: y1 = y2. Z kolei zaBo|enie, |e g jest funkcj daje równo[: z1 = z2. Ostatecznie z obu wykazanych powodów wynika, |e relacja g æ% f jest funkcj. Ad 2. Niech zgodnie z zaBo|eniem obie funkcje tj. f i g bd ró|nowarto[ciowe i niech (g æ% f)(x1) = (g æ% f)(x2). Z faktu ró|nowarto[ciowo[ci funkcji g wynika równo[: f(x1) = f(x2). Dalej ju| z ró|nowarto[ciowo[ci funkcji f mamy, |e x1 = x2. Oznacza to, |e g æ% f jest ró|nowarto[ciowa. Ad 3. Zgodnie z zaBo|eniem niech f i g bd  na . Zatem dla ka|dego elementu z " C istnieje element y " B, |e z = g(y). Podobnie dla ka|dego y " B istnieje x " A, |e y = f(x). Std te| mamy zagwarantowane dla ka|dego z " C istnienie takich elementów x " A oraz y " B, |e c = g(y) =g(f(x)). Jest to zgodne z definicj funkcji  na , któr tym razem speBnia g æ% f. Zatem funkcje f : A ’! B i g : B ’! C wyznaczaj now funkcj, któr oznaczamy przez g æ% f tak, |e h : A ’! C i okre[lon dla wszystkich x " A warunkiem: h(x) =g(f(x)), któr nazywamy superpozycj (zBo|eniem) funkcji f i g i oznaczamy symbolem g æ% f. Tak wic dla ka|dego x " A: (g æ% f)(x) =(g æ% f)(x) PrzykBad. Niech f : ’! bdzie okre[lona wzorem: f(x) =x2 +1, za[ g : ’! wzorem: g(x) =sin x. Obie te funkcje maj wspóln dziedzin, natomiast ró|ne przeciwdziedziny. Mo- |emy dla tych funkcji rozwa|a zarówno superpozycj f æ% g jak i g æ% f. Mamy: (g æ% f)(x) =g(f(x)) = sin (x2 +1) za[ (f æ% g)(x) =sin2 x +1. 6. FUNKCJE 22 Jak Batwo zauwa|y porównujc oba te zBo|enia, a wBa[ciwie przeciwdziedziny tych zBo|eD, superpozycja funkcji nie jest przemienna. Twierdzenie. Dla dowolnych funkcji f : A ’! B, g : B ’! C i h : C ’! D h æ% (g æ% f) =(h æ% g) æ% f. Do wó d. Bezpo[rednio z definicji zBo|enia funkcji mamy, |e dla dowolnego x " A zachodz równo[ci: (h æ% (g æ% f))(x) =h((g æ% f)(x)) = h(g(f(x))), ((h æ% g) æ% f)(x) =(h æ% g)(f(x)) = h(g(f(x))). Porównujc je dostajemy tez twierdzenia. Twierdzenie. Dla dowolnej funkcji f : A ’! B nastpujce warunki s równowa|ne: 1. f ma funkcj odwrotn; 2. f jest bijekcj; 3. relacja odwrotna f-1 jest funkcj. Dowód. ZaBó|my zgodnie z 1. mamy, |e f ma funkcj odwrotn i oznaczmy j przez g. Zatem g : B ’! A. Gdy f(x1) = f(x2), to g(f(x1)) = g(f(x2)). Z drugiej strony mamy z zaBo|enia, |e g æ% f = iA, a wic x1 = x2. Oznacza to ró|nowarto[ciowo[ funkcji f. Teraz poka|emy, |e f jest  na . Niech y " B bdzie dowolnie wybrany i niech a = g(y). Std f(x) =f(g(y)) = y, bo f æ% g = iB. Oznacza to, |e f jest  na (czyli jest bijekcj). Obecnie przypu[my, |e speBniony jest warunek 2. twierdzenia. Niech y " B bdzie dowolnie wybrany. Z tego, |e f jest  na wynika, |e istnieje x " A dla którego f(x) =y. To za[ oznacza, |e y, x " f-1. ZaBó|my teraz, |e y, x1 " f-1, a tak|e y, x2 " f-1. Wtedy otrzymujemy równo[: f(x1) =f(x2), a z ró|nowarto[ciowo[ci funkcji f mamy x1 = x2. Oznacza to, |e relacja f-1 jest funkcj. Niech teraz speBniony bdzie warunek 3. Dla ka|dego x " A mamy: x, x " f-1f, gdy| x, f(x) " f. Konsekwencj tego faktu jest, |e iA †" f-1 æ% f. Gdy zaBo|ymy, |e x1, x2 " f-1 æ% f, to istnieje y " B dla którego x1, y "f oraz y, x2 "f-1. Wynika std równie|, |e y, x1 "f-1, a skoro f-1 jest funkcj, to x1 = x2. Zatemf-1 æ% f = iA. Dla funkcji f : A ’! B wprowadzili[my poprzednio pojcie obrazu elementu x zbioru A poprzez funkcj f. Przypomnijmy, |e jest to taki element y zbioru B, |e x, y "f. Je[li teraz X †" A bdzie dowolnym podzbiorem dziedziny funkcji f. Obrazem zbioru X poprzez funkcj f : A ’! B nazywamy zbiór f(X) †" B, |e f(X) = {f(x)} = {y " B| istnieje x " X, |e y = f(x)} x"X Je[li Y †" B, to przeciwobrazem zbioru Y poprzez funkcj f nazywamy zbiór f-1(Y ) okre- [lony równo[ci: f-1(Y ) = {f-1(y)} = {x " A| f(x) " Y }. y"Y 7. DEFINICJE INDUKCYJNE 23 Twierdzenie. Dla dowolnej funkcji f : A ’! B oraz rodziny X podzbiorów zbioru A i rodziny Y podzbiorów zbioru B mamy: 1. f ( X ) = {f(X)| X "X }; 2. je[li X = ", to f ( X ) †" {f(X)| X "X }; 3. f-1 ( Y) = f-1(Y )| Y "Y ; 4. je[li Y = ", to f-1 (Y) = f-1(Y )| Y "Y . Dowód. Ad 1. Zgodnie z definicj obrazu zbioru poprzez funkcj mamy dla dowolnego X "X , |e f(X) = {f(x)}. Zatem skoro X = X, to dostajemy natychmiast, |e x"X X"X f X = f {f(x)} = {f(X)| X "X } X"X x"X Ad 2. Niech y " f X . Zatem istnieje x " X , |e y = f(x). Na mocy definicji iloczynu zbiorów (w szczególno[ci definicji iloczynu rodziny zbiorów) mamy, |e x " X dla wszystkich X "X . Z drugiej strony oznacza to, |e f(x) " {f(X)}. Tak wic teza 2. jest prawdziwa. X"X Ad 3. Przyjmijmy, |e x " f-1 Y jest dowolnie wybrany. Std za[ wynika, |e f(x) " Y. Dalej z definicji sumy zbiorów wynika, |e istnieje zbiór Y " Y, do którego nale|y f(x). To z kolei oznacza, |e istnieje Y "Y, |e x " f-1(Y ). W konsekwencji jest tak wtedy i tylko wtedy, gdy x " {f-1}. Y "Y Ad 4. Technika dowodowa tej tezy jest analogiczna do zaprezentowanej w poprzednich pod- punktach. 7. Definicje indukcyjne Jak to zostaBo omówione w paragrafie 3. zbiór liczb naturalnych jest najmniejszym zbio- rem zawierajcym 0 i zamknitym ze wzgldu na jednoargumentow operacj nastpnika. Te wBasno[ci zbioru liczb naturalnych umo|liwiaj definiowanie w nim pewnych funkcji. Dla przykBadu niech f oznacza dziaBanie dodawania liczb naturalnych (dwuargumentow i wewntrzn operacj w ) tj. f : × ’! . Mamy: f(m, 0) = m, f(m, n ) = (f(m, n)) . Przy u|yciu tych dwóch równo[ci mo|emy wykonywa dziaBanie dodawania w zbiorze . Liczba m wystpujca w tej definicji nosi nazw parametru. Jest to liczba naturalna dowolnie ustalona. 7. DEFINICJE INDUKCYJNE 24 Twierdzenie. (o definiowaniu przez indukcj) Niech A i B bd dowolnie ustalonymi zbio- rami i niech B = ", za[ g : A ’! B i h : B×A×N ’! B dowolnymi funkcjami. Istnieje dokBadnie jedna funkcja f : A×N ’! B speBniajca dla dowolnych x " A oraz n " nastpujce warunki: f(x, 0) = g(x), f(x, n ) = h(f(x, n), x, n). Na wstpie uprzedzmy, |e dowód tego twierdzenia zostanie przedstawiony w dalszej cz[ci wykBadu. Dodajmy te|, |e w przedstawionym twierdzeniu zbiór A jest zbiorem parametrów. Jako efekt tego twierdzenia mo|emy przedstawi pewne uporzdkowanie zaprezentowanej poprzednio definicji dodawania liczb naturalnych. Rol funkcji g peBni funkcja identyczno[ i w zbiorze liczb naturalnych, za[ rol funkcji h operacja nastpnika. Warto[ funkcji f dla liczb naturalnych m i n oznaczamy tradycyjnie poprzez m + n. Teraz przedstawimy definicj mno|enia liczb naturalnych. Bdziemy si trzyma oznaczeD u|ytych w twierdzeniu. Mno|enie liczb naturalnych jest to jedyna funkcja f : × ’! okre[lona ukBadem równaD: f(m, 0) = 0, f(m, n ) = m + f(m, n). Funkcja g ma w tym przypadku posta g(x) =0 dla x " , za[ h ma posta h(x, y, z) =y + x, dla x " , y " , z " . Rozpatrzmy teraz operacj iteracji, któr oznaczymy przez Iter i wtedy Iter : P(A × A) × N ’!P(A × A) dla ka|dej relacji binarnej w A, przy czym o zbiorze A niczego nie zakBadamy. Dla relacji †" A × A przyjmujemy definicj: Iter( , 0) = iA, Iter( , n ) = æ% Iter( , n), gdzie Iter( , n) oznacza n-krotne zBo|enie relacji ze sob. Funkcja g (z ostatniego twier- dzenia) jest okre[lona nastpujco: g : P(A × A) ’! P(A × A), g( ) = iA, przy czym " P(A × A). Za[ funkcja h (równie| wymieniona w ostatnim twierdzeniu) ma posta: h : P(A × A) ×P(A × A) × ’! P(A × A), h( 1, 2, n) = 2 æ% 2, dla 1 "P(A × A) i 2 "P(A × A) oraz n " . Dla ilustracji przedstawionego opisu rozpatrzmy nastpujc sytuacj. Niech k " bdzie dowoln liczb naturaln dodatni i niech A = {0, 1}k oraz niech Õ : {0, 1}k ’!{0, 1} oznacza pewn funkcj k-argumentow. Wtedy dla dowolnego x0, x1, . . . , xk-1 mamy Õ( x0, x1, . . . , xk-1 ) =xk. 7. DEFINICJE INDUKCYJNE 25 Funkcja Õ okre[lona poprzednio pozwala na okre[lenie odwzorowania IÕ : {0, 1}k ’!{0, 1}", zwanego systemem iteracyjnym funkcji Õ, gdzie {0, 1}" oznacza zbiór wszystkich sBów (cigów) nieskoDczonych nad alfabetem {0, 1}. Cigi takie nazywamy obliczeniami systemu IÕ, a okre[- lamy je nastpujc równo[ci: IÕ( x0, x1, . . . , xk-1 ) =(x0, x1, . . . , xk-1, xk, xk-1, . . .) gdzie dla dowolnego i " jest xi+k = Õ( xi, xi+1, . . . , xi+k ). W oparciu o funkcj Õ mo|emy okre[li relacj Õ †"{0, 1}k ×{0, 1}k. Je[li przyjmiemy, |e x0 := x0, x1, . . . , xk-1 oraz x1 := x1, x2, . . . , xk, Õ( x0, x1, . . . , xk-1 ) , to: def xi, xj " Õ Ð!Ò! xj = xi|1, Õ(xi) , gdzie xi|1 = x1, x2, . . . , xk-1 jest elementem {0, 1}k-1 powstaBym z xi poprzez  obcicie pierw- szego wyrazu. Zatem relacja Õ ustala zale|no[ midzy sBowani dlugo[ci k nad alfabetem {0, 1}. Mo|emy sprawdzi, |e dla tego przypadku s speBnione warunki definicyjne naBo|one na operacj iteracji. Mamy mianowicie: Zerowe zBo|enie relacji Õ jest dziaBaniem to|samo[ciowym. Mamy: Iter( Õ, 0)(x) =x dla dowolnego x "{0, 1}k. (n + 1)-krotne zBo|enie relacji Õ speBnia warunek: Iter( Õ, n ) = Õ æ% Iter( Õ, n), co oznacza, |e n+1(x0) = Õ æ% n(x0) = Õ(xn-1) =xn Õ Õ dla dowolnego x0 "{0, 1}k. Przedstawiony przykBad relacji Õ pokazuje, |e iteracja, a co za tym idzie definiowanie induk- cyjne, odwoBuje si nie tylko do poprzedniej warto[ci, ale wynik uzale|niony jest od wszystkich dotychczas obliczonych warto[ci. Mamy na ten temat nastpujce twierdzenie. Twierdzenie. Dla dowolnych zbiorów A oraz B, gdzie B = ", niech g : A ’! B za[ h : B" × A × ’! B bd dowolnymi funkcjami. Istnieje wtedy dokBadnie jedna funkcja f : A × ’! B speBniajca dla dowolnego x " A oraz dowolnego n " równo[ci: f(x, 0) = g(x), f(x, n ) = h((f(x, 0) · · · f(x, n)), x, n), gdzie (f(x, 0) · · · f(x, n)) oznacza sBowo w B", którego literami s f(x, 0), . . . , f(x, n). 7. DEFINICJE INDUKCYJNE 26 Dowód. Funkcja f, o której mowa w twierdzeniu jest tylko jedna. Zauwa|my bowiem, |e gdyby istniaBy dwie takie funkcje f1 i f2, to dla wszystkich n " oraz dowolnie wybranego x " A byBoby: f1(x, n) =f2(x, n). Mianowicie je[li f1(x, 0) = g(x) oraz f2(x, 0) = g(x), to dla dowolnego x i n = 0 warunek jest speBniony. Przypu[my teraz, |e dla x " A oraz ustalonego n " dla f1(x, n) =h((f1(x, 0) · · · f1(x, n - 1)), x, n- 1) oraz f2(x, n) =h((f2(x, 0) · · · f2(x, n - 1)), x, n- 1) zachodzi f1(x, n) =f2(x, n) oraz f1(x, n ) = f2(x, n ) Mamy, |e f1(x, n ) =h((f1(x, 0) · · · f1(x, n - 1)), f1(x, n), x, n) oraz f2(x, n ) =h((f2(x, 0) · · · f2(x, n - 1)), f2(x, n), x, n). Poniewa| z zaBo|enia h jest funkcj, to dla tych samych argumentów przyjmuje te same warto[ci. Std na mocy zasady indukcji dla wszystkich n " jest f1(x, n ) =f2(x, n ). Poka|emy teraz istnienie funkcji f. Wykorzystamy w tym celu twierdzenie o definiowaniu przez indukcj. Niech B = B" oraz niech g : A ’! B bdzie okre[lona w ten sposób, |e g (x) jest sBowem jednoliterowym. Ponadto niech h : B × A × ’! B bdzie okre[lona nastpujco: h (w, x, n) =wh(w, x, n), tj. do sBowa w dopisywana jest litera h(w, x, n). Niech teraz f : A× ’! B oznacza jedyn funkcj okre[lon indukcyjnie poprzez warunki: f (x, 0) = g (x), f (x, n ) = h (f (a, n), a, n). Symbolem : B" ’! B oznaczymy funkcj, która ka|demu niepustemu sBowu w przypo- rzdkowuje ostatni (tj. skrajn praw) liter wystpujc w tym sBowie. Po to, by nie byBa funkcj cz[ciow na B" zakBadamy, |e dla sBowa pustego µ jej warto[ jest równa (µ) =b0, gdzie b0 jest dowolnie ustalonym elementem alafabetu B. Funkcj f : A × ’! B okre[lamy równo[ci: f(x, n) = (f (x, n)). Poka|emy, |e f (x, n) =(f(x, 0), . . . , f(x, n)) (c&) Dowód poprowadzimy przez indukcj wzgldem n. Gdy n =0, to f (x, 0) = (g (x)) = ( (g (x))) = ((f (x, 0))) = (f(x, 0)). 8. RELACJE RÓWNOWA{NOZCI 27 Dodatkowo mamy: f (x, n ) =h (f (x, n)x, n) =f (x, n)h(f (x, n)x, n)) = =(f(x, 0) · · · f(x, n)) (f (x, n )) =(f(x, 0) · · · f(x, n)f(x, n )). Nale|y jeszcze wykaza, |e f speBnia warunki naBo|one na ni w twierdzeniu. Mamy, |e f(x, 0) = (f (x, 0)) = (g (x)) = g(x). Z drugiej strony f(x, n ) = (f (a, n )) = (h (f (x, n), x, n)) = = (f (x, n)h (f (x, n), x, n)) = h (f (x, n), x, n) = = h((f(x, 0) · · · f(x, n)) , a, n). Dodajmy, |e ostatnia równo[ jest konsekwencj (c&). Ostatecznie wykazali[my, |e f jest funkcj o jakiej mówi ostatnie twierdzenie. 8. Relacje równowa|no[ci W zale|no[ci od wBasno[ci jakie speBnia relacja binarna mo|emy rozwa|a ró|ne kategorie takich relacji. Obecnie zajmiemy si relacjami, które s zwrotne, symetryczne i przechodnie (definicje tych wBasno[ci zostaBy podane w paragrafie 3). Relacj speBniajc wymienione trzy wBasno[ci nazywamy relacj równowa|no[ci (lub równowa|no[ci). Relacje równowa|no[ci s zwykle oznaczane symbolem H". PrzykBady. (1) Rozwa|my ogóB emitowanych przez Narodowy Bank Polski banknotów i pozostajcych w obiegu. Oznaczmy ten zbiór przez X. Okre[lmy w nim relacj[ równo[ci nominaBów banknotó  bez wzgld na inne ich atrybuty takie jak seria, numer i stan. Tak okre[ona relacja speBia de- finicj relacji równowa|no[ci. Zauwa|my przy tym, |e zbiór X zostaB przez t relacj podzielony na rozBczne podzbiory zBo|one z banknotów o nominale 10, 20, 50, 100, 200 zBotych. (2) Je[li na pBaszczy|nie À wprowadzimy relacj równolegBo[ci prostych, to oka|e si |e relacja ta jest równie| relacj równowa|no[ci. Z jej punktu widzenia jedyn interesujca cech jest kierunek prostej. Ta relacja dzieli pBaszczyzn À na podzbiory prostych o jednakowym kierunku, z tym |e podzbiorów takich jest nieskoDczenie wiele. (3) Rozwa|my dowolny niepusty zbiór X, a w nim relacj H" zdefiniowan w ten sposób, |e x H" y wtt, gdy x = y. Batwo zauwa|y, |e jest ona relacj równowa|no[ci. 8. RELACJE RÓWNOWA{NOZCI 28 Niech X bdzie dowolnym niepustym zbiorem, za[ H" okre[lon w nim dowoln relacj równowa|no[ci. Dla dowolnego elementu x ze zbioru X symbolem x H" bdziemy oznacza zbiór tych wszystkich elementów y ze zbioru X, |e s one wrelacji H" z elementemx tj.: x H" = {y " X| x, y "H"} (º) Podzbiory elementów zbioru X okre[lone równo[ci (º) nazywamy klasami równowa|no[ci relacji H" w X lub te| klasami abstrakcji relacji H" w X. Precyzyjniej, klas x H" nazywamy klas równowa|no[ci (abstrakcji) relacji H" w X wyznaczon przez x lub te| o reprezentancie x. Zbiór wszystkich klas równowa|no[ci relacji H" w X oznaczamy symbolem X/ H" i nazywamy zbiorem ilorazowym zbioru X wzgldem relacji równowa|no[ci H". Niech X bdzie dowolnym niepustym zbiorem. Rodzin   podzbiorów tego zbioru nazywamy rozbiciem zbioru X (podziaBem zbioru X) wtt, ka|dy z elementów rodziny   jest zbiorem niepustym; elementy rodziny   s parami rozBczne; suma wszystkich elementów rodziny   jest równa zbiorowi X. Elementy rodziny   nazywane s klasami rozbicia. Zatem, ka|da z relacji rozpatrywanych w ostatnim przykBadzie dzielc zbiory, w których byBa okre[lona wyznaczaBa rodzin bdc przykBadem rozbicia. Zajmijmy si teraz wBasno[ciami klas abstrakcji dowolnej relacji równowa|no[ci. Mówi o tym nastpujce twierdzenie. Twierdzenie. Niech X bdzie dowolnym niepustym zbiorem, za[ H" dowoln okre[lon w nim relacj równowa|no[ci. Wtedy dla ka|dego x, x1, x2 " X speBnione s nastpujce warunki: x " x H", (i) x1 H" = x2 H" Ð!Ò! x1 H" x2, (ii) x1 H" = x2 H" =Ò! x1 H" )" x2 H" = ". (iii) Dowód. Poniewa| H" jest zwrotna z definicji, jako relacja równowa|no[ci, wic dla dowolnego x " X zachodzi x H" x, wic x " x H". Przypu[my, |e x1 H" ‚" x2 H". Wtedy x1 " x2 H", a wic na mocy definicji relacji równowa|no[ci x1 H" x2. Odwrotnie, gdy x2 H" x1, wtedy je[li x " x1 H" to x H" x1. Poniewa| jednak H" jest przechodnia, to x " x2 H". Oznacza to, |e x1 H" ‚" x2 H" i mamy równowa|no[ x1 H" ‚" x2 H" postpujc podobnie pokazujemy, |e x2 H" ‚" x1 H". Dlatego x1 H" = x2 H". 8. RELACJE RÓWNOWA{NOZCI 29 Przejdzmy teraz do dowodu warunku (iii), który przeprowadzimy metod nie wprost. ZaBó|- my wic, |e zbiory x1 H" i x2 H" nie s rozBczne. Istnieje zatem taki element x, który nale|y do ka|dego z nich. Na mocy (º) mamy, |e x1 H" x i x2 H" x. Jednocze[nie symetryczno[ relacji H" gwarantuje, |e x1 H" x i x H" x2. Przechodnio[ z kolei powoduje, |e x1 H" x2  co w poBczeniu z (ii) prowadzi do równo[ci x1 H" = x2 H". Otrzymali[my sprzeczno[, co oznacza koniec dowodu warunku (iii). Podamy teraz, jako konsekwencj ostatniego twierdzenia, twierdzenie nazywane zasad abs- trakcji. Twierdzenie. (zasada abstrakcji) Dowolna relacja równowa|no[ci H" okre[lona w niepustym zbiorze X ustala podziaB tego zbioru na rozBczne i niepuste podzbiory, mianowicie na klasy równowa|no[ci tej relacji, w taki sposób, |e dwa elementy x, y zbioru X nale| do tej samej klasy równowa|no[ci wtedy i tylko wtedy, gdy x H" y. PrzykBady. (1) Rozpatrzmy zbiór wszystkich liczb caBkowitych i niech m bdzie dowoln liczb na- turaln nie mniejsz ni| 2, któr zwykle nazywamy moduBem. O liczbach a i b mówimy, |e s równe modulo m i piszemy a a" b(mod m) wtedy i tylko wtedy, gdy ró|nica tych liczb jest podzielna przez m. Aatwe sprawdzenie warunków definicji relacji równowa|no[ci pokazuje, |e relacja równo[ci liczb modulo m jest tak wBa[nie relacj. Wobec tego, na mocy ostatniego twierdzenia, dzieli ona zbiór na rozBczne podzbiory  klasy równowa|no[ci. Jest ich jak Batwo si przekona m. Wypiszmy je zatem: 0 H" = {. . . , -m, 0, m, . . .}, . . . , m - 1 H" = {. . . , -m - 1, -1, m- 1, . . .}. Pierwsza z nich jest zbiorem liczb, których reszta z dzielenia przez m jest równa 0. Podobnie, ostatnia z nich jest zbiorem wszystkich tych liczb caBkowitych, których reszta z dzielenia przez m jest równa m-1. Je[li m = 2, to zbiór ilorazowy /(mod 2) skBada si z dwóch klas abstrakcji 0 H" i 1 H". (2) Niech A bdzie dowolnym zbiorem, który traktujemy jak alfabet, za[ A" zbiorem sBów nad A. Ponadto niech L †" A bdzie dowolnie ustalonym podzbiorem sBów. W oparciu o zbiór L okre[lamy relacj <"L w A" w nastpujcy sposób: je[li u " A", w " A", to u, w "<"L wtedy i tylko wtedy, gdy dla dowonych sBówx " A" oraz y " A" zachodzi równowa|no[: xuy " L Ð!Ò! xwy " L. Opisowo oznacza to, |e sBowa u i w s w relacji <"L wtedy i tylko wtedy, gdy bez wzgldu na kontekst w jakim si znajduj pozostaj w L. Ta relacja równowa|no[ci jest istotnym narzdziem jzyków formalnych. Je|eli zbiór ilorazowy A/ <"L jest skoDczony, to jzyk L nosi nazw jzyka regularnego. (3) Rozpatrzmy alfabet postaci A = *"{+, ×, (, )}, w którym nawiasy s symbolami alfabetu, podobnie jak symbole dziaBaD: + -dodawania i ×  mno|enia. Przez W oznaczamy najmniejszy zbiór sBów nad alfabetem A speBniajcym warunki: 1. dla n " jest n "Z; 8. RELACJE RÓWNOWA{NOZCI 30 2. dla u "Z oraz w "Z jest (u + w) "Z oraz (u × w) "Z. Ka|dy z elementów zbioru Z nazywamy wyra|eniem. Relacj " Z × Z okre[lamy nast- pujco: u w wtt, gdy wyra|enia u i w wyznaczaj t sam liczb naturaln. Relacja ta jest równie| równowa|no[ci. (4) Niech teraz A i B bd dowolnymi zbiorami oraz niech f : A ’! B. Dla funkcji f, A, B okre[lamy relacj zwan jdrem funkcji i oznaczan przez ker(f) w nastpujcy sposób: x1, x2 "ker(f) Ð!Ò! f(x1) =f(x2). Poniewa| relacja równo[ci elementów dowolnego zbioru jest równowa|no[ci, to tak|e relacja ker(f) jest równowa|no[ci. 8.1. Liczby caBkowite. Dotychczas nie byBy rozwa|ane przez nas wBasno[ci algebraiczne zbiorów z dziaBaniami, jednak obecnie potrzebne bd pewne fakty z tym zwizane. ZakBadamy mianowicie, |e w zbio- rze okre[lone s dziaBania dodawania i mno|enia, rozumiane jako dwuargumentowe funkcje okre[lone w paragrafie dotyczcym definiowania indukcyjnego. Liczb caBkowit c bdziemy reprezentowa w postaci pary a, b takiej, |e c + a = b. Aatwo zauwa|amy, |e dla ustalonego c istnieje nieskoDczenie wiele takich par. Z tego powodu w zbiorze × definiujemy relacj H" tak, |e: a1, b1 H" a2, b2 wtedy i tylko wtedy, gdy a1 + b2 = a2 + b1. Zauwa|amy z tego zapisu, |e dwie pary pozostaj ze sob w relacji, gdy ich poprzedniki ró|ni si od nastpników o t sam liczb. Podkre[lmy jeszcze raz, |e zarówno poprzedniki jak i nastpniki par s liczbami naturalnymi. Twierdzenie. Relacja H" jest równowa|no[ci w × . Dowód. Zwrotno[ realcji H" wynika wprost z definicji. Symetria z kolei oznacza, |e a1, b1 H" a2, b2 wtedy i tylko wtedy, gdy a1 + b2 = a2 + b1 podczas, gdy a2, b2 H" a1, b1 wtedy i tylko wtedy, gdy a2 + b1 = a1 + b2. Z uwagi na prawe strony ostatnich równowa|no[ci mamy wBasno[ symetrii dla relacji H". Wyka|emy teraz przechodnio[. Niech a1, b1 H" a2, b2 oraz a2, b2 H" a3, b3 Oznacza to z definicji, |e a1 + b2 = a2 + b1 oraz a2 + b3 = a3 + b2. Std za[ wynika, |e a1 +(a2 + b2) +b3 =(a2 + b2) +a3 + b1, 8. RELACJE RÓWNOWA{NOZCI 31 dlatego a1 + b3 = a3 + b1 wtedy i tylko wtedy, gdy a1, b1 H" a3, b3 . co [wiadczy o tym, |e H" jest równowa|no[ci w × . Jako relacja równowa|no[ci H" dzieli × na klasy abstrakcji, które to klasy nazywamy liczbami caBkowitymi. Zbiór / H" oznaczamy symbolem i nazywamyzbiorem liczb caBkowitych. Wzbiorze wprowadzamy dwa dziaBania. (±) a, b H" •" a , b H" = a + a , b+ b H" (²) a, b H" a , b H" = (a · a ) +(b · b ), (a · b ) +(b · a ) H". Lemat. Je[li a1, b1 H" a2, b2 oraz a , b H" a , b , to 1 1 2 2 (") a1 + a , b1 + b H" a1 + a , b1 + b 1 1 2 2 ("") (a1 · a ) +(b1 · b ), (a1 + b ) +(b1 + a ) H" (a2 · a ) +(b2 · b ), (a2 + b ) +(b2 + a ) 1 1 1 1 2 2 2 2 Dowód. Zgodnie z definicj relacji H" mamy: a1, b1 H" a2, b2 Ô!a1 + b2 = a2 + b1 oraz a , b H" a , b Ô!a + b = a + b Ð!Ò! a1 + b1 +2=a2 + b1 +2Ð!Ò! a1 + b1 = a2 + b1. 1 1 2 2 1 2 2 1 a1 + a , b1 + b H" a2 + a , b2 + b Ð!Ò!a1 + a +(b2 + b ) = b1 + b +(a2 + a ) 1 1 2 2 1 2 1 2 czyli a1 + a1 +1+b2 +1+b2 +1+1=b1 + b1 +1+a2 +1+a2 +1+1 Std ju| a1 + b2 = a2 + b1  co oznacza, |e (") jest prawd. Podobnie postpujemy przy dowodzie (""). 8.2. Liczby wymierne. æ% Jak poprzednio niech oznacza zbiór liczb caBkowitych, za[ := \ {0}. Rozpatrzmy æ% iloczyn kartezjaDski × , którego elementami s pary liczb a, b , gdzie nastpnik pary nie æ% mo|e by zerem. W zbiorze × definiujemy relacj okre[lon nastpujco: a1, b2 a2, b2 wtedy i tylko wtedy, gdy a1b1 = a2b1. Mówic jzykiem opisowym pary liczb caBkowitych pozostaj ze sob w relacji wtedy i tylko wtedy, gdy poprzedniki tych par s w takiej samej proporcji do nastpników. Tak wic 2, 6 , -1, -3 , 27, 81 , to przykBady par pozostajcych w relacji . " Twierdzenie. Relacja †" × jest równowa|no[ci. 9. TEORIA MOCY 32 Dowód. Zwrotno[ otrzymujemy natychmiast: def a, b a, b Ð!Ò! ab = ab. Ponadto def a1, b1 a2, b2 Ð!Ò! a1b2 = a2b1 Ð!Ò! a2b1 = a1b2 Ð!Ò! a2, b2 a1, b1 , co oznacza, |e jest symetryczna. Teraz zbadamy przechodnio[. Mamy: a1, b1 a2, b2 oraz a2, b2 a3, b3 . Oznacza to, |e a1b2 = a2b1 oraz a2b3 = a3b2, std a1b2a2b3 = a2b1a3b2, co daje (a1b3)(a2b2) = (a3b1)(a2b2). Zatem je[li tylko a2 =0, to a1b3 = a3b1 czyli a1, b1 a3, b3 . Oznacza to, |e jest przechodnia i dlatego relacja ta jest równowa|no[ci. æ% Relacja dzieli zbiór × na rozBczne klasy abstrakcji, które to klasy nazywamy liczbami æ% wymiernymi. Zbiór ( × )/ nazywamy zbiorem liczb wymiernych i oznaczamy przez . Wzbiorze okre[lamy dziaBania dwuargumentowe: •" i zwane odpowiednio dodawaniem i mno|eniem liczb wymiernych. A oto ich definicje: a1, b1 •" a2, b2 = a1b2 + a2b1, b1b2 a1, b1 a2, b2 = a1a2, b1b2 a Z przyczyn praktycznych, ale i historycznych par a, b uto|samiamy zwykle z napisem . b a Zatem symbol zwany uBamkiem zwykBym oznacza klas abstrakcji pewnej specjalnej relacji b równowa|no[ci. Dla liczb wymiernych podobnie jak to ma miejsce w przypadku liczb caBkowitych mo|na pokaza, |e przy wykonywaniu dziaBaD dodawania i mno|enia wybór konkretnego reprezentanta klasy abstrakcji nie ma wpBywu na wynik dziaBania. W odró|nieniu od liczb caBkowitych oba wprowadzone dziaBania arytmetyczne tj. dodawanie i mno|enie maj dziaBania odwrotne (poza dzieleniem przez 0). 9. Teoria mocy Niech A i B bd dowolnymi zbiorami. Zbiory te bdziemy nazywa równolicznymi wtedy i tylko wtedy, gdy istnieje funkcja f ró|nowarto[ciowa i odwzorowujca zbiór A na zbiór B. Fakt równoliczno[ci zbiorów A i B bdziemy wyra|a piszc: A <" B. Pojcie równoliczno[ci zbiorów jest uogólnieniem na dowolne zbiory  zbiory elementów dowolnej natury  pojcia równej liczebno[ci. W my[l tej definicji równoliczne s zbiory A = {7, t, ±, } i B = {c&, f&, e&, `&}. Rozpatrzmy jednak bardziej interesujcy przykBad. PrzykBad. Niech a, b " oraz a < b. Rozwa|my przedziaB (a; b). Poka|emy, |e prze- dziaB (a; b) jest równoliczny ze zbiorem liczb rzeczywistych. W tym celu, zgodnie z warunkami 9. TEORIA MOCY 33 definicji równoliczno[ci, nale|y wskaza funkcje ró|nowarto[ciow i wzajemnie jednoznacznie przeprowadzajc (a; b) na . Zauwa|my, |e funkcja tangens przeprowadza otwarty przedziaB 1 (-1À; À) na przedziaB (-"; +"). Zatem nale|y zmodyfikowa tak dziedzin funkcji tangens, 2 2 by przeksztaBcaBa ona w przedziaB (a; b). W tym celu przeksztaBcamy przedziaB (a; b) poprzez 1 wzajemnie jednoznaczn i ró|nowarto[ciow funkcj h na przedziaB (-1À; À). Niech zatem 2 2 1 1 h : (a; b) -’! - À; À 2 2 oraz a+b x - 2 h : x -’! À · b - a Batwo sprawdzi, |e funkcja h speBnia wszystkie potrzebne warunki. Dokonujc teraz superpo- zycji odwzorowaD f i h otrzymujemy funkcj f æ% h ró|nowarto[ciow i wzajemnie jednoznacznie przeprowadzajc zbiór (a; b) na . Zatem zgodnie z definicj zbiory te s równoliczne. Ostatni przykBad pokazuje, |e zbiór nieskoDczony mo|e by równoliczny ze swoim podzbiorem wBa[ci- wym. Twierdzenie. Relacja równoliczno[ci zbiorów jest relacj równowa|no[ci. Dowód. Poniewa| relacj równoliczno[ci zbiorów jest zdefiniowana poprzez bijekcj, to dla dowolnego zbioru A jest on równoliczny z samym sob i bijekci tak realizuje identyczno[ iA. Z kolei symetria relacji równoliczno[ci wynika z faktu, |e ka|da bijekcja jest funkcj odwracaln. Natomiast przechodnio[ wynika z udowodnionego poprzednio faktu, |e zBo|enie bijekcji jest bijekcj. Relacja równoliczno[ci zbiorów, jako równowa|no[ dzieli zbiory na rozBczne klasy zbiorów i uto|samia ze sob zbiory równoliczne. Przyjmujemy umow, |e ka|demu zbiorowi mo|emy przyporzdkowa pewien nowy atrybut, który zwyczajowo oznacza bdziemy jako |A|, zwany moc zbioru A. (Niekiedy u|ywane jest tak|e inne onaczenie: cardA od angielskiego sBowa cardinality.) Ponadto zbiory A i B maj t sam mo, wtedy i tylko wtedy, gdy s one równoliczne. Wyra|amy ten fakt piszc: A <" B Ð!Ò! |A| = |B|. Wida std, |e moc zbioru jest cech klasy abstrakcji relacji równoliczno[ci zbiorów. Moce zbiorów nazywamy tak|e liczbami kardynalnymi. Zbiór A bdziemy nazywa skoDczonym wtedy i tylko wtedy, gdy istnieje liczba naturalna n, |e A <" n (tu n rozumiemy jako zbiór wszystkich liczb naturalnych mniejszych ni| n). Mówimy wtedy, |e A jest n-elementowy. Ka|dy zbiór, który nie jest skoDczony nazywamy nieskoDczonym. Przyjmujemy umow, |e moc zbioru n-elementowego jest równa n, za[ moc zbioru liczb naturalnych oznaczamy symbolem 5!0. Twierdzenie. 1. Dla ka|dego n " nie istnieje funkcja ró|nowarto[ciowa z n *"{n} w n. 2. Je[li m " , n " oraz m <" n, to m = n. 9. TEORIA MOCY 34 3. Nie istnieje liczba naturalna równoliczna z , co oznacza, |e jest nieskoDczony. Dowód. Ad 1. Dowód zostanie poprowadzony przez indukcj. Gdy n = 0, to twierdzenie jest prawdziwe, poniewa| nie istnieje funkcja okre[lona na zbiorze niepustym o warto[ciach w zbiorze pustym. Przypu[my teraz, |e twierdzenie zachodzi dla n " oraz niech f : n *"{n}*"{n } ’!n *"{n} oznacza funkcj ró|nowarto[ciow. Gdy f nie przyjmuje warto[ci n, lub te| gdy f(n ) =n, to zaw|ajc f do n *"{n} (w notacji relacyjnej oznacza to funkcja ma wtedy posta f )" (n × n )) otrzymujemy funkcj ró|nowarto[ciow z n*"{n} w n  prowadzi to do sprzeczno[ci z zaBo|eniem indukcyjnym. Przyjmujc natomiast f(i) =n, gdzie i n oraz zakBadajc, |e j = f(n ) mamy i| z tego, |e f jest ró|nowarto[ciowa wynika j <n. Wtedy funkcja g : n *"{n} ’!n okre[lona warunkiem: f(x), gdy x = i g(x) = j, gdy x = i, jest ró|nowarto[ciowa. Sprzeczno[ ta pokazuje, |e f nie mo|e by ró|nowarto[ciowa. Zatem (i) zachodzi. Zajmiemy si teraz podpunktem (ii). Dla m " oraz n " poka|emy, |e: Je[li istnieje funkcja ró|nowarto[ciowa z m w n, to m †" n.(") Indukcja prowadzona jest wzgldem m. Gdy m = 0, to twierdzenie jest prawdziwe. Przypu- [my, |e (") zachodzi i niech f : m ’! n bdzie ró|nowarto[ciowa. Skoro m †" m , to istnieje funkcja ró|nowarto[ciowa z m w n, a wic z zaBo|enienia indukcyjnego mamy m †" n. Przypa- dek, gdy m = n nie jest mo|liwy ze wzgldu na poprzedni podpunkt. Std m = n i w oparciu o wBasno[ci zbioru liczb naturalnych mamy, |e m " n. Ostatecznie m = m *"{m} oraz m ‚" n, co pokazuje, |e warunek (") jest speBniony. Z kolei (ii) jest konsekwencj ("). Dla dowodu (iii) zauwa|my, |e gdyby istniaBa funkcja ró|nowarto[ciowa f : ’! n, to jej zaw|enie do n *"{n} byBaby funkcj ró|nowarto[ciow z n *"{n} w n, a to stoi w sprzeczno[ci z (i). 9.1. Zbiory przeliczalne Zbiór A nazywamy przeliczalnym wtedy i tylko wtedy, gdy jest skoDczony, bdz równoliczny ze zbiorem liczb naturalnych. Przez cig o wyrazach w niepustym zbiorze A bdziemy rozumie ka|d funkcj z w A. Twierdzenie. Niepusty zbiór A jest przeliczalny wtedy i tylko wtedy, gdy jest on zbiorem wyrazów pewnego nieskoDczonego cigu. Dowód. Rozpocznijmy od przypadku, gdy A = {a0, a1, . . . , am-1} tzn., gdy jest skoDczony. Wtedy cig (±n) mo|emy okre[li nastpujco: an, gdy n "{0, 1, . . . , m- 1}, ±n = am-1, gdy n "{m, . . .}, 9. TEORIA MOCY 35 Je[li za[ A jest zbiorem przeliczalnym nieskoDczonym, to istnieje funkcja f : ’! A, co oznacza, |e A jest zbiorem wyrazów pewnego cigu (cigu nieskoDczonego) (±n), dla którego zachodzi równo[: f(±n) =f(n) dla wszystkich n " . ZaBó|my, |e A jest zbiorem wyrazów pewnego cigu (±n). Je|eli A jest skoDczony, to z definicji jest zbiorem przeliczalnym. Je|eli za[ jest zbiorem nieskoDczonym, to kBadc f(1) = ±1 i f(k) niech bdzie równe pierwszemu wyrazowi cigu (±n) ró|nemu od f(k - i) dla 1 i <k otrzymujemy funkcj f : ’! A ró|nowarto[ciow przeksztaBcajc ma A. Std A jest równoliczny z . Twierdzenie. Podzbiór zbioru przeliczalnego jest zbiorem przeliczanym. Dowód. Niech A bdzie zbiorem przeliczalnym oraz niech B ‚" A. Je[li B jest przeliczalny, to jest skoDczony z definicji. Je[li za[ jest nieskoDczony, to zaBó|my, |e B A. Poniewa| A jest zbiorem przeliczalnym, to istnieje funkcja f : ’! A bdca bijekcj. Niech teraz g : ’! B bdzie funkcj okre[lon równo[ci: g(1) = f(k1), przy czym k1 jest najmniejsz liczb naturaln, dla której f(k1) " B, g(n) =f(k1) dla n>1, gdzie kn jest najmniejsz liczb naturaln, dla której kn >kn-1 oraz f(kn) " B. Funkcja g jest ró|nowarto[ciowa i przeksztaBca na B. Wynika std, |e B jest równoliczny z , a wic przeliczalny i nieskoDczony. Inny sposób dowodu. Niech A oznacza niepusty zbiór przeliczalny oraz niech B †" A. Z poprzedniego twierdzenia wiemy, |e istnieje funkcja f z w A. Niech x0 " B bdzie dowolnie wyró|niony. Okre[lamy funkcj g : A ’! B w nastpujcy sposób: x, gdy x " B )" A, g(x) = x0, gdy x " A \ B. Funkcja g jest funkcj z A na B, a zatemB jest przeliczalny. Twierdzenie. Je|eli f : A ’! B jest dowoln funkcj oraz X †" A jest zbiorem przeliczal- nymm to f(X) jest przeliczalny. Dowód. Niech f : A ’! B bdzie dowoln funkcj oraz niech X †" A bdzie przeliczalny. Gdy X = ", to f(X) = " jest przeliczalny. Gdy za[ X = ", to istnieje funkcja g : ’! X bdca  na X. Niech f|X oznacza obcicie funkcji f do X, co oznacza, |e f|X = f )" (X × B). Jest przy tym f|X przeprowadza X na f(X) a zBo|enie f|X æ% g : ’! f(X) jest  na f(X). Oznacza to na mocy wcze[niejszego twierdzenia, |e f(X) jest zbiorem przeliczalnym. Lemat. Funkcja f : × ’! okre[lona równo[ci f( m, n ) = 2n(2m +1) - 1 jest bijekcj. 1 2 1 Dowód. Przypu[my, |e 2n (2m1 +1) - 1 = 2n (2m2 +1) - 1. Wtedy 2n (2m1 +1) = 2 2n (2m2 + 1). Z zasadniczego twierdzenia arytmetyki (twierdzenia o jednoznaczno[ci rozkBadu na czynniki pierwsze) wynika, |e n1 = n2, co implikuje równo[ 2m1 +1 = 2m2 +1, a w konsekwencji m1 = m2. Tak wic f jest ró|nowarto[ciowa. Dla pokazania, |e f jest  na obierzmy dowoln liczb naturaln k i przyjmijmy, |e n " k +1 oznacza najwiksz liczb naturaln tak, |e 2n dzieli k +1. Wynika std, |e jest liczb 2n 1 k +1 nieparzyst, bo gdyby tak nie byBo, to n nie byBaby najwiksza. Wezmy m = - 1 . 2 2n Wtedy f( m, n ) =k  co oznacza, |e f jest funkcj  na zbiór . 9. TEORIA MOCY 36 Twierdzenie. Je[li A i B s przeliczalne, to A × B jest przeliczalny. Dowód. Je[li którykolwiek ze zbiorów A i B jest pusty, to A × B jest pusty, a zatem przeliczalny. ZaBó|my, |e |aden z tych zbiorów nie jest pusty. Poza tym niech f : ’! A i g : ’! B bd funkcjami na. Funkcj h okre[lamy nastpujco: h : × ’! A × B, h( m, n ) = f(m), g(n) . Funkcja h przeksztaBca  na A × B, co oznacza, |e zbiór ten jest przeliczalny. Twierdzenie. Je|eli {Ai| i " I} jest przeliczaln rodzin zbiorów przeliczalnych (I jest przeliczalny oraz ka|de Ai jest zbiorem przeliczalnym), to Ai jest tak|e zbiorem przeliczalnym. i"I Dowód. Niech {Ai| i " } oznacza rodzin zbiorów przeliczalnych. ZakBadamy, |e ka|dy z elementów tej rodziny jest zbiorem niepustym. Niech f : ’! I bdzie  na I oraz dla ka|dego i " I niech gi : ’! Ai oznacza przeksztaBcenie  na . Okre[lamy funkcj h : × ’! Ai i"I równo[ci h( m, n ) = gf(m)(n). Funkcja h jest  na Ai, gdy| je[li a " Ai, to istnieje i"I i"I i " I takie, |e a " Ai. Istniej wtedy m, n " takie, |e f(m) =i (przypomijmy, |e f jest  na I) oraz gi(n) =a (funkcja gi jest  na Ai). Wynika std, |e h( m, n ) =gf(m)(n) =gi(n) =a, co pokazuje, |e h jest  na Ai. Jako obraz zbioru przeliczalnego zbiór jest przeliczalny. i"I i"I Wniosek. Zbiór liczb caBkowitych jako suma zbioru liczb naturalnych oraz przeliczalnego zbioru liczb caBkowitych ujemnych jest przeliczalny. Wniosek. Zbiór liczb wymiernych jako podzbiór zbioru × jest przeliczalny. Wniosek. Dla dowolnego przeliczalnego zbioru A oraz dowolnego n " zbiór An wszystkich funkcji z n w A jest przeliczalny. Wniosek. Dla dowolnego przeliczalnego zbioru A zbiór A" wszystkich sBów skoDczonych nad A przeliczalny. 9.2. Zbiory nieprzeliczalne Twierdzenie. (Cantora) Dla ka|dego zbioru A nie istnieje funkcja z A  na zbiór P(A). Dowód. Przypu[my, |e f : A ’!P(A) jest  na P(A). Wtedy A0 = {a " A| a " f(a)}. Skoro f jest  na P(A), to istnieje a0 " A, |e f(a0) =A0. Zatem a0 " A0 wtedy i tylko wtedy, gdy a0 " f(a0). 9. TEORIA MOCY 37 Otrzymali[my, |e a0 " A0 wtedy i tylko wtedy, gdy a0 " A0 Sprzeczno[ ta dowodzi, |e f nie mo|e by funkcj  na P(A). A wic wstpne przypuszczenie byBo faBszywe. Wniosek. Zbiór potgowy P(A) nie jest równoliczny z |adnym z podzbiorów zbioru A. Wniosek. Zbiór wszystkich podzbiorów zbioru liczb naturalnych oraz zbiór wszystkich nies- koDczonych cigów o wyrazach ze zbioru {0, 1} s zbiorami nieprzeliczalnymi. Wniosek. Nie istnieje zbiór wszystkich zbiorów. Dowód. Je[liby A byB zbiorem wszystkich zbiorów, wtedy ka|dy podzbiór zbioru A nale- |aBby do A, czyli P(A) †" A. Wtedy P(A) byBby równoliczny z pewnym podzbiorem zbioru A, co przeczy pierwszemu z wniosków mówicemu o nierównoliczno[ci zbioru potgowego P(A) ze zbiorem A. Przyjmujemy umow, |e moc zbioru wszystkich podzbiorów zbioru liczb naturalnych tj. zbioru P( ) nazywa bdziemy continuum i oznacza przez . 9.3. Porównywanie liczb kardynalnych Je[li A i B s dowolnymi zbiorami to mówimy, |e moc zbioru A jest mniejsza lub równa mocy zbioru B i piszemy |A| |B| wtedy i tylko wtedy, gdy istnieje funkcja ró|nowarto[ciowa z A w B. Ü Lemat. Je[li A <" à oraz B <" B, to istnieje funkcja ró|nowarto[ciowa z A w B wtedy i Ü tylko wtedy, gdy istnieje funkcja ró|nowarto[ciowa z à w B. Ü Dowód. Niech Õ : A ’! à oraz È : B ’! B bd bijekcjami. Wtedy, gdy f : A ’! B jest Ü Ü ró|nowarto[ciowa, to ÈfÕ-1 : à ’! B jest tak|e ró|nowarto[ciowa. Podobnie je[li g : à ’! B jest ró|nowarto[ciowa, to È-1gÕ : A ’! B jest tak|e ró|nowarto[ciowa. Mówimy, |e moc zbioru A jest mniejsza od mocy zbioru B i piszemy |A| < |B|, gdy|A| |B| oraz |B| |A|. Twierdzenie. (Lemat Banacha) Dla dowolnych funkcji f : A ’! B oraz g : B ’! A istniej zbiory A1 †" A, A2 †" A oraz B1 †" B,B2 †" B takie, |e: 1. A1 *" A2 = A, A1 )" A2 = "; 2. B1 *" B2 = B, B1 )" B2 = "; 3. f(A1) =B1; 4. g(B2) =A2. Dowód lematu Banacha zostanie przeprowadzony w oparciu o metod punktu staBego, która przedstawiona zostanie pózniej. 9. TEORIA MOCY 38 Lemat. Je[li A, A , B i B s takimi zbiorami, |e: A <" A , B <" B , A )" B = " oraz A )" B = ", to A *" B <" A *" B . Dowód. Niech f : A ’! A oraz g : B ’! B bd bijekcjami. Wtedy f *" g jest bijekcj ustalajc równoliczno[ A *" B <" A *" B . Z tego, |e f *" g jest bijekcj wynika, |e A )" B = ". Ró|nowarto[ciowo[ funkcji f *" g implikuje, |e A )" B = ". Zatrzymajmy si nad warunkami niepusto[ci przeci zbiorów A i B oraz A i B . Rozpatrz- my zbiory: A = {1, ©} oraz B = {©, »}, gdzie A *" B = {1, ©, »}. Ponadto niech A = {", } i B = {˜,  }, za[ bijekcje f i g niech maj posta: 1 ’!" © ’!   f : g : © ’! » ’! ˜ Poniewa| A *"B = {", , ˜,  }, a std ju| mamy, |e A*"B <" A *"B . Wida std istot zaBo|eD lematu. Mo|na oczywi[cie wskaza inne jeszcze przykBady niespeBniania zaBo|eD i wynikajce z tego konsekwencje. Twierdzenie. Je[li A, B i C s dowolnymi zbiorami, to 1. |A| |A|; 2. je[li |A| |B| oraz |B| |C|, to |A| |C|; 3. twierdzenie Cantora-Bernsteina: je[li |A| |B| oraz |B| |A|, to |A| = |B|. Dowód. Podpunkty 1. oraz 2. s prostymi konsekwencjami defincji mocy zbioru. Przedsta- wimy dowód cz[ci 3. Przyjmijmy, |e f : A ’! B oraz g : B ’! C s funkcjami ró|nowarto[- ciowymi. Wykorzystajmy lemat Banacha uzyskujc rozbicia zbioru A i B wpostaci A1 †" A i A2 †" A oraz B1 †" B i B2 †" B, dla których zachodz równo[ci: A1 *" A2 = A, A1 )" A2 = " (i) B1 *" B2 = B, B1 )" B2 = " (ii) f(A1) =B1 (iii) =A2 (iv) g(B2) Konsekwencj (iii) jest A1 <" B1, za[ konsekwencj (iv), |e A2 <" B2. Z równo[ci (i) i (ii) oraz z ostatniego lematu mamy, |e A <" B. Twierdzenie. Zbiór liczb rzeczywistych jest równoliczny ze zbiorem {0, 1} . Zbiór liczb rzeczywistych ma moc continuum. Dowód. Niech Õ : {0, 1} ’! bdzie okre[lona warunkiem: §# " ª# f(n) ª# ª# , je[li f-1({0}) jest nieskoDczony, ª# ¨# 2n n=1 Õ(f) = " ª# f(n) ª# ª# ª# - , je[li f-1({0}) jest skoDczony, ©# 2n n=1 Wyka|emy ró|nowarto[ciowo[ funkcji Õ. Zauwa|my, |e je[li f-1({0}) jest nieskoDczony, to Õ(f) 0. Gdy natomiast jest skoDczony, to Õ(f) < 0. ZaBó|my, |e f oraz g s dwoma cigami 9. TEORIA MOCY 39 nieskoDczonymi zawierajcymi nieskoDczenie wiele zer. Poza tym niech k bdzie najmniejsz liczb o tej wBasno[ci, |e f(k) = g(k). Przyjmijmy (bez utraty ogólno[ci), |e f(k) = 0 oraz g(k) = 1. Gdy Õ(f) = Õ(g), to odejmujc k - 1 pocztkowych wyrazów w odpowiednich szeregach dostaniemy: " " f(n) 1 g(n) = + . (v) 2n 2k 2n n=k+1 n=k=1 " 1 1 Wynika std, |e szereg po lewej stronie ma sum mniejsz od = (zawiera nies- 2n 2k n=k+1 1 koDczenie wiele zer). Z drugiej strony szereg po prawej stronie ma sum nie mniejsz ni| . Z 2k tego powodu nie jest mo|liwa równo[ (v)  dowodzi to, |e Õ(f) = Õ(g). W sytuacji, gdy f i g zawieraj jedynie skoDczenie wiele zer, to postpujemy podobnie. Wtedy szere pe lewej stronie 1 d|y do sumy nie wikszej ni| podczas, gdy szereg po prawej stronie d|y do sumu wikszej 2k 1 od (wynika to z faktu, |e g zawiera tylko skoDczenie wiele zer). Zatem i w tym przypadku 2k równo[ (v) jest mo|liwa. Oznacza to, |e przeksztaBcenie Õ jest ró|nowarto[ciowe. Poza tym |{0, 1}| | |. Aby wykaza prawdziwo[ nierówno[ci przeciwnej definiujemy przeksztaBcenie È : (0, 1) ’!{0, 1} , przyporzdkowujce ka|dej z liczb przedziaBu (0, 1) jej reprezentacj binarn. Jest to cig bi- narny f : ’!{0, 1} o tej wBasno[ci, |e je[li a " (0, 1) jest wybran liczb, to " f(n) a = . 2n n=0 Przyjmujemy ponadto umow, |e gdy rozwinicie o skoDczonej i nieskoDczonej liczbie zer, wybie- ramy to znich, które ma nieskoDczon liczb zer. Funkcja È jest ró|nowarto[ciowa, a wic |(0, 1)| |{0, 1}N|. Poniewa| wiemy, |e (0, 1) <" , to na mocy twierdzenia Cantora-Bernsteina zachodzi teza twierdzenia. 9.4. DziaBania na liczbach kardynalnych Dla rozBcznych zbiorów A i B przez moc sumy zbiorów A i B rozumiemy sum mocy: |A| + |B|. Na mocy lematu o równoliczno[ci sum zbiorów rozBcznych mamy zagwarantowan poprawno[ tej definicji tj. jej niezale|no[ od wyboru reprezentantów. Lemat. Je[li A, A , B i B s takimi zbiorami, |e: A <" A , to A × B <" A × B . Dowód. Niech dane bd bijekcje f : A ’! A oraz g : B ’! B . Funkcja h : A×B ’! A ×B okre[lona równo[ci h(a, b) = f(a), g(b) jest bijekcj. 9. TEORIA MOCY 40 Ró|nowarto[ciowo[ funkcji h wynika z ró|nowarto[ciowo[ci funkcji skBadowych f i g oraz warunku równo[ci par uporzdkowanych. Przypu[my teraz, |e h(A × B) A × B . Oznacza to istnienie przynajmniej jednej pary a , b " A × B nie majcej przeciwobrazu poprzez funkcj h. W konsekwencji nie istnieje bdz przeciwobraz elementu a poprzez funkcj f czyli f-1(a ), bdz przeciwobraz b poprzez funkcj h czyli -1(b ). Jednak |adna z tych mo|liwo[ci zaj[ nie mo|e z uwagi na definicyjne g wBasno[ci funkcji f i g. Sprzeczno[ ta oznacza, |e teza lematu zachodzi. Iloczyn mocy zbiorów A i B (bez zakBadania rozBczno[ci) tj. |A||B| definiujemy jako moc zbioru A × B. Poprawno[ tej definicji wynika z ostatniego lematu. Lemat. Je[li A, A , B i B s takimi zbiorami, |e: A <" A , to AB <" (A )B . Dowód. Niech dane bd bijekcje f : A ’! A oraz g : B ’! B . Definiujemy funkcj: Õ : AB ’! (A )B w nastpujcy sposób: dla dowolnej funkcji h : A ’! B przyjmujemy: Õ(h) =ghf-1. Funkcj odwrotn do Õ jest È : (A )B ’! AB okre[lona dla funkcji h : A ’! B równo[ci: È(h ) =g-1h f. Funkcja ta jest bijekcj na mocy twierdzenia o wBasno[ciach bijekcji. Bezpo[rednio z ostatniego lematu wynika poprawno[ nastpujcej definicji. Moc zbioru funkcji AB definiujemy jako potg mocy |A||B|. W przeszBo[ci pokazywali[my, |e zbiór wszystkich liczb caBkowitych jest przeliczalny, co oznacza, |e 5!05!0 = 5!0. Mo|na wykaza, |e je[li tylko n > 0 jest skoDczone, to 5!n = 5!0. Z 0 0 drugiej strony pokazali[my równie|, |e 25! = . DziaBania dodawania, mno|enia i potgowania liczb kardynalnych zaw|one do zbiorów skoD- czonych pokrywaj si z operacjami arytmetycznymi dodawania, mno|enia i potgowania. Twierdzenie. Dla dowolnej liczby kardynalnej |A| zachodzi nierówno[: |A| < 2|A|. Dowód. Funkcja Õ : A ’!P(A) okre[lona dla {a} "A równo[ci: Õ(a) ={a} jest funkcj ró|nowarto[ciow. Std |A| < 2|A|. Z drugiej strony twierdzenie Cantora gBosi, |e nie istnieje funkcja z A na zbiór potgowy P(A). Std |A| < 2|A|. |C| Twierdzenie. Dla dowolnych zbiorów A, B, C zachodzi równo[: |A||B| = |A||B||C|. C Dowód. Naszym celem jest pokazanie równoliczno[ci zbiorów AB oraz AB×C. Wtym C celu niech Õ : AB ’! AB×C bdzie okre[lona nastpujco: f : C ’! AB oraz dla b " B i c " C Õ(f)(b, c) =(f(c))(b). Warto zauwa|y, |e Õ(f) : B × C ’! A, za[ f(c) : B ’! A. 10. RELACJE PORZDKUJCE 41 Niech teraz È : AB×C ’! AB C oznacza funkcj, która ka|dej funkcji g : B × C ’! A przyporzdkowuje funkcj È(g) : C ’! AB tak, |e: dla dowolnego c " C funkcja (È(g)) (c) : B|toA zachodzi równo[: ((È(g))(c)) (b) =g(b, c). Wyka|emy, |e È jest funkcj odwrotn do Õ. Niech f : C ’! AB bdzie dowoln funkcj. Wtedy dla dowolnych b " B oraz c " C zachodz równo[ci: ((È(Õ))(c)) (b) =Õ(f)(b, c) =(f(c))(b). Poniewa| równo[ci te zachodz dla dowolnego b " B, to (È(Õ(f))) (c) =f(c), to za[ oznacza wobec dowolno[ci c " C, |e (Õ(È(f))) = f. Niech teraz g : B × C ’! A bdzie dowolne oraz niech dowolne bdzie b " B i c " C. Wtedy (Õ(È(g))) (b, c) =((È(g))(c)) (b) =g(b, c). Poniewa| b " B oraz c " C s dowolne, to mamy (Õ(È(g))) = g. Jest to równoznaczne z faktem bycia przez È funkcj odwrotn do Õ. Oznacza to wic, |e Õ jest bijekcj ustalajc równoliczno[. 5!0 5!0 0 5!0 0 0 Na mocy tego twierdzenia mamy równie|: = 25! =25! 5!0 =25! = 10. Relacje porzdkujce Je[li · †" A × A jest zwrotna, antysymetryczna i przechodnia, to mówimy, |e · jest relacj porzdku cz[ciowego w A, za[ par A, · nazywamy zbiorem cz[ciowo uporzdkowanym. W przypadku, gdy A, · jest zbiorem cz[ciowo uporzdkowanym, a dodatkowo relacja · jest spójna, to mówimy, |e · jest relacj porzdku liniowego, za[ par A, · nazywamy zbiorem uporzdkowanym liniowo lub te| BaDcuchem. PrzykBady. A. Je[li A jest dowolnym niepustym zbiorem to para P(A), †" jest zbiorem cz[ciowo uporzd- kowanym. B. Je[li oznacza zbiór liczb naturalnych, za[ | †" × oznacza relacj podzielno[ci w tym zbiorze okre[lon warunkiem: def m, n "| Ð!Ò! istnieje k " , |e k · m = n, to , | jest zbiorem cz[ciowo uporzdkowanym. C. Relacja †" × rozumiana jako relacja niewikszo[ci w jest relacj porzdku cz[ciowe- go, a wic , jest uporzdkowany cz[ciowo. Relacja ta jest ponadto spójna, zatem , jest liniowo uporzdkowany. 10. RELACJE PORZDKUJCE 42 Wprost z definicji relacji zawierania otrzymujemy nastpujcy wynik. Wniosek. Ka|da rodzina zbiorów wraz z relacj zawierania jest zbiorem cz[ciowo uporzd- kowanym. D. Niech dany bdzie niepusty zbiór A traktowany jak alfabet oraz niech jak poprzednio A" oznacza zbiór wszystkich sBów skoDczonych nad A. Wzbiorze A" definiujemy relacj porzdku prefiksowego. Mówimy, |e sBowo w " A" jest prefiksem sBowa u " A" i piszemy w, u " wtedy i tylko wtedy, gdy istnieje sBowo w " A", |e u = ww . Para A", jest zbiorem uporzdkowanym def cz[ciowo (formalnie mo|emy napisa tak: w, u " Ð!Ò! istnieje w " A", |e u = ww ). Dowód tej obserwacji pozostawiamy jako nietrudne wiczenie. E. Podobnie jak w przykBadzie D. symbol A oznacza alfabet, za[ A" zbiór wszystkich sBów skoDczonych nad A. ZakBadamy, |e A jest cz[ciowo uporzdkowany przez relacj . W oparciu o lx relacj porzdku cz[ciowego okre[lamy now relacj ’! dziaBajc w A". Relacj t bdziemy nazywa porzdkiem leksykograficznym nad A, i definiujemy j nastpujco: dla dowolnych lx sBów u " A" oraz w " A" mamy: w, u " ’! wtt, gdy w, u " lub gdy istnieje i < min(|w|, |u|) takie, |e w(i) <u(i) oraz dla ka|dego j <i, zachodzi w(j) =u(j). Wniosek. Porzdek leksykograficzny nad A, jest porzdkiem cz[ciowym. Gdy nato- miast A, jest zbiorem liniowo uporzdkowanym, to tak|e porzdek leksykograficzny jest po- rzdkiem liniowym. lx Dowód. Relacja ’! jest zwrotna z definicji porzdku . Zajmijmy si teraz dowodem lx lx antysymetrii. Niech w, u " ’! oraz u, w " ’!. Je[li w, u " oraz u, w " , to u = w. Gdy za[ istnieje i <min(|w|, |u|), |e w(i) <u(i) oraz dla ka|dego j < i jest w(j) =u(j), to u nie mo|e by prefiksem w, a to oznacza, |e istnieje k < min(|w|, |u|), |e u(k) <w(k) oraz dla ka|dego w(j) =u(j). Std nie jest mo|liwe ani to, |e i k, ani te|, |e k i. Sprzeczno[ ta pokazuje, |e jedynym mo|liwym przypadkiem jest taki, |e w jest prefiksem u i na odwrót. lx Oznacza to u = w, czyli relacja ’! jest antysymetryczna. lx lx lx Poka|emy, |e je[li w, u " ’! oraz u, v " ’!, to w, v " ’!. Rozpatrzmy po kolei wszystkie mo|liwo[ci: 1. w jest prefiksem u (tj. w, u " ); 2. istnieje i1 < min(|w|, |u|), |e w(i1) <u(i1) oraz dla ka|dego j <i1 jest w(j) =u(j); 3. u jest prefiksem v (tj. u, v " ); 4. istnieje i2 < min(|w|, |u|), |e w(i2) <u(i2) oraz dla ka|dego j <i2 jest w(j) =u(j). lx Je[li speBnione s warunki 1. oraz 3., to w, v " , a zatem w, v " ’!. Gdy zachodzi 1. oraz 4., to je|eli |w| i2 wtedy w, v " . W przypadku, gdy i2 < |w|, to skoro w, u " , wic w(i2) = u(i2) v(i2) oraz na wszystkich pozycjach wcze[niejszych sBowa w i u pokrywaj si (maj identyczne litery). Wynika lx std, |e w, v " ’!. Je|eli zachodz warunki 2. oaz 3., to i1 < |v| i postpujc analogicznie jak w poprzednim lx przypadku dostajemy, |e w, v " ’!. 11. KRESY ZBIORÓW. KRATY. 43 Teraz rozpatrzmy ostatni mo|liwo[, a mianowicie, |e zachodz 2. oraz 4.. Gdy i1 i2, to w(i1) u(i1) v(i1), w(i1) = u(i1) to za[ implikuje, |e w(i1) = v(i1). Dodatkowo dla j < i1 lx jest w(j) =u(j) =v(j). Fakty te Bcznie daj warunek: w, v " ’!. W przypadku, gdy i2 <i1, to postpujc podobnie jak poprzednio pokazujemy, |e i2 jest numerem pierwszego miejsca, na lx którym ró|ni si sBowa w oraz v i w(i2) v(i2). To oznacza, |e w, v " ’!. lx Poniewa| w ka|dym z rozpatrywanych przypadków wystpiBa przechodnio[ relacji ’!, to dowód przechodnio[ci jest zakoDczony. Je[li porzdek w A jest liniowy, to dla dowolnych sBów w, u z których |adne nie jest pre- fiksem drugiego, je[li i <min(|w|, |u|) jest najmniejsz tak liczb, dla której w(i) = u(i), to lx lx w, u " ’!, je[li tylko w(i) u(i); oraz u, w " ’! w przypadku przeciwnym. Wynika std, |e lx ’! jest porzdkiem liniowym. Rozpatrzmy teraz zbiór cz[ciowo uporzdkowany {0, 1}, , przy czym uporzdkowanie jest takie, |e 0 1. PrzykBadem BaDcucha wstpujcego jest cig: lx lx lx lx lx lx µ ’! 0 ’! 00 ’! . . . ’! 0k ’! 0k+1 ’! . . . podczas, gdy przykBadem BaDcucha zstpujcego jest cig: lx lx lx lx . . . ’! 0k+11 ’! 0k1 ’! . . . ’! 1. lx Zauwa|amy równie| zale|no[ 0k ’! 0n1 dla dowolnych liczb k " oraz n " . Dla porzdku przypomnijmy, |e µ jest symbolem sBowa pustego. 11. Kresy zbiorów. Kraty. Rozpatrzmy zbiory cz[ciowo uporzdkowane A, A i B, B oraz funkcj f : A ’! B. Mówimy, |e f jest monotoniczna wtt, gdy dla ka|dego x1 " A oraz x2 " A zachodzi warunek: je[li x1 A x2 to f(x1) B f(x2). Funkcj f nazywamy izomorfizmem wtt, gdy f oraz f-1 s monotonicznymi bijekcjami. Je[li A, A i B, B s izomorficzne, to piszemy A, A B, B . W ka|dym zbiorze cz[ciowo uporzdkowanym A, A relacja porzdku cz[ciowego A generuje now relacj <A†" A × A zwan relacj poprzedzania okre[lon warunkiem: a1 <A a2 wtt, gdy a1, a2 " A oraz a1 = a2 (tj. a1 A a2 i a1 = a2). A W zbiorze cz[ciowo uporzdkowanym A, A element ¥" " A nazywamy elementem najmniejszym w A, A wtt, gdy dla wszystkich a " A zachodzi warunek: A A ¥" , a " A (¥" A a). Mówimy natomiast, |e aæ% " A jest elementem minimalnym w tym zbiorze wtt, gdy nie istnieje a " A, |e a aæ%. 11. KRESY ZBIORÓW. KRATY. 44 A Element nazywamy elementem najwikszym w A, A wtt, gdy speBniony jest warunek: A A a, " A (a A ). Element aæ% nazywamy elementem maksymalnym wzbiorze A, A , gdy nie poprzedza on |adnego elementu w zbiorze A tzn. je[li nie istnieje a " A, |e aæ% " A a. OdwoBajmy si teraz do przypadków zbiorów uporzdkowanych omówionych poprzednio. W zbiorze cz[ciowo uporzdkowanym P(X), przez relacj inkluzji, elementem maksy- malnym jest zbiór X i jest to jedyny element maksymalny. Natomiast w drugim z omawianych przypadków tj. w zbiorze , | nie ma elementu maksymalnego poniewa| n|2n i n =2n dla wszystkich liczb naturalnych. Ka|dy zbiór cz[ciowo uporzdkowany A, A okre[la poprzez relacj odwrotn do A no- wy zbiór cz[ciowo uporzdkowany A, -1 . Ozbiorze A, -1 mówimy, |e okre[la w stosunku A A do A, A porzdek dualny. Dualno[ t wida midzy elementami wyró|nionymi obu porzd- A ków i tak na przykBad je[li ¥" jest elementem najmniejszym w A, A , to jest równocze[nie elementem najwikszym w A, -1 . Podobnie z elementem najwikszym w A, A . A Twierdzenie. W zbiorze cz[ciowo uporzdkowanym A, A istnieje co najwy|ej jeden element najwikszy (najmniejszy). Element najwikszy (najmniejszy) jest maksymalny (mini- malny) w tym zbiorze. A A Dowód. Przypu[my, |e oraz s elementami najwikszymi w A, A . Wtedy 1 2 A A A A równocze[nie zachodz warunki oraz , to jednak na mocy antysymetrii 1 2 2 1 A A relacji porzdku cz[ciowego A oznacza, |e = . 1 2 A ZaBó|my teraz, |e " A jest elementem najwikszym. Wprost z definicji elementu maksy- A malnego mamy, |e gdyby aæ% " A byB takim elementem, to byBoby aæ%, ale z kolei definicja A elementu najwikszego gwarantuje, |e dla wszystkich a " A, wtymdla aæ% jest a A . Dalej A ju| z antysymetrii relacji porzdku cz[ciowego dostajemy = aæ%. PrzykBad. Niech A bdzie rodzin zbiorów uporzdkowan przez relacj porzdku cz[ci- owego ‚". Rodzina A skBada si przy tym z nastpujcych zbiorów: {a, d}, {a, e}, {a, b, c}, {a, c, d}, {a, b, c, d}, {a, b, c, e}. Wzbiorze A, ‚" elementami minimalnymi s zbiory {a, d}, {a, e} i {a, b, c}, natomiast elemen- tami maksymalnymi zbiory {a, b, c, d} i {a, b, c, e}. Wida std, |e zbiór cz[ciowo uporzdko- wany mo|e mie wicej ni| jeden element minimalny i wicej ni| jeden element maksymalny. Jednocze[nie nale|y zauwa|y, |e w A, ‚" nie ma ani elementu najmniejszego, ani elementu najwikszego. Niech A, A ) bdzie zbiorem cz[iowo uporzdkowanym oraz niech X †" A(!). Wtedy: element ³ " A nazywamy ograniczeniem górnym zbioru X, je|eli dla wszystkich a " X zachodzi warunek: a A ³, natomiast element ´ " A (!) nazywamy ograniczeniem dolnym zbioru X, je|eli dla ka|dego a " A jest: ´ A a. 11. KRESY ZBIORÓW. KRATY. 45 Zwrómy uwag, |e definicje ograniczeD dolnego i górnego nie mówi, |e je[li element jest ograniczeniem dolnym czy te| górnym, to jest on co najwy|ej jeden  czy tylko jeden. Fakt ten, jak si niebawem oka|e, ma bardzo powa|ne konsekwencje. PrzykBad. Niech , | bdzie zbiorem cz[ciowo uporzdkowanym przez relacj podziel- no[ci. Ponadto, niech A = {12, 18, 30}. Ograniczeniami dolnymi zbioru A s liczby 1,2,3,6  poniewa| ka|da z nich jest dzielnikiem liczb 12, 18, 30, za[ ograniczeniami górnymi tego zbioru s 180, 360, 540, . . . , n· 180, . . ., gdy| ka|da z liczb zbioru A dzieli te liczby. Zbiór “X wszystkich ograniczeD górnych zbioru X jest oczywi[cie podzbiorem zbioru cz[- ciowo uporzdkowanego (A, A). Je[li “X ma element najmniejszy, to nazywamy go kresem górnym zbioru X i oznaczamy symbolem X (lub te| sup X i czytamy: supremum X). Po- dobnie, je[li zbiór ”X wszystkich ograniczeD dolnych zbioru X ma element najwikszy, to nazywamy go kresem dolnym tego zbioru i oznaczamy przez X (lub te| inf X (i czytamy: infimum X). PrzykBad. Jeszcze raz rozwa|my zbiór cz[ciowo uporzdkowany , | z ostatniego przy- kBadu oraz zbiór X zdefiniowany jak poprzednio. W zbiorze ograniczeD górnych tego zbioru 180, 360, 540, . . . , n· 180, . . . elementem najmniejszym jest liczba 180  bowiem wszystkie pozo- staBe s jej wielokrotno[ciami. Matomiast elementem najwikszym w zbiorze ograniczeD dolnych jest liczba 6, gdy| ka|da z liczb 1,2,3,6 dzieli liczb 6. Mamy zatem: X = 6 oraz X = 180. Zwykle elementami wyró|nionymi w zbiorze cz[ciowo uporzdkowanym A, A nazywamy elementy maksymalne i minimalne oraz elementy najmniejszy i najwikszy. Je|eli natomiast X †" A do jego elementów wyró|nionych doBczamy tak|e kresy dolny i górny. Wida z tego, |e kresy zbioru wystpuj zawsze w konte[cie przestrzeni z relacj porzdku. Mo|e si zdarzy, |e w tym samym zbiorze okre[lonych jest kilka relacji porzdku cz[cio- wego. Wtedy konieczne jest, a nie tylko wskazane, opatrywanie elementów wyró|nionych in- deksami relacji wzgldem której s one wyró|nione. Gdy za[ w zbiorze wystpuje jedna tylko relacja porzdku cz[ciowego, to mo|emy wska|nik taki zaniedba. Porzdek cz[ciowy A, A nazywamy krat wtt, gdy dla ka|dej pary elementów istniej kresy dolny i górny. Natomiast krat zupeBn nazywamy taki zbiór cz[ciowo uporzdkowany, w którym ka|dy podzbiór X †" A ma kresy dolny i górny. Twierdzenie. Dla dowolnego porzdku cz[ciowego A, A nastpujce warunki s rów- nowa|ne: 1. A, A jest krat zupeBn; 2. ka|dy podzbiór zbioru X †" A ma kres górny w A, A ; 3. ka|dy podzbór X †" A ma kres dolny w A, A . Dowód. Bezpo[rednio z definicji mamy ukBad implikacji 1. =Ò! 2. oraz 1. =Ò! 3. Zajmiemy si teraz implikacj 2. =Ò! 1. W tym celu zaBó|my, |e ka|dy podzbiór X zbioru A, A ma kres górny. Ponadto niech ”X oznacza zbiór wszystkich ograniczeD dolnych zbioru X w A, A . Umówmy si, |e aæ% = ”X. Ponadto niech x " X. Z definicji, dla dowolnego 11. KRESY ZBIORÓW. KRATY. 46 ´ " ”X jest ´ A x. Zatemx jest ograniczeniem górnym zbioru ”X. Wynika std, |e aæ% A x. Oznacza to, |e aæ% jest ograniczeniem dolnym zbioru X, bo x " X zostaB wybrany dowolnie. Z drugiej strony je[li ´ jest ograniczeniem dolnym zbioru X, to ´ " ”X. Zatem´ A aæ%. Std a0 jest najwikszym ograniczeniem dolnym zbioru X, czyli aæ% X. Podobnie dowodzimy, |e 3. =Ò! 1. PrzykBady. 1. Rozpatrzmy dowolny niepusty zbiór A. Wtedy oczywi[cie para P(A), †" jest porzdkiem cz[ciowym. Je[li A jest dowoln rodzin zbiorów nale|cych do P(A), to kresem górnym tej rodziny jest zbiór stanowicy sum jej elementów tj. A = A. Kresem dolnym rodziny A jest za[ zbiór A = A  przy zaBo|eniu, |e A = ", za[ ", gdy A = ". Wynika std, |e P(A), †" jest krat zupeBn. 2. Rozpatrzmy relacj podzielno[ci | wzbiorze . W tym przypadku nie mo|emy dla dowol- nego podzbioru mówi o istnieniu jego kresu górnego, bo jak wykazali[my w przeszBo[ci zbiór jest nieograniczony. Natomiast ka|dy niepusty podzbiór tego zbioru ma element najmniejszy. 3. Rozpatrzmy alfabet binarny {0, 1} oraz porzdek prefiksowy. Para {0, 1}", , gdzie jest symbolem porzdku prefiksowego, jest zbiorem cz[ciowo uporzdkowanym. W takim przypadku zbiór {0, 1} nie ma kresu górnego, ale ma kres dolny jest nim sBowo puste tj. {0, 1} = µ. Zatem{µ} jest jedynym prefiksem sBów 0 oraz 1. Na zakoDczenie tej cz[ci zajmiemy si jeszcze krótko porzdkiem liniowym. Przypomnijmy, |e jest to wzbogacony o warunek spójno[ci porzdek cz[ciowy. Mamy nastpujce fakty. Twierdzenie. Je[li A, A jest zbiorem liniowo uporzdkowanym oraz X ‚" A, to tak|e zbiór X, A|X jest liniowo uporzdkowany. Dowód. Skoro dla wszystkich par elementów zbioru A zachodziBy definicyjne warunki relacji porzdku liniowego, to zachodz one z definicji dla par elementów dowolnego podzbioru zbioru A Twierdzenie. Dla ka|dego elementu a0 zbioru liniowo uporzdkowanego A, A nastpu- jce warunki s równowa|ne: 1. a0 jest elementem najwikszym, 2. a0 jest elementem maksymalnym, Dowód. W zbiorze uporzdkowanym liniowo a0 jest elementem najwikszym wtedy i tylko wtedy, gdy dla ka|dego elementu a " A jest a A a0. Zatem nie istnieje takie a " A, |e a0 A a  co oznacza, |e a0 jest elementem maksymalnym. Teraz zaBó|my, |e a0 jest elementem maksymalnym i nie jest elementem najwikszym. Ozna- czaBoby to, |e a0 <A a0, bo ka|dy element a " A, w tym a0 jest jego poprzednikiem. Ta sprzeczno[ potwierdza tez. 12. TWIERDZENIA O PUNKCIE STAAYM 47 Analogicznie jak poprzednio mo|emy uzasadni prawdziwo[ nastpujcego twierdzenia. Twierdzenie. Dla ka|dego elementu a0 zbioru liniowo uporzdkowanego a, A nastpu- jce warunki s równowa|ne: 1. a0 jest elementem najmniejszym, 2. a0 jest elementem minimalnym, Na zakoDczenie bez dowodu przedstawimy bardzo istotne, z praktycznego punktu widzenia, twierdzenie. Twierdzenie. Je[li A, A jest zbiorem liniowo uporzdkowanym oraz X jest niepustym zbiorem skoDczonym, to istniej w X elementy najmniejszy i najwikszy. 12. Twierdzenia o punkcie staBym TwierdzeD takich jest kilka, my przedstawimy te, które bd istotne z punktu widzenia czekajcych nas zadaD. Na wstpie zdefiniujmy jednak pojcie, któremu s one po[wicone. Je[li A jest dowolnym niepustym zbiorem, za[ f : A ’! A dowoln funkcj, to mówimy, |e f ma w A punkt staBy wtt, gdy istnieje a " A, |e f(a) =a. Twierdzenie. (Knastera-Tarskiego) Dla kraty zupeBnej A, A oraz funkcji monotonicznej f : A ’! A funkcja ma najmniejszy punkt staBy å " A. Dowód. Oznaczmy przez à = {a " A|f(a) a} oraz niech å = Ã. Je|eli a " Ã, to å A a. Ponadto z zaBo|enia monotonoczno[ci funkcji f mamy: f(å) A f(a), za[ z definicji zbioru à mamy f(a) A a. Acznie mamy f(å) A f(a) a dla elementów Ã. Wynika std, |e f(å) jest ograniczeniem dolnym zbioru Ã. A poniewa| z zaBo|enia jest kresem dolnym, to f(å) A å. Nierówno[ ta w poBczeniu z monotoniczno[ci funkcji f daje, |e f(f(å)) A f(å). To za[ gwarantuje, |e f(å) " Ã. Std poniewa| å jest ograniczeniem dolnym z à to å A f(å). W poBczeniu z faktem, |e f(å) A å na mocy antysymetrii relacji A mamy å = f(å). Dla wykazania, |e å jest najmniejszym punketm staBym przypu[my, |e f(a ) =a . Jednak a " à oraz å A a . Zatem dowód zakoDczony. PrzykBady. Rozpatrzmy alfabet A o tej wBasno[ci, |e {0, 1} †"A. Okre[lamy funkcj f : P(A") ’!P(A") okre[lon równo[ci: f(X) ={µ}*"{0w|w " X}*"{1w|w " X} Funkcja f jest monotoniczna, a zbiór {0, 1}" jest najmniejszym punktem staBym. Dowód twierdzenia Banacha Niech f : A ’! B oraz g : B ’! A. Funkcj Õ : P(A) ’!P(A) okre[lamy równo[ci: Õ(X) =A - - f(X)). g(B 12. TWIERDZENIA O PUNKCIE STAAYM 48 Operacja dopeBniania zbioru do przestrzeni jest antymonotoniczna, bo odwraca porzdek okre[- lony w przestrzeni poprzez relacj zawierania. Wynika std, |e funkcja Õ jest monotoniczna. Niech teraz A1 bdzie punktem staBym funkcji Õ. Zbiór ten okre[la jednoznacznie pozostaBe zbiory: A2 = A \ A1, B1 = f(A1), B2 = B \ B1. Nale|y pokaza, |e A2 = (B2). Skoro g = \ B1) = \ f(A1)), g(B2) g(B g(B to A \ =A \ \ f(A1)) = Õ(A1) =A1. g(B2) g(B Dlatego =A \ A1 = A2, g(B2) a zatemA2 =  co koDczy dowód. g(B2) Dla ustalonego zbioru uporzdkowanego A, A ka|dy jego niepusty podzbiór X †" A, którego ka|de dwa elementy maj ograniczenie górne nazywamy zbiorem skierowanym. Innymi sBowy, je[li x1 " X oraz x2 " X, to istnieje x3 " X, |e x1 A x3 oraz x2 A x3. Zauwa|amy, |e zbiór skierowany jest uogólnieniem BaDcucha. Przez porzdek zupeBny rozumie bdziemy ka|dy taki zbiór uporzdkowany A, A , |e A ma element najmniejszy oraz ka|dy zbiór skierowany ma kres górny. Je[li A, A oraz B, B s porzdkami zupeBnymi, to funkcj f : A ’! B nazywamy cigB wtt, gdy f zachowuje kresy górne zbiorów skierowanych. Oznacza to, |e dla dowolnego zbioru skierowanego X ze zbioru A, A zbiór f(X) , ma kres górny w B, B , a przy tym: f ( X) = f (X). Wniosek. Je[li A, A oraz B, B s porzdkami zupeBnymi oraz f : A ’! B jest cigBa, to f jest monotoniczna. Dowód. Niech zgodnie z zaBo|eniem twierdzenia f : A ’! B bdzie cigBa. Je[li a1 A a2, to {a1, a2} jest skierowany i jego kresem górnym jest a2. Zatem f(a2) =f ( {a1, a2}) = {f(a1), f(a2)}. Wynika std, |e f(a1) B f(a2)  co oznacza zgodnie z definicj monotoniczno[ funkcji f. Wniosek. Superpozycja funkcji cigBych jest funkcj cigB. Dowód. Poniewa| w przeksztaBceniu cigBym obrazem zbioru skierowanego jest zbiór skie- rowany, to w poBczeniu z porzednim wnioskiem otrzymujemy monotoniczno[ superpozycji. Twierdzenie. Je[li A, A jest porzdkiem zupeBnym oraz f : A ’! A jest funkcj cigB, to f ma najmniejszy punkt staBy a0 oraz a0 = {fn(¥")|n " }. 13. LEMAT KURATOWSKIEGO-ZORNA 49 Dowód. Na wstpie zwrómy uwag na fakt, |e zbiór {fn(¥")| n " } jest BaDcuchem, co oznacza, |e jest zbiorem skierowanym. Jest to konsekwencj tego, |e dla dowolnego n " mamy: fn(¥") fn+1(¥"). Dowód tej zale|no[ci mo|emy przeprowadzi przez Indukcj. Je[li n = 0, to oczywi[cie ¥" jest elementem najmniejszym. Drugi krok indukcyjny jest konsekwencj zaBo|onej w twierdzeniu funkcji f. Zatem z dowolno[ci wyboru n " mamy na mocy Zasady Indukcji Matematycznej pewno[, |e fn(¥") fn+1(¥"), a w efekcie otrzymujemy, |e istnieje a0 = {fn(¥")|n " }. Ponadto: f(a0) = f ( {fn(¥")|n " }) = {fn(¥")|n " } = ({fn(¥")|n " } *"{¥"}) = {fn(¥")|n " } = a0. Powodem tego jest fakt, |e po pierwsze funkcja f jest z zaBo|enia monotoniczna, a po dru- gie dodanie elementu najmniejszego ¥" do dowolnie wybranego zbioru nie zmienia jego kresu dolnego. Zatem a0 jest punktem staBym. Nale|y teraz wykaza, |e jest to najmniejszy (w sensie relacji ) punkt staBy. Przypu[my, |e a" jest dowolnym punktem staBym czyli takim, |e f(a") =a". Znów postpujc przez indukcj wzgldem n mamy, |e fn(¥") a", dla wszystkich n " . Wy- nika std, |e a" jest ograniczeniem górnym zbioru {fn(¥")|n " }. Oznacza to w konsekwencji, |e a0 a". Std istotnie, a0 jest najmniejszym punktem staBym. 13. Lemat Kuratowskiego-Zorna Poza dowodami konstrukcyjnymi czyli takimi, w których wykazujemy istnienie obiektów opisywanych w twierdzeniu osobn grup stanowi dowody twierdzeD, w których dowodzimy istnienia postulowanego obiektu, ale nie okre[lamy wyraznie jego postaci. Takie dowody na- zywamy dowodami niekonstruktywnymi. Jednym z najwa|niejszych narzdzi dowodów niekon- struktywnych odgrywa twierdzenie Kuratowskiego-Zorna zwane w bibliografii matematycznej Lematem Kuratowskiego-Zorna. Twierdzenie. (Lemat Kratowskiego-Zorna) Ka|dy zbiór cz[ciowo uporzdkowany, którego ka|dy BaDcuch ma ograniczenie górne zawiera element maksymalny. Dowód twierdzenia zostanie przeprowadzony w przyszBo[ci. Wniosek. Ka|dy porzdek cz[ciowy mo|na rozszerzy do porzdku liniowego. Dowód. Niech A, A bdzie dowolnym zbiorem cz[ciowo uporzdkowanym. Poka|emy, |e istnieje relacja porzdku liniowego †" A2, |e A‚" . A A A Symbolem P oznaczamy zbiór wszystkich porzdków cz[ciowych l na A takich, |e ord A A A‚" l . Oznaczmy przez L BaDcuch w P (okre[lony ze wzgldu na relacj inkluzji). Gdy A ord L = ", to A= ", to A jest ograniczeniem górnym L. Przypu[cmy, |e L = ". Dla dokoDczenia dowodu wykorzystamy nastpujcy lemat. A Lemat. Je[li A jest dowolnie ustalonym zbiorem, to P jest porzdkiem cz[ciowym w ord zbiorze A. 14. DOBRE UFUNDOWANIE 50 A Z tego lematu dostajemy, |e L jest ograniczeniem górnym w P BaDcucha L. Lemat ord A Kuratowskiego-Zorna zapewnia o istnieniu elementu maksymalnego w P , który oznaczymy ord przez æ% . Porzdek ten jest liniowy. Gwarantuje to nastpujcy lemat. A Lemat. W dowolnym zbiorze A elementem maksymalnym w zbiorze wszystkich porzdków A cz[ciowych P jest porzdek cz[ciowy wtt, gdy porzdek ten jest liniowy. ord 14. Dobre ufundowanie Zbiorem dobrze ufundowanym nazywamy ka|dy zbiór cz[ciowo uporzdkowany A, A , dla którego nie istnieje w A nieskoDczony cig zstpujcy elementów tj., nie istnieje funkcja ró|nowarto[ciowa f : ’! A taka, |e dla wszystkich n " ma miejsce nierówno[: f(n+1) A f(n). Przez dobry porzdek rozumiemy porzdek liniowy dobrze ufundowany. Twierdzenie. Porzdek cz[ciowy A, A jest dobrze ufundowany wtt, gdy ka|dy niepusty podzbiór zbioru A zawiera element minimalny. Dowód. ZaBó|my, |e A, A jest zbiorem dobrze ufundowanym oraz, |e X †" A jest nie- pustym podzbiorem nie majcym elementu minimalnego. Zdefiniujemy cig f : ’! X w nastpujcy sposób: f(0) " X jest dowolnym elementem. ZaBó|my, |e f jest ju| okre[lona dla liczb k n oraz, |e dla wszystkich k < n jest f(k ) <A f(k). Wtedy f(n ) przyjmuje- my jako dowolny element zbioru X taki, |e f(n ) <A f(n). Istnienie takiego elementu f(n ) jest konsekwencj faktu, |e f(n) nie jest elementem minimalnym w X. Zatem zostaB okre[lony nieskoDczony zstpujcy cig elementów zbioru A. Sprzeczno[ ta pokazuje, |e ka|dy niepusty podzbiór zbioru A ma element minimalny. Je[li teraz f : ’! A jest nieskoDczonym zstpujcym cigiem elementów zbioru A, to f( ) jest niepustym podzbiorem A nie majcym elementu minimalnego. Jako konsekwencj twierdzenia otrzymujemy nastpujcy wniosek. Wniosek. Zbiór , liczb naturalnych z porzdkiem bdcym relacj niewikszo[ci jest dobrym porzdkiem. PrzykBad. (i) Je[li A jest dowolnym zbiorem traktowanym jak alfabet, to zbiór wszytkich sBów nad A z porzdkiem prefiksowym jest dobrze ufundowany. Mianowicie, gdyby byBo, |e w0 >w1 > . . . jest zstpujcym cigiem sBów, to wystarczy jako funkcj f wystpujc w definicji zbioru dobrze ufundowanego wzi funkcj dBugo[ci sBowa i wtedy dostajemy zstpujcy cig liczb naturalnych |w0| > |w1| > . . ., co na mocy ostatniego wniosku nie jest mo|liwe. (ii) Zbiór lx {0, 1}, ’! z porzdkiem leksykograficznym generowanym przez porzdek 0 1 nie jest dobrze ufundowany, bo cig lx lx lx lx . . . ’! 0k+11 ’! 0k1 ’! . . . ’! 1 tworzy nieskoDczony BaDcuch zstpujcy. (ii) Ka|dy skoDczony porzdek jest dobrze ufundowany. (iv) Je[li mamy dowoln rodzin zbiorów skoDczonych F, to F, †" jest dobrze ufundowany. Jest to konsekwencj faktu, |e dla skoDczonych zbiorów F1 i F2 je[li F1 F2, to |F1| < |F2|. W 15. INDUKCJA NOETHEROWSKA 51 tej sytuacji nieskoDczony zstpujcy cig zbiorów prowadziBby do nieskoDczonego zstpujcego zbioru liczb naturalnych. 15. Indukcja noetherowska Zasad Indukcji Matematycznej sformuBowan dla liczb naturalnych mo|na rozszerzy na zbiory dobrze ufundowane. Zasad t precyjzuje nastpujce twierdzenie. Twierdzenie. (Zasada indukcji noetherowskiej) Je[li A, A jest porzdkiem dobrze ufun- dowanym oraz je[li X †" A speBnia warunek: dla dowolnie wybranego a " A z tego, |e wszystkie elementy x speBniajce nierówno[ x<A a nale| do X wynika, |e a " X, wówczas X = A. Dowód. Niech A \ X = " oraz niech a0 " A \ X bdzie elementem minimalnym. Std je[li x <A a0, mamy x " X. Z zaBo|enia a0 " X. Sprzeczno[ do jakiej doszli[my pokazuje, |e A \ X = ", tj. A = P . ZaBó|my teraz, |e A, A jest porzdkiem dobrze ufundowanym. Przyjmijmy dla dowolnego a " A nastpujce oznaczenie: O(a) ={x " A : x<A a}. Zbiór O(a) nazywa bdziemy odcinkiem pocztkowym zbioru A, A . Zbiory dobrze ufundowane umo|liwiaj definiowanie funkcji przez indukcj. Mówi o tym nastpujce twierdzenie. Przyjmijmy przedtem oznaczenie: symbol PF(A, B) oznaczaB bdzie zbiór wszystkich funkcji cz[ciowych z A w B. 15. INDUKCJA NOETHEROWSKA 52 Twierdzenie. (o definiowaniu funkcji przez indukcj noetherowsk) Je[li A, A jest zbiorem dobrze ufundowanym, to dla dowolnych zbiorów B i C oraz dowolnej funkcji h : PF(A × C, B) × A × C ’! B istnieje dokBadnie jedna funkcja f : A × C ’! B speBniajca dla dowolnych x " A oraz c " C nastpujcy warunek: f(x, c) =h(f )" (O(x) × C × B), x, c). Dowód. Na wstpie poka|emy, |e dla ka|dego x " A istnieje funkcja fx : (O(x)*"{x})×C ’! B taka, |e dla dowolnych y A x i oraz c " C zachodzi równo[: (") fx(y, c) =h(fx )" (O(y) × C × B)x, c). Wykorzystamy w tym celu indukcj noetherowsk wzgldem x. ZaBó|my, |e y <A x oraz, |e fy : (O(y) *"{y}) × C ’! B jest funkcj speBniajc warunek ("). W tym celu obierzmy dowolne y1 <x oraz y2 <x. Twierdzimy, |e dla dowolnego z " A, dla którego z A y1 oraz z A y2 oraz dowolnego c " C zachodzi równo[: fy (y, c) =fy (y, c). 1 2 Jest to konsekwencj zaBo|enia indukcynego oraz zale|no[ci ("). Std g = {fy|y <A} jest funkcj o dziedzinie O(x) × C. Mo|emy zatem okre[li funkcj fx poprzez równo[: fx(y, c) =g *"{ x, h(g, y, c) }, przy czym y A x oraz c " C. Funkcja ta speBnia ("), co koDczy dowód tej cz[ci. Udowodniona wBasno[ implikuje, |e dla dowolnych x1 " A oraz x2 " A zachodzi równo[: fx (y, c) =fx (y, c) 1 2 przy y A x1, y A x2 i c " C. W konsekwencji f = {fx|x " A} jest funkcj o dziedzinie A × C. Otrzymujemy: f(x, c) =fx(x, x) =h(fx )" (O(x) × B × C), x, c) =h(f )" (O(x) × C × B), x, c). To za[ oznacza, |e twierdzenie jest prawdziwe. Skomentujmy podstawowe fakty. Otó| zbiór C, o którym mówi twierdzenie jest zbiorem parametrów. Poza tym definicja indukcyjna, o której mówi twierdzenie, sprowadza si do okre- [lenia funkcji na argumencie x w zale|no[ci od zdefiniowanej ju| cz[ci funkcji na argumentach mniejszych od x ze wzgldu na relacj <A. W przypadku, gdy x jest elementem minimalnym wzbiorze A, to teza twierdzenia redukuje si do zale|no[ci: f(x, c) =h(", x, c). Dla peBniejszego zrozumienia twierdzenia odwoBajmy si do przykBadu. PrzykBad. Rozpatrzmy funkcj konkatenacji sBów nad alfabetem X, tj. funkcj f : X" × X" ’! X". 16. DOBRE PORZDKI 53 Przypu[cmy, |e dla ka|dego a " X okre[lona jest funkcja ga : X" ’! X" taka, |e dla dowolnego sBowa w " X" jest ga(w) =aw. Niekiedy funkcja ga nazywana jest niekiedy a-tym nastpnikiem. Funkcj f okre[la ukBad równaD: f(µ, w) = w, f(au, w) = ga(f(u, w)), gdy a " X. OdwoBujc si do twierdzenia o definiowaniu przez indukcj noetherowsk mo|emy ostatni definicj zapisa w postaci sformalizowanej nastpujco: A = B = C = X" h : [PF(X" × X", X") × X" × X"] ’! X" przy czym ga(f(u , w)), gdy u = au oraz u , w "Dom(f), h(f, u, w) = w, w pozostaBych przypadkach. Wzbiorze A okre[lamy porzdek w nastpujcy sposób: je[li u " A oraz w " A, to w u wtt, gdy istnieje w " A, |e u = w w. Porzdek A, jest dobrze ufundowany poniewa| jest izomorficzny z porzdkiem prefik- sowym na zbiorze A (izomorfizm taki ustala funkcja przyporzdkowujca sBowu w jego lustrzane odbicie wR). Zwrómy uwag, |e warunki definicyjne funkcji f s równowa|ne warunkowi (") ostatniego twierdzenia. 16. Dobre porzdki W przeszBo[ci byBa ju| mowa o dobrych porzdkach, przez które rozumieli[my porzdki liniowe dobrze ufundowane. Analiz wBasno[ci takich porzdków rozpocznijmy od nastpujcego twierdzenia. Twierdzenie. Je[li A, jest zbiorem liniowym dobrze uporzdkowanym, to dla dowolnych a " A oraz b " A takich, |e a = b odcinki O(a) oraz O(b) nie s izomorficzne. Dowód. Niech b <a oraz niech f : O(a) ’!O(b) bdzie izomorfizmem. ZaBó|my, |e a " A jest najmniejszym elementem, dla którego istnieje c < a, |e O(a) oraz O(c) s izomorficzne. Zbiór O(b) jest podzbiorem wBa[ciwym zbioru O(a), to za[ oznacza, |e O(b) \ f(O(b)) = ". Przyjmijmy, |e c jest elementem najmniejszym w zbiorze O(b)\f(O(b)) = ". Zachodzi warunek: f(O(b)) †"O(c). Ze sposobu wyboru elementu c wynika, |e dla dowolnego x <A c, poniewa| x "O(b), to x " f(O(b)). Std: f(O(b)) = O(c), co oznacza, |e odcinki pocztkowe O(b) i O(c) s izomorficzne. Z zaBo|enia mamy c <A b <A a, co powoduje sprzeczno[ z wyborem elementu a. 16. DOBRE PORZDKI 54 Wniosek. {aden zbiór dobrze uporzdkowany nie jest izomorficzny ze swoim odcinkiem pocztkowym. Rozpatrzmy dwa zbiory dobrze uporzdkowane A, A oraz B, B . Ponadto niech » b- dzie elmentem nie nale|cym do zbioru B, a jednocze[nie niech B = B *"{»}. Wzbiorze B porzdek generowany jest przez porzdek w B, z tym zastrze|eniem, |e » jest elementem najwikszym w sensie B w zbiorze B . Funkcj g : A ’! B okre[limy z wykorzystaniem in- dukcji noetherowskiej. Mianowicie dla a " A przez g(a) rozumie bdziemy element najwikszy w zbiorze B \ {g(x)|x <A a}, je[li tylko zbiór ten jest niepusty. W przypadku, gdy jest on pusty, przyjmujemy, |e g(a) = ». Tak okre[lon funkcj nazywa bdziemy przeksztaBceniem kanonicznym indukowanym przez A, A oraz B, B . Przedstwiona konstrukcja bdzie przez nas wielokrotnie wykorzystywana. Warto wic grun- townie j przemy[le. Lemat 1. Je[li A, A i B, B s zbiorami dobrze uporzdkowanymi oraz g : A ’! B jest przeksztaBceniem kanonicznym indukowanym przez te zbiory, to: 1. dla ka|dego a " A, je[li g(a) = », to g(O(a)) = O(g(a)); 2. je[li a " A jest najmniejszym elementem takim, |e g(a) =», to g(O(a)) = B. Dowód. Warunek 1. dowiedziemy posBugujc si indukcj noetherowsk wzgldem a. Zwró- my uwag, |e poniewa| g(a) = », to nie jest istotne czy odcinek pocztkowy wyznaczony przez g(a) jest brany wzgldem zbioru B czy te| zbioru B . Z zaBo|enia co do funkcji g wynika, |e g(a) "{g(x)|x<A a}. Niech c bdzie dowolnym elementem odcinka O(a). Je[liby byBo g(a) <B g(c), to byBoby g(a) "O(g(c)) = g(O(c)) †"{g(x)|x<A a}, to za[ stoi w sprzeczno[ci z tym, |e g(a) " {g(x)|x <A a}. Z tego samego powodu mamy g(c) = g(a). Std g(O(a)) †"O(g(a)). Je[li teraz na odwrót przyjmiemy b <B g(a) dla pewnego b " B, to poniewa| g(a) jest naj- mniejszym elementem speBniajcym warunek g(a) " {g(x)|x <A a}, wic istnieje c <A a, |e b = g(c). Zatem b " g(O(a)), co dowodzi (i). Aby dowie[ 2. zauwa|amy, |e skoro g(»), to B †" {g(x)|x <A a} = g(O(a)). Jednak z drugiej strony mamy na podstawie zaBo|eD punktu (i) mamy, |e dla ka|dego c <A a jest g(c) " B. Ostatecznie g(O(a)) †" B. Wprost z tego lematu mamy wniosek. Twierdzenie. Dla zbiorów dobrze uporzdkowanych A, A i B, B oraz przeksztaBcenia kanonicznego g : A ’! B indukowanego przez te zbiory zachodz warunki: 1. g jest monotoniczna; 2. je[li » " to g jest ró|nowarto[ciowa; g(A), 16. DOBRE PORZDKI 55 3. je[li » " oraz a " A jest najmniejszym elementem takim, |e g(a) =», to B, B g(A) jest izomorficzny z odcinkiem pocztkowym O(a). Kolejny fakt pokazuje, |e przeksztaBcenie kanoniczne jest najmniejszym spo[ród wszystkich funkcji monotonicznych midzy dwoma ustalonymi dobrymi porzdkami. Lemat 2. Dla zbiorów dobrze uporzdkowanych A, A i B, B oraz przeksztaBcenia kanonicznego g : A ’! B indukowanego przez te zbiory dla dowolnej funkcji monotonicznej i ró|nowarto[ciowej f : A ’! B oraz dwolnego a " A zachodzi nierówno[: g(a) B f(a). W szczególno[ci wynika std, |e je[li istnieje monotoniczna i ró|nowarto[ciowa funkcja z A, A w B, B , to » " oraz g : A ’! B jest ró|nowarto[ciowa. g(A) Dowód. W pierwszym etapie dowiedziemy prawdziwo[ci nierówno[ci przez indukcj noet- herowsk wzgldem a, przy dodatkowym zaBo|eniu, |e g(a) = ». Obierzmy dowolne takie », |e g(a) = » oraz przypu[cmy, |e f(a) <B g(a). Skoro g(a) " {g(x)|x <A a}, to w oparciu o definicj funkcji g wnioskujemy, |e istnieje x <A, |e f(a) = g(x). Z zaBo|enia indukcyjne- go mamy g(x) B f(x). Zatem f(a) B f(x), a to przeczy zaBo|eniu o monotoniczno[ci i ró|nowarto[ciowo[ci funkcji f. Sprzeczno[ ta dowodzi, |e f(a) B g(a). ZaBó|my teraz, |e g(a) =» i niech a " A bdzie najmniejszym elementem o taj wBasno[ci. Z lematu 1. wynika, |e B = {g(x)|x<A a}. Istnieje wic x<A a, |e f(a) =g(x). Z wcze[niejszej cz[ci dowodu wynika, |e g(x) B f(x). Tak wic f(a) B f(x) oraz podobnie jak poprzednio dostajemy sprzeczno[. Musi wic by, |e g(a) = ». PozostaBa cz[ ostatniego lematu jest konsekwencj jego pierwszej cz[ci oraz ostatniego twierdzenia. Lemat 3. Dla zbiorów dobrze uporzdkowanych A, A i B, B oraz przeksztaBceD ka- nonicznych g : A ’! B oraz h : B ’! A indukowanych przez stosowne zbiory mamy, |e dla ka|dego a " A dla którego g(a) = », zachodzi równo[: hg(a) =a. Dowód. Lemat dowiedziemy stosujc indukcji noetherowsk wzgldem a " A speBniajce- go warunek g(a) = ». Obierzmy dowolne takie a oraz rozpatrzmy zbiór X = {h(y)|y <B g(a)}. Dowiedziemy, |e X = O(a). Przyjmijmy, |e x = h(y) dla pewnego y <B g(a). Z okre[lenia funkcji g mamy, |e istnieje z <A a dla którego y = g(z). Dlatego wykorzystujc zaBo|enie indukcyjne dostajemy: h(y) =hg(z) =z. Dlatego x<A a. Odwrotnie, je[li x <A a, to na mocy lematu 1. mamy g(x) <B g(a) oraz z zaBo|enia indukcyjnego x = hg(x). Std x " X. To koDczy dowód równo[ci X = O(a). Ostatecznie A\ X = " i hg(a) jest elementem najmniejszym w tym zbiorze. Elementem tym jest oczywi[cie a. 17. LICZBY PORZDKOWE 56 17. Liczby porzdkowe Podobnie jak liczby kardynalne s pewnymi obiektami przyporzdkowanymi zbiorom rów- nolicznym wedBug wcze[niej omówionej zasady, tak liczby porzdkowe s obiektami przyporzd- kowanymi zbiorom dobrze uporzdkowanym. Mianowicie liczby te reprezentuj klasy dobrych porzdków izomorficznych. Zauwa|my, |e izomorfizm zbiorów dobrze uporzdkowanych jest zjawiskiem zwrotnym, sy- metrycznym i przechodnim jednak nie mo|emy powiedzie, |e jest to relacja równowa|no[ci. Podobnie jak to miaBo miejsce w przypadku liczb kardynalnych równie| w przypadku liczb porzdkowych poprawnie jest mówi o klasie zbiorów, które konkretna liczba porzdkowa re- prezentuje ni| o pewnej cesze klasy abstrakcji relacji równowa|no[ci okre[lonej przez izomor- fizm zbiorów. Jak Batwo zgadn, powodem jest dowiedziony wcze[niej fakt nieistnienia zbioru wszystkich zbiorów. Do jednej klasy zbiorów dobrze uporzdkowanych nale| zatem dwa dobre porzdki, wtedy i tylko wtedy, gdy istnieje izomorfizm midzy tymi porzdkami. Mówimy wtedy, |e porzdki te maj t sam liczb porzdkow. Zatem liczba porzdkowa ± lub inaczej typ porzdkowy ± zbioru dobrze uporzdkowanego A, A jest to obiekt charakteryzujcy nie tylko zbiór dobrze uporzdkowany A, A , ale wszystkie zbiory dobrze uporzdkowane izomorficzne z nim. Pi- szemy wtedy A, A = ±. Przyjmujemy przy tym umow, |e je[li n jest liczb naturaln, to dobremu porzdkowi n, odpowiada liczba porzdkowa n. Je[li natomiast , , to liczb porzdkow tego zbioru jest omega tj. É. Na liczbach porzdkowych mo|emy okre[li dziaBanie dodawania wedBug nastpujcych za- sad: (i) je[li A, A oraz B, B s dobrymi porzdkami o liczbach porzdkowych odpowiednio ± i ², to liczba porzdkowa charakteryzuje porzdek bdcym rozszerzeniem porzdków A oraz B w taki sposób, |e wszystkie elementy zbioru A s mniejsze od elementów zbioru B  w nowym porzdku. Zwykle dokonuje si zaBo|enia, |e zbiory A i B s rozBczne. (ii) Dodawanie liczb porzdkowych nie jest dziaBaniem przemiennym. Dla przykBadu 1 + É = É, natomiast É +1 = É. Powodem tego jest fakt, |e É + 1 reprezentuje porzdek w elementem najwikszym, natomiast É porzdek bez elementu najwikszego. Izomorfizm przeprowadza po- nadto element najwikszy na element najwikszy. W przypadku liczb porzdkowych skoDczonych dodawanie tych liczb ma identyczne wBas- no[ci jak dodawanie liczb naturalnych. Je[li A, A oraz B, B s dobrymi porzdkami o liczbach (typach) porzdkowych ± oraz ², to mówimy, |e ± jest mniejsza lub równa od ² (piszemy zwyczajnie ± ²) wtt, gdy istnieje monotoniczna i ró|nowarto[ciowa funkcja f : A ’! B. Przyjmujemy, |e ±<² wtt, gdy ± ² oraz A, A i B, B nie s izomorficzne. Twierdzenie. Je[li A, A oraz B, B s zbiorami dobrze uporzdkowanymi o typach od- powiednio ± i ², to: ±<² wtt, gdy A, A jest izomorficzny z pewnym odcinkiem pocztkowym zbioru B, B . Dowód. Ko n i e c z n o [ . Przyjmijmy, |e g : A ’! B jest przeksztaBceniem kanonicz- nym indukowanym przez zbiory dobrze uporzdkowane A, A i B, B . Funkcja g jest ró|- nowarto[ciowa na podstawie wcze[niejszego twierdzenia (» nie nale|y do a w takim przy- g(A), 17. LICZBY PORZDKOWE 57 padku twierdzenie gwarantuje ró|nowarto[ciowo[). Ró|no[ typów porzdkowych i zaBo|enie ±<² oznacza, |e g nie mo|e by  na B. Niech teraz b " B \ oznacza najmniejszy element w tym zbiorze. Chcemy pokaza, |e g(A) ("). =O(b) g(A) Niech a " A bdzie dowolnym elementem. Je[liby b <B g(a), to istniaBoby x<A a, |e b = g(x)  mimo, |e wybór elementu b temu przeczy. Dlatego g(a) <B b, a w konsekwencji g(a) "O(b). Odwrotnie, je[li c <B b, to ze sposobu wyboru b mamy c " Zatem równo[ (") jest g(A). dowiedziona. Z warunku (") wynika, |e jest izomorficzny z O(b). g(A) Do s t a t e c z n o [ . Je[liby A, A oraz B, B byBy izomorficzne, to B, B byBby z kolei izomofriczny ze swoim odcinkiem pocztkowym. Temu za[ przeczy wcze[niejsze twier- dzenie. Twierdzenie Cantora. Je[li A, A oraz B, B s zbiorami dobrze uporzdkowanymi o typach porzdkowych ± i ², a przy tymje[li ± ² i ² ±, to ± = ². Dowód. Niech g : A ’! B oraz h : B ’! A bd kanonicznymi przeksztaBceniami in- dukowanymi przez A, A oraz B, B . Z wcze[niejszego lematu wynika, |e » " (A) oraz g » " h(B). Inny wcze[niejszy lemat gwarantuje, |e g oraz h s izomorfizmami. Twierdzenie. (prawo trichotomii dla liczb porzdkowych) Je[li ± i ² s dowolnymi liczbami porzdkowymi, to zachodzi jedna z nastpujcych mo|liwo[ci: (i) ±<², (ii) ±>², (iii) ± = ². Dowód. Z wcze[niejszych spostrze|eD wnioskujemy, |e |adne dwa przypadki nie mog zacho- dzi równocze[nie. Poka|emy, |e musi zaj[ dowolnie wybrany. W tym celu obierzmy zbiory A, A oraz B, B o typach porzdkowych odpowiednio ± i ². Niech nastpnie g : A ’! B oraz h : B ’! A bd kanonicznymi przeksztaBceniamim indukowanymi przez zbiory A, A oraz B, B . Z twierdzenia poprzedzajcego lemat 2. mamy, |e je[li » " to ± ², a wic (i) lub g(A), (ii). Analogicznie je[li » " h(B), to ² ± oraz zachodzi (i) lub (iii). Je[li natomiast » " g(A), to zachodzi (ii). Gdy jest, |e » " h(B), to (i). Twierdzenie. Ka|dy zbiór liczb porzdkowych jest dobrze uporzdkowany przez relaj . Dowód. Je[li Z jest dowolnie ustalonym zbiorem liczb porzdkwoych, to z twierdzenia Can- tora oraz prawa trichotomii dla liczb porzdkowych wynika, |e Z jest liniowo uporzdkowany. Niech ±1 > ±2 > . . . bdzie nieskoDczonym BaDcuchem zstpujcym w Z. Przyjmijmy ponadto, |e dla wszystkich i 0 jest A, A = ±i. Chcemy pokaza, |e dla dowolnego i >0 istnieje ai " A0, |e odcinek pocztkowy O(ai) jest izomorficzny z Ai oraz, |e ai+1 <A ai. 0 WBasno[ t dowiedziemy poprzez indukcj prowadzon wzgldem i. Skoro a1 <a0, to na mocy wcze[niejszego twierdzenia wiemy, |e istnieje a1 " A0, |e A, A jest izomorficzny z O(a1). Niec teraz i >1. Postpujc podobnie znajdziemy c " Ai-1, Ai, A jest izomorficzny z i O(c). Z zaBo|enia indukcyjnego wiadomo, |e Ai-1, A jest izomorficzny z O(ai-1) †" A0. i-1 Niech ai " O(ai-1) bdzie elementem bdcym obrazem c w tym izomorfizmie. Z wBasno[ci 17. LICZBY PORZDKOWE 58 izomorfizmu wiemy, |e odcinek pocztkowy przechodzi w przeksztaBceniu izomorficznym na odcinek pocztkowy. Std odcinki O(c) oraz O(ai) s izomorficzne. Wynika std, |e Ai, A i jest izomorficzny z O(ai). ZostaB zatem zdefiniowany nieskoDczony zstpujcy cig w A0, A . Uzyskali[my sprzecz- 0 no[, co oznacza, |e Z jest dobrze uporzdkowany. 17.1. Twierdzenie Zermelo Twierdzenie Zermelo Ka|dy zbiór mo|na dobrze uporzdkowa tj. dla ka|dego zbioru A istnieje relacja dobrego porzdku na A. Dowód. Je[li R jest zbiorem wszystkich par X, r o tej wBasno[ci, |e X †" A oraz r jest dobrym porzdkiem w X. Ponadto niech Z bdzie zbiorem wszystkich liczb porzdkowych odpowiadajcych elementom zbioru R. Poniewa|, jak gBosi ostatnie twierdzenie, ka|dy zbiór liczb porzdkowych jest dobrze uporzdkowany przez relacj , to równie| Z, jest takim zbiorem. Okre[lmy funkcj f : Z ’! A poprzez indukcj noetherowsk. ZaBó|my, |e a0 " A jest dowolnie ustalonym elementem. Je[li ± " Z, to jako warto[ f(±) przyjmujemy dowolny element zbioru A \ {f(²)| ² < ±}  je[li tylko zbiór ten jest niepusty. Gdy {f(²)|² < ±} = A, to przyjmujemy f(±) =a0. Chcemy pokaza, |e f(Z) =A. Je[li zaBo|ymy, |e X = f(Z) = A, to bezpo[rednio z definicji funkcji f otrzymujemy, |e f jest ró|nowarto[ciowa, a wic w zbiorze X mo|na okre[li dobry porzdek r, indukowany przez porzdek w Z. Porzdek ten jest izomorficzny z Z, . PoBó|my, |e Z, = ³. Skoro Z, " R, to ³ " Z, a wic O(³) †" Z. Oznacza to, |e Z byBby izomorficzny ze swoim odcinkiem pocztkowym. Jest to jednak sprzeczne z wcze[niej dowiedzionym twierdzeniem, a wic przypuszczenie byBo faBszywe. Zatem prawd jest, |e f(Z) =A. Je|eli istnieje ± " Z, |e {f(²)|² < ±} = A, to niech ± bdzie najmniejsz liczb o tej wBasno[ci. Wtedy funkcja f ograniczona do O(±) jest ró|nowarto[ciowa i skoro f(O(±)) = A, to indukuje ona dobry porzdek na zbiorze A. Je|eli dla ka|dego ± " Z jest {f(²)|² <±} = A, to f jest ró|nowarto[ciowa i z tego, |e f(Z) =A wynika i| tak|e w tym przypadku f indukuje dobry porzdek na A. Bezpo[redni konsekwencj twierdzenia Zermelo i prawa trichotomii dla liczb porzdkowych mamy nastpujcy twierdzenie. Twierdzenie. Dla dowolnych zbiorów A i B bdz |A| |B|, bdz te| |B| |A|. Dowód. Zbiory A i B mo|na dobrze uporzdkowa. Je[li ± i ² s typami porzdkowymi tych zbiorów, to na mocy prawa trichotomii dla liczb porzdkowych jest ± ² lub te| ² ±. W pierwszym przypadku jest |A| |B|, za[ wdrugim|B| |A|. 17. LICZBY PORZDKOWE 59 17.2. Dowód lematu Kuratowskiego-Zorna Dowód. Przypu[my, |e A, A jest porzdkiem cz[ciowym, w którym ka|dy BaDcuch ma graniczenie górne. Poka|emy, |e A zawiera element maksymalny. Przyjmijmy, |e Z jest dowolnym zbiorem o mocy wikszej ni| A i niech oznacza dobry porzdek w zbiorze Z, którego istnienie gwarantuje twierdzenie Zermelo. Zdefiniujemy funkcj f : Z ’! A przez indukcj noetherowsk. Niech z " Z i niech X = {f(u)| z"Z}. Z zaBo|enia indukcyjnego wynika, |e X jest BaDcu- chemm, a zatem ma ograniczenie górne. Je|eli X ma jakie[ ograniczenie górne a pochodzce ze zbioru A \ X, to definiujemy f(z) = a, gdzie a jest dowolnie wybranym elementem o tej wBasno[ci. W przeciwnym przypadku X zawiera swoje wBasne ograniczenie górne, które musi by elementem najwikszym w X. KBadziemy wtedy f(z) =a. Poniewa| |Z| > |A|, to funkcja f nie mo|e by ró|nowarto[ciowa. Istnieje zatem z0 " Z, |e dla wszystkich z, je|eli z0 z" z, to f(z0) =f(z). Z definicji funkcji f wynika, |e f(z0) jest elementem maksymalnym w A, A . Zatem lemat Kuratowskiego-Zorna jest dowiedziony. Tak lemat Kuratowskeigo-Zorna jak i twierdzenie Zermelo wymagaj dla dowodu nowego aksjomatu, zwanego aksjomatem wyboru. Aksjomat ten gBosi, |e dla ka|dej niepustej rodziny zbiorów istnieje funkcja, która ka|demu zbiorowi przyporzdkowuje pewien element tego zbio- ru. Funkcj t nazywa si funkcj wyboru. Okazuje si, |e pewnik wyboru jest równowa|ny twierdzeniu Zermelo oraz lematowi Kuratowskiego-Zorna, na gruncie pozostaBych aksjomatów teorii mnogo[ci. Wcze[niej mówili[my o niekonstruktywno[ci dowodu. Otó| oba wymienione twierdzenia maj dowody niekonstruktywne tj. dowodzi si istnienia obiektu nie pokazujc jak obiekt ten wyglda, a [ci[lej, jak mo|na go otrzyma.

Wyszukiwarka

Podobne podstrony:
Logika i teoria mnogości
Teoria kary skrypt
Teoria mnogosci
Teoria mnogości
Teoria mnogosci zadania [Part 01 dvi]
Teoria Mnogości 1
Zadania Logika i teoria mnogosci
TEORIA LITERATURY WAŻNE Skrypt Z 48 Formalizm rosyjski
TEORIA LITERATURY WAŻNE Skrypt Z 44 Literatura i teatralna koncepcja dramatu
TEORIA LITERATURY WAŻNE Skrypt Istota dzieła lirycznego
TEORIA LITERATURY WAŻNE Skrypt Ingarden
TEORIA LITERATURY WAŻNE sKRYPT 1 Katharsis i mimesis w Poetyce Arystotelesa
TEORIA LITERATURY WAŻNE Skrypt Z 43 Literackie struktury rodzajowe (epika, liryka, dramat)
TEORIA LITERATURY WAŻNE Skrypt Z 47 Hermeneutyka
TEORIA LITERATURY WAŻNE Skrypt Arystoteles etc
TEORIA LITERATURY WAŻNE Skrypt Z 46 Strukturalizm (w badaniach literackich)
TEORIA LITERATURY WAŻNE Skrypt Z 2 Epos i tragedia w Poetyce Arystotelesa

więcej podobnych podstron