Glava 1. Beskonačni skupovi
Definicija
Skupovi
A
i
B
su iste kardinalnostu (iste moći, ekvi-
valentni) ako postoji bijekcija
f
:
A
7→
B.
Tada pišemo
card
(
A
) =
card
(
B
)
ili
|
A
|
=
|
B
|
ili
|
A
∼
B.
Zadatak.
Dokazati da je
∼
relacija ekvivalencije.
Primjer.
f
(
x
) =
x
|
x
|−
1
je bijekcija skupa realnih brojeva i
intervala
(
−
1
,
1)
.
Zadatak.
Naći bijekciju skupa
N
i skupa svih parnih brojeva.
Zadatak.
Naći bijekciju skupa
Q
+
i skupa
N
.
Zadatak.
Da li postoji raconalna funkcija
f
sa cjelobrojnim
koeficijentima, takva da je
Q
⊆
f
(
Z
)?
Rješenje.
Ne! Zaista, ako je
lim
x
→∞
f
(
x
) =
a,
|
a
|
<
+
∞
,
tada postoji
N
takvo da za
Definicija
Kardinalni broj skupa
A
je ne ve ci od kardinalnog
broja skupa
B
(pišemo
cardA
≤
cardB
ako i samo ako postoji
C
⊆
B
, takvo da je
A
∼
C.
Primjer 2.
Skup je beskonačan ako i samo ako je ekvivalentan
nekom svom pravom dijelu.
Zadatak.
Dokazati da je na skupu kardinalnih brojeva
≤
relacija poretka.
Teorema
(Cantor, Bernstein).
Ako je
cardA
≤
cardB
i
cardB
≤
cardA
, tada je
cardA
=
cardB.
Dokaz.
Neka su
f
:
A
7→
B
i
g
:
B
7→
A
injekcije. Ideja je da
se modifikuje funkcija
f
da bude sirjekcija. Prvo je redefinišemo
na slici
g
(
B
)
, tako da ovde bude inverzija
g
. Naravno, ovo može
narušiti injektivnost, pa ćemo to raditi iterativno, tako što ćemo
smanjivati skupove na kojima se pravi redefinicija, beskonačno
dugo, dok ne postignemo cilj. Dakle, prvo imamo
C
0
=
A
g
(
B
)
,
a zatim uočavamo da je elementi skupa
f
(
C
0
)
imaju dva originala,
jedan za
f
, a drugi za
g
−
1
.
Zato ostavljamo da je
f
nepromijenjeno
1
za
c
0
∪
C
1
, C
1
=
g
(
f
(
C
0
))
Precizno,
C
0
=
A
g
(
B
)
, C
n
+1
=
g
(
f
(
C
n
))
i
C
=
∪
∞
n
=1
C
n
.
Postavimo
h
(
a
) =
f
(
a
)
,
ako
a
∈
C
i
h
(
a
) =
g
−
1
(
a
)
ako
a
6∈
C.
Tada je
h
dobro definisana funkcija i
h
je bijekcija. Provjera
(1) Sirjektivnost: Ako je
b
∈
B
, tada razlikujemo dvije moguńosti:
(1a) ako je
b
∈
f
(
C
)
, tada je
b
=
f
(
a
)
, a
∈
C,
pa je
h
(
a
) =
f
(
a
) =
b
. Ako
a
6∈
f
(
C
)
tada posmatramo
a
:=
g
(
b
)
.
Prema
definiciji
C
0
,
a
6∈
C
0
. Pošto je
f
(
C
n
)
⊆
f
(
C
)
,
to
b
6∈
f
(
C
n
) =
C
n
+1
, ni za jedno
n
. Dakle,
a
6∈
C
, pa je
h
(
a
) =
g
−
1
(
a
) =
b
.
(1b) Injektivnost. Pošto su
f
i
g
−
1
injekcije, dovoljno je dokazati
da nije moguća jednakost
f
(
c
) =
g
−
1
(
a
)
,
za neko
c
∈
C
i
a
∈
A
C
.
Pošto
c
∈
C
, postoji
n
≥
0
, takvo da je
c
∈
C
n
.
Dakle,
g
(
f
(
c
)
∈
C
n
+1
pa dakle i u
C
. Odavde slijedi
g
(
f
(
c
) =
g
(
g
−
1
(
a
)) =
a
nije u
C.
Kontradikcija.
Bez gubljenja opštosti, pretpostavljamo da su
A
i
B
disjunktni.
Za svako
a
∈
A
(ili slično za svako
b
∈
B
), posmatramo dvostrani
niz
· · · →
f
−
1
(
g
−
1
(
a
))
→
g
−
1
(
a
)
→
a
→
f
(
a
)
→
g
(
f
(
a
)
→ · · ·
Za svako
a
, ovaj niz može da se završi lijevu u
f
−
1
ili u
g
−
1
.
Kažemo da je tada to
A
-stoper element ako završi u skupu
A
ili
B
-
stoper ako završi u skupu
B.
U protivnom, je duplo-beskonačan.
Tako se dobija jedna korespondencija nizova i elemenata skupa
A
i nizova i elemenata skupa
B
.
Drugačija formulacija: Ako su
f
:
A
7→
B
i
g
:
B
7→
A
injekcije, tada postoje particije
A
1
, A
2
⊆
A
i
B
1
, B
2
⊆
B,
takve
da je
f
(
A
1
) =
B
1
, g
(
B
2
) =
A
2
.
Posledice su već veoma čudne.
Teorema.
(Cantor).
cardX < card
P
(
X
)
.
Dokaz.
Jasno je da je
cardX
≤
card
P
(
X
)
.
Ako je
f
:
X
7→
P
(
X
)
bijekcija, tada se posmatranjem skupa
A
=
{
x
∈
X
:
x
6∈
2
Za skup koji je besknačana a nije prebrojiv kažemo da je
nepre-
brojiv
.
Primjer.
Bijekcija skupa
Q
+
i
N
, po principu redjanja brojeva
po visini.
Zadatak.
Da li postoji racionalna funkcija
f
sa cjelobrojnim
koefciijentima, antakva da za svaki racional broj
r
postoji cijeli
broj
k
, takav da je
f
(
k
) =
r
? Drugim riječima, pitamo se da li
u dokazu da je skup racionalnih brojeva prebrojibv, možemo naći
bijekciju (ili surjekciju) skupa cijelih brojeva na skup racionalnih
brojeva.
Rjeěnje.
Odgovor: Ne! Ako bi
f
bila takva funkcija , tada
možemo razlikovati dvije mogućnosti. Ako je
lim
x
→∞
f
(
x
) =
q
konačan broj, tada bi svi racionalni brojevi van intervala
(
q
−
1
, q
+
1)
bili slike konačnog podskupa skupa cijelih brojeva, a to nije
moguće. Ako je pak
lim
x
→∞
f
(
x
) =
∞
, tada bi postojao interval
(
−
a, a
)
, a >
0
,
takav da svi racionalni brojevi iz tog intervala slike
konačnog podskupa skupa cijelih brojeva, što nije moguće.
Zadatak.
Konstruisti bijekciju izmedju
[0
,
1]
i
(0
,
1)
.
(Uput-
stvo: Posmatramo niz
x
n
= 1
/
(
n
+ 1)
i preslikavanje
f
(0) =
x
1
, f
(1) =
x
2
, f
(
x
k
) =
x
k
+2
, k
= 1
,
2
, . . . ,
i
f
(
x
) =
x
za ostale
x
∈
[0
,
1]
. Tada je
f
bijekcija.
Zadatak.
Postoji li neprekidna bijekcija
f
: [
a, b
]
→
R
?
Zadatak.
Konstruisati bijekciju kružnice i
[0
,
1]
.
Zadatak.
Konstruisati bijekciju unutrašnjosti i spoljašnosti
kruga.
Zadatak.
konstrisati bijekciju kruga i kvasrata, odnosno izmedju
kruga i zvezdaste oblasti.
Zadatak.
Konstruisati bijekciju izmedju skupa iracionanih
brojeva i skupa realnih brpjeva.
Zadatak.
Posmatramo preslikavanje
f
: (0
,
1]
×
(0
,
1]
→
(0
,
1]
4
definisano sa
f
(0
.a
1
a
2
. . . ,
0
.b
1
b
2
. . .
) = 0
.a
1
b
1
a
2
b
−
2
. . .
. Da leje
to injekcija? da li je bijekcija?
Zadatak.
Konstruisati bijekciju izmedju racionalnih brojeva
sa odsječka
[0
,
1]
i tačak kavdarta
[0
,
1]
×
[0
,
1]
sa racionalnim
koordinatama.
Zadatak.
Konstruisati bijekciju izmedju skupa prirodnih bro-
jeva i skupa svih konačnih podskupova skupa prirodnih brojeva.
Rješenje.
Prvo svakom skupu
{
n
1
, n
2
, . . . , n
k
} ⊆
N
(
n
1
<
n
<
· · ·
< n
k
) pridružimo broj
0
.
0
. . .
100
. . .
1
, gdje 1 stoje na
mjestu
n
1
, n
2
, . . . ,
t.j. razlomak
1
/
2
n
1
+
· · ·
+ 1
/
2
n
k
,
a zatim ovaj
skup preslikajmo na
N.
Zadatak.
Skup svih nizova prirodnih brojeva je iste kardinal-
nosti kao skup svih rastućih nizova prirodnih brojeva.
Zadatak.
Neka je
E
skup nenegativnih realnih brojeva i
F
skup svih suma konačnih podskupova skupa
E
i
s
sup
F
. Dokazati
da ako je
s <
+
∞
, tada je
E
najviše prebrojiv skup.
Rješenje.
Neka je
E
n
=
{
x
∈
E
:
x >
1
/n
}
i
B
=
{
x
∈
E
:
x
6
= 0
}
.
Tada je
B
=
∪
E
n
.
Ako je
B
neprebrojiv= skup, tada je
bar jedno
E
n
0
prebrojiv skup. Ali svi elementi u
E
n
0
su veći od
1
n
0
, pa njihove konačne sume ne mogu biti ograničene.
Zadatak.
Dokazati da je skup svih tačaka prekida monotone
funkcije
f
: [
a, b
]
→
R
je najviše prebrojiv. (Uputstvo: Skup
tačaka prekida
E
jednak je
∪
E
n
, gdje je
E
n
skup tačaka prekida
gdje je skok veći od
1
/k.
Zadatak.
Dokazati da ako je
E
neprebrojiv skup nenegativnih
brojeva, tada postoji
a
, takvo da je
E
∩
[
a,
+
∞
)
neprebrojiv. Da
li tvrdjenje važi ako se "neprebrojiv" zamijeni sa "beskonačan".
Zadatak.
Da li je moguće prebrojiv skup translirati tako
da novi skup nema zajedničkih tačaka sa
E
? (Slično pitanje sa
kružnicom i rotacijom.)
5
5. Dokazati da su segment
[0
,
1]
i kvadrat
[0
,
1]
×
[0
,
1]
iste
moći.
Rješenje.
Označimo
A
= [0
,
1]
i
B
= [0
,
1]
×
[0
,
1]
.
Jasno je da
je
card
(
A
)
≤
card
(
B
)
,
jer je
A
iste moći kao skup
B
1
= [0
,
1]
×
{
0
} ⊆
B
(odgovarajuća bijekcija
f
:
A
→
B
1
je
f
(
x
) = (
x,
0)
.
)
Odavde slijedi i da je
card
(
A
)
≤
card
(
B
)
.
Dokažimo obrnutu inkluziju.
Prisjetimo se da se svaki re-
alni broj
x
iz
(0
,
1]
može na jedinstven način
zapisati u obliku
x
= 0
.a
1
a
2
. . . a
n
. . .
koji se ne završava sa beskonačno mnogo
nula. Posmatrajmo sada preslikavanje
g
:
D
→
C
(0
,
1]
na sljedeći
način: ako je
x
= 0
.a
1
a
2
. . . a
n
. . . , y
= 0
.b
1
b
2
. . . b
n
. . .
, tada
postavimo
g
(
x, y
) = 0
.a
1
b
1
a
2
b
2
. . . a
n
b
n
. . .
.
Preslikavanje
g
je
injekcija, jer ako je
(
x, y
) = (0
.a
1
a
2
. . . a
n
. . . ,
0
.b
1
b
2
. . . b
n
. . .
)
,
(
u, v
) = (0
.c
1
c
2
. . . c
n
. . . ,
0
.d
1
d
2
. . . d
n
. . .
)
a pri tome
g
(
x, y
) =
g
(
u, v
)
,
tada je
0
.a
1
b
1
a
2
b
2
. . . a
n
b
n
. . .
= 0
.c
1
d
1
c
2
d
2
. . . c
n
d
n
. . . ,
odakle, slijedi
a
i
=
c
i
, b
i
=
d
i
,
za
i
= 1
,
2
, . . . .
To znači da
je
(
x, y
) = (
u, v
)
, odnosno preslikavanje
g
:
D
→
C
je injek-
cija.
Skup
C
1
=
g
(
D
)
⊆
C
i skupovi
D
i
C
1
su iste moći.
Dakle,
cardC
≤
cardD
, pa prema Kantor-Bernstajnovoj teo-
remi je
cardC
=
cardD.
Pošto su skupovi
(0
,
1]
i
[0
,
1]
iste moći,
odavde slijedi da je
A
= [0
,
1]
iste moći sa
B
= [0
,
1]
×
[0
,
1]
.
(
Komentar. Primijetimo da
g
nije bijekcija. Na primjer, ako
je
z
= 0
.
12301010
. . .
10
. . .
∈
(0
,
1]
,
tada ne postoji uredjen par
(
x, y
)
∈
(0
,
1]
×
(0
,
1]
,
takav da je
g
(
x, y
) =
z.
)
Zadatak.
Naći bijekciju izmedju skup racionalnih brojeva (iz
[0
,
1]
) i tačaka sa racionalnim koordinatama (kvadrata
[0
,
1]
×
[0
,
1]
.
)
Zadatak.
Naći bijekciju izmedju skupa svih polinoma sa racional-
nim koeficijentima i skupa
N.
Zadatak.
Naći bijekciju izmedju skupa svih konačnih pod-
7
