Teorija skupova

Vježbe

Radna verzija!

(10. siječnja 2006.)

Vedran Čačić

Sadržaj

Dio 1. Uvod 5

Poglavlje 1. Par logičkih napomenâ 6 1. Implikacija 6 2. Ostalo 6

Poglavlje 2. Operacije sa skupovima 7 1. Osnovne operacije, odnosi, zadavanje 7 2. Familije skupova. Generalizirani presjek i unija 8 3. Zadaci 9 4. Još zadataka s generaliziranim unijama i presjecima 10

Poglavlje 3. Funkcije 11 1. Uredeni parovi i Kartezijevi produkti 11 2. Injekcije, surjekcije, bijekcije 13 3. Primjeri 14 4. Zadaci 14

Dio 2. Kardinalni i ordinalni brojevi 17

Poglavlje 4. Beskonačna kombinatorika 18 1. Ekvipotentni skupovi 18 2. Primjeri 19 3. Računanje s kardinalnim brojevima 21 4. Kardinalni brojevi još nekih skupova 24 5. Primjeri iz analize 27

Poglavlje 5. Relacije i uredaji 30 1. Osnovno o relacijama 30 2. Parcijalni uredaji 31 3. Primjeri 34 4. Totalno uredeni skupovi. Sličnosti 37 5. Invarijante sličnosti 40 6. Nekoliko težih zadataka 44 7. Uredajni tipovi i karakterizacije 46 8. Računanje s uredajnim tipovima 47

Poglavlje 6. Ordinali 50 1. Motivacija i pregled 50

SADRŽAJ 4

2. Dobro uredeni skupovi 51

Dio 1

Uvod

POGLAVLJE 1 Par logičkih napomenâ

1. Implikacija

p → q ⟺ ¬p ∨ q Implikacija nije ništa drugo nego disjunkcija (kojoj je prvi član negiran); dakle, samo u jednom slučaju je lažna: ⊤ → ⊥ ⟺ ⊥. Preostale tri mogućnosti su istinite.

Negacija implikacije: ¬(p → q) ⟺ p ∧ ¬q

Obrat i kontrapozicija: p → q ⇍⇒^{opć.} q → p ⟺ ¬p → ¬q

2. Ostalo

Jedinstvenost: ∃!xφ(x) : ⟺ ∃x∀y(φ(y) ↔ x = y)

Poredak kvantifikatorâ je bitan: ∃∀ ⟹ ∀∃, ali obrat općenito ne vrijedi.

Slobodne nastupe varijablî ne smijemo preimenovati, dok vezane smijemo:

• ∃x(x ∈ y) ⟺ ∃z(z ∈ y) ⟺ y ≠ ∅

• to nije isto što i ∃x(x ∈ z) (z nije prazan)

• takoder, ∃x(x ∈ x) je nešto sasvim treće: “postoji objekt koji je element samog sebe”

Rješavanje jednadžbi možemo shvatiti kao pojednostavljivanje izraza za odredeni skup: npr. \{x ∈ ℝ : \frac{x−1}{x+1} ≤ 0\} je samo kompliciranije ime za ⟨−1, 1].

POGLAVLJE 2 Operacije sa skupovima

1. Osnovne operacije, odnosi, zadavanje

\underline{Napomena:} Za većinu matematičkih teorijâ, skupovi su sekundarni objekti. Na primjer, u realnoj analizi, primarni objekti su realni brojevi i označuju se obično malim slovima, dok su skupovi uglavnom skupovi brojeva i označuju se velikim slovima. No u teoriji skupova, skupovi su primarni objekti, i prirodno ih je označavati i malim slovima ako treba (velika slova onda možemo koristiti za skupove skupova, skupove skupova skupova, itd.).

Ako su a i b skupovi, možemo definirati nove skupove pomoću njih:

• a ∩ b := {x : x ∈ a ∧ x ∈ b} — presjek
• a ∪ b := {x : x ∈ a ∨ x ∈ b} — unija
• a \ b := {x : x ∈ a ∧ x ∉ b} — razlika

• a△b := (a ∪ b) \ (a ∩ b) = (a \ b) ∪ (b \ a) — simetrična razlika

kao i neke odnose izmedu njih:

• a ⊆ b : ⟺ ∀x(x ∈ a → x ∈ b) — podskup

• Princip ekstenzionalnosti:

a = b : ⟺ ∀x(x ∈ a ↔ x ∈ b) ⟺ a ⊆ b ∧ b ⊆ a — jednakost (Važno: za skupove se ∈ smatra osnovnom relacijom — pomoću nje se može definirati čak i jednakost)

• a ⊂ b : ⟺ a ⊆ b ∧ a ≠ b — pravi podskup

Za skupovne operacije vrijede brojni zakoni:

• Komutativnost i asocijativnost presjeka, unije, i simetrične razlike

• Idempotentnost presjeka i unije: ⋆ ∪ ⋆ = ⋆ ∩ ⋆ = ⋆

• Distributivnost presjeka prema uniji, i unije prema presjeku • Distributivnost presjeka prema simetričnoj razlici — ostale

distributivnosti ne vrijede općenito

Dokažite ih za DZ — ono što ne vrijedi opovrgnite kontraprimjerom!

\underline{Napomena:} U teoriji skupova su skupovi skupova uobičajena stvar. Štoviše, kao što ćemo kasnije vidjeti, svi elementi skupova su zapravo skupovi.

P(a) := {x : x ⊆ a} — partitivni skup od a Primijetimo, x ∈ P(a) ⟺ x ⊆ a.

Zadavanje skupova:

• nabrajanjem elemenata — zgodno za konačne skupove (poput {π, e, γ}); primjenjivo i za beskonačne, ali treba osigurati dovoljno elemenata za razumijevanje strukture skupa (npr. ℕ = {0, 1, 2, 3, …} — da, u teoriji skupova smatramo 0 ∈ ℕ)

• svojstvom — vrlo općenito definiranje, čak preopćenito za neke svrhe: na taj način definirane “klase” ne moraju uopće biti skupovi (npr. {x : x ∉ x} nije skup — Russell); ipak, u slučaju “vadenja” elemenata s nekim svojstvom iz skupa, uvijek dobivamo skup (npr. {x : x ∈ ℂ ∧ x^{2} = −1} — često se piše skraćeno kao {x ∈ ℂ : x^{2} = −1})

• kao slika neke funkcije na nekom skupu; na primjer, {x^{2} : x ∈ ℚ} je dobro zadan skup — primijetimo da nismo morali specificirati iz kojeg su skupa ovi x^{2}.

2. Familije skupova. Generalizirani presjek i unija

Kao što rekosmo, skupovi skupova su uobičajena pojava u teoriji skupova. Ako je a skup čiji su elementi skupovi, vrijedi a = {b : b ∈ a}. Unija svih b-ova koji su u a je takoder tada skup, definiran s

⋃ a := ⋃_{b∈a} b := {x : ∃b(b ∈ a → x ∈ b)}

Primijetimo, x ∈ ⋃ a ⟺ ∃b(x ∈ b ∈ a).

Specijalno, ako je a dvočlani skup a = {r, s}, tada je ⋃ a = r ∪ s — dokažite!

Takoder, ako a nije prazan (sadrži bar jedan element), presjek svih elemenata od a je takoder skup, definiran s

⋂ a := ⋂_{b∈a} b := {x : ∀b(b ∈ a → x ∈ b)}

Analogno, ⋂{r, s} = r ∩ s.

Po uzoru na oznaku ⋃_{b∈a} b, možemo napraviti i ⋃_{b∈a} f(b), gdje je f bilo kakva skupovna funkcija (npr. P na odgovarajućem skupu) — prvo napravimo skup s := {f(b) : b ∈ a} (slika funkcije f na skupu a), a onda je traženi skup upravo ⋃ s.

Često se tada oznake sugestivno promijene: b se zove indeks ι, a se zove skup indeksa I, dok se vrijednost f(ι) općenito označava s A_{ι}. Skup {A_{ι} : ι ∈ I} (ponekad i sama funkcija ι ↦ A_{ι} restringirana na I) tada se zove familija skupova. Imamo

x ∈ ⋃_{ι∈I} A_{ι} ⟺ ∃ι ∈ I(x ∈ A_{ι})

3. Zadaci

(1) Je li P(a) ∩ P(b) = P(a ∩ b)?

\underline{Rj.:} Jest. Za proizvoljan x, dokažimo da je x ∈ P(a) ∩ P(b) ↔ x ∈ P(a ∩ b). To se naravno svodi na x ⊆ a ∧ x ⊆ b ↔ x ⊆ a ∩ b, što se lako dokaže.

(2) Je li P(a) \ P(b) = P(a \ b)?

\underline{Rj.:} Nije (nikada), jer ∅ ∈ P(⋆) za svaki ⋆. Dakle ∅ je element desne strane, a nije element lijeve.

(3) Je li P(a) ∪ P(b) = P(a ∪ b)?

\underline{Rj.:} Općenito nije, npr. za a := \{1\} ∧ b := \{2\}. Ponekad jest, npr. kad je a ⊆ b.

(4) P(a) = P(b) ⟺ a = b — DZ

(5) Vrijedi li a ∈ b ⟺ P(a) ∈ P(b)?

\underline{Rj.:} Jedan smjer vrijedi: ako je P(a) ∈ P(b), to znači P(a) ⊆ b, pa su svi elementi od P(a) ujedno u b. Budući da je a ∈ P(a) (a je jedan takav), vrijedi a ∈ b. Drugi smjer ne vrijedi: na primjer, za a := {1} ∧ b := {{1}}.

(6) ∀a({∅, {∅}} ∈ PPP(a))

\underline{Rj.:} Znamo ∅ ∈ P(⋆), dakle specijalno ∅ ∈ P(a). To znači {∅} ⊆ P(a) (jer su svi njegovi elementi u P(a)), odnosno {∅} ∈ PP(a). Takoder iz ∅ ∈ P(⋆) za ⋆ := P(a) imamo ∅ ∈ PP(a), što zajedno s gornjim daje da su svi elementi od {∅, {∅}} u PP(a). Dakle, {∅, {∅}} je podskup od PP(a), odnosno element od PPP(a).

(7) Izračunajte P(∅) ∩ PP(∅) ∩ PPP(∅).

\underline{Rj.:} Budući da je prvi operand P(∅) = \{∅\}, a ∅ se, znamo, nalazi i u ostalim P-ovima, presjek je upravo {∅}.

(8) Što su ⋂ a i ⋃ a ako je a jednočlan? Što je ⋃ ∅? \underline{Rj.:} (⋃\{⋆\} = ⋂\{⋆\} = ⋆ ∧ ⋃ ∅ = ∅)

(9) Za proizvoljan skup a, kakvi odnosi vrijede izmedu a, ⋃ P(a) i P(⋃ a)? \underline{Rj.:} a = ⋃ P(a) ⊆ P(⋃ a). Dokažimo prvu jednakost. Trebamo dokazati a ⊆ ⋃ P(a) i ⋃ P(a) ⊆ a. Za prvu inkluziju, uzmimo proizvoljni x ∈ a.

4. JOŠ ZADATAKA S GENERALIZIRANIM UNIJAMA I PRESJECIMA 10

Budući da je a ∈ P(a), dobivamo da postoji b((= a)) ∈ P(a) takav da je x ∈ b, odnosno x ∈ ⋃ P(a). Za drugu inkluziju, neka je x ∈ ⋃ P(a). To znači ∃r(r ∈ P(a) ∧ x ∈ r). No r ∈ P(a) znači r ⊆ a, pa x ∈ r povlači x ∈ a. Za a ⊆ P(⋃ a), neka je x ∈ a proizvoljan. Svaki element od x je time ujedno element od ⋃ a, pa je x ⊆ ⋃ a, odnosno x ∈ P(⋃ a). Inkluzija P(⋃ a) ⊆ a općenito ne vrijedi, jer ∅ ne mora nužno biti element od a (npr. za a := ∅). ((Može se i kardinalnim argumentom.))

4. Još zadataka s generaliziranim unijama i presjecima

Dokažimo distributivnost:

⋃_{i∈I} A_{i} ∩ ⋃_{j∈J} B_{j} = ⋃_{i∈I} ⋃_{j∈J}(A_{i} ∩ B_{j})

\underline{Rj.:} Ako je x ∈ ⋃_{i∈I} A_{i} ∩⋃_{j∈J} B_{j}, to znači x ∈ ⋃_{i∈I} A_{i} i x ∈ ⋃_{j∈J} B_{j}. Ovo prvo znači da postoji i_{0} ∈ I takav da je x ∈ A_{i_{0}}, a ovo drugo da postoji j_{0} ∈ J sa svojstvom x ∈ B_{j_{0}}. To dvoje daje x ∈ A_{i_{0}} ∩ B_{j_{0}}. Sad idemo unatrag: postoji j_{0} ∈ J takav da je x ∈ A_{i_{0}} ∩ B_{j_{0}}, znači da je x ∈ ⋃_{j∈J} A_{i_{0}} ∩ B_{j}. Budući da to vrijedi za neki i_{0} ∈ I, imamo x ∈ ⋃_{i∈I} ⋃_{j∈J}(A_{i} ∩ B_{j}). Za drugi smjer, x ∈ ⋃_{i∈I} ⋃_{j∈J}(A_{i} ∩ B_{j}) znači da, kao gore, postoje i_{0} ∈ I i j_{0} ∈ J takvi da je x ∈ A_{i_{0}} ∩ B_{j_{0}}. No sada iz x ∈ A_{i_{0}} možemo zaključiti x ∈ ⋃_{i∈I} A_{i}, a jednako tako iz x ∈ B_{j_{0}} možemo zaključiti x ∈ ⋃_{j∈J} B_{j}. To dvoje zajedno daje x ∈ ⋃_{i∈I} A_{i} ∩ ⋃_{j∈J} B_{j}, što smo i trebali.

Vrijedi i druga (dualna) distributivnost,

⋂_{i∈I} A_{i} ∪ ⋂_{j∈J} B_{j} = ⋂_{i∈I} ⋂_{j∈J}(A_{i} ∪ B_{j})

\underline{Rj.:} Za dokaz, prvo uzmimo x ∈ ⋂_{i∈I} A_{i} ∪ ⋂_{j∈J} B_{j}. To znači x ∈ ⋂_{i∈I} A_{i} ili x ∈ ⋂_{j∈J} B_{j}. Tvrdnja je simetrična zamjenom A-ova i B-ova (te I i J), pa BSOMP ovo prvo. Dakle, x je u svim A_{i}-ovima. No to znači da se za proizvoljni j, x nalazi i u A_{i} ∪ B_{j}, odnosno x ∈ ⋂_{j∈J} A_{i} ∪ B_{j} za svako i ∈ I, što smo i trebali. Ako je x element desne strane, imamo da za sve mogućnosti i ∈ I i j ∈ J, vrijedi x ∈ A_{i} ili x ∈ B_{j}. Ako je x u svim A_{i}-ovima, imamo tvrdnju. U suprotnom, recimo x ∉ A_{i_{0}}, i pogledajmo sve skupove oblika A_{i_{0}} ∪ B_{j} (za sve j ∈ J). x je u svima njima, a nije u A_{i_{0}}, dakle je u svim B_{j}-ovima, i opet imamo tvrdnju.

POGLAVLJE 3 Funkcije

1. Uredeni parovi i Kartezijevi produkti

Za skupove x i y, definiramo ureden par (x, y) kao skup {{x}, {x, y}}. Glavno svojstvo uredenih parova je:

(a, b) = (c, d) ⟺ a = c ∧ b = d

Dokažimo to! \underline{Rj.:} Smjer (⇐) je trivijalan, jednom kad primijetimo da su skupovi u potpunosti odredeni svojim elementima: tvrdnju “ako je x = x′ i y = y′, tada je {x, y} = {x′, y′} primijenimo dva puta. Za drugi smjer, treba više pisati. Imamo da je svaki element od (a, b) takoder element od (c, d). Ti elementi su {a} i {a, b}. To što je {a} ∈ (c, d) znači {a} = {c} ili {a} = {c, d}. U prvom slučaju je a = c, a u drugom je a = c = d, dakle u svakom slučaju a = c. Sada iz {a, b} ∈ (c, d) slično, i koristeći već dokazano a = c, dobijemo b = d.

Projekcije (x i y) se iz uredenog para (x, y) mogu dobiti pomoću skupovnih operacijâ:

(1) ⋃ ⋂(x, y) = ⋃({x} ∩ {x, y}) = ⋃{x} = x
(2) ⋂ ⋃(x, y) = ⋂{x, y} = x ∩ y
(3) ⋃ ⋃(x, y) = x ∪ y
(4) ⋂ ⋃(x, y) ∪ (⋃ ⋃(x, y) \ ⋃ ⋂(x, y)) =

