Prve aksiome teorije skupova

Osnovna literatura: Prva dva poglavlja knjige

[MP] Žarko Mijajlović, Zoran Petrović. Matematička logika. Elementi teorije skupova. Zavod za
udžbenike, Beograd 2012.

1 Matematički univerzum
Potpuno neformalno govoreći, možemo reći da matematika postoji isključivo u svom zamišljenom matema-
tičkom univerzumu koji nema ničega zajedničkog sa realnim svetom. Univerzum čine objekti koje nazi-
vamo skupovima, dok sam univerzum nije skup. Dakle, jedini matematički objekti su skupovi. U gov-
ornom jeziku univerzum označavamo sa V , dok njegove objekte označavamo sa A, B, a, b, A0 , B 0 , a0 , b0 , ....
Osim jednakosti objekata (nešto je jednako samo samom sebi, koju iznačavamo sa =, u univerzumu pos-
toji još samo jedna osnovna relacija izmedju para objekata: to je relacija pripadnosti ∈, a a ∈ b čitamo
‘objekat a pripada objektu b’ ili ‘objekat a je element objekta b‘. Sa a ∈ / b označavamo da objekat a ne
pripada objektu b. Naglasimo da a priori ne pretpostavljamo ništa o prirodi objekata univerzuma, kao
ni o relaciji pripadnosti; pretpostavljamo samo da važe osnovni logički zakoni vezani za osobine relacije
jednakosti: takvi su: a = a, iz a = b sledi b = a, iz a = b i c ∈ a sledi c ∈ b, iz b = c i c ∈
/ a sledi b ∈/ a,
...
Matematičke osobine univerzuma i njegovih objekata su one čije značenje možemo precizno definisati
i koje se odnose na osobine relacije ∈, a to su one koje možemo izraziti formulama prvog reda. Na primer:
‘objekat A nema elemenata’ jeste matematičko svojstvo objekta jer se izražava formulom ¬∃y(y ∈ x).

Formalizam

Formalno govoreći, osobine univerzuma i njegovih objekata iskazujemo formulama, t.j odredjenim
nizovima simbola. Simboli koje koristimo čine jezik teorije skupova. Njega čine simbol relacije
jednakosti ≈, simbol relacije pripadnosti ∈ kao i ostali simboli potrebni za gradjenje formula:

• Simboli logičkih veznika: ¬ ∧ ∨ ⇒ ⇔

• Kvantifikatori (ili kvantori) ∃ ∀

• Leva i desna zagrada i zapeta: ( ) ,

• Promenljive: x, x0 , x0 , x1 , ..., y, y 0 , . . ..

Primetimo da razlikujemo simbol = kojim označavamo jednakost kada govornim jezikom opisujemo
svojstva univerzuma, od simbola formalnog jezika ≈ koji koristimo u formulama; slično je za ∈ i ∈.
Reč jezika je bilo koji konačan niz simbola, a samo odredjene reči, koje nazivamo formulama, koris-
timo za iskazivanje matematičkih tvrdjenja. Formule (prvog reda) definišemo tako što prvo definišemo

1
najjednostavnije formule, a to su atomske formule. Atomske formule su reči oblika u ≈ v i u ∈ v, gde
su u i v neke promenljive (moguće i jedna te ista). Zatim ćemo opisati pravila na osnovu kojih se od
jednostavnijih formula mogu praviti složenije.
• Ako su ϕ i ψ formule i u promenljiva, tada je formula i svaka od reči

¬ϕ (ϕ ∧ ψ) (ϕ ∨ ψ) (ϕ ⇒ ψ) (ϕ ⇔ ψ) ∀u ϕ i ∃u ϕ .

Formula prvog reda je samo ona reč koja se može dobiti od atomskih formula u konačno mnogo
koraka primenom gornjih postupaka.
Proces gradjenja formule predstavljamo drvetom potformula. Na primer, drvo potformula formule
∃ y(y ∈ x ∧ ¬y ≈ x) je:
y≈x

y ∈ x ¬y ≈ x

(y ∈ x ∧ ¬y ≈ x)

∃ y(y ∈ x ∧ ¬y ≈ x)

Složenost formule prvog reda φ, u oznaci sl(φ), je prirodan broj koji predstavlja ukupan broj simbola
logičkih veznika i kvantifikatora (računajući i višestrukost) koji učestvuju u njenom gradjenju. Formalna
definicija je rekurzivna:

• Ako je φ atomska formula, tada je sl(φ) = 0.

• Ako je φ oblika ∃x ψ, ∀x ψ ili ¬ψ, tada je sl(φ) =def sl(ψ) + 1.

• Ako je φ oblika (ψ ∧ θ), (ψ ⇒ θ), (ψ ⇔ θ) ili (ψ ∨ θ), tada je sl(φ) =def sl(ψ) + sl(θ) + 1.

Formalno, skup svih slobodnih promenljivih formule φ, u oznaci F v(φ), definišemo rekurzivno po
složenosti formule φ.
• Ako je φ atomska formula, tada čine (obe) promenljive koje učestvuju u njoj (F v(x ∈ y) = {x, y}.

• Ako je φ oblika ¬ψ, tada je F v(φ) =def F v(ψ).

• Ako je φ oblika ψ ∧ θ ili ψ ∨ θ, tada je F v(φ) =def F v(ψ) ∪ F v(θ).

• Ako je φ oblika ∃x ψ ili ∀x ψ, tada je F v(φ) =def F v(ψ) r {x}.

Promenljiva x može u formuli biti slobodna iako se u njoj pojavljuje kvantifikovanje ∃x; na primer, u
formuli x ≡ y ∧ ∃x ¬(x ≡ y). Dakle, jedna te ista promenljiva u formuli može imati i slobodno i vezano
pojavljivanje. Po pravilu, u matematici izbegavamo upotrebu formula koje sadrže dvojako pojavljivanje
iste promenljive, zato što ono zamagljuje pravo značenje formule. Tako, umesto prethodne formule
koristi se formula x ≡ y ∧ ∃z ¬(z ≡ y) koja ima isto značenje.
Slobodna i vezana pojavljivanja možemo slikovito opisati u drvetu potformula. Prethodno primetimo
da se svako pojavljivanje promenljive u formuli javlja u nekoj atomskoj potformuli te formule. Prema
tome, slobodna i vezana pojavljivanja možemo objasniti na skupu svih atomskih formula koje učestvuju

2
u gradjenju formule, odnosno dovoljno je označiti ih na listovima drveta potformula. Procedura je
sledeća: za svako pojavljivanje nekog kvantifikatora, na primer ∃x, u formuli precrtamo u svim atomskim
formulama koje su u listovima drveta iznad čvora drveta na kome se ∃x pojavljuje sva pojavljivanja
promenljive x. Učinimo to za svaki kvantifikator koji se pojavljuje u formuli. Pojavljivanja neprecrtanih
promenljivih u listovima drveta su slobodna, a precrtana su vezana. Uzmimo primer formule x ∈
y ∧ ∃ y(x ∈ y ∧ y ∈ y). Dejstvom kvantifikatora ∃y, zaokruženog na mestu pojavljivanja, precrtavamo sva
pojavljivanja promenljive y u atomskim formulama iznad njega. Potom u formuli precrtamo sva vezana
pojavljivanja promenljivih, a neprecrtana uokvirimo.

x ∈6 y 6 y ∈6 y

(x ∈ y ∧ y ∈ y)

x∈y ∃ y (x ∈ y ∧ y ∈ y)

x ∈ y ∧ ∃ y( x ∈6 y∧ 6 y ∈6 y)

Slobodne promenljive ove formule su x i y; y ima tri vezana i jedno slobodno pojavljivanje u njoj, dok
x ima sva tri pojavljivanja slobodna.

• Rečenice su formule bez slobodnih promenljivih.

• φ(x) označava da formula φ ima jedinu slobodnu promenljivu x; slično za φ(x, y),...

Značenje formule na srpskom jeziku odredjujemo tako što logičke veznike prevodimo na uobičajen
način, kvantifikator ∀ prevodimo sa ‘za sve skupove’, a kvantifikator ∃ sa ‘postoji skup’. Na primer:
• Rečenica ∃x x 6∈ x ima značenje: postoji (neki) skup a takav da važi a ∈ / a, što je u jeziku
ekvivalentno sa ‘postoji skup koji nije svoj element’. Naglasimo da ovde nismo na govornom
jeziku rekli ‘postoji skup x’ jer smo ranije rekli da ćemo skupove u jeziku označavati sa a, b, A, B...
dok simmole x, y koristimo u formalnom (logičkom) jeziku.

• Rečenica ∀x x 6∈ x ima značenje: za svaki skup a važi a ∈

/ a, odnosno ‘nijedan skup nije svoj
element’.
Rečenicama želimo da izrazimo osobine našeg univerzuma, njima izražavamo matematička tvrdjenja.
One treba da imaju logičko značenje univerzuma: mogu važiti u njemu ili ne. Usput, za sada ne znamo
da li ijedna od gornje dve rečenice važi ili ne, jer one ne izražavaju osnovne logičke zakone (kakav je na
primer ∀x∀yf orallz(x ≈ y ⇒ (x ∈ z ⇔ y ∈ z)). Ispostaviće se ipak da one važe u univerzumu, jer su
posledice aksioma koje ćemo uvesti.
U slučaju niza različitih kvantifikatora treba biti posebno obazriv i prevoditi postupno, jedan po
jedan.
Na primer formulu ∃x∀y(y ∈ / x) prevodimo postupno:
– Postoji (neki) skup a takav da važi ∀y(y ∈ / a)
– Postoji skup a takav da za svaki skup b (pa i za b = a) važi b ∈ / a.
Formule koje nisu rečenice imaju slobodne promenljive pa njima ne pridajemo logičko značenje.
Tako, formulu φ(x) (jedina slobodna promenljiva je x) tumačhimo kao ‘x ima svojstvo φ’. Na primer,
∀y y 6∈ x označava ‘x nema nijedan element’.

3
 Ako je a neki skup, tada možemo pridati značenje iskazu ‘skup a zadovoljava formulu φ(x)’ prevodeći
kvantifikatore na govorni jezik. Kažemo i da ‘važi φ(a)’ što zapisujemo tako što u formuli φ(x) svako
slobodno pojavljivanje promenljive x zamenimo sa a. Na primer: ‘skup a ima bar dva elementa’ je isto
što i ‘važi ∃y∃z(¬y ≈ z ∧ y ∈ a ∧ z ∈ a)’ ili ‘a zadovoljava formulu ∃y∃z(¬y ≈ z ∧ y ∈ x ∧ z ∈ x)’
Zadatak Opisati formulom φ(x) svojstva:
1. x ima bar tri elementa.
2. x ima bar jedan element koji nema ni jedan element.
3. x ima ima bar dva elementa i bar jedan od njih nema ni jedan element.

2 Osnovne aksiome
(A1) Aksioma ekstenzionalnosti. ∀x∀y(x ≈ y ⇔ ∀u(u ∈ x ⇔ u ∈ y))
Dva skupa su jednaka ako i samo ako imaju iste elemente.

Definicija 1. Skup a je podskup skupa b (oznaka a ⊆ b) akko je svaki element skupa a ujedno i
element skupa b. Skup a je pravi podskup skupa b, u oznaci a ⊂ b ili a ( b, ako je a ⊆ b i a 6= b
(postoji element skupa b koji ne pripada skupu a).

Formalno, x ⊆ y možemo posmatrati i kao formulu: to je skraćeni zapis formule ∀u(o ∈ x ⇔ u ∈ y.

(A2) Aksioma praznog skupa. ∃x∀y(y ∈ / x)
Postoji skup koji nema nijedan element.
Primenom aksiome ekstenzionalnosti dokazuje se sledeća činjenica.

Fakt 1. Postoji jedinstven skup koji nema nijedan element. Označavamo ga sa ∅ ili 0.

(A3) Aksioma para. ∀x∀y∃z∀u(u ∈ z ⇔ (u = x ∨ u = y)

Za svaka dva skupa postoji skup čiji su oni jedini elementi.
Primenom aksiome ekstenzionalnosti dokazuje se sledeća činjenica.

Fakt 2. Za svaka dva skupa a, b postoji jedinstven skup koji čiji su oni jedini elementi. Označavamo ga
sa {a, b}, a ukoliko je a = b koristimo i oznaku {a} umesto {a, a}.

Zadaci za vežbu:

1. Dokazati da za svaki skup a važi 0 ⊆ a.

2. Dokazati da ako je a ⊆ 0, tada je a = 0.

3. Dokazati da su skupovi 0, {0}, {{0}} i {0, {0}} medjusobno različiti.

Definicija 2. 1 =def {0} 2 =def {0, {0}} = {0, 1}

Iz dosadašnjih aksioma ne možemo zaključiti da postoji skup sa bar tri različita elementa. To će
omogućiti naredna aksioma.
(A4) Aksioma unije. ∀x∃y∀u(u ∈ y ⇔ ∃v(v ∈ x ∧ u ∈ v))
Za svaki skup a postoji skup b čiji su jedini elementi skupovi koji pripadaju nekom elementu skupa a.

Fakt 3. Za svaki skup a postoji jedinstven skup b koji zadovoljava uslov prethodne aksiome. Takav
skup se zove unija skupa a i označava se sa ∪a.

4
 • Skup ∪{A, B} označavamo i sa A ∪ B.

Zadaci:

1. Dokazati da za sve skupove a, b, c postoji jedinstven skup čiji su oni jedini elementi. Označavamo
ga sa {a, b, c}.
(Posmatrati skup ∪{{a, b}, {b, c}} ...)

2. Dokazati da za sve skupove a, b, c, d postoji jedinstven skup čiji su oni jedini elementi.

3. Dokazati da za sve skupove a, b, c, d, e, f postoji jedinstven skup čiji su oni jedini elementi.

4. Izračunati: ∪2 = ..... ∪{1, 2} = ..... ∪{2} = .....

5. Koja od tvrdjenja {0} ∈ 2, 1 ∈ {2}, {1} ∈ 2, 1 ⊆ 2 i 2 ⊆ {2} su tačna?

(A5) Aksioma partitivnog skupa. ∀x∃y∀u(u ∈ y ⇔ u ⊆ x)

Za svaki skup a postoji skup b čiji su jedini elementi (svi mogući) podskupovi skupa a.

Fakt 4. Za svaki skup a postoji jedinstven skup b koji zadovoljava uslov prethodne aksiome. Taj skup
je partitivni skup skupa a i označavamo ga sa P(a).

Primetimo da za svaki skup A važi ∅ ∈ P(A) i A ∈ P(A), pa je P(A) 6= ∅.

Zadaci za vežbu:

1. Izračunati: P(0) = ..... P({0}) = ....., P({{0}}) = ... P({0, 1}) = .....

2. Dokazati da iz A ⊆ B sledi P(A) ⊆ P(B).

3. Koja od tvrdjenja P(0) ∈ 1, P(1) ⊆ 2, 2 ∈ P(2), P(1) ∈ 2 i P(0) ⊆ ∪1 su tačna

4. Pronaći bar jedan skup x za koji važi i bar jedan za koji ne važi x ⊆ P(x).

5. Dokazati da ako skup A ima n elemenata, tada P(A) ima 2n elemenata.

6. Ako skup A ima n elemenata, koliko rešenja ima jednačina ∪x = A?

(A6) Shema aksioma izdvajanja.

Za svaki skup a i za svako svojstvo P (u) (skupa u) postoji skup b koji čine tačno oni elemenati
skupa a koji imaju svojstvo P .
Prethodna rečenica se ne može izraziti jednom formulom teorije skupova, jer se tvrdjenje odnosi na
svako svojstvo P (u). Svojstvo nekog skupa x formalno opisujemo formulom teorije skupova φ(x), pa za
svaku formulu φ(u) imamo po jednu aksiomu

∀x∃y∀u(u ∈ y ⇔ (u ∈ x ∧ φ(u))).

Zato se ovde radi o (beskonačnom) spisku aksioma, odnosno shemi aksioma.

Fakt 5. Za svaki skup a i svojstvo P (x) skup b iz prethodne aksiome je jedinstven; označavamo ga sa
{x ∈ a | P (x)} ili {x ∈ a : P (x)}

5
3 Skupovne operacije
Uniju skupa, kao i uniju dva skupa smo definisali. Kao posledicu aksiome izdvajanja možemo definisati
i sledeće operacije sa skupovima:

• Presek skupova A ∩ B =def {x ∈ A | x ∈ B}

• Razlika skupova A i B je A r B =def {x ∈ A | x ∈

/ B}

• Simetrična razlika A∆B =def (A r B) ∪ (B r A)

• Presek skupa ∩a =def {x ∈ ∪a | x pripada svakom elementu skupa a}

Za predstavljanje skupovnih operacija koristimo Venove dijagrame.

B

B r (A ∪ C)

(A ∩ B) r C (B ∩ C) r A

A∩B∩C

A r (B ∪ C) (A ∩ C) r B C r (A ∪ B)

A C

1. Napisati što kraće formule koje definišu osenčene skupove:

A A A

B C B C B C

2. Zaokružiti redni broj tvrdjenja koja važe za sve skupove A, B i C, a precrtati ona koja ne važe.

(a) (A∆B)∆C ⊆ (A ∪ B)∆C.

6
 (b) (B ∩ C)∆A ⊆ (A ∩ B) ∪ C.
(c) (A r B)∆C = (A∆C) ∪ (B ∩ C).
(d) (A∆B) r C = ((A r C) ∪ (B r C)) r (B ∩ C).
(e) Ako je A∪(B∆C) = (C ∩B)∪A, tada je B ⊆ A. (∀x∀y∀z(x∪(y∆z) = (z ∩y)∪x ⇒ y ⊆ x)).
(f) Ako je A ∩ B = B \ A, tada je B ⊆ A (∀x∀y(x ∩ y = y r x ⇒ y ⊆ x))
(g) Ako je A ⊆ B, onda je A∆C ⊆ B∆C.
(h) Ako je A ∪ (B∆C) = (A ∪ B) ∩ C, tada je A ⊆ C.

3. Zaokružiti redni broj tvrdjenja koja važe za sve skupove A i B, a precrtati ona koja ne važe.

(a) Ako je A ⊆ B, tada je P(A) ⊆ P(B).

(b) P(A) ∪ P(B) = P(A ∪ B).
(c) P(A) ∩ P(B) = P(A ∩ B).
(d) P(A)∆P(B) ⊆ P(A∆B).
(e) P(A) r P(B) = P(A r B).
(f) P(A) r P(B) ⊆ P(A∆B).
(g) P((A ∩ B) r C) ⊆ P(A ∪ C) ∪ P(B ∪ C).
(h) P((A ∪ B)) ∪ P(C)) ⊆ P(A ∪ C) ∪ P(B ∪ C).

4. Zaokruži tačna tvrdjenja a precrtaj netačna.

(a) Za sve skupove A, B i C važi (A∆B) ∪ C ⊆ (A ∪ B)∆C.

(b) Za sve skupove A i B postoji skup C takav da je (A∆B) ∪ C = (A ∪ B)∆C.
(c) Za sve skupove B i C postoji skup A takav da je (A∆B) ∪ C ⊆ (A ∪ B)∆C.
(d) Za svaki skup A postoje skupovi B i C takvi da je (A∆B) ∪ C = (A ∪ B)∆C.
(e) Za sve skupove A i B postoji skup C takav da je (A∆B) ∪ C ⊆ (A ∪ B)∆C.
(f) Za svaki skup A postoji skup B takav da za svaki skup C važi (A∆B) ∪ C = (A ∪ B)∆C.

5. Neka su dati skupovi A i B. Odrediti sve skupove X za koje važi (X ∪ A)∆(B r A) = (A r X)∆B.
Rešenje. X = ∅.

6. Neka su dati skupovi A i B. Odrediti sve skupove X za koje važi A ∩ X = (X ∪ A)∆(A r B).
Rešenje. X = A ∩ B.

7. Odrediti koja od narednih tvrdjenja su tačna (uporediti sa zadatkom 4).

(a) Za sve skupove A i B jednačina (A∆B) ∪ X = (A ∪ B)∆X ima resšenje.

(b) Za sve skupove B i C jednačina (X∆B) ∪ C ⊆ (X ∪ B)∆C ima rešenje.
(c) Za svaki skup A jednačina (A∆X) ∪ Y = (A ∪ X)∆Y ima rešenje.
(d) Za sve skupove A i B ‘nejednačina’ (A∆B) ∪ X ⊆ (A ∪ B)∆X ima rešenje.

8. Neka je A ∪ B ∪ X ⊆ C. Dokazati
(C r (A ∪ X))∆B = (C r (B ∪ X))∆A ako i samo ako X ⊆ A ∩ B.

• Naredni zadaci se odnose na konačne skupove i |X| označava broj elemenata skupa X.

7
 9. Dokazati da za svaka dva skupa važi: |A| + |B| = |A ∪ B| + |A ∩ B|.

10. Postoje li skupovi A, B takvi da je:

a) |A| − |A ∩ B| > |A ∪ B| − |B|?

b) |A| + |B| > |A ∪ B| + 2|A ∩ B|?
c) |A| + 2|B| 6 |A ∪ B| + |A ∩ B|?
d) |A| + 2|B| < |A ∪ B| + 2|A ∩ B|?

11. Zaokruži tačna tvrdjenja a precrtaj netačna.

(a) Za svaki konačan skup A postoji skup B takav da je |A| + 2|B| > 2|A ∪ B| + |A ∩ B|.
(b) Postoji konačan skup A takav da za svaki (konačan) skup B važi |A|+2|B| > 2|A∪B|+|A∩B|.
(c) Za svaki konačan skup A postoji skup B takav da je |A| + 2|B| < |A ∪ B| + 2|A ∩ B|.
(d) Postoji konačan skup A takav da za svaki (konačan) skup B važi |A|+2|B| < |A∪B|+2|A∩B|.
(e) Za svaki konačan skup A postoji skup B takav da je 2|A| − |B| > |A ∪ B| + 2|A ∩ B|.

12. Dokazati da za sve konačne skupove važi: |A|+|B|+|C|+|A∩B ∩C| = |A∩B|+|A∩B|+|B ∩C|.

13. Postoje li (konačni) skupovi A, B i C takvi da važi:

(a) |A| + |B| + |C| = 2|A ∪ B| + |A ∩ B| + |B ∩ C|

(b) |A| + |C| + |A ∩ B ∩ C| > |A ∪ B| + 2|B ∩ C|.
(c) |A| + |B| + |C| − |A ∩ B ∩ C| > |A ∪ B| + |A ∩ B| − |B ∩ C|.

14. Odrediti najmanji prirodan broj n za koji postoje skupovi A, B i C takvi da je |B ∪C| =n, |A| = 8,
|B r A| = 6, |A r C| = 4 i |B ∩ C| = 3. Odgovor: n = 10

15. Odrediti najmanji prirodan broj n za koji postoje skupovi A, B i C takvi da je |B ∪ C| =n |A| = 9,
|C r A| = 7, |A r B| = 5 i |B ∩ C| = 3. Odgovor: n = 11

16. Odrediti najmanji prirodan broj n za koji postoje skupovi A, B i C takvi da je |C| =n, |ArB| = 12,
|A r C| = 7, |C r A| = 6 i |C r B| = 10. Odgovor: n = 11.

17. Odrediti najmanji prirodan broj n za koji postoje skupovi A, B i C takvi da je |B| =n, |ArB| = 12,
|A r C| = 6, |B r C| = 4, |C r A| = 6 i |C r B| = 10. Odgovor: n = 6.

18. Neka su A, B, C konačni skupovi takvi da je |A4B| + |B4C| = |A4C|. Dokazati A ∩ C ⊆ B ⊆

A ∪ C.

8
Komplement
U matematici obično unapred fiksiramo neki dovoljno veliki skup koji sadrži sve objekte koji nas zani-
maju, takozvani univerzum ili univerzalni skup. Obično ga označavamo sa U . Univerzum nije fiksiran
skup i menja se. Na primer, ako nas zanimaju tvrdjenja o prirodnim brojevima, možemo uzeti da je U
skup prirodnih brojeva, kod realnih U = R ...
Fiksirajmo univerzum U i posmatrajmo njegove podskupove A, B, C ∈ P(U ). Skup U r A je
komplement skupa A i označavamo ga sa Ac .

Ac

Osnovni identiteti su:

Ac ∩ B c = (A ∪ B)c Ac ∪ B c = (A ∩ B)c A r B = A ∩ Bc A∆B = Ac ∆B c

1. Koja od sledećih tvrdjenja važe za sve skupove U i A, B, C ∈ P(U ):

(a) (A ∩ B c ) ∩ (Ac ∪ B) = ∅
(b) Ac ∩ B c ∩ C c = (A ∪ B ∪ C)c
(c) (A ∩ B c ) r C ⊆ (A∆C) r B
(d) (Ac ∩ B) ∪ C c ⊆ (Ac ∪ B ∪ C)c

2. Dati su skupovi A i B. Odrediti sve skupove X za koje važi A ∩ X = B ∩ X = A ∩ B i

A ∪ B ∪ X = A ∪ B.

3. Za skupove A, B i C važi B ⊆ A i A ∩ C = ∅. Odrediti sve skupove X za koje važi A r X = B i

X r A = C.

4. Neka je U skup koji ima bar 1001 elemenat. Zaokruži tačna tvrdjenja a precrtaj netačna.

(a) Za sve skupove A, B ∈ P(U ) postoji skup C ∈ P(U ) takav da je (Ac ∆B) ∪ C = (Ac ∪ B)∆C.
(b) Za sve skupove B, C ∈ P(U ) postoji skup A ∈ P(U ) takav da je (Ac ∆B) ∪ C = (Ac ∪ B)∆C.
(c) Za svaki skup A ∈ P(U ) postoje skupovi B, C ∈ P(U ) takvi da je (Ac ∆B) ∪ C = (Ac ∪ B)∆C.
(d) Za svaki skup A ∈ P(U ) postoji skup B ∈ P(U ) takav da za svaki skup C ∈ P(U ) važi
(Ac ∆B) ∪ C = (Ac ∪ B)∆C.

9
Venov dijagram 4 skupa
U

D B

C A

1. Neka su A, B, C, D konačni skupovi takvi da je D ⊆ A ∪ B, D ⊆ C i |A4B| + |B r C| + |C r

D| + |B ∩ D| = |A|. Dokazati B ∪ C ⊆ A. Da li mora da važi B ⊆ C ili C ⊆ B?

2. Dati su skupovi A, B, C i D, Odrediti sve skupove X za koje je

(A ∩ X) ∪ (C ∩ X c ) = (A ∩ X) ∪ (D ∩ X c ) i (B ∩ X) ∪ (C ∩ X c ) = (B c ∩ X) ∪ (D ∩ X c ).

4 Raselov paradoks (razrešenje)

Aksioma izdvajanja nam omogućuje da izdvojimo sve elemente fiksiranog skupa A koji imaju svojstvo
P i da formiramo skup {x ∈ A mod P )x)} čiji su to jedini elementi. Prema tome, ta aksioma nam ne
dozvoljava izdvajanje svih skupova koji imaju svojstvo P i formiranje skupa od njih!!!
Na primer, neka je P (x) svojstvo x ∈ / x. Pretpostavimo da postoji skup r koji se sastoji od svih
skupova koji imaju to svojstvo. Imamo dve mogućnosti:
10 r ∈ r.
Svaki element x skupa r ima svojstvo x ∈ / x, što ne važi za skup r. Prema tome, r ne pripada sebi.
Kontradikcija; ovaj slučaj nije moguć.
20 r ∈ / r.
Skup r sadrži sve skupove koji imaju svojstvo x ∈ / x. Prema tome, r pripada samom sebi. Kon-
tradikcija; ni ovaj slučaj nije moguć.
Ni jedan od dva alučaja nije moguć, pa zaključujemo da je polazna pretpostavka pogrešna i da ne
postoji skup koji se sastoji od svih skupova koji imaju svojstvo x ∈ / x.

