Z množicami smo izrazili številne matematične objekte, na primer:
preslikavo f : A → B lahko izrazimo kot funkcijsko relacijo med A in B, torej kot
podmnožico A × B,
kvocientna množica A/R je množica ekvivalenčnih razredov, ekvivalenčni razredi so spet
množice,
Ali je možno vse matematične objekte predstaviti z množicami? Da!
Par (x, y) lahko predstavimo z množico {{x}, {x,y}}. Tako dobimo
A × B := { {{x}, {x,y}} | x ∈ A, y ∈ B }
Elemente vsote A + B kodiramo takole:
ι₁(x) = (x, 0) = {{x}, {x,∅}}
ι₂(x) = (x, 1) = {{x}, {x,{∅}}}
Na množicah definiramo operacijo naslednik:
x⁺ := x ∪ {x}
Naravna števila nato kodiramo tako, da za ničlo vzamemo ∅ in uporabljamo
operacijo naslednik:
0 = ∅
1 = ∅⁺ = {0} = {∅}
2 = 1⁺ = {0, 1} = {∅, {∅}}
3 = 2⁺ = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}
4 = 3⁺ = {0, 1, 2, 3} = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}
...
Vidimo, da je vsako naravno število kar množica svojih predhodnikov.
Cela števila so kvocient N × N:
Z = (N × N)/∼
kjer je
(a,b) ∼ (c,d) ⇔ a + d = c + b.
Urejeni par (a, b) predstavlja razliko števil a in b.
Racionalna števila so kvocient:
Q = (Z × {n ∈ N | n > 0})/≈
kjer je
(a,m) ≈ (b,n) ⇔ a n = b m.
Realno število je Dedekindov rez, torej podmnožica Q.
In tako naprej. Ne pravimo, da je kodiranje vseh matematičnih objektov z množicami vedno dobra ideja, vendar pa je dejstvo, da je to možno, pomembno spoznanje osnov matematike. Iz njega na primer sledi tole: če je teorija množic neprotislovna, potem je neprotislovna tudi vsa matematika, ki jo lahko kodiramo z množicami (torej več ali manj vsa običajna matematika).
Zermelo-Fraenkelovi aksiomi teorije množic:
Ekstenzionalnost: množici A in B, ki imata iste elemente, sta enaki.
Neurejeni par: za vsak x in y je {x, y} množica, ki vsebuje natanko x in y:
∀ x y z . z ∈ {x, y} ⇔ z = x ∨ z = y
Okrajšava: {x} = {x, x}.
Unija: za vsako množico A je ⋃ A množica, ki vsebuje natanko vse
elemente množic iz A
∀ A x . x ∈ ⋃ A ⇔ ∃ B ∈ A . x ∈ B
Prazna množica: množica ∅ nima elementa:
∀ x . x ∉ ∅
Neskončna množica: obstaja množica, ki vsebuje ∅ in je zaprta za operacijo naslednik
(x⁺ = x ∪ {x}).
∃ A . ∅ ∈ A ∧ ∀ x ∈ A . x⁺ ∈ A
Podmnožica: za vsako množico A in formulo φ je {x ∈ A | φ(x)}
množica, ki vsebuje natanko vse element iz A, ki zadoščajo φ:
∀ y . y ∈ {x ∈ A | φ(x)} ⇔ φ(y)
Potenčna množica: za vsako množico A je P(A) množica, ki vsebuje
natanko vse njene podmnožice:
∀ S . S ∈ P(A) ⇔ S ⊆ A
Zamenjava: če je A množica in f : A → Set preslikava, je razred
{ y ∈ V | ∃ x ∈ A . y = f(x) }
množica.
Dobra osnovanost: relacija ∈ je dobro osnovana.
Aksiom izbire: vsaka družina nepraznih množic ima funkcijo izbire
Definicija: Veriga v delni urejenosti (P, ≤) je taka podmnožica V ⊆
P, ki je z ≤ linearno urejena, kar pomeni ∀ x y ∈ V . x ≤ y ∨ y ≤ x.
Primeri:
Če je (P, ≤) linearno urejena, je vsaka podmnožica veriga
V (P(Q), ⊆) imamo neštevno verigo
V = {S ∈ P(Q) | S je doljna množica}
Množica S ⊆ Q je doljna, če velja ∀ x y ∈ Q . x ≤ y ∧ y ∈ Q ⇒ x ∈ Q.
Zornova lemma: Če ima v delni urejenosti (P, ≤) vsaka veriga zgornjo mejo,
potem ima P maksimalni element.
Dokaz: dokaz se naslanja na aksiom izbire in Bourbaki-Wittov izrek o negibnih točkah (glej
spodaj). Naj bo C množica vseh verig v P. Uredimo jo z ⊆. Na njej definiramo preslikavo
f : C → C, ki razširi verigo, če ni maksimalna, sicer je ne spremeni (tu uporabimo
izbiro):
V ∈ C maksimalna veriga v P (glede na ⊆), definiramo f(V) := V.V ∈ C ni maksimalna veriga v P, potem obstaja tak x ∈ P \ V, da je V
∪ {x} spet veriga. V tem primeru izberemo tak x in definiramo f(V) := V
∪ {x}.Po izreku Bourbaki-Witt ima f negibno vrednost V ∈ C. Ta V je maksimalna
veriga V, saj bi sicer veljalo, da je V = f(V) = V ∪ {x} za neki x ∉ V,
kar ni možno. Naj bo m zgornja meja za verigo V. Trdimo, da je m
maksimalni element v P: denimo, da velja m ≤ y za m ∈ P. Ker je V ∪ {y}
veriga, ki vsebuje maksimalno verigo V, sledi V = V ∪ {y}, od tod pa y ∈ V
ter y ≤ m. Torej je m = y in m je res maksimalni element. □
Definicija: Naj bo (P, ≤) delna ureditev. Preslikava f : P → P je progresivna, ko
velja x ≤ f(x) za vsak x ∈ P.
Opomba: progresivna preslikav ni nujno monotona (poiščite protiprimer!).
Izrek (Bourbaki-Witt): Naj bo (P, ≤) neprazna delna ureditev, v kateri ima
vsaka veriga zgornjo mejo in f : P → P progresivna preslikava. Tedaj ima f
negibno točko: to je tak x ∈ P, da velja f(x) = x.
Dokaz: opuščen.
Izrek: V teoriji množic brez aksioma izbire so naslednje izjave ekvivalentne:
Dokaz:
(1 ⇒ 2) Glej Zornovo lemo.
(2 ⇒ 3) Skica dokaza: naj bo A poljubna množica, ki jo želimo dobro urediti.
Definirajmo delne dobre ureditev množice A: to so pari (B,R), kjer je B ⊆ A
in R ⊆ B × B dobra ureditev na B. Za delni dobri ureditvi (B,R) in
(C,Q) pravimo, da je (C,Q) razširitev (B,R), kadar velja B ⊆ C, R ⊆ Q in
še, da je B začetni segment v C, kar pomeni:
∀ x y ∈ C: x Q y ∧ y ∈ B ⇒ x ∈ B.
Kadar je (C,Q) razširitev (B,R), pišemo (B,R) ≼ (C,Q). Naj bo P množica vseh delnih
dobrih ureditev množice A,
P = { (B, R) | B ⊆ A in R ⊆ B × B in R je dobra ureditev B },
urejena z relacijo ≼. Očitno je ≼ delna ureditev. Trdimo, da imajo verige v
P zgornje meje glede na ≼: če je V ⊆ P veriga dobro urejenih podmnožic
A, je njena zgornja meja (D,S) kar unija po komponentah:
D := ⋃ {B | (B, R) ∈ V}
S := ⋃ {R | (B, R) ∈ V}
Preverimo, da velja (D,S) ∈ P. Očitno je (D,S) stroga linearna ureditev
(vaja). Denimo, da bi v (D,S) imeli neskončno padajočo verigo
... S x₃ S x₂ S x₁ S x₀.
Obstaja (B,R) ∈ V, da je x₀ ∈ B. Potem bi bila x₀, x₁, x₂, x₃, ...
padajoča veriga v (B,R), kar ni možno, saj je (B,R) dobro urejena. Res, ker
je xᵢ ∈ V, obstaja (C,Q), da je xᵢ ∈ C. Če velja (B,R) ≼ (C,Q), potem
xᵢ ∈ B po definicijo ≼. Če velja (C,Q) ≼ (B,R), potem xᵢ ∈ B, ker velja
C ⊆ B. Torej je (D,S) res delna ureditev P.
Preverimo še, da velja (B,R) ≼ (D,S) za vsak (B,R) ∈ V. Denimo, da je y ∈ D,
x ∈ B in y S x. Obstaja (C,Q) ∈ V, da je y ∈ C. Če velja (C,Q) ≼ (B,R),
potem y ∈ C ⊆ B. Če pa velja (B,R) ≼ (C,Q), potem je y ∈ B po definiciji ≼.
Po Zornovi lemi obstaja maksimalni element (B,R) v P. Trdimo, da je B = A. Če bi namreč
obatajal x ∈ B \ A, bi lahko razširili (B,R) na večjo dobro ureditev tako, da bi dodali x
na konec B:
(B ∪ {x}, R')
y R' z ⇔ z = x ∧ (y,z) ∈ R
To ni možno, ker je (B,R) maksimalna delna ureditev. Torej je res A = B in
našli so dobro ureditev A.
(3 ⇒ 1) Naj bo A : I → Set družina nepraznih množic. Naj bo ≺ dobra ureditev
na uniji ⋃ A. Ker so vse množice Aᵢ neprazne, ima vsaka od njih prvi element
glede na ≺. Torej lahko definiramo funkcijo izbire f s predpisom
f(i) = prvi element Aᵢ. □
Izrek: Vsak vektorski prostor ima vektorsko bazo.
Dokaz: Naj bo L vektorski prostor. Definiramo množico
P = { B ⊆ L | B je linearno neodvisna }.
Množico P delno uredimo z relacijo ⊆. Trdimo, da imajo verige v P zgornje
meje: zgornja meja verige V ⊆ P, je kar njena unija ⋃_(B ∈ V) B. Seveda je
treba preveriti, da je unija verige linearno neodvisnih množic spet linearno
neodvisna (vaja). Po Zornovi lemi obstaja maksimalni element v P, torej
maksimalna linearno neodvisna množica B v L. To pa je seveda vektorksa baza
za L. □