= (x ∩ y) ∪ ((x ∪ y) \ x) = (y ∩ x) ∪ (y \ x) = y (dokažite sve skupovne jednakosti korištene u gornjem redu!)

Za skupove a i b, definiramo Kartezijev produkt:

A × B := {(x, y) : x ∈ a ∧ y ∈ b}

Ako je x ∈ a i y ∈ b, tada su oba u a ∪ b. Dakle {x} i {x, y} su podskupovi od a ∪ b, odnosno elementi od P(a ∪ b). To znači da je (x, y) podskup od P(a ∪ b), pa je element od PP(a ∪ b). Svaki uredeni par elemenata od a i b se nalazi u tom skupu, pa je Kartezijev produkt a × b podskup tog skupa: a × b ⊆ PP(a ∪ b), odnosno

a × b ∈ PPP(⋃{a, b})

Dokažite (pogledajte bilješke iz EM1) sljedeća svojstva Kartezijevog produkta:

• Kartezijev produkt je distributivan prema uniji, presjeku i skupovnoj razlici.

• Monoton je: a ⊆ b ∧ c ⊆ d ⟹ a × c ⊆ b × d.

• Prazan skup ima svojstvo nule: a × ∅ = ∅ × a = ∅.

• Dopušta kraćenje: a × b = a × c, uz a ≠ ∅, povlači b = c. (Uputa: ako je x ∈ a i y ∈ b \ c, tada je (x, y) ∈ a × b \ a × c.)

Za skup A, (Kartezijev) kvadrat skupa A, A^{2}, definira se kao Kartezijev produkt A sa samim sobom:

A^{2} := {(a, b); a ∈ A ∧ b ∈ A} .

Kartezijev kvadrat singletona je

{⋆}^{2} = {⋆}×{⋆} = {(⋆, ⋆)} = {{{⋆}, {⋆, ⋆}}} = {{{⋆}, {⋆}}} = {{{⋆}}}

Kartezijev kvadrat praznog skupa je, naravno, prazan (općenito, Kartezijev produkt praznog skupa s bilo kojim skupom je prazan). Dakle, ∅ je primjer skupa koji je jednak svom Kartezijevom kvadratu. No za

dokazati da je to jedini takav skup, moramo imati snažniju aksiomatiku — na primjer, aksiom utemeljenosti.

Relacija izmedu skupova A i B je podskup njihovog Kartezijevog produkta: ρ ⊆ A×B. Dakle, to je skup nekih uredenih parova (x, y), gdje je x ∈ A i y ∈ B. Ako je (x, y) ∈ ρ, još kažemo “x i y su u relaciji ρ”, i pišemo skraćeno xρy.

Binarna relacija na skupu A je podskup njegovog Kartezijevog kvadrata: ρ ⊆ A^{2}. Dakle, to je relacija izmedu skupa i njega samog, odnosno skup nekih uredenih parova elemenata od A. Binarne relacije mogu imati mnoga specijalna svojstva, o kojima će biti više riječi kasnije.

Sada je lako precizno definirati funkciju — to je relacija izmedu domene i kodomene, koja ima svojstvo da za svaki x iz domene postoji jedinstveni y iz kodomene koji je s njim u relaciji:

(f : D → K) : ⟺ f ⊆ D × K ∧ (∀x ∈ D)(∃!y ∈ K)((x, y) ∈ f)

Važna posljedica toga je da u teoriji skupova obično funkciju s proširenom kodomenom smatramo istom funkcijom: to je jednostavno isti skup, samo što je jednom podskup od D×K, a drugi put od D×K′. Na primjer, f = {(1, 5), (2, 6)} možemo promatrati kao funkciju s {1, 2} u {5, 6}, no jednako tako je možemo promatrati i kao funkciju s {1, 2} u {1, 2, 3, 4, 5, 6}, ili čak u ℕ.

2. Injekcije, surjekcije, bijekcije

Bitno svojstvo funkcije f : a → b:

∀x ∈ a ∃!f(x) ∈ b

— važno je i postojanje i jedinstvenost!

Ako je f : a → b, a se zove domena, a b kodomena funkcije f. Pišemo a =: dom(f). Kodomena nije toliko bitna, što slijedi iz napomene na kraju prethodne točke — skupovno jedna te ista funkcija može imati različite kodomene.

Skup svih funkcijâ s a u b označavamo s b^{a} (pazite na redoslijed!). Alternativna oznaka je^{b}a — primijetite da je u svakom slučaju domena eksponent, a kodomena baza.

Slika skupa: ako je f : A → B i C ⊆ A,

f^{⟩}(C) := {f(x) : x ∈ C}

(standardna oznaka za to u “uobičajenoj” matematici je samo f(C), no u teoriji skupova je sasvim moguće da je isti C ujedno i podskup i element domene, pa tada nije jasno označava li f(C) vrijednost funkcije, ili sliku funkcije. Naravno, kad nema mogućnosti zabune, može se i u teoriji skupova pisati jednostavno f(C).)

Slika funkcije je specijalni slučaj gornjeg:

im(f) := f^{⟩}(dom f) = {f(x) : x ∈ dom f}

Restrikcija funkcije: ako je f : A → B i C ⊆ A, f|_{C} je funkcija s domenom C (i kodomenom B), definirana istim pravilom kao f.

DZ: dokažite: f^{⟩}(C) = im(f|_{C}).

Praslika skupa: ako je f : A → B i D ⊆ B,

f^{⟨}(D) := {x ∈ dom(f) : f(x) ∈ D}

(“standardna” oznaka je f^{−1}(D), no to može dovesti do zabune s oznakom za vrijednost inverza funkcije. Primijetimo da je f^{⟨}(D) dobro definirano bez obzira na to je li f bijekcija.)

Primijetimo, ako je f : a → b, tada je f^{⟩} : P(a) → P(b), a f^{⟨} : P(b) → P(a).

Za funkciju f ∈ b^{a} kažemo da je

• injekcija ako ∀x_{1,2} ∈ a (f(x_{1}) = f(x_{2}) → x_{1} = x_{2})

• surjekcija (na b) ako ∀y ∈ b ∃x ∈ a (y = f(x))

• bijekcija ako je injekcija i surjekcija

3. Primjeri

(1) (n ↦ 2n) : ℕ → 2ℕ je bijekcija

(2) tg : ⟨−\frac{π}{2}, \frac{π}{2}⟩ → ℝ je bijekcija

(3) sin : ℝ → [−1, 1] je surjekcija, ali nije injekcija

(4) exp : ℝ → ℝ je injekcija, ali nije surjekcija

(5) Za svaki S, χ : P(S) → {0, 1}^{S} je bijekcija (podskupu A ⊆ S pridruži njegovu karakterističnu funkciju χ_{A} : S → {0, 1})

Dokažite to za domaću zadaću!

Ako je domena prazna: jedina funkcija s praznom domenom je upravo ∅ : ∅ → K (kodomena je proizvoljna, no slika joj je uvijek ∅) — ona je tada injekcija, a surjekcija je akko je K = ∅. Imamo dakle K^{∅} = {∅} za svaki K, i specijalno ∅^{∅} = {∅}.

Ako je domena neprazna, a kodomena prazna: takvih funkcijâ nema! Za D ≠ ∅, imamo ∅^{D} = ∅. Primijetimo bitnu razliku izmedu ova dva slučaja!

4. Zadaci