Stav 1.3 [MP] Svaki neprazan skup a ima podskup koji nije element skupa a.
(Drugim rečima: za svaki skup a važi P(a) 6⊆ a.)

Posledica 1.4 [MP] Ne postoji skup koji sadrži sve skupove.

Možemo li iz dosadašnjeg da zaključimo da ne postoji skup x takav da je x = {x}??? (Čudno, ali

NE.)

10
Dekartov proizvod
Uredjeni par skupova a i b je skup (a, b) definisan na sledeći način:

(a, b) =def {{a}, {a, b}} .

Naredno tvrdjenje sadrži najvažniju osobinu uredjenih parova.

Stav 1.5 [MP] Za skupove a, b, c, d važi: (a, b) = (c, d) ako i samo ako je a = c i b = d.

Definišemo i uredjenu trojku skupova (a, b, c) =def ((a, b), c) . Slično se definiše i uredjena četvorka,
...., uredjena n-torka.

Vežba

1. (a, b, c) = (a0 , b0 , c0 ) ako i samo ako a = a0 , b = b0 i c = c0 .

2. Ako a ∈ A i b ∈ B, tada (a, b) ∈ P(P(A ∪ B)).

Definišemo Dekartov proizvod skupova A i B

A × B =def {x ∈ P(P(A ∪ B)) | postoje a ∈ A i b ∈ B tako da x = (a, b)}.

11