(1) Funkcija je istodobno konstanta i bijekcija ako i samo ako su joj domena i kodomena jednočlani. \underline{Rj.:} (⇐) Ako je f : \{a\} → \{b\}, f(a) mora biti neki element od {b}, dakle mora biti f(a) = b. Tada je f konstanta (za sve x iz domene, f(x) = b), injekcija (“svi” elementi domene su jednaki), i surjekcija (za svaki element kodomene postoji original — jedini takav je b, a za njega postoji a). (⇒) Ako je f : A → B konstanta, to znači da postoji b iz kodomene takav da je ∀x ∈ A(f(x) = b. Kad bi domena bila prazna, taj b ne bi uopće bio pogoden, pa f ne bi bila surjekcija. Kad bi u domeni postojala bar dva elementa, recimo x_{1} i x_{2}, bili bi različiti s istim slikama, pa f ne bi bila injekcija. Kad bi u kodomeni postojao još neki element osim b, on ne bi bio u slici (jer se svi x ∈ A preslikaju u b), pa f ne bi bila surjekcija. Dakle, i A i B moraju sadržavati točno jedan element.

(2) Kompozicija injekcijâ je injekcija.

Kompozicija surjekcijâ je surjekcija. Ako znamo da je f ∘ g bijekcija, što možemo zaključiti o f i g? (DZ — na ovo posljednje potražite odgovor na Forumu.)

(3) Neka je f : A → A takva da je za svaki n ∈ ℕ, f^{n} = id_{A}. Dokažite da je f bijekcija. (f^{n} označava n-struku kompoziciju f sa samom sobom. id_{A} označava identitetu na A: funkciju iz A^{A}, definiranu s x ↦ x.)

\underline{Rj.:} Za n = 2, imamo f_{∘}^{2} = f ∘ f = id_{A}. To znači da je f sama sebi i lijevi i desni inverz, pa je bijekcija. ((Štoviše, iz id_{A} = f_{∘}^{3} = f ∘ f ∘ f = id_{A} ∘f = f zaključujemo da mora biti f = id_{A}.))

(4) Neka je h ∈ A^{A}. Dokažite: h je surjekcija akko za sve f i g iz A^{A} vrijedi f ∘ h = g ∘ h → f = g. \underline{Rj.:} (⇒) Imamo da za svaki a ∈ A vrijedi f(h(a)) = g(h(a)), odnosno za svaki b ∈ im h = A, f(b) = g(b). (¬ ⇒ ¬) Pretpostavimo da h nije surjekcija: neka je a ∈ A neki element koji nije u slici od h, i b := h(a). Naravno, b ≠ a jer b jest u slici od h. Definirajmo f kao konstantu b, a g kao funkciju koja preslikava a ↦ a, a sve ostale elemente u b. Vrijedi f ≠ g (jer je f(a) = b ≠ a = g(a)), ali (dokažite!) f ∘ h = f = g ∘ h.

(5) Neka je h ∈ A^{A}. Dokažite: h je injekcija akko za sve f i g iz A^{A} vrijedi h ∘ f = h ∘ g → f = g. (DZ — prilično analogno prethodnom zadatku.)

(6) Ako f : A → B ima desni inverz (funkciju g : B → A takvu da je f ∘ g = id_{B}), tada je surjekcija. (Obrat vrijedi uz pretpostavku

AC!)

\underline{Rj.:} Ako vrijedi (∀b ∈ B)(f(g(b)) = b), tada očito svaki element b ∈ B ima original — na primjer g(b).

(7) Neka je f : A → B, te X i Y podskupovi od A. Tada vrijedi • f^{⟩}(X ∪ Y) = f^{⟩}(X) ∪ f^{⟩}(Y)

• f^{⟩}(X ∩ Y) ⊆ f^{⟩}(X) ∩ f^{⟩}(Y) (ali ⊇ općenito nije)

• f^{⟩}(X \ Y) ⊇ f^{⟩}(X) \ f^{⟩}(Y) (ali ⊆ općenito nije) Neka je f : A → B, te X i Y podskupovi od B. Tada vrijedi

• f^{⟨}(X ∪ Y) = f^{⟨}(X) ∪ f^{⟨}(Y)

• f^{⟨}(X ∩ Y) = f^{⟨}(X) ∩ f^{⟨}(Y)

• f^{⟨}(X \ Y) = f^{⟨}(X) \ f^{⟨}(Y) (DZ — rješenja potražite u bilješkama iz MA1!)

(8)^{⋆}f^{⟨} je surjekcija akko je f injekcija, i

f^{⟨} je injekcija akko je f surjekcija.

(9) Ako je A ⊆ B, tada za svaki S vrijedi A^{S} ⊆ B^{S}. (U teoriji skupova kodomenu ne smatramo esencijalnim dijelom funkcije: sin : ℝ → ℝ i sin : ℝ → ℝ ∪ {i} smatramo jednom te istom funkcijom. Pogledajte i napomenu nakon stroge definicije funkcije.)

(10) Ako je f : A → B, i C ⊆ A, vrijedi C ⊆ f^{⟨}(f^{⟩}(C)), no jednakost ne vrijedi općenito. \underline{Rj.:} (⊆) Za proizvoljni c ∈ C i d := f(c), vrijedi d ∈ f^{⟩}(C), pa c ima svojstvo da se njegova slika nalazi u f^{⟩}(C). Dakle c ∈ f^{⟨}(f^{⟩}(C)).

(⊉) Za sin : ℝ → ℝ, i C := [−\frac{π}{2}, \frac{π}{2}], imamo sin^{⟩}(C) = [−1, 1], a sin^{⟨}([−1, 1]) = ℝ ⊃ C.

(11) Ako je f : A → B, te C ⊆ A ∧ D ⊆ B, tada f^{⟩}(C) ⊆ D ⟺ C ⊆ f^{⟨}(D). \underline{Rj.:} Obje tvrdnje znače (∀x ∈ C)(f(x) ∈ D).

Dio 2

Kardinalni i ordinalni brojevi

POGLAVLJE 4 Beskonačna kombinatorika

1. Ekvipotentni skupovi

Možemo reći da je teorija skupova nastala kada je Cantor, našavši način kako brojiti beskonačne skupove, učinio beskonačnost predmetom matematički strogog proučavanja. Naime, brojenje je uspostavljanje bijekcije s nekim unaprijed poznatim skupom (brojem). Obično koristimo konačne brojeve, za prebrajanje konačnih skupova. Na primjer, konačan broj 2 možemo definirati kao skup {∅, {∅}}, i onda za (npr.) skup orijentacijâ na nekom pravcu možemo reći da ima 2 elementa, jer je jednostavno uspostaviti bijekciju izmedu skupa tih orijentacijâ i fiksiranog (dogovorenog) broja 2.

No za prebrajanje beskonačnih skupova, trebaju nam beskonačni brojevi. Na primjer, beskonačan broj ℵ_{0} možemo definirati kao skup ℕ, i tada za (npr.) skup svih riječî sastavljenih samo od slova a možemo reći da ima ℵ_{0} elemenata, jer je jednostavno uspostaviti bijekciju izmedu skupa takvih riječî i upravo dogovorenog broja ℵ_{0} (naravno, svakoj riječi pridružimo njenu duljinu).

To ćemo u ovom dijelu i činiti: prebrajati beskonačne skupove (uspostavljati bijekcije s nekim drugim beskonačnim skupovima), pokušati definirati brojeve (tzv. kardinalne brojeve) koji nam za to mogu služiti, definirati operacije na tim brojevima, i proučavati njihova svojstva.

Pri tome treba imati na umu osnovno svojstvo beskonačnih skupova:

Skup je beskonačan akko postoji bijekcija izmedu njega i nekog njegovog pravog podskupa.

Dakle, skup može imati jednako mnogo elemenata kao i njegov pravi podskup. Štoviše, to upravo karakterizira beskonačne skupove. Na primjer, ℵ_{0} je beskonačan (odnosno skup ℕ je beskonačan) jer postoji njegov pravi podskup Nl := ℕ \ {0}, koji takoder ima ℵ_{0} elemenata: bijekcija je n ↦ n − 1. S druge strane, gore spomenuti broj 2 (odnosno skup {∅, {∅}}) je konačan, jer svaki njegov pravi podskup ima strogo manje elemenata: {∅} i {{∅}} imaju po 1 element, dok ∅ ima 0 elemenata.

Formalizirajmo to:

Za dva skupa kažemo da su ekvipotentni ako postoji bijekcija s jednog na drugi:

A ∼ B : ⟺ (∃f ∈ B^{A})(f je bijekcija)

Za skup kažemo da je prebrojiv (ili strogo prebrojiv) ako je ekvipotentan s ℕ (tj. ako ima ℵ_{0} elemenata).

Za skup kažemo da je najviše prebrojiv ako je konačan ili prebrojiv. Inače (dakle ako je beskonačan i nije prebrojiv) kažemo da je neprebrojiv.

Ako je f : A → B injekcija, tada je f : A → im f bijekcija (surjektivnost smo postigli proglasivši sliku kodomenom). To znači da je dom f ∼ im f, kad god je f injekcija.

2. Primjeri

Skup nepozitivnih cijelih brojeva je prebrojiv. (n ↦ −n je bijekcija izmedu njih.)

Skup neparnih prirodnih brojeva je prebrojiv. (n ↦ 2n + 1 je tražena bijekcija.)

ℝ ∼ ℝ^{+} (exp je injekcija na ℝ, čija je slika ℝ^{+}.)

ℝ^{2} ∼ ℂ ((x, y) ↦ x + iy je bijekcija.)

Svaka dva segmenta (ili otvoreni, ili poluotvoreni, ili zatvoreni intervali) u ℝ su ekvipotentni. (Afina funkcija je bijekcija.)

((Zapravo, možemo reći “svi segmenti u ℝ su ekvipotentni”, jer ekvipotentnost ima svojstva relacije ekvivalencije: refleksivnost, simetričnost i tranzitivnost.))

Sve kružnice u ravnini su ekvipotentne. (DZ – traži se prikladno odabrana kompozicija translacije i homotetije.)

Da bismo rješavali kompliciranije zadatke, treba nam sljedeći pojam:

Za skupove A i B, kažemo da je A (kardinalno) ispred B, i pišemo A ≲ B, ako postoji injekcija s A u B, odnosno ako je A ekvipotentan nekom podskupu od B (dokažite da je to dvoje ekvivalentno).

kao i sljedeći teorem:

(Cantor–Bernstein) Ako je A kardinalno ispred B, i B kardinalno ispred A, tada su A i B ekvipotentni:

A ≲ B ∧ B ≲ A ⟹ A ∼ B

Sada možemo lako dokazati i tvrdnje poput:

[0, 1] ∼ ⟨0, 1⟩ \underline{Rj.:} Po Cantor–Bernsteinovom teoremu, dovoljno je naći injekcije u oba smjera. U tu svrhu mogu poslužiti f : [0, 1] → ⟨0, 1⟩; x ↦ (x+1)/3, i g : ⟨0, 1⟩ → [0, 1]; x ↦ x (ovo posljednje pokazuje da je podskup nekog skupa uvijek kardinalno ispred njega).

Ako je A ⊆ B ⊆ C i A ∼ C, tada je i B ∼ C (tj. sva tri skupa su ekvipotentni). \underline{Rj.:} Označimo s f bijekciju izmedu A i C. Tada su id_{B} : B → C i f^{−1} : C → B tražene injekcije.

⟨0, 1⟩ ∼ [0, 1⟩ ∼ ⟨0, 1] ∼ [0, 1] \underline{Rj.:} Direktno iz prethodnog. Pokušajte direktno konstruirati potrebne bijekcije.

Svi netrivijalni (s različitim krajevima) ograničeni intervali u ℝ su ekvipotentni. \underline{Rj.:} Svaki je, afinom funkcijom, ekvipotentan odgovarajućem intervalu od 0 do 1.

ℝ ∼ ⟨−\frac{π}{2}, \frac{π}{2}⟩ (arc tg je bijekcija)

Svaki interval (s bar dvije točke) je ekvipotentan s ℝ. \underline{Rj.:} Ako interval I sadrži bar dvije točke a i b, tada sadrži i cijeli podinterval ⟨a, b⟩, koji je afinom funkcijom ekvipotentan s ⟨−\frac{π}{2}, \frac{π}{2}⟩, a time i s cijelim ℝ. Inkluzija ⟨a, b⟩ ⊆ I ⊆ ℝ sada daje tvrdnju.

Svi intervali (s bar po 2 točke) u ℝ su ekvipotentni. \underline{Rj.:} Direktno iz tranzitivnosti ekvipotentnosti.

Kardinalni broj skupa ℝ zovemo kontinuum, i označavamo s 𝔠. Dakle, gornja tvrdnja kaže da svi netrivijalni intervali u ℝ imaju kontinuum elemenata.

ℕ^{2} je prebrojiv. Općenitije, ℕ^{n} je prebrojiv za svaki n ∈ ℕ od 1 nadalje. \underline{Rj.:} f : ℕ^{n} → ℕ; (i_{1}, i_{2}, …, i_{n}) ↦ 2^{i_{1}}3^{i_{2}} · . . . · p_{n}^{i_{n}} (s p_{k} je označen k-ti prosti broj po veličini) je jedna injekcija. g : ℕ → ℕ^{n}; k ↦ (k, k, …, k) je druga.

ℕ^{∗} := ⋃_{n∈ℕ} ℕ^{n} je prebrojiv. \underline{Rj.:} f : ℕ^{∗} → ℕ; (i_{1}, i_{2}, …, i_{n}) ↦ 2^{i_{1}+1}3^{i_{2}+1} · . . . · p_{n}^{i_{n}+1} je jedna injekcija. g : ℕ → ℕ^{∗}; k ↦ (k) je druga.

Štoviše, A^{∗} je prebrojiv za svaki prebrojivi A — dokažite to!

ℤ je prebrojiv. \underline{Rj.:} Budući da je ℕ ⊂ ℤ (dakle i ℕ ≲ ℤ), sve što nam treba je injekcija sa ℤ u neki prebrojivi skup. Lako se provjeri da je m ↦ (2+sgn m, |m|) injekcija sa ℤ u ℕ^{2}.

ℚ je prebrojiv. \underline{Rj.:} Kao gore, dovoljno je primijetiti da je p/q ↦ (p, q), gdje su p i q relativno prosti, injekcija s ℚ u ℤ × ℕ.

Naravno, ℤ×ℕ je prebrojiv, što možemo opet dokazati metodom dvije injekcije, no možda to možemo i direktno, računajući s ℵ_{0} kao i s ostalim brojevima? Pokazuje se da možemo, i time ćemo se sada baviti.

3. Računanje s kardinalnim brojevima

Iako ne znamo strogo što su kardinalni brojevi, znamo puno o njima. To su neki objekti (nesumnjivo skupovi) pridruženi skupovima, koji govore koliko elemenata oni imaju. Preciznije, kad skupu A pridružimo njegov kardinalni broj κ (u oznaci κ = card A), time želimo reći “Skup A ima κ elemenata”. Pri tome κ može biti konačan, poput

0 = card ∅
1 = card{0}
2 = card{0, 1}
⋮

— ili može biti beskonačan, poput ℵ_{0} = card ℕ ili 𝔠 = card ℝ.

Kardinalne brojeve možemo usporedivati, i računati s njima — za dva kardinalna broja κ = card A i μ = card B:

• kažemo da su jednaki, ako su skupovi A i B ekvipotentni (κ = μ : ⟺ A ∼ B).

• kažemo da je κ manji ili jednak μ ako je skup A kardinalno prije B (κ ≤ μ : ⟺ A ≲ B).

• kažemo da je κ strogo manji od μ ako je A kardinalno prije B, ali nije ekvipotentan s njim (κ < μ : ⟺ A ≲ B ∧ A ≁ B).

• definiramo njihov zbroj kao kardinalni broj unije A i B, pod pretpostavkom da su A i B disjunktni (κ+μ := card(A ∪^{.} B)).

• definiramo njihov produkt kao kardinalni broj Kartezijevog produkta skupova A i B (κ · μ := card(A × B)).

• definiramo potenciju s bazom κ i eksponentom μ kao broj funkcijâ s B u A (κ^{μ} := card A^{B}).

Samo jedna mala napomena u vezi zbroja: što ako A i B nisu disjunktni? Izlazi da se uvijek mogu naći skupovi s istim kardinalnim brojevima, koji jesu disjunktni — specijalno, skupovi A × {0} ∼ A i B × {1} ∼ B su takvi. Onda se κ + μ definira kao kardinalni broj njihove unije.

Gornji odlomak, i definicija množenja kardinalnih brojeva, daju nam

κ · 1 = card A · card{0} = card(A × {0}) = card A = κ ,

odnosno 1 (kao kardinalni broj jednočlanih skupova) je neutralni element za množenje kardinalnih brojeva. Jednako tako, 0 je neutralni element za zbrajanje (∅ je disjunktan sa svakim skupom). Takoder, vrijede i mnogi drugi zakoni: asocijativnost i komutativnost zbrajanja i množenja, distributivnost množenja prema zbrajanju, kao i svojstvo nule: κ · 0 = 0. Takoder, za potenciranje vrijedi:

κ^{μ_{1}+μ_{2}} = κ^{μ_{1}} · κ^{μ_{2}}
(κ^{μ_{1}})^{μ_{2}} = κ^{μ_{1}·μ_{2}}
(κ_{1} · κ_{2})^{μ} = κ_{1}^{μ} · κ_{2}^{μ}
κ_{1} ≤ κ_{2} ⟹ κ_{1}^{μ} ≤ κ_{2}^{μ}
μ_{1} ≤ μ_{2} ∧ κ ≠ 0 ⟹ κ^{μ_{1}} ≤ κ^{μ_{2}}

(za dokaz vidjeti bilješke iz kombinatorike — “kombinatorni dokazi” obično prolaze i u beskonačnim slučajevima)

Dokažimo samo zadnju tvrdnju, za ilustraciju zašto nam treba pretpostavka κ ≠ 0: neka je κ = card A, μ_{1} = card B i μ_{2} = card C. Imamo pretpostavku A ≁ ∅ (što zapravo znači da je A neprazan), te da je card B ≤ card C, što znači da imamo injekciju f : B → C. Sliku od f označimo s D — to je podskup od C ekvipotentan s B.

Trebamo dokazati da je card A^{B} ≤ card A^{C}, odnosno naći neku injekciju s A^{B} u A^{C}. Ako uzmemo neku funkciju iz A^{B} (dakle g : B → A), njoj trebamo (injektivno) pridružiti neku funkciju s C u A. Naravno, budući da je f bijekcija izmedu B i D, lako je vidjeti da možemo pridružiti g ↦ g′ := g ∘ f^{−1}, funkciju s D u A, i to je injektivno pridruživanje. No kako proširiti g′ na preostale elemente iz C \D, ako ih ima? Budući da je A neprazan, postoji neki a ∈ A. Njega možemo pridružiti svim ostalim elementima iz C, i na taj način dobiti funkciju iz A^{C}, koju možemo pridružiti funkciji g.

Štoviše, ne samo da dokaz ne prolazi, nego ni tvrdnja ne vrijedi općenito za κ = 0: na primjer, 0 ≤ 2, ali 1 = 0^{0} ≰ 0^{2} = 0. No u svim ostalim slučajevima, isključujući 0^{0} = 1, potenciranje je monotona operacija.

I ostale operacije su monotone:

κ_{1} ≤ κ_{2} ⟹ κ_{1} + μ ≤ κ_{2} + μ ∧ κ_{1} · μ ≤ κ_{2} · μ

— no treba napomenuti da nisu strogo monotone: na primjer, 1 < 2, ali ℵ_{0} + 1 = ℵ_{0} = ℵ_{0} + 2 (dokažite!).

Monotonost, zajedno s dosad dokazanim svojstvima, kao i važnom vezom izmedu ℵ_{0} i 𝔠, koju ćemo upravo dokazati, omogućit će nam brojne korisne zaključke o kardinalnim brojevima.

Dokažimo: 𝔠 = 2^{ℵ_{0}}.

Dokaz. Na lijevoj strani je card ℝ, a na desnoj je card({0, 1}^{ℕ}), za što smo prije vidjeli da je jednako card P(ℕ) (općenito, kardinalni broj partitivnog skupa nekog prebrojivog skupa). Trebamo konstruirati dvije injekcije:

Ako realnom broju x pridružimo skup svih racionalnih brojeva koji su manji od njega (dakle, f(x) := ℚ ∩ ⟨−∞, x⟩), to će biti preslikavanje f : ℝ → P(ℚ). Takoder će biti injektivno: ako su x i y dva različita realna broja (BSOMP x < y), tada postoji racionalan broj q takav da je x < q < y. Tada će biti q ∈ f(y), ali q ∉ f(x), dakle bit će f(x) ≠ f(y). To znači da je f injekcija, odnosno da je 𝔠 = card ℝ ≤ card P(ℚ) = 2^{ℵ_{0}}.

S druge strane, ako podskupu A ⊆ ℕ pridružimo realan broj g(A) := ∑_{n∈A} 3^{−n} (taj red s pozitivnim članovima konvergira, jer je majoriran geometrijskim redom s kvocijentom \frac{1}{3}), to je takoder injekcija: ako su A i B dva različita podskupa od ℕ, tada s c označimo najmanji prirodni broj koji jest u jednom od njih, ali nije u drugom. Dakle, c := min(A△B), i BSOMP c ∈ A \ B. Sada se lako vidi, koristeći činjenicu da se A i B podudaraju na 0, 1, 2, …, c − 1, da je g(A) > g(B), dakle g je injekcija, odnosno 𝔠 = card ℝ ≥ card P(ℕ) = 2^{ℵ_{0}}. □

Sada možemo dokazati brojne jednakosti medu kardinalnim brojevima:

1 + 1 = 2 \underline{Rj.:} 1 = card\{0\}, što znači da nam trebaju dvije disjunktne kopije od {0}, na primjer {0} × {0} = {(0, 0)} i {0} × {1} = {(0, 1)}. Njihova unija je {(0, 0), (0, 1)}, a taj skup je trivijalno ekvipotentan s {0, 1} (x ↦ (0, x) je bijekcija izmedu njih).

ℵ_{0}^{2} = ℵ_{0} \underline{Rj.:} Direktno iz ℕ^{2} ∼ ℕ, što smo dokazali. Ili: injekcija (x, y) ↦ 2^{x} · 3^{y} nam daje ℵ_{0}^{2} ≤ ℵ_{0}, a takoder imamo ℵ_{0} = ℵ_{0} · 1 ≤ ℵ_{0} · ℵ_{0} = ℵ_{0}^{2} (primijetite kako smo iskoristili monotonost množenja: iz 1 ≤ ℵ_{0} množenjem s ℵ_{0} slijedi nejednakost koja nam treba).

ℵ_{0} + ℵ_{0} = ℵ_{0} \underline{Rj.:} Po distributivnosti, ℵ_{0} + ℵ_{0} = ℵ_{0} · 1 + ℵ_{0} · 1 = ℵ_{0} · (1 + 1) = ℵ_{0} · 2.

Dakle, treba dokazati ℵ_{0}·2 = ℵ_{0}. No to slijedi iz 1 ≤ 2 ≤ ℵ_{0} množenjem s ℵ_{0}: dobijemo ℵ_{0} ≤ 2 · ℵ_{0} ≤ ℵ_{0} · ℵ_{0} = ℵ_{0}.

𝔠^{ℵ_{0}} = 𝔠 — odnosno, svih realnih (ili kompleksnih, ili nad nekim intervalom, itd.) nizova ima kontinuum) \underline{Rj.:} Znamo da je 𝔠 = 2^{ℵ_{0}}. Dignimo to na ℵ_{0}: 𝔠^{ℵ_{0}} = (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0}·ℵ_{0}} = 2^{ℵ_{0}} = 𝔠.

Za svaki kardinalni broj κ izmedu 2 i 𝔠, vrijedi κ^{ℵ_{0}} = 𝔠 (odnosno, ako skup S ima bar 2 elementa, a najviše kontinuum elemenata, tada nizova nad S ima kontinuum). Specijalno, ℵ_{0}^{ℵ_{0}} = 𝔠. \underline{Rj.:} Direktno iz prethodnog zadatka: 2 ≤ κ ≤ 𝔠 dignemo na ℵ_{0}, i iskoristimo monotonost potenciranja za nenul-baze.

𝔠^{2} = 𝔠 (kompleksnih brojeva ima kontinuum) \underline{Rj.:} Imamo 𝔠^{2} = (2^{ℵ_{0}})^{2} = 2^{ℵ_{0}·2} = 2^{ℵ_{0}}

𝔠^{𝔠} = 2^{𝔠} (funkcijâ s ℝ u ℝ ima koliko i podskupova od ℝ) \underline{Rj.:} Imamo 2 ≤ 𝔠 ≤ 2^{𝔠} (zadnja nejednakost je posljedica Cantorovog teorema). Dignuvši to na 𝔠, dobijemo 2^{𝔠} ≤ 𝔠^{𝔠} ≤ (2^{𝔠})^{𝔠} = 2^{𝔠·𝔠} = 2^{𝔠^{2}}2^{𝔠}.

Još neki rezultati operacijâ s kardinalnim brojevima, za DZ:

2^{2} = 2 · 2 = 2 + 2 = 4
𝔠 · 2 = 𝔠 · ℵ_{0} = 𝔠
𝔠 + ℵ_{0} = 𝔠
ℵ_{0}^{𝔠} = 2^{𝔠}

4. Kardinalni brojevi još nekih skupova

Dokažimo: Svaki beskonačan podskup od ℕ je prebrojiv.

Dokaz. Neka je S ⊆ ℕ beskonačan. Funkciju f : ℕ → S definiramo totalnom indukcijom:

f(n) := min(S \ {f(0), f(1), …, f(n − 1)})

(specijalno, f(0) = min S). Budući da je S beskonačan, u svakom koraku će još ostati nepridruženih elemenata od S, a budući da je S ⊆ ℕ, od svih njih će postojati najmanji.

Da je f injekcija, vidi se ovako: ako su i i j različiti prirodni brojevi, BSOMP i < j. No to znači da je

f(j) = min(S \ {f(0), …, f(i), …, f(j − 1)}) ,

odnosno, f(i) je isključen prilikom odabira vrijednosti za f(j). To znači da je f(i) ≠ f(j).

Surjektivnost od f se vidi tako da se (matematičkom indukcijom) pokaže da je svaki n ∈ S već medu f(0), f(1),…, f(n). □

card ℙ = ℵ_{0} \underline{Rj.:} Direktna posljedica prethodno dokazanog.

card 𝔸 = ℵ_{0} \underline{Rj.:} (𝔸 označava skup svih (realnih) algebarskih brojeva, odnosno svih realnih brojeva koji su nultočke polinomâ s cjelobrojnim koeficijentima.)

Jedna nejednakost je očita: budući da je svaki racionalni broj algebarski (m/n je nultočka od n · x − m), imamo ℵ_{0} = card ℚ ≤ card 𝔸. Za drugu nejednakost, treba nam injekcija s 𝔸 u neki prebrojivi skup. Uzmimo ℕ^{∗}, za koji znamo da je prebrojiv, i realizirajmo preslikavanje ovako: uzmimo proizvoljni x ∈ 𝔸. Znamo da je x nultočka nekog polinoma s cjelobrojnim koeficijentima p(x) = a_{n}x^{n} + … + a_{0}. Taj polinom, osim x, može imati i druge realne nultočke: budući da ih ima konačno mnogo, možemo ih poredati po veličini. Neka je x m-ta od njih. Dakle, broju x možemo pridružiti (2n + 3)-torku

(m, |a_{n}|, 1 + sgn a_{n}, |a_{n−1}|, 1 + sgn a_{n−1}, …, |a_{0}|, 1 + sgn a_{0}) ∈ ℕ^{∗}

koja ga na jednoznačan način odreduje — jedini problem je što to možemo učiniti na više načina — jedan algebarski broj je nultočka mnogih polinomâ. Ipak, kao što ćemo kasnije vidjeti, skup ℕ^{∗} ima dobro svojstvo da se medu svim reprezentacijama gornjeg oblika može odabrati najmanja s obzirom na neki uredaj, pa tako imamo pridruži-

vanje. Da nema tog dobrog svojstva, takoder bismo mogli odabrati po jednu reprezentaciju za svaki algebarski broj, ali bi to u općem slučaju zahtijevalo korištenje aksioma izbora.

(DZ: dokažite, na sličan način, da je ℚ[x] — skup polinoma u jednoj varijabli s racionalnim koeficijentima — prebrojiv.)

Svih poligona u ravnini, s vrhovima iz ℚ^{2}, ima prebrojivo mnogo. \underline{Rj.:} Kao i gore, možemo vidjeti da je ℚ^{2} ne samo prebrojiv, već jednom kad imamo konkretnu bijekciju q : ℚ^{2} ↔ ℕ, možemo točke iz ℚ^{2} urediti po vrijednostima funkcije q (više o uredajima u sljedećem poglavlju). Budući da su vrijednosti od f prirodni brojevi, moguće je za svaki poligon naći njegov “prvi” vrh — preciznije, onaj kojem je vrijednost funkcije q najmanja. Jednom kad to imamo, lako je konstruirati injekciju sa skupa koji promatramo, u ℚ^{∗}: svakom poligonu P nademo prvi vrh (x_{1}, y_{1}), i krećući se od njega u pozitivnom smjeru pišemo redom koordinate vrhova:

P ↦ (x_{1}, y_{1}, x_{2}, y_{2}, …, x_{n}, y_{n}) ∈ ℚ^{∗} .

Drugu injekciju je vrlo jednostavno konstruirati: prirodnom broju n pridružimo trokut s vrhovima (0, 0), (1, 0) i (0, n).

Svih intervalâ (otvorenih, poluotvorenih, poluzatvorenih i zatvorenih) u ℝ, s racionalnim krajevima, ima prebrojivo mnogo. \underline{Rj.:} Označimo skup svih tih intervalâ sa I. Injekciju sa I u prebrojivi skup možemo konstruirati na primjer ovako (po slučajevima):

f : I → ℚ^{3}
f(⟨a, b⟩) := (1, a, b)
f(⟨a, b]) := (2, a, b)
f([a, b]) := (3, a, b)
f([a, b⟩) := (4, a, b)

Vidimo da vrijednost funkcije f ovisi i o tipu intervalâ, i o njegovim krajevima. Budući da različiti intervali imaju ili različit tip, ili različite krajeve (kažemo da je interval jednoznačno odreden svojim tipom i krajevima), vidimo da je f injekcija. Druga injekcija je na primjer g : ℚ → I ; g(r) := [0, r].

DZ: dokažite da svih intervalâ u ℝ (bez ograničenja na racionalnost krajeva), ima kontinuum.

Konačnih podskupova od ℕ ima prebrojivo mnogo. \underline{Rj.:} Svaki konačni podskup X ⊂ ℕ možemo urediti po veličini: recimo X = {a_{1}, …, a_{k}}, gdje je a_{1} < a_{2} < … < a_{k}. Ako sada pridružimo X ↦ (a_{1}, …, a_{k}), vidimo da smo dobili injekciju s našeg skupa (možemo ga označiti s P_{kon}(ℕ)) u prebrojiv skup ℕ^{∗}. S druge strane, g : ℕ → P_{kon}(ℕ) ; g(n) := {n} je injekcija.

Beskonačnih podskupova od ℕ (zapravo od bilo kojeg prebrojivog skupa) ima kontinuum. \underline{Rj.:} Skup svih beskonačnih podskupova od ℕ označimo s P_{¬kon}(ℕ). Dokazat ćemo da je taj skup ekvipotentan s P(Nl ), gdje je Nl = ℕ \ {0}. Jedna injekcija je f : P_{¬kon}(ℕ) → P(Nl ) ; A ↦ {x + 1 ; x ∈ A} (jednostavno skup translatiramo za 1 u desno). Ako smo krenuli od (beskonačnog) podskupa od ℕ, dobit ćemo podskup od Nl , i to je injekcija (jer je x ↦ x + 1 injekcija). Druga injekcija je zanimljivija:

g : P(Nl ) → P_{¬kon}(ℕ) ; A ↦ \{ \begin{matrix}A , & A beskonačan \\ ℕ \ A , & A konačan \end{matrix} .

Njene vrijednosti su očito sve beskonačni podskupovi od ℕ, no kako znamo da je injekcija? Pretpostavimo g(A) = g(B), za neke A i B podskupove od Nl . Ako su A i B beskonačni, to direktno znači da je A = g(A) = g(B) = B. Ako su pak oba konačni, iz A = ℕ \ g(A) = ℕ \ g(B) = B vidimo da je A = B.

No što ako je jedan konačan, a drugi beskonačan (BSOMP A konačan, B beskonačan)? Tada se lako vidi 0 ∈ ℕ \ Nl ⊆ ℕ \ A = g(A), te 0 ∉ Nl ⟹ 0 ∉ B = g(B), pa nikako ne može biti g(A) = g(B) (jedan ima 0 kao element, a drugi nema).

5. Primjeri iz analize

Ovdje ćemo se obično baviti skupovima funkcijâ. Prisjetimo se, svih funkcija iz A u B ima card B^{A} = (card B)^{card A}. Korolari toga, koje smo već spomenuli:

• cjelobrojnih/racionalnih/realnih/kompleksnih nizova ima 𝔠;

• realnih funkcijâ s domenom ℚ ima 𝔠;

• realnih funkcijâ s domenom ℝ ima 2^{𝔠}.

Sada idemo na kompliciranije primjere.

Realnih funkcijâ realne varijable (dakle, onih kojima je kodomena ℝ, a domena proizvoljni neprazni podskup od ℝ) ima 2^{𝔠}. \underline{Rj.:} Skup svih takvih označimo s F (^{⊆}ℝ). Očito ih ima bar 2^{𝔠}, jer je ℝ^{ℝ} ⊂ F (^{⊆}ℝ). S druge strane, imamo injekciju

g : F (^{⊆}ℝ) → P(ℝ) × ℝ^{ℝ} ; g(f) := (dom f, f̃) ,

gdje je f̃funkcija f proširena (recimo nulom) na cijeli ℝ. Iz toga imamo

card F (^{⊆}ℝ) ≤ card(P(ℝ) × ℝ^{ℝ}) = 2^{𝔠} · 2^{𝔠} = 2^{𝔠+𝔠} = 2^{𝔠} .

Drugi način: možemo direktno naći bijekciju.

h : F (^{⊆}R) ↔ (ℝ ∪ {i})^{ℝ} ; h(f) := f^{∗} ,

gdje je f^{∗}(x) := f(x) ako je x ∈ dom f, a i inače.

Neprekidnih funkcijâ sa ℝ u ℝ ima 𝔠: card C(ℝ) = 𝔠. \underline{Rj.:} Koristimo teorem iz analize, koji kaže da je proširenje neprekidne funkcije s ℚ u ℝ po neprekidnosti, jedinstveno. To znači da je preslikavanje

|_{ℚ} : C(ℝ) → ℝ^{ℚ} ; f ↦ f|_{ℚ} ,

injekcija. (Naime, ako je f|_{ℚ} = g|_{ℚ}, te su f i g neprekidne s domenom ℝ, tada je za svaki ℝ ∋ x = lim_{n} q_{n}, f(x) = lim_{n} f(q_{n}) = lim_{n} g(q_{n}) = g(x).)

Dakle, card C(ℝ) ≤ card ℝ^{ℚ} = 𝔠^{ℵ_{0}} = 𝔠. S druge strane, svakom realnom broju x možemo pridružiti konstantnu funkciju c_{x}, c_{x}(y) = x za svaki y ∈ ℝ. To (pridruživanje x ↦ c_{x}) je očito injekcija s ℝ u C(ℝ), te je 𝔠 = card ℝ ≤ card C(ℝ).

Ograničenih funkcijâ sa ℝ u ℝ ima card B(ℝ) = 2^{𝔠}. \underline{Rj.:} Uočivši da su sve funkcije s ℝ u [0, 1] ograničene, i uzevši u obzir napomenu o irelevantnosti proširenja kodomene (funkcija s A u B je ujedno i funkcija s A u C za svaki C ⊇ B), imamo [0, 1]^{ℝ} ⊆ B(ℝ) ⊆ ℝ^{ℝ}. Uzevši kardinalne brojeve tih skupova, dobijemo

2^{𝔠} ≤ card B(ℝ) ≤ 2^{𝔠} .

DZ: koliko ima ograničenih i neprekidnih funkcija: card BC(ℝ) =?

DZ: koliko ima derivabilnih funkcijâ s ℝ u ℝ: card D(ℝ) =?

Periodičkih funkcijâ s ℝ u ℝ ima card P (ℝ) = 2^{𝔠}. \underline{Rj.:} Očito P (ℝ) ⊆ ℝ^{ℝ}, pa card P (ℝ) ≤ 2^{𝔠}. Za drugu nejednakost, primijetimo da svakoj realnoj funkciji f : [0, 1⟩ → ℝ prirodno odgovara funkcija perioda 1, definirana s g(x) = f(rd(x)), gdje smo označili s rd(x) := x − ⌊x⌋ = x mod 1, razlomljeni dio od x. Lako se vidi da je f ↦ f ∘ rd injekcija s ℝ^{[0,1⟩} u P (ℝ), te imamo i card P (ℝ) ≥ 2^{𝔠}.

(Strogo) konveksnih funkcijâ s ℝ u ℝ ima card K(ℝ) = 𝔠. \underline{Rj.:} Iz analize znamo da su sve konveksne funkcije ujedno neprekidne: K(ℝ) ⊆ C(ℝ), pa je traženi kardinalni broj manji ili jednak prije odredenom card C(ℝ) = 𝔠. S druge strane, svakom pozitivnom broju a možemo jednostavno injektivno pridružiti konveksnu (kvadratnu) funkciju x ↦ a · x^{2}. Dakle konveksnih funkcijâ ima bar koliko i pozitivnih realnih brojeva, a to je card ℝ^{+} = 𝔠.

Surjekcijâ s ℝ na ℝ ima card S(ℝ) = 2^{𝔠}. \underline{Rj.:} Očito ih nema više od toga (jer S(ℝ) ⊆ ℝ^{ℝ}). Da ih ima bar toliko, može se vidjeti ovako: preslikavanje koje svakoj funkciji f : ℝ_{0}^{−} → ℝ pridružuje surjekciju f ∪ ln (proučite kako djeluje ta funkcija, te se uvjerite da je ona zaista element od S(ℝ)!), je injekcija. Dakle card S(ℝ) ≥ card ℝ^{ℝ_{0}^{−}} = 2^{𝔠}. Objašnjenje: jednostavno smo funkciju f proširili ln-om. Dobili smo funkciju koja na nepozitivnim brojevima djeluje kao f, a na pozitivnim kao ln. To je surjekcija jer je već ln “pokupio” sve realne brojeve u kodomeni.

Konvergentnih nizova ima 𝔠. \underline{Rj.:} Znamo da ih ima manje ili jednako nego svih nizova, dakle najviše 𝔠. S druge strane, za svaki x ∈ ℝ postoji konstantni niz (x, x, x, ….), koji je očito konvergentan (limes mu je x), i to pridruživanje (x ↦ (x, x, x, ….)) je injekcija s ℝ u skup konvergentnih nizova. Dakle, ima ih bar card ℝ = 𝔠.

Nizova s limesom 6 ima 𝔠. \underline{Rj.:} Sigurno ih nema više nego svih konvergentnih nizova, dakle ≤ 𝔠. S druge strane, svakom realnom x možemo injektivno pridružiti niz koji konvergira k 6, ovako: x ↦ (6 − x, 6 − \frac{x}{2}, 6 − \frac{x}{3}, ….) (ili jednostavnije, x ↦ (x, 6, 6, 6, ….) — primijetimo da je i ovo injekcija, iako se dobiveni nizovi podudaraju svuda osim u prvom mjestu).

Za netrivijalne konačnodimenzionalne realne vektorske prostore V i W, linearnih operatorâ s V u W ima card Hom(V, W) = 𝔠. \underline{Rj.:} Znamo da svaki konačnodimenzionalni vektorski prostor ima bazu, pa fiksirajmo baze e = (e_{0}, …, e_{n−1}) u V i f = (f_{0}, …, f_{m−1}) u W. Takoder znamo da je koordinatizacija A ↦ A(e, f) izomorfizam, dakle specijalno bijekcija, izmedu Hom(V, W) i ℝ^{m×n}, odnosno linearnih operatorâ s V u W ima točno koliko i realnih matricâ tipa m × n, a to je card ℝ^{card(m×n)} = 𝔠^{m·n} = 𝔠 (jer su V i W netrivijalni, m · n ≥ 1).

Uz oznake kao u prethodnom zadatku, koliko ima regularnih linearnih operatora s V na W? \underline{Rj.:} Ako je m ≠ n (odnosno V ≅ W̸), odgovor je 0: nema izomorfizma izmedu V i W. S druge strane, ako je m = n (BSOMP V = W), odgovor je 𝔠: ≤ 𝔠 zbog prethodnog zadatka (nema ih više nego svih linearnih operatorâ), a ≥ 𝔠 jer svakom realnom skalaru α ≠ 0 možemo pridružiti (injektivno) regularni operator α · I. Dakle card GL(V) = card GL(n, ℝ) ≥ card ℝ \ {0} = 𝔠.

POGLAVLJE 5 Relacije i uredaji

1. Osnovno o relacijama

Ponovimo:

• Ureden par skupova a i b, (a, b), definira se kao {{a}, {a, b}}. Dva uredena para su jednaka ako su im prve komponente jednake, i druge komponente jednake. Komponente a i b se mogu dobiti iz (a, b) pomoću generaliziranih skupovnih operacijâ.

• Kartezijev produkt skupova A i B, A×B, je skup svih uredenih parova kojima je prva komponenta iz A, a druga iz B. A×B je element od PPP(⋃{A, B}). Operacija Kartezijevog produkta je distributivna prema elementarnim skupovnim operacijama, i koristi se za definiranje produkta kardinalnih brojeva.

• Relacija izmedu skupova A i B je podskup njihovog Kartezijevog produkta: ρ ⊆ A × B. Dakle, za svaki par (a, b), pri čemu je a ∈ A ∧ b ∈ B, možemo pitati je li on u ρ. Ako jest, pišemo aρb; u suprotnom, pišemo a ρ̸ b.

• Binarna relacija na skupu A je relacija izmedu A i A, odnosno podskup Kartezijevog kvadrata A × A = A^{2}. Iako se svaka relacija izmedu A i B može promatrati kao binarna relacija na A ∪ B (dokažite!), ipak je prirodno binarne relacije gledati kao relacije izmedu objekata iste “vrste”.

Ubuduće će nas zanimati samo binarne relacije.

Binarna relacija ρ na skupu A može imati sljedeća svojstva (sve izjave su univerzalno kvantificirane po A, odnosno za varijable se pretpostavlja da označavaju proizvoljne elemente od A):

• ρ je refleksivna ako vrijedi xρx (za svaki x iz A);

• ρ je irefleksivna ako vrijedi x ρ̸ x (opet, za svaki x ∈ A);

• ρ je simetrična ako vrijedi xρy ⇒ yρx;

• ρ je asimetrična ako vrijedi xρy ⇒ y ρ̸ x;

• ρ je antisimetrična ako vrijedi xρy ∧ yρx ⇒ x = y;

• ρ je tranzitivna ako vrijedi xρy ∧ yρz ⇒ xρz;

• ρ je itranzitivna ako vrijedi xρy ∧ yρz ⇒ x ρ̸ z;

• ρ je koneksna ako vrijedi xρy ∨ yρx ∨ x = y; Pokažimo prvo da su mnoga od tih svojstava medusobno povezana:

Irefleksivnost ∧ tranzitivnost ⇒ asimetričnost. \underline{Rj.:} Pretpostavimo da je ρ na A irefleksivna i tranzitivna, te da nije asimetrična. Ovo zadnje znači da postoje a i b iz A, takvi da je aρb ∧ bρa. Po tranzitivnosti bi tada trebalo biti aρa (kao i bρb), a to je u kontradikciji s irefleksivnošću.

Asimetričnost ⇒ antisimetričnost ∧ irefleksivnost. \underline{Rj.:} Kad bi bilo aρb ∧ bρa za asimetričnu relaciju ρ, to bi značilo aρb ∧ ¬(aρb), što je kontradikcija — iz čega slijedi bilo što, pa tako i a = b. Kad bi, za neki a ∈ A, bilo aρa, po asimetričnosti bi bilo i ¬(aρa), što je kontradikcija. Dakle vrijedi i irefleksivnost.

Refleksivnost ∧ simetričnost ∧ koneksnost ⇒ univerzalnost (ρ = A^{2}). Uzmimo proizvoljne a i b iz A. Tada po koneksnosti imamo tri slučaja:

1. aρb.

2. bρa. Tada je po simetričnosti i aρb.

3. a = b. Tada je po refleksivnosti aρa, dakle i aρb.

Dakle, uvijek je aρb, za sve a i b iz A, odnosno ρ = A^{2}.

Simetričnost ∧ tranzitivnost ⇒ reducirana refleksivnost (postoji skup na kojem je ρ refleksivna relacija). \underline{Rj.:} Ako s B označimo skup samo onih elemenata od A koji se zaista pojavljuju u relaciji ρ (zbog simetričnosti, to možemo dobiti i kao B := {x ∈ A : (∃y ∈ A)(xρy)} — uočite sličnost s definicijom slike funkcije), tada je ρ binarna relacija i na B. Štoviše, ako je b ∈ B proizvoljan, postoji a ∈ A takav da je bρa. Po simetričnosti je tada i aρb, te po tranzitivnosti bρb. Dakle ρ je refleksivna na B.

2. Parcijalni uredaji

Relacije nam služe da opišemo odnose elemenata. Promotrimo neke jednostavne odnose medu skupovima, i pogledajmo koja svojstva oni imaju. Po uzoru na njih, definirajmo skupine gornjih svojstava koje ćemo smatrati “dobrima”.

• “Biti podskup”. Ako je S bilo kakav skup, za proizvoljne njegove elemente a i b možemo pitati je li a ⊆ b. Dakle, imamo relaciju ⊆ na skupu S. Lako se vidi da je ona refleksivna, antisimetrična i tranzitivna. S obzirom na to da nam ⊆ služi da u(spo)redujemo skupove (kažemo koji je “veći” a koji “manji”), općenito relaciju s ta tri svojstva zovemo refleksivni parcijalni uredaj, skraćeno RPU. (‘parcijalni’ jer ne možemo svaka dva skupa “usporediti”, na primjer {1} i {2}). Općenito o takvim relacijama razmišljamo pomoću fraze “manje ili jednako”, i bilježimo ih simbolima poput ⪯.

• “Biti pravi podskup”. Kao i gore, samo sada imamo relaciju ⊂ na S. Takoder je antisimetrična (štoviše, asimetrična) i tranzitivna, no za razliku od ⊆, relacija ⊂ je irefleksivna. Jednako nam tako može služiti za uredivanje skupova, i jednako tako ne možemo uvijek svaka dva skupa usporediti, pa općenito relaciju koja je irefleksivna i tranzitivna (vidjeli smo da to povlači a(nti)simetričnost) zovemo irefleksivni parcijalni uredaj, skraćeno IPU. Općenito o takvim relacijama razmišljamo pomoću fraze “strogo manje”, i bilježimo ih simbolima poput ≺.

• “Biti ekvipotentan”. Ako promotrimo relaciju ∼ na skupu S, odnosno za svaka dva njegova elementa se pitamo jesu li ekvipotentni, vidimo da ona ima svojstva refleksivnosti, simetričnosti i tranzitivnosti. Ona nam takoder služi za usporedivanje skupova, ali drugačije: ne tako da kaže koji je od dva skupa “veći” a koji je “manji”, već koja dva su po nečem “jednaki” (ovdje po kardinalitetu, odnosno broju elemenata). Binarnu relaciju s ta tri svojstva zovemo relacija ekvivalencije, skraćeno REQ. Općenito o takvim relacijama razmišljamo pomoću fraze “jednako”, i bilježimo ih simbolima poput ∼. Ponovite iz Elementarne matematike što znate o particijama i vezi particijâ s relacijama ekvivalencije!

Primijetimo sljedeću stvar o RPU i IPU: ako na skupu A imamo neki IPU ≺, njemu prirodno odgovara jedan RPU na A, definiran formulom a ⪯ b : ⟺ a ≺ b ∨ a = b. Takoder, ako imamo zadan RPU, recimo ⪯, na skupu A, jednako lako možemo definirati pripadni IPU: a ≺ b : ⟺ a ⪯ b ∧ a ≠ b. Drugim riječima, izmedu skupa svih RPU na A i skupa svih IPU na A postoji prirodna bijekcija ⪯↦≺. To nas dovodi do zaključka da su RPU i IPU samo dva načina za opisati jedan te isti koncept (parcijalni uredaj elemenata od A), baš kao što su relacije ekvivalencije i particije dva načina za opisati jedan te isti koncept (poistovjećivanje pojedinih elemenata nekog skupa). Kao posljedica toga, često se jednostavno govori o parcijalnom uredaju, a iz tipa oznake (≺ ili ⪯), ili konteksta zadatka, treba odrediti misli li se na refleksivni ili irefleksivni parcijalni uredaj. Ako je potpuno svejedno, podrazumijeva se IPU.

Ako je R parcijalni uredaj na skupu A, često se promatra struktura (A, R) skupa s parcijalnim uredajem na njemu, i kaže se da je to parcijalno ureden skup, skraćeno PUS.

U PUSovima možemo definirati mnoge druge pojmove preko uredaja. Kao što je već rečeno, koristit ćemo IPU ili RPU, kako nam već više odgovara za pojedinu definiciju.

Neka je (A, ≺) PUS. (≺ je IPU: pripadni RPU označimo s ⪯. Naravno, b ≻ a znači a ≺ b, i b ⪰ a znači a ⪯ b.) Neka je takoder B neki podskup od A, i a neki element od A. Kažemo:

• a je donja meda za B ako (∀b ∈ B)(a ⪯ b).

• a je gornja meda za B ako (∀b ∈ B)(a ⪰ b).

• a je najmanji element od B ako je a donja meda za B, i a ∈ B.

• a je najveći element od B ako je a gornja meda za B, i a ∈ B.

• a je minimalni element od B ako a ∈ B ∧ ¬(∃b ∈ B)(b ≺ a).

• a je maksimalni element od B ako a ∈ B ∧ ¬(∃b ∈ B)(b ≻ a).

• a je infimum za B ako je a najveća donja meda za B.

• a je supremum za B ako je a najmanja gornja meda za B.

• početni komad (u A) od a je p_{A}(a) := {b ∈ A : b ≺ a}.

• prethodnik od a je bilo koji element od p_{A}(a).

• neposredni prethodnik od a je maksimalni element od p_{A}(a).

• B je gust (u A) ako (∀(a_{1}, a_{2}) ∈≺)(∃B ∈ B)(a_{1} ≺ b ∧ b ≺ a_{2}).

• B je kofinalan (u A) ako (∀a ∈ A)(∃b ∈ B)(b ⪰ a).

Primijetimo bitnu razliku izmedu definicije najmanjeg i minimalnog (te analogno najvećeg i maksimalnog) elementa: najmanji je onaj element danog skupa, koji je “manji” od svih ostalih, dok je minimalan onaj od kojeg nema “manjih” u tom skupu. Za parcijalne uredaje, to općenito nije isto: za dani element a ∈ B, elemente skupa B možemo u odnosu na njega podijeliti u četiri skupine:

(1) oni jednaki a. Naravno, to je samo a: skup takvih je {a}.

(2) oni “manji” od a. Skup takvih je početni komad u B od a, odnosno p_{(B,≺∩B^{2})}(a).

(3) oni “veći” od a. Skup takvih je takoder početni komad od a, ali u obrnuto uredenom skupu, p_{(B,≻∩B^{2})}(a).

(4) svi ostali — dakle, oni neusporedivi s a.

Najmanji je onaj element za kojeg su druga i četvrta skupina prazne (dakle, svi elementi od B, osim njega, su u trećoj skupini). Minimalan je onaj za kojeg je druga skupina prazna (ali četvrta ne mora biti). Iz toga direktno slijedi da je najmanji element ujedno i minimalan, no obrat ne vrijedi općenito. Takoder, tamo gdje nema neusporedivih elemenata (više o tome kasnije), ta dva pojma se podudaraju.

Jednako tako, najveći je onaj element za kojeg su treća i četvrta skupina prazne, dok je maksimalan onaj za kojeg je treća skupina prazna. Vrijede analogni zaključci: “biti najveći” povlači “biti maksimalan”, ali obrat ne vrijedi općenito — ipak, vrijedi ako nema neusporedivih elemenata.

Štoviše, najmanji (i najveći) element je jedinstven (ako postoji): ako su a i b dva takva, vrijedi a ⪯ b jer je a najmanji, i b ⪯ a jer je b najmanji, pa po antisimetričnosti imamo a = b. Zato možemo imati oznaku za najmanji i najveći element (ako su definirani): najm B i najv B. Naravno, minimalni (maksimalni) element ne mora biti jedinstven: ako imamo dva neusporediva elementa a i b, oba su minimalni (i maksimalni) elementi skupa {a, b}.

Budući da je infimum od B jednostavno najveći element skupa svih donjih medâ za B, on je takoder jedinstven, pa možemo imati oznaku inf B. Analogno za supremum, sup B.

DZ: je li neposredni prethodnik zadanog elementa nužno jedinstven? Dajte dokaz ili kontraprimjer.

Ako su (A, ≺) i (B, ◁) dva PUSa, na Kartezijevom produktu A × B možemo definirati parcijalni uredaj ⊣ formulom

(a_{1}, b_{1}) ⊣ (a_{2}, b_{2}) : ⟺ a_{1} ≺ a_{2} ∧ b_{1} ◁ b_{2} .

⊣ se zove produktni uredaj, i prirodni je način da se Kartezijev produkt parcijalno uredi. No nedostaju mu mnoga dobra svojstva: na primjer, njegov pripadni RPU nije ekvivalentno definiran kao produkt pripadnih RPUova ⪯ i ⊴. Konkretno, na primjer, ako je b_{1} ≠ b_{2}, parovi (a, b_{1}) i (a, b_{2}) su neusporedivi u irefleksivnom produktnom uredaju (provjerite!). Bolje načine za urediti Kartezijev produkt ćemo promotriti kasnije.

3. Primjeri

(1) Ako su Σ i Π dvije particije skupa X, kažemo da je Σ finija od Π, ako vrijedi

(∀A ∈ Σ)(∃B ∈ Π)(A ⊆ B)

(na primjer, particija {{1, 2}, {3, 5}, {4}} skupa {1, 2, 3, 4, 5} je finija od particije {{1, 2}, {3, 4, 5}}). Tada je “biti finija” parcijalni uredaj na skupu svih particijâ od X. \underline{Rj.:} Ovdje se očito radi o RPU: particija jest finija od same sebe, po gornjoj definiciji. Dakle, treba provjeriti tri svojstva:

refleksivnost: Ako je Σ proizvoljna particija od X, za svaki blok A ∈ Σ postoji taj isti blok (nazovimo ga) B = A ∈ Σ, tako da je A = B, specijalno A ⊆ B.

antisimetričnost: Neka je Σ finija od Π, i Π finija od Σ. Za svaki blok A ∈ Σ, postoji blok B ∈ Π takav da je A ⊆ B. Za taj blok B, budući da je Π finija od Σ, postoji blok C ∈ Σ takav da je B ⊆ C. Sveukupno imamo A ⊆ C, te kad bi bilo A ⊂ C, morali bismo imati (svojstva particije!) ∅ ≠ A = A ∩ C = ∅, što je kontradikcija. Dakle A = C, pa i A = B, odnosno, svaki element od Σ je u Π: Σ ⊆ Π. Analogno bismo dobili i Π ⊆ Σ.

tranzitivnost: Neka je Σ finija od Π, i Π finija od Ω. Kao gore, ako za svaki blok A ∈ Σ postoji nadskup B ∈ Π, a za njega postoji nadskup C ∈ Ω, imamo A ⊆ C, te time da je Σ finija od Ω (za svaki A postoji C).

(2) Standardni uredaj na ℝ^{ℝ},

f ≤ g : ⟺ (∀x ∈ ℝ)(f(x) ≤ g(x)) ,

je RPU. Naravno, postoje neusporedivi elementi: na primjer, identiteta f(x) := x i promjena predznaka g(x) := −x su neusporedive — za pozitivne x je f(x) > g(x), dok je za negativne f(x) < g(x).

(3) ⊂ na skupu S := P({0, 1, 2})\{∅} je IPU. (Već je rečeno, ⊂ je prototip IPUa na familijama skupova, i često se podrazumijeva kao parcijalni uredaj ako on nije naveden.) Vrijede sljedeće tvrdnje:

• {0} i {1} su neusporedivi.

• {0, 1} i {1, 2} su neusporedivi.

• {0, 1} i {1} su usporedivi: {1} ⊂ {0, 1}.

• Singletoni ({0}, {1} i {2}) su minimalni elementi od S.

• Ne postoji najmanji element od S.

• Najveći element od S je najv S = {1, 2, 3}.

• najm{{2}, {0, 2}, {1, 2}, {0, 1, 2}} = {2}.

• {1, 2} je gornja meda za {{1}}.

• {0, 2} nije gornja meda za {{1}}.

• inf{{1}, {2}} ne postoji (u S).

• inf{{1, 2}, {0, 1}} = {1}.

• sup S = {0, 1, 2}.

• inf ∅ = {0, 1, 2} (u S). Eventualno treba objasniti posljednji redak: donja meda za ∅ je bilo koji element koji nije manji ili jednak od svih elemenata praznog skupa — dakle bilo koji element od S. Najveća donja meda je tada najveći element od S, a to je {0, 1, 2}.

(4) Na skupu S := {1, 2, 3, 4, 5, 6}, relacija

δ := {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), (2, 6), (3, 6)}

je IPU (pažljiviji čitatelj će u δ prepoznati restrikciju relacije stroge

djeljivosti). 1 je najmanji element. 4, 5 i 6 su maksimalni elementi — najvećeg elementa nema. Infimum skupa {2, 4, 6}

je 2, dok supremum tog skupa ne postoji (u S). inf{4, 5} = 1.

(5) Promotrimo PUS (ℕ\{0, 1}, |) (prirodni brojevi od 2 nadalje, s refleksivnom relacijom djeljivosti). Minimalni elementi su upravo prosti brojevi, i oni su medusobno neusporedivi. Najmanjeg elementa nema. Maksimalnih elemenata nema (svaki broj n dijeli na primjer 2n), pa nema ni najvećeg. Supremum konačnog nepraznog skupa je najmanji zajednički višekratnik brojeva u tom skupu.

(6) Promotrimo strukturu (ℤ, |).

Ovdje ne možemo pričati o pojedinim elementima kao o maksimalnim/minimalnim/najvećim/najmanjim, budući da | na ℤ nije RPU (niti IPU): ne zadovoljava svojstvo antisimetričnosti. Naime, 6| − 6 i −6|6, ali 6 ≠ −6.

(7) Malo bolje ureden skup od PUSa je tzv. “usmjereni skup”, u kojem svaki dvočlani podskup ima gornju medu. Dakle, usmjeren skup je PUS (A, ≺) koji ima svojstvo

(∀a ∈ A)(∀b ∈ A)(∃g ∈ A)(g ⪰ a ∧ g ⪰ b) .

Primijetimo: ako nemamo neusporedivih elemenata, a i b ćemo uvijek moći usporediti, pa će onaj veći biti dobar g. No usmjerenost je slabije svojstvo od toga (vidjeti (5) za primjer usmjerenog skupa s neusporedivim elementima). Ipak vrijedi: U usmjerenom skupu je maksimalni element, ako postoji, jedinstven — štoviše, najveći. Dokažimo to! \underline{Rj.:} Neka je PUS (A, ≺) usmjeren, i a ∈ A maksimalan. Dakle, ne postoji b ≻ a u A. Pretpostavimo da a nije najveći — dakle, ¬(∀c ∈ A)(a ⪰ c), odnosno (∃c ∈ A)(a ⪰̸ c). Uzmimo jedan takav c. Očito c ≠ a. Zbog usmjerenosti, skup {c, a} ima gornju medu, neka je to b. Dakle vrijedi b ⪰ a, što znači b ≻ a ∨ b = a. Oba slučaja vode na kontradikciju: b ≻ a jer je a maksimalan, a b = a jer bi onda trebalo biti a = b ⪰ c.

(8) Svaki kofinalan podskup usmjerenog PUSa je takoder usmjeren. \underline{Rj.:} Neka je (A, ≺) usmjeren PUS, i neka je B ⊆ A kofinalan. Ako je {b, c} dvočlani podskup od B, to je ujedno i dvočlani podskup od A, pa ima gornju medu u A: a ∈ A takav da je a ⪰ b∧a ⪰ c. Budući da je B kofinalan, za taj a postoji g ∈ B takav da je g ⪰ a, a onda po tranzitivnosti i g ⪰ b ∧ g ⪰ c. Dakle, svaki dvočlani podskup od B ima gornju medu u B.

(9) Neka je S proizvoljan skup. Promotrimo (refleksivno ureden) PUS (P(S), ⊆). Njegov najveći element je S, dok je najmanji element ∅. Za proizvoljnu familiju F ⊆ P(S), gornja meda od F je bilo koji podskup od S koji sadrži (kao podskupove) sve F ∈ F. Najmanja gornja meda je onda sup F = ⋃ F. Analogno, za F ≠ ∅, inf F = ⋂ F, dok je inf ∅ = S (u P(S)). Vidimo da u promatranom PUSu svaki podskup ima i infimum i supremum. Takav PUS se zove (uredajno) potpun. Primijetimo razliku od potpunosti skupa ℝ u analizi, gdje samo neprazni ograničeni skupovi imaju infimum/supremum. No

kad bismo ℝ proširili s još dva elementa, +∞ i −∞, te definirali (∀x ∈ ℝ)(−∞ < x ∧ x < +∞), tako dobiven skup bi bio uredajno potpun.

(10)^{⋆}Za uredajnu potpunost dovoljno je tražiti samo jedan od gornja dva uvjeta: “svaki podskup ima infimum” je ekvivalentno sa “svaki podskup ima supremum”. Ideja dokaza: supremum nekog skupa je infimum skupa njegovih gornjih medâ.

4. Totalno uredeni skupovi. Sličnosti

Vidjeli smo da mnoge pojmove ne možemo prirodno i intuitivno definirati u PUSovima — smetaju nam neusporedivi elementi. Usmjereni skupovi su donekle bolji, ali još uvijek ne dovoljno. Zato ćemo se ubuduće ograničiti na proučavanje skupova u kojima nema neusporedivih elemenata. (Poslije ćemo promatrati još bolje uredaje.)

Totalno ureden skup (skraćeno TUS) je PUS (A, ≺), koji ima dodatno svojstvo (∀a ∈ A)(∀b ∈ A)(a ≺ b ∨ a = b ∨ b ≺ a). Za pripadni RPU tada vrijedi (∀a ∈ A)(∀b ∈ A)(a ⪯ b∨b ⪯ a). Dakle, u TUSovima nema neusporedivih elemenata, i kao posljedica toga pojmovi najmanjeg i minimalnog, te najvećeg i maksimalnog, elementa se podudaraju. Ako postoje za skup B ⊆ A, zovemo ih jednostavno minimum i maksimum od B, i označavamo s min B i max B. Štoviše, kao što se lako dokaže indukcijom po broju elemenata, svaki konačan podskup TUSa ima minimum i maksimum. Svi TUSovi su takoder usmjereni: za gornju medu skupa {a, b} možemo uzeti max{a, b}.

Imajući TUSove, možemo definirati totalan uredaj i na Kartezijevom produktu (dakle puno bolje nego produktni uredaj), i to na dva važna načina. Neka su (A, <_{A}) i (B, <_{B}) dva TUSa. Definiramo sljedeće uredaje na A × B:

• Leksikografski uredaj je definiran formulom

(a_{1}, b_{1}) <_{L} (a_{2}, b_{2}) : ⟺ a_{1} < a_{2} ∨ (a_{1} = a_{2} ∧ b_{1} < b_{2}) .

• Antileksikografski uredaj je definiran formulom

(a_{1}, b_{1}) < (a_{2}, b_{2}) : ⟺ b_{1} < b_{2} ∨ (b_{1} = b_{2} ∧ a_{1} < a_{2}) .

Usprkos nazivu, koji potječe od duge prakse uredivanja riječî u rječnicima, antileksikografski uredaj je prirodniji uredaj na produktu TUSova, što će postati jasnije uskoro. Zato se antileksikografski uredaj često podrazumijeva kada se govori o produktu dva TUSa.

Primijetimo da oba gornja uredaja, i leksikografski i antileksikografski, proširuju produktni uredaj: ako je jedan par manji od drugog u produktnom uredaju, bit će i leksikografski i antileksikografski manji od njega. Dakle, gornja dva uredaja se razlikuju samo po tome kako ureduju parove koji su bili neusporedivi u produktnom uredaju.

Dokažimo da je antileksikografski uredaj zaista totalni uredaj:

irefleksivnost: Pokušajmo usporediti (a, b) s (a, b). Niti vrijedi b <_{B} b (irefleksivnost od <_{B}), niti vrijedi b = b ∧ a <_{A} a (irefleksivnost od <_{A}), pa vidimo da (a, b) ≮ (a, b).

tranzitivnost: Neka je (a, b) < (c, d) i (c, d) < (e, f). Svaka od tih nejednakosti vodi na dva slučaja, pa ukupno imamo četiri mogućnosti:

∗ b <_{B} d∧d <_{B} f. Po tranzitivnosti od <_{B}, imamo b <_{B} f,

a iz toga (a, b) < (e, f).

∗ b <_{B} d ∧ (d = f ∧ c <_{A} e). Opet imamo b <_{B} d = f,

odnosno b <_{B} f, iz čega (a, b) < (e, f).

∗ (b = d ∧ a <_{A} c) ∧ d <_{B} f. Imamo b = d <_{B} f, i opet

b <_{B} f.

∗ b = d ∧ a <_{A} c ∧ d = f ∧ c <_{A} e. Po tranzitivnosti od <_{A},

imamo b = f ∧ a <_{A} e, odnosno (a, b) < (e, f).

totalnost: Neka je (a, b) ≠ (c, d). To znači a ≠ c ∨ b ≠ d. Ako je b ≠ d, zbog totalnosti od <_{B} imamo b <_{B} d ∨ d <_{B} b. U prvom slučaju je (a, b) < (c, d), a u drugom je (c, d) < (a, b). Ako je pak b = d, tada mora biti a ≠ c, odnosno zbog totalnosti od <_{A}, a <_{A} c ∨ c <_{A} a. Opet, u prvom slučaju je b = d ∧ a <_{A} c, odnosno (a, b) < (c, d), dok je u drugom (c, d) < (a, b). Dakle, svaka dva para se mogu usporediti antileksikografski.

No glavna snaga TUSova nije u produktima, već u preslikavanjima. Za TUSove kao strukture se može prirodno definirati pojam homomorfizma, koji se u tom slučaju zove “sličnost”, i odgovara pojmu strogo rastuće surjekcije u analizi.

Neka su (A, <_{A}) i (B, <_{B}) dva TUSa. Preslikavanje f : A → B zovemo sličnost izmedu A i B, ako je f bijekcija koja čuva uredaj:

a <_{A} a′ ⟹ f(a) <_{B} f(a′) .

Ako postoji sličnost izmedu ta dva TUSa, kažemo da su oni slični, i pišemo (A, <_{A}) ≃ (B, <_{B}). Ako se na A i B podrazumijevaju uredaji (na primjer ⊂), pišemo samo A ≃ B.

Primijetimo da je sličnost strogo jača od ekvipotentnosti: ako izmedu dva TUSa postoji sličnost, ona je bijekcija, te ta dva TUSa imaju isti broj elemenata. No obrat ne mora vrijediti: na primjer, nemoguće je naći sličnost izmedu TUSa (ℕ, <) i (ℕ, >), iako je trivijalno ℕ ∼ ℕ. Malo zanimljiviji primjer: ℤ i ℚ, sa standardnim uredajima, nisu slični, iako su ekvipotentni (oba su prebrojivi). Naravno, za ℚ i ℝ odmah znamo da nisu slični — budući da nisu ekvipotentni. Možda je zanimljivo reći i da su za konačne TUSove ta dva pojma ekvivalentna: konačni TUSovi su slični ako i samo ako su ekvipotentni.

Dokažimo da sličnost TUSova, iako se u definiciji traži samo jedan smjer, zapravo čuva uredaj u oba smjera: odnosno, ako za sličnost f vrijedi f(a) <_{B} f(a′), tada vrijedi i a <_{A} a′. \underline{Rj.:} Pretpostavimo suprotno: a ≮_{A} a′. Zbog totalnosti od <_{A}, tada mora biti a = a′ ili a′ <_{A} a. U prvom slučaju je f(a) = f(a′), pa ne može biti f(a) <_{B} f(a′) zbog irefleksivnosti. U drugom slučaju je f(a′) <_{B} f(a), pa opet ne može biti f(a) <_{B} f(a′), ovaj put zbog antisimetričnosti.

DZ: sličnim argumentom dokažite da je umjesto bijektivnosti dovoljno tražiti surjektivnost: funkcija koja čuva uredaj je nužno injekcija.

Ako mislimo da su dva TUSa slični, jedan način (iako ne uvijek najlakši — više kasnije) kako to dokazati je da jednostavno nademo sličnost: bijekciju koja čuva uredaj. Na primjer:

Ako je a < b i c < d za realne brojeve a, b, c i d, tada je, uz standardni uredaj, ⟨a, b⟩ ≃ ⟨c, d⟩. \underline{Rj.:} Funkcija x ↦ b+ \frac{d−b}{c−a}(x−a) (jednadžba pravca kroz (a, c) i (b, d)!) je sličnost.

(uz standardni uredaj) ℝ ≃ ℝ^{+} := ⟨0, +∞⟩ \underline{Rj.:} exp je jedna tražena sličnost. DZ: nadite ih još!

ℝ^{+} ≃ ℝ^{−} \underline{Rj.:} x ↦ −\frac{1}{x} je jedna sličnost.

ℝ ≃ ⟨−1, 1⟩ \underline{Rj.:} \frac{2}{π} · arc tg je jedna sličnost.

ℚ ≃ ⟨−1, 1⟩ ∩ ℚ \underline{Rj.:} Ne, (\frac{2}{π} · arc tg)|_{ℚ} nije tražena sličnost (zašto?). Treba nam strogo rastuća surjekcija na racionalne brojeve izmedu −1 i 1. Jedna takva dana je formulom x ↦ \frac{x}{1+|x|} — dokažite da je to tražena sličnost!

⟨0, 2⟩ ≃ ⟨0, 1] ∪ ⟨2, 3].

\underline{Rj.:} Jedna sličnost je zadana s f(x) := \{ \begin{matrix}x , & x ≤ 1 \\ x + 1 , & x > 1 \end{matrix} .

DZ: ℝ ≃ ℝ \ [0, 1⟩.

DZ: [0, 1] ≃ [0, 1] \ ⟨\frac{1}{3}, \frac{2}{3}] ≃ [0, 1] \ (⟨\frac{1}{3}, \frac{2}{3}] ∪ ⟨\frac{1}{9}, \frac{2}{9}] ∪ ⟨\frac{7}{9}, \frac{8}{9}]) (i tako dalje).

5. Invarijante sličnosti

No kako dokazati da dva TUSa nisu slični? Pokazuje se da je to najefikasnije raditi pomoću invarijanata. Naime, sličnost je, kao i ekvipotentnost, relacija ekvivalencije na bilo kojem skupu TUSova (iako svi TUSovi zajedno ne čine skup), te za neku klasu TUSova možemo reći da su svi oni medusobno slični (na primjer, svi tročlani TUSovi su medusobno slični). Invarijanta sličnosti je onda svojstvo koje svi medusobno slični TUSovi ili istodobno imaju, ili istodobno nemaju. Preciznije:

Za svojstvo TUSova P kažemo da je invarijanta sličnosti ako, za sve TUSove A i B, A ≃ B ∧ P (A) ⇒ P (B). Postoje mnoge invarijante sličnosti, i dokazi da je nešto invarijanta sličnosti obično su jednostavni, iako znaju biti dugački (vidjeti dolje). Ako nademo neku invarijantu sličnosti P takvu da jedan TUS ima svojstvo P, a drugi ga nema, odmah znamo da ta dva TUSa ne mogu biti slični.

Već smo vidjeli primjer trivijalne invarijante sličnosti: kardinalni brojevi. Ako dva skupa imaju različite kardinalne brojeve (npr. jedan je prebrojiv, a drugi nije; ili je jedan konačan, a drugi beskonačan), znamo da nisu slični. Invarijante sličnosti su obično svojstva iskazana pomoću broja elemenata, i uredaja — odnosno, onog što sličnosti čuvaju. Na primjer:

Svojstvo “imati najveći element (maksimum)” je invarijanta sličnosti. \underline{Rj.:} Trebamo dokazati da ako TUS (A, <_{A}) ima najveći element (recimo a), te (A, <_{A}) ≃ (B, <_{B}), tada i B mora imati najveći element. Označimo sličnost izmedu A i B s f. Tvrdimo da je f(a) najveći element od B. Zaista, uzmimo proizvoljni b ∈ B, različit od f(a). Taj b je, zbog surjektivnosti od f, slika nekog c ∈ A. Takoder, zbog injektivnosti od f, c ≠ a. Budući da je a = max A, znamo da je c <_{A} a. Sada po sličnosti f, f(c) <_{B} f(a), odnosno b <_{B} f(a). Budući da to vrijedi za proizvoljni b ∈ B \ {f(a)}, zaključujemo da je f(a) najveći element u B.

Svojstvo “biti gust” (gustoća) je invarijanta sličnosti. \underline{Rj.:} Neka je TUS (A, <_{A}) gust, (B, <_{B}) neki TUS sličan s (A, <_{A}), i f : A → B sličnost. Trebamo dokazati da je (B, <_{B}) gust. Uzmimo proizvoljni par (b_{1}, b_{2}) ∈<_{B} (dakle, b_{1,2} ∈ B takve da vrijedi b_{1} <_{B} b_{2}). Po surjektivnosti, ti b_{1} i b_{2} su slike po f nekih elemenata a_{1} i a_{2} iz A. Budući da, kao što smo vidjeli, f čuva uredaj i u suprotnom smjeru, iz b_{1} <_{B} b_{2} možemo zaključiti a_{1} <_{A} a_{2}. Sada, budući da je (A, <_{A}) gust, izmedu a_{1} i a_{2} postoji neki element a (dakle, a ∈ A takav da vrijedi a_{1} <_{A} a <_{A} a_{2}). No tada je, po sličnosti, b_{1} <_{B} f(b) <_{B} b_{2}, odnosno f(b) je element izmedu b_{1} i b_{2} koji smo trebali naći. Budući da to vrijedi za proizvoljne b_{1} <_{B} b_{2}, zaključujemo da je B gust.

Uredajna potpunost je invarijanta sličnosti. \underline{Rj.:} Dovoljno je vidjeti da je “svaki podskup ima supremum” invarijanta sličnosti (tvrdnja za infimum onda slijedi iz toga, ili po simetričnosti argumenta). Pa neka u TUSu (A, <_{A}) svaki podskup ima supremum, i neka je f sličnost izmedu (A, <_{A}) i (B, <_{B}). Neka je D ⊆ B proizvoljni podskup od B. Taj D je slika po f nekog podskupa C ⊆ A (preciznije, C := f^{⟨}(D)). U skupu A, podskup C ima supremum — označimo ga s c. Tvrdimo da je f(c) = sup D. Treba vidjeti da je f(c) gornja meda za D, i da je najmanja takva. Ovo prvo se vidi lako: neka je b ∈ D proizvoljni element. On je slika nekog a ∈ A, a po definiciji skupa C, mora biti a ∈ C. Dakle a ≤_{A} c = sup C, pa je i b ≤_{B} f(c) (lako se vidi, primjenom injektivnosti, da sličnost čuva i pripadni RPU, i to u oba smjera — dokažite!). Još je ostalo vidjeti da je f(c) najmanja gornja meda za D. Pa pretpostavimo da postoji neka manja, e <_{B} f(c). Taj e ∈ B je slika nekog a ∈ A, i sad se sličnim argumentom kao u gornjem odlomku dokaže da iz “e je gornja meda za D” slijedi “a je gornja meda za C”. No tada mora biti a ≥_{A} c (jer je c najmanja gornja meda za C, te po sličnosti e ≥_{B} f(c), što je u kontradikciji s pretpostavkom e <_{B} f(c). Dakle f(c) = sup D.

Svojstvo “svaki početni komad je konačan” je invarijatna sličnosti. \underline{Rj.:} Neka je u TUSu (A, <_{A}) svaki početni komad konačan, i neka je f : (A, <_{A}) ≃ (B, <_{B}) (često se skraćeno tako piše) sličnost TUSova. Uzmimo proizvoljni početni komad p_{B}(b) u B. Taj početni komad je jednostavno skup svih elemenata u B, manjih od nekog fiksnog elementa b ∈ B. No b je slika nekog a ∈ A, i po sličnosti vrijedi: za svaki c ∈ A, c <_{A} a ako i samo ako je f(c) <_{B} b — odnosno, c ∈ p_{A}(a) ⟺ f(c) ∈ p_{B}(b). Zbog bijektivnosti od f, dobijemo i da je restrikcija f|_{p_{A}(a)} takoder bijekcija, izmedu p_{A}(a) i p_{B}(b). Dakle ta dva početna komada imaju jednak broj elemenata — a budući da je po pretpostavci p_{A}(a) konačan, mora takav biti i p_{B}(b).

Kao što vidimo, svi dokazi invarijantnosti su poprilično “na isti kalup”

— što i nije tako slučajno, ako smo upoznati s teorijom koja stoji iza

Bethovog teorema definabilnosti. Dokažite da su sljedeća svojstva takoder invarijante sličnosti:

• Postojanje “predzadnjeg” elementa: takvog da postoji točno jedan element veći od njega.

• “Svaki neprazan podskup ima najmanji element” (dobar uredaj — svojstvo koje će nam biti vrlo bitno kasnije).

• “Svaki element ima neposrednog prethodnika ako nije najmanji, i neposrednog sljedbenika ako nije najveći” (diskretan uredaj).

• “ℝ-potpunost”: svaki neprazan podskup koji ima gornju medu, ima supremum.

• “Postoji samo konačno mnogo elemenata koji nemaju neposrednog prethodnika.”

• “Izmedu svaka dva elementa postoji samo konačno mnogo elemenata” (lokalno konačan uredaj).

Pokažimo sada kako se koriste invarijante sličnosti:

ℕ ≄ ℤ^{−} (ili (ℕ, <) ≄ (ℕ, >)) \underline{Rj.:} ℕ ima najmanji element (konkretno, 0), dok ℤ^{−} nema (za svaki a ∈ ℤ^{−} postoji manji a − 1 ∈ ℤ^{−}). Budući da je postojanje najmanjeg elementa invarijanta sličnosti, ta dva TUSa ne mogu biti slični.

ℚ ≄ ℤ \underline{Rj.:} ℚ je gust: za svaka dva a < b u ℚ, postoji \frac{a+b}{2} ∈ ℚ takav da je a < \frac{a+b}{2} < b. ℤ nije gust: recimo, izmedu 0 ∈ ℤ i 1 ∈ ℤ ne postoji nijedan cijeli broj. Gustoća je invarijanta sličnosti, dakle ℚ ne može biti sličan ℤ.

ℕ ≄ ℕ^{2} (sjetimo se, ℕ^{2} je Kartezijev kvadrat — na njemu podrazumijevamo antileksikografski uredaj) \underline{Rj.:} U ℕ postoji samo jedan element bez neposrednog prethodnika: 0 (svaki n ∈ ℕ \ {0} ima neposrednog prethodnika: n − 1 ∈ ℕ). U ℕ^{2} pak, postoji beskonačno mnogo elemenata bez neposrednog prethodnika: to su svi parovi iz ℕ^{2} oblika (0, n). Zaista, budući da od 0 nema manjih elemenata u ℕ, svaki antileksikografski prethodnik od (0, n) mora biti oblika (a, m), pri čemu je m < n. No nijedan od njih nije neposredan, jer postoji veći (a + 1, m) koji je takoder prethodnik od (0, n). Budući da je “postoji samo konačno mnogo elemenata bez neposrednog prethodnika” invarijanta sličnosti, nužno slijedi ℕ ≄ ℕ^{2}.

ℝ ≄ ℝ \ ℚ \underline{Rj.:} U ℝ, kao što znamo, svaki ograničen neprazan podskup ima supremum. Dokažimo da to u ℝ \ ℚ nije slučaj. Budući da je to svojstvo invarijanta sličnosti, iz toga će odmah slijediti tražena ne-sličnost. Promotrimo skup [0, 2] \ ℚ. To je očito podskup od ℝ \ ℚ, i neprazan je (recimo, sadrži element \sqrt{2}). Takoder je ograničen — recimo, gornja meda mu je \sqrt{5} ∈ ℝ \ ℚ (primijetimo da ne možemo reći npr. “gornja meda mu je 3”, jer 3 ∉ ℝ \ ℚ), a donja −\sqrt{5} ∈ ℝ \ ℚ. No, taj skup nema supremum u ℝ \ ℚ — za svaku gornju medu g ∈ ℝ \ ℚ skupa [0, 2] \ ℚ, možemo napraviti sljedeće: Promotrimo broj \frac{g}{2} +1. Lako se vidi da je to iracionalan pozitivan broj izmedu 2 i g. Ako je g < 2, to je element od [0, 2] \ ℚ, veći od g, dakle kontraprimjer za tvrdnju da je g gornja meda tog skupa. Ako je pak g > 2, to je takoder gornja meda za taj skup, manja od g. Naravno, ne može biti g = 2, jer g ∉ ℚ. Dakle, ne postoji najmanja gornja meda, u ℝ \ ℚ, za skup [0, 2] \ ℚ.

ℝ ≄ ℝ × 2 ((= ℝ × {0, 1} , s antileksikografskim uredajem)) \underline{Rj.:} Takoder, dokazat ćemo da ovaj desni skup nije ℝ-potpun. Pogledajmo prvo kako on izgleda: u njemu imamo dvije vrste parova — one oblika (r, 0), i one oblika (r, 1). Nazovimo prve “crveni”, a druge “plavi”. Antileksikografski uredaj kaže da su svi crveni manji od svih plavih, te da se crveni medusobno, kao i plavi medusobno, usporeduju kao i realni brojevi (njihove prve komponente). Efektivno, imamo dvije kopije od ℝ (“crveni ℝ” i “plavi ℝ”), svaka s prirodnim uredajem, posložene jedna do druge. Sada je jasno gdje neće biti supremuma: “crveni ℝ” (precizno, ℝ × {0}) je podskup od ℝ × 2, neprazan (na primjer, (0, 0) ∈ ℝ×{0}) i ograničen odozgo (na primjer, svaki (r, 0) je manji od (0, 1)), no nema najmanju gornju medu: svaka gornja meda mora biti “plava” (dokažite!), oblika (r, 1), a onda za nju postoji još manja gornja meda (r − 1, 1).

ℝ ≄ 2 × ℝ \underline{Rj.:} Opet imamo u desnom skupu dvije vrste točaka, no sad se prvo usporeduju po svojoj realnoj vrijednosti, a tek ako su realne vrijednosti jednake, kažemo da je crvena manja od plave. Ovaj skup očito nije sličan ℝ, jer uopće nije gust: na primjer, (0, 0) i (1, 0) (“crvena” i “plava” nula) su medusobno susjedni elementi, i nema nijednog elementa od 2 × ℝ izmedu njih.

ℝ × 2 ≄ 2 × ℝ (odnosno, (ℝ × 2, <) ≄ (ℝ × 2, <_{L})) \underline{Rj.:} Budući da smo vidjeli da desni skup nije gust, dovoljno je vidjeti da lijevi jest. Uzmimo u ℝ × 2 dva elementa (a, b) < (c, d). Ako su oba “iste boje” (b = d), tada izmedu njih postoji aritmetička sredina (\frac{a+c}{2}, b) iste boje. Ako su različitih bojâ, manji mora biti crveni, a veći plavi: b = 0 ∧ d = 1. No tada je recimo element (a + 1, 0) sigurno veći od (a, 0) = (a, b), a manji od (c, 1) = (c, d).

ℤ ≄ ℤ × 2 \underline{Rj.:} Skup ℤ je lokalno konačan: izmedu a ∈ ℤ i b ∈ ℤ ima samo konačno mnogo, konkretno |a − b| + 1, elemenata. S druge strane, skup ℤ × 2 nije lokalno konačan: izmedu (−1, 0) i (−1, 1) nalaze se svi elementi oblika (n, 0), za n ∈ ℕ — njih beskonačno mnogo.

ℤ × ℕ ≄ ℕ × ℤ \underline{Rj.:} U ℤ × ℕ svaki element (z, n) ima neposrednog prethodnika: to je (z − 1, n). No u ℕ × ℤ postoje elementi bez neposrednog prethodnika (štoviše, njih beskonačno mnogo): (0, z), za proizvoljni z ∈ ℤ.

6. Nekoliko težih zadataka

(1) Za svaki prirodni n, svi PUSovi kardinaliteta n su medusobno slični (odnosno, za konačne skupove je ekvipotentnost ekvivalentna sličnosti). \underline{Rj.:} Indukcijom po n, dokazat ćemo da je svaki skup s n elemenata sličan standardnom skupu n := {0, 1, …, n − 1}, sa standardnim uredajem <. Baza je trivijalna: svi skupovi s 0 elemenata su čak jednaki (prazan skup je jedinstven), pa su pogotovo slični (∅ je sličnost). Pretpostavimo da tvrdnja vrijedi za neki prirodni k. Ako je A proizvoljni skup s k + 1 elemenata, tada A ima maksimalni element (što se takoder može dokazati matematičkom indukcijom po k — DZ), označimo ga s a. Skup A \ {a} sada ima k elemenata, pa je po pretpostavci indukcije sličan sa standardno uredenim {0, …, k − 1}. Ako tu sličnost označimo s f : A \ {a} ≃ k, tvrdimo da je f_{+} := f ∪ {(a, k)} sličnost izmedu A i k + 1. Zaista, za svaka dva (različita, dakle BSOMP b <_{A} c) elementa b i c iz A, vrijedi jedno od sljedećeg:

• Nijedan od njih nije a. Tada su oba u A \ {a}, pa po pretpostavci indukcije f(b) < f(c), a time i f_{+}(b) < f_{+}(c) (jer je f_{+} proširenje od f).

• Jedan od njih je a (ne mogu biti oba, jer smo uzeli različite). Budući da smo pretpostavili b <_{A} c, mora biti c = a. No tada je f_{+}(b) = f(b) (jer je b ∈ A \ {a}), a to je najviše k − 1 (jer je to maksimum kodomene od f), što je strogo manje od k = f_{+}(a) = f_{+}(c), što smo i trebali dokazati.

(2) Neka je A proizvoljan skup. Ako promotrimo skup U(A) svih (irefleksivnih) parcijalnih uredajâ na A, tada je taj skup prirodno ureden relacijom ⊂ (“jedan uredaj je pravi podskup drugog” znači da u drugom uredaju možemo usporediti sve elemente koje smo mogli i u prvom, s jednakim ishodom, i još neke elemente koji su u prvom uredaju bili neusporedivi). Tada su maksimalni elementi PUSa (U(A), ⊂) upravo totalni uredaji na A. \underline{Rj.:} Jedan smjer je jasan: ako je < totalni uredaj na A, tada je maksimalan: kad bi ˜< bio njegov pravi nadskup, bilo bi (x, y) ∈ ˜< i (x, y) ∉< za neke x i y. Budući da je ˜< irefleksivan, imamo x ≠ y, a kako vrijedi x ≮ y, mora biti y < x (jer je < totalan), pa i y ˜<x (jer je ˜< nadskup od <), što je u kontradikciji s antisimetričnošću od ˜<.

Za drugi smjer treba malo više pisati: neka je < maksimalni element u U(A). Treba dokazati da je totalan. Pretpostavimo da nije, i neka su x i y dva neusporediva elementa s obzirom na <. Konstruirajmo novi uredaj ovako:

˜< := {a ∈ A; a ≤ x} × {b ∈ A; b ≥ y} ⋃ <

— odnosno, u < ubacimo još sve parove oblika (a, b), gdje je a ≤ x ∧ b ≥ y. Primijetimo da smo time ubacili i par (x, y), ali potencijalno i mnoge druge. ˜< je svakako binarna relacija na A (podskup od A^{2}). Dokažimo da je to IPU na A:

irefleksivnost Pretpostavimo da je z ˜<z za neki z. Budući da nije z < z (< je irefleksivna relacija), jedino je moguće z ≤ x∧z ≥ y, no to bi po tranzitivnosti dalo y ≤ x, što je kontradikcija s neusporedivošću x i y. Dakle, takav z ne postoji, pa imamo irefleksivnost.

tranzitivnost Neka je p ˜<q ∧q ˜<r za proizvoljne p, q i r iz A. Ako su oba para (p, q) i (q, r) već u <, imamo p < r po tranzitivnosti od <, pa i p ˜<r. Oba ne mogu biti novododani, jer bi to vodilo na q ≤ x ∧ q ≥ y, što je kontradikcija kao u prošlom odlomku. Dakle, još je ostao slučaj kada je jedan novododan, a drugi je u < — BSOMP p ≤ x∧q ≥ y∧q < r. Sada imamo y ≤ q < r odnosno y < r, što zajedno s p ≤ x daje p ˜<r.

Dakle, ˜< ∈ U(A). Po definiciji, <⊆ ˜<. Budući da je trivijalno x ˜<y ali x ≮ y, vrijedi ˜< ⊃<, što je u kontradikciji s pretpostavkom da je < maksimalan element u U(A).

(3) Neka je (A, <) proizvoljan TUS. Dokažite da postoji TUS (B, ⊂) (sa standardnim uredajem “biti pravi podskup”), sličan s A. \underline{Rj.:} Za B uzmimo skup svih početnih komada u A, dakle {p_{A}(a) ; a ∈ A}; a za sličnost preslikavanje p_{A} koje svakom a ∈ A pridružuje njegov početni komad p_{A}(a). To preslikavanje je surjekcija po definiciji: B je definiran kao slika od p_{A}. Treba još vidjeti da je injekcija, i da čuva uredaj (iz toga će odmah slijediti da je B TUS).

Ako su x ≠ y dva različita elementa iz A, oni su usporedivi (jer je A TUS), pa BSOMP x < y. No to znači x ∈ p_{A}(y). S druge strane, x ∉ p_{A}(x) (irefleksivnost), pa vidimo da su p_{A}(x) i p_{A}(y) različiti. Dakle, p_{A} je injekcija.

Štoviše, ako je x < y, za svaki element z ∈ p_{A}(x) vrijedi z < x < y, odnosno po tranzitivnosti z < y, dakle z ∈ p_{A}(y).

Drugim riječima, p_{A}(x) ⊆ p_{A}(y), a u gornjem odlomku smo vidjeli da nisu jednaki (zbog x ≠ y), dakle p_{A}(x) ⊂ p_{A}(y), što smo i trebali dokazati.

7. Uredajni tipovi i karakterizacije

Vidjeli smo da se dva skupa mogu pokazati sličnim našavši konkretnu sličnost izmedu njih (i dokazavši da je to sličnost), te da se mogu pokazati ne-sličnim našavši invarijantu sličnosti koju jedan ima, a drugi nema. No što ako ne možemo naći ni jedno ni drugo? Na primjer, promotrimo skupove ℚ i 𝔸 (racionalnih i algebarskih brojeva). Prebrojivi su oba. Ograničeni — nijedan. Diskretni — nijedan. Lokalno konačni — nijedan. Gusti — oba. Na svim invarijantama sličnosti koje nam padaju na pamet, podudaraju se. Pa ipak, ne čini se da možemo naći neku konkretnu sličnost izmedu ta dva TUSa. Kako riješiti taj problem?

Pokazuje se da obično ne moramo proučavati bezbrojne invarijante sličnosti: za svaki od “lijepih” TUSova kojima ćemo se baviti (ℕ, ℤ, ℚ i ℝ), postoji nekoliko “reprezentativnih” invarijanata sličnosti, u kojima je dovoljno da se neki TUS podudara s danim “lijepim” TUSom, pa da mu bude sličan. Uskoro ćemo navesti te reprezentativne invarijante sličnosti, samo prvo donekle formalizirajmo pojam “svi medusobno slični TUSovi” koji nam je trebao još za invarijante sličnosti.

Za dva TUSa (A, <_{A}) i (B, <_{B}) kažemo da imaju isti uredajni (ordinalni) tip, i pišemo τ(A, <_{A}) = τ(B, <_{B}), ako su slični. Primijetimo da je to dobro definirano, jer je svaki TUS sličan samom sebi (identiteta je sličnost), sličnost TUSova se može invertirati (i inverz sličnosti je sličnost, kao što smo dokazali), te vrijedi tranzitivnost, jer je kompozicija sličnostî ponovo sličnost. Takoder primijetimo kako je to analogno definiciji kardinalnih brojeva: ne kažemo što su kardinalni brojevi, već definiramo kad dva skupa imaju isti kardinalni broj (ekvipotentni su).

Sjetimo se, kod kardinalnih brojeva imali smo nekoliko medusobno neekvipotentnih skupova, čije kardinalne brojeve smo označili posebnim simbolima: 0 za ∅, 1 za {0}, 2 za {0, 1}, i tako dalje; zatim ℵ_{0} za ℕ, te 𝔠 za ℝ. Ovdje takoder imamo nekoliko medusobno ne-sličnih TUSova, čije ordinalne tipove označujemo posebnim simbolima:

• ω := τ(ℕ, <) • π := τ(ℤ, <)
• η := τ(ℚ, <) • λ := τ(ℝ, <)

Sada, na primjer, kad želimo reći da je neki TUS sličan ℚ (sa standardnim uredajem), možemo reći da je njegov uredajni tip jednak η.

Teoremi o uredajnoj karakterizaciji (nabrajanje reprezentativnih invarijanata za svaki od gornjih tipova) glase:

• Ako je TUS (A, <_{A}) konačan (dakle, card A = n ∈ ℕ), tada je τ(A, <_{A}) = n.

• Ako je TUS (A, <_{A}) beskonačan, i svaki početni komad mu je konačan, tada je τ(A, <_{A}) = ω.

• Ako je TUS (A, <_{A}) prebrojiv, obostrano neograničen (nema ni najmanjeg ni najvećeg elementa), i lokalno konačan, tada je τ(A, <_{A}) = π.

• Ako je TUS (A, <_{A}) prebrojiv, obostrano neograničen i gust, tada je τ(A, <_{A}) = η.

• Ako je TUS (A, <_{A}) beskonačan (dovoljno je da je neprazan), obostrano neograničen, ℝ-potpun i separabilan (sadrži prebrojiv gust podskup), tada je τ(A, <_{A}) = λ.

Sada je lako vidjeti: ℚ ≃ 𝔸 \underline{Rj.:} Tip od ℚ je η po definiciji. Treba još vidjeti da je τ(𝔸, <) = η. Znamo otprije da je 𝔸 prebrojiv. Za proizvoljan a ∈ 𝔸, a−1 je takoder algebarski, i manji od a, dok je a + 1 takoder algebarski, i veći od a — dakle, 𝔸 nema ni najmanji ni najveći element. Takoder, za a i b algebarske takve da je a < b, sigurno postoji racionalan broj q izmedu njih (štoviše, izmedu svaka dva realna broja postoji racionalan). No q je algebarski (m/n je rješenje jednadžbe nx − m = 0), pa je 𝔸 gust. Teorem o uredajnoj karakterizaciji tipa η sada daje sličnost.

DZ: dokažite primjenom teoremâ o uredajnoj karakterizaciji: ℙ ≃ ℕ 3ℤ ≃ ℤ ℚ \ ℕ ≃ ℚ

8. Računanje s uredajnim tipovima

Prisjetimo se, za kardinalne brojeve smo mogli definirati jednakost, usporedivanje, zbrajanje, množenje i potenciranje. Za ordinalne tipove ne možemo to sve definirati (bar ne tako da ima lijepa svojstva), no nešto možemo. Primjerice, jednakost ordinalnih tipova smo definirali već u prethodnoj točki. Sada ćemo definirati množenje i zbrajanje.

Podsjetimo se definicijâ množenja i zbrajanja kardinalnih brojeva: za κ = card A ∧ μ = card B, bilo je definirano κ · μ := card(A × B), te κ+μ := card(A×{0}∪B×{1}). Specijalno, ako su A i B bili disjunktni, zbroj smo mogli definirati i jednostavnije, kao card(A ∪ B).

Da bismo to pretvorili u definicije za ordinalne tipove, moramo još specificirati uredaj na gornjim skupovima A × B i A × {0} ∪ B × {1}.

No to su oba skupovi uredenih parova, a na uredenim parovima znamo da postoji prirodan uredaj: antileksikografski. Dakle:

Neka su σ i ν dva ordinalna tipa, σ := τ(A, <) i ν := τ(B, <). Tada definiramo σ · ν := τ(A × B, <), te σ + ν := τ(A × {0} ∪ B × {1}, <), s antileksikografskim uredajima.

Pogledajmo zbroj preciznije. Promatrajući A × {0} i B × {1}, možemo reći da smo obojali sve elemente od A u crveno, te sve elemente od B u plavo. Usporedujući ih antileksikografski, prvo usporedujemo njihovu boju: budući da je 0 < 1, vidimo da su svi crveni prije svih plavih. Ako su pak iste boje, usporedujemo ih kako već znamo: dva crvena uredajem u A, a dva plava uredajem u B. U specijalnom slučaju, kada su A i B disjunktni, njihove elemente uopće ne moramo bojati (“obojani” su već time kojem skupu pripadaju): u zbroju, prvo dolaze svi elementi iz A (uredeni kao što su bili u A), a nakon toga svi elementi iz B (uredeni kao što su bili u B). Na neki način, novi uredaj je <_{A} ∪ <_{B} ∪ A × B.

Postoji još jedna unarna operacija na ordinalnim tipovima: ako je σ := τ(A, <), definiramo reverzni tip (ponekad se zove i “inverzni”, ali treba imati na umu da to nije inverzni element s obzirom na gornje operacije) od σ kao σ^{∗} := τ(A, >), dakle uredajni tip obrnuto uredenog skupa. Na primjer, ω^{∗} = τ(ℕ, >), i vidjeli smo da je različit od ω, no svi ostali spomenuti tipovi (π, η, λ, kao i svi konačni) su jednaki svojim reverznim tipovima (DZ).

Vrijede brojni zakoni koji vežu te operacije (podrazumijevamo da su ρ = τ(A, <), σ = τ(B, <), te (ν = τ(C, <) proizvoljni uredajni tipovi):

(1) Zbrajanje je asocijativno: (ρ + σ) + ν = ρ + (σ + ν). Zaista,

s x ↦ \{ \begin{matrix}(a, 0) , & x = ((a, 0), 0) \\ ((b, 0), 1) , & x = ((b, 1), 0) \\ ((c, 1), 1) , & x = (c, 1) \end{matrix} je dana sličnost izmedu

(A × {0} ∪ B × {1}) × {0} ∪ C × {1} i

A × {0} ∪ (B × {0} ∪ C × {1}) × {1} (provjerite!).

(2) Množenje je asocijativno: (ρ · σ) · ν = ρ · (σ · ν). Zaista, ((a, b), c) ↦ (a, (b, c)) je sličnost izmedu TUSova (A × B) × C i A × (B × C).

(3) 0 = ∅ je neutralni element za zbrajanje. Primijetimo, A×{0}∪ ∅ × {1} je zapravo A × {0}, a ∅ × {0} ∪ A × {1} je A × {1}, te je prva projekcija sličnost bilo kojeg od tih skupova s A.

(4) 1 = {0} je neutralni element za množenje: a ↦ (a, 0) odnosno a ↦ (0, a) je sličnost izmedu A i A × 1 odnosno 1 × A.

(5) Vrijedi jedna distributivnost množenja (slijeva) prema zbrajanju: ρ · σ + ρ · ν = ρ · (σ + ν). Zanimljivo je da se sličnost (izmedu kojih skupova?) dobiva istim “pravilom” kao i za dokazivanje asocijativnosti množenja: ((a, d), j) ↦ (a, (d, j)).

(6) DZ: kako se reverz ponaša s obzirom na zbrajanje i množenje? Dokažite. (Rješenje: (ρ + σ)^{∗} = σ^{∗} + ρ^{∗}, te (ρ · σ)^{∗} = ρ^{∗} · σ^{∗}.)

Takoder, mnoga svojstva danih operacijâ ne vrijede:

(1) Ne vrijede zakoni kraćenja: na primjer, 1 + ω = ω (dakle 1 + ω = 0 + ω, a 1 ≠ 0). Zaista, s (a, b) ↦ a + b je dana sličnost izmedu 1 × {0} ∪ ℕ × {1} i ℕ. Takoder, ω^{∗} + 1 = ω^{∗}. Ne vrijede ni za množenje: na primjer, 2 · ω = ω (sličnost je (a, b) ↦ a + 2b). Da ne vrijedi ni drugi zakon kraćenja za množenje, vidi se iz η · η = η, što se može dokazati primjenom teorema o uredajnoj karakterizaciji: leksikografski ureden ℚ^{2} je prebrojiv, obostrano neograničen i gust (dokažite!), dakle tipa η.

(2) Ne vrijedi komutativnost zbrajanja. Naime, vidjeli smo gore 1 + ω = ω, no ω + 1 ≠ ω (primjena invarijanata sličnosti: ℕ × {0} ∪ 1 × {1} ima najveći element (0, 1), dok ga ℕ nema. Ne vrijedi ni komutativnost množenja. Gore smo vidjeli 2·ω = ω, preostaje vidjeti ω · 2 ≠ ω — a to je zato što je početni komad p_{ω·2}(0, 1) = ℕ×{0} beskonačan, dok su u ℕ svi početni komadi konačni.

(3) Ne vrijedi druga distributivnost množenja (zdesna) prema zbrajanju: specijalno, ω · 2 + 1 · 2 ≠ (ω + 1) · 2. Dokažite to!

Uputa: skup predstavnik lijeve strane ima predzadnji element, dok ga skup predstavnik desne strane nema.

Sada vidimo da mnoge dosadašnje zadatke možemo zapisati kao nejednakosti s ordinalnim tipovima: na primjer, dosad smo vidjeli da vrijedi:

• ω ≠ ω · ω,

• λ, λ · 2 i 2 · λ su svi medusobno različiti,

• π ≠ π · 2,

• ω·π ≠ π·ω (još jedan kontraprimjer komutativnosti množenja).

Primjenom teorema o uredajnoj karakterizaciji, ili nalaženjem konkretnih sličnosti (učinite to!), može se vidjeti da vrijedi:

• ω^{∗} + ω = π = 2 · π,

• η + η = η · η = η,

• λ + 1 + λ = (1 + λ) · π = λ.

POGLAVLJE 6 Ordinali

1. Motivacija i pregled

Vidjeli smo da ordinalni tipovi imaju svoju aritmetiku, koja u nekom pogledu profinjuje aritmetiku kardinalnih brojeva: na primjer, unutar kardinalnog broja ℵ_{0} našli smo bogatstvo raznih ordinalnih tipova — ω, π, η, i njihovih izvedenicâ, od kojih su mnogi medusobno bitno različiti.

Ipak, neke stvari koje smo imali definirane za kardinalne brojeve, poput usporedivanja po veličini i potenciranja, nedostaju. Možda bismo i mogli reći da je u nekom smislu π “manji” od η, no kako usporediti na primjer ω i ω^{∗}? Nekako se čini da postoje “nepopravljivo neusporedivi” ordinalni tipovi.

Da bismo to riješili, trebamo se usredotočiti na skupove koji su još bolje uredeni od općenitih TUSova. Mnogi ordinalni tipovi će pri tome otpasti, no na onom što ostane (ordinalni tipovi koji preostanu zvat će se ordinalni brojevi ili redni brojevi) imat ćemo jako dobru strukturu, koja će u izvjesnom smislu biti “najbolja moguća” za ono što želimo postići: aritmetiku beskonačnosti.

Vidjet ćemo da će taj pristup imati još jednu pozitivnu stranu: umjesto “poludefinicijâ” tipa “kažemo da skupovi imaju jednak kardinalni broj ako i samo ako su ekvipotentni, ali nigdje ne definiramo što kardinalni broj jest”, za ordinalne brojeve imat ćemo konkretne skupove (zovu se ordinali) koji će ih predstavljati. Tako ćemo moći preciznije formalizirati i mnoge pojmove koji u sebi nose ideju “nadogradivanja u beskonačnost”, jedan od kojih je svakako i sama kumulativna hijerarhija (više o tome na predavanjima).

Štoviše, tako izgradena teorija ordinalâ bit će dovoljno snažna da se u njoj može strogo definirati čak i pojam kardinalnog broja (no da bismo vidjeli da se on podudara s onim što smo intuitivno napravili u poglavlju na početku ovog dijela, trebat će nam aksiom izbora). Uvid u to može se vidjeti na primjeru konačnih skupova: iako općenite kardinalne brojeve još ne znamo definirati unutar teorije skupova, konačni kardinalni brojevi su upravo prirodni brojevi (uključujući nulu), za koje smo vidjeli da postoje prirodne definicije: n := {0, 1, …, n − 1}. Iako se na prvi pogled takva definicija čini cirkularnom, pokazuje se da nije, i upravo svojstvo koje omogućuje da se takve definicije mogu “legalno” provoditi, bit će ono što razlikuje dobro uredene skupove, kojima ćemo se ubuduće baviti, od uobičajenih TUSova.

Naravno, u slučaju prirodnih brojeva, radi se o principu rekurzivne definicije, koji se zasniva na istoj ideji kao i princip matematičke indukcije. Pokazat će se da, kad prirodne brojeve proširimo na općenite ordinale, ista ideja i dalje funkcionira, i omogućuje princip transfinitne indukcije i definicije transfinitnom rekurzijom — što će nama biti prilično bitno, jer omogućuje rješavanje široke klase zadataka, na sličan način kao i matematička indukcija na prirodnim brojevima.

2. Dobro uredeni skupovi

Za PUS (A, <) kažemo da je dobro ureden (skraćeno DUS), ako svaki njegov neprazan podskup ima najmanji element. Lako je vidjeti da je svaki DUS totalno ureden: kad bi x i y bili njegovi neusporedivi elementi, tada njegov dvočlani podskup {x, y} ne bi mogao imati najmanji

element. Zbog tog svojstva, kao i činjenice da se u TUSovima podudaraju pojmovi najmanjeg i minimalnog elementa, često se navodi ekvivalentna definicija: DUS je TUS u kojem svaki neprazan podskup ima minimum. Treba samo napomenuti da to nije ekvivalentno zahtjevu da svaki podskup ima minimalan element, ako a priori ne znamo da se radi o TUSu. Takvi skupovi (koji nisu nužno totalno uredeni, ali su parcijalno uredeni i svaki neprazan podskup im ima minimalan element) zovu se dobro utemeljeni skupovi — no skraćenica DUS se ovdje odnosi na dobro uredene skupove.

Budući da su DUSovi samo specijalni TUSovi, na njima je moguće promatrati sličnosti, invarijante i ordinalne tipove. Važna činjenica je da je “biti DUS” invarijanta sličnosti, tako da za svaka dva skupa koji imaju isti ordinalni tip, ili su oba DUSovi, ili nijedan od njih nije DUS. Drugim riječima, sâmi ordinalni tipovi se dijele u dvije skupine: ordinalni tipovi DUSova, i ordinalni tipovi skupova koji nisu DUSovi. Ubuduće ćemo se fokusirati na ove prve, i zvat ćemo ih ordinalni brojevi.

Svi konačni ordinalni tipovi (0, 1, 2,…) su ujedno i ordinalni brojevi, što se lako vidi matematičkom indukcijom: 0 je ordinalni broj jer TUS tipa 0 uopće nema nepraznih podskupova, a ako je k ordinalni broj, neprazni podskup B TUSa A tipa k + 1, za koji smo dokazali da ima najveći element max A =: a, je ili {a}, ili ima neprazan presjek s A\{a}. U svakom slučaju ima najmanji element: u prvom slučaju je to a, njegov jedini element, a u drugom je to upravo min(B \ {a}) (koji postoji po pretpostavci indukcije, jer je B \ {a} neprazan podskup skupa A \ {a} tipa k — te je manji i od a, jer je a najveći element).

2. DOBRO UREdENI SKUPOVI 52

Postoje li beskonačni DUSovi? Naravno, postoje — najpoznatiji primjer je skup prirodnih brojeva ℕ.