1.
Skupovi
• Skup je jednostavno kolekcija razliˇcitih objekata. ovi objekti mogu biti brojevi
ili nešto sasvim drugo.
• Npr. svi studenti prve godine ekonomije se mogu smatrati jednim skupom, isto
kao što parni brojevi {2, 4, 6, 8, 10, . . .} formiraju skup.
• Postoje dva naˇcina prikazivanja skupova: enumeracijom i deskripcijom.
• Skup pozitivnih cijelih brojeva možemo prikazati kao
Z+ := {1, 2, 3, 4, 5, . . .},
ili kao
Z+ := {x ∈ Z | x > 0}.
• Kao drugi primjer, skup A svih cijelih brojeva ve´cih od 2, a manjih od 6 se može
predstaviti kao
A = {3, 4, 5},
ili kao
A = {x ∈ Z | 2 < x < 6}.
• Skup sa ograniˇcenim brojem elemenata se zove konaˇcan skup, inaˇce je beskonaˇcan.
• Pripadnost skupu se oznaˇcava sa simbolom ∈. Dakle 3 ∈ {2, 3, 4}. Nepripadnost
skupu se oznaˇcava sa ∈,
/ npr. 3 ∈
/ {4, 5, 6}.
1.1.
Odnosi medu
¯ skupovima
• Odnosi medu
¯ skupovima se predstavljaju simbolima
=, ⊂, ⊆, ⊃, ⊇
• Primjetite da dok se ∈ prikazuje odnos elementa i skupa, npr. ⊂ prikazuje odnos
izmedu
¯ dva skupa!
• Dok je npr. 3 ∈ N, N ⊂ R.
• Koliko podskupova skupa {1,2,3} možemo formirati? To su
{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
• Da li nešto zaboravljamo? Prazan skup je podskup svakog skupa!
• Generalno, ako skup ima n elemenata, onda on ima 2n podskupova.
• Jako je bitno razlikovati slijede´ce: i {0}.
• Još bitnija je razlika izmedu
¯ i {}!!!
• Ako dva skupa nemaju zajedniˇckih elemenata, onda se oni zovu disjunktni.
1.2.
Operacije na skupovima
• Unija dva skupa je skup koji sadrži sve elemente ta dva skupa, dakako bez ponavljanja!
A = {1, 3, 5, 6}, B = {2, 4, 6}, A ∪ B = {1, 2, 3, 4, 5, 6}.
• Presjek dva skupa je skup koji sadrži sve zajedniˇcke elemente ta dva skupa.
A = {1, 3, 5, 6}, B = {2, 4, 6}, A ∩ B = {6}.
• Razlika dva skupa je skup koji sadrži sve elemente skupa A koji nisu u skupu B
A = {1, 3, 5, 6}, B = {2, 4, 6}, A \ B = {1, 3, 5}.
Primjetite da je B \ A = {2, 4}!
• Uvedimo sada pojam univerzalnog skupa. Ako posmatramo realne brojeve, onda
o tome skupu možemo razmišljati kao o skupu svih realnih brojeva R.
• Onda možemo definisati komplement Ac nekog skupa A, kao skup svih elemenata uinverzalnog skupa koji nisu u skupu A.
A = N = {1, 2, 3, 4, . . .}, U = R, Ac = {0, −1, −2, −3, −4, . . .}.
1.3.
Zakoni operacija na skupovima
• Komutativni zakoni:
A ∪ B = B ∪ A,
A ∩ B = B ∩ A.
• Zakoni asocijacije:
A ∪ (B ∪ C) = (A ∪ B) ∪ C,
A ∩ (B ∩ C) = (A ∩ B) ∩ C.
• Zakoni distribucije:
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
• Provjerite zakone asocijacije i distribucije na skupovima:
A = {4, 5}, B = {3, 6, 7}, C = {2, 3}.
• Zakoni asocijacije:
A ∪ (B ∪ C) = (A ∪ B) ∪ C,
A ∩ (B ∩ C) = (A ∩ B) ∩ C.
• Zakoni distribucije:
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
• Zada´ca :)
2
Direktni proizvod skupova
Definicija 1..1. Uredeni
par elemenata a i b je skup elemenata {{a}, {a, b}} koji se
¯
kratko obilježava sa (a, b).
Uredena
trojka (a, b, c) je ((a, b), c).
¯
Definicija 1..2. Cartesiev (Descartesov) proizvod dva neprazna skupa A i B je skup
svih uredenih
parova (a, b), cˇ ija je prva komponenta a ∈ A, a druga komponenta
¯
b ∈ B. Taj se skup oznaˇcava
A × B = {(a, b)|a ∈ A ∧ b ∈ B}.
2.
Relacije i preslikavanja
2.1.
Binarne relacije
Binarne relacije
Definicija 2..1. Neka su A, B 6= ∅. Svaki podskup ρ Descartesovog proizvoda A × B
naziva se binarna ili dvoˇclana relacija na skupu A × B.
Za dva elementa a i b sa svojstvom (a, b) ∈ ρ kažemo da su u relaciji ρ i pišemo
aρb.
Na sliˇcan naˇcin kao kod Descartesovog proizvoda, pojam binarne relacije možemo
da proširimo na pojam n-arne relacije na skupu A1 × A2 × . . . × An . Skup svih
prvih komponenti binarne relacije ρ naziva se lijeva oblast relacije ρ i oznaˇcava sa Dl ρ
i respektivno za drugi Dr ρ.
Unija svih oblasti cˇ ini polje binarne relacije i oznaˇcava se sa Dρ.
2.2.
Relacija ekvivalencije i relacija poretka
Relacija ekvivalencije
Neka su biname relacije ρα gdje α pripada nekom indeksnom skupu definisane
u nepraznom skupu A. tj ρα ∈ A × A. Medu
¯ svim takvim relacijama u skupu A
izdvajamo one koje imaju slijede´ca svojstva:
1. Refleksivnost : (∀a ∈ Dρ) : aρa;
2. Simetriˇcnost : (∀a, b, c ∈ Dρ) : aρb ⇒ bρa;
3. Antisimetriˇcnost : (∀a, b, ∈ Dρ) : (aρb ∧ bρa) ⇒ a = b;
4. Tranzitivnost : (∀a, b, c ∈ Dρ) : (aρb ∧ bρc) ⇒ aρc.
Definicija 2..2. Binarna relacija definisana u skupu A naziva se relacija ekvivalencije
i oznacava sa “∼” (ˇcita se “tilde”), ako je refleksivna, simetriˇcna i tranzitivna.
3
Primjer 2..3. U skupu cijelih brojeva Z, neka je m 6= 0 fiksan broj, stavimo:
x ∼ y : ⇐⇒ ∃k ∈ Z tako da je x − y = k · m.
Tada kažemo da su x i y identiˇcni po modulu m i pišemo x ≡ y(modm). Ova relacija
je relacija ekvivalencije u Z.
Jedna od posljedica uvodenja
relacije ekvivalencije na nekom skupu A je podjela
¯
skupa A pomo´cu relacije ∼. Posmatrajmo skup u skupu A indeksiran proizvoljnim
elementom x ∈ A :
C(x) = {y ∈ A|y ∼ x}.
Skup C(x) naziva se klasa ekvivalencije elementa x.
Stav 2..4. Ako su C(x) i C(y) dvije klase ekvivalencije u skupu A, tada je C(x) =
C(y) ili C(x) ∩ C(y) = ∅.
Definicija 2..5. Binarna relacija definisana u skupu A naziva se relacija poretka i oznaˇcava sa “” ako je refleksivna, antisimetriˇcna i tranzitivna.
Za dva elementa x, y ∈ A koji su u relaciji “” kažemo da su uporedivi, a za skup
u kome je definisana relacija poretka “” kažemo da je ureden.
¯
Primjer 2..6. Neka je F proizvoljna familija skupova u kojoj je definisana relacija:
A B : ⇐⇒ A ⊂ B.
Ovako definisana relacija u F je jedna relacija poretka.
Definicija 2..7. Neka je u skupu A definisana relacija poretka . Element a ∈ A
naziva se majoranta ili gornje ograniˇcenje skupa A1 ⊂ A, ako je
(∀x ∈ A1 ) : x a.
Ako je pri tome a ∈ A, tada je a maksimalni element skupa A1 .
Definicija 2..8. Neka je u skupu A definisana relacija poretka . Element b ∈ A
naziva se minoranta ili donje ograniˇcenje skupa A1 ⊂ A, ako je
(∀x ∈ A1 ) : b x.
Ako je pri tome a ∈ A, tada je a minimalni element skupa A1 .
Definicija 2..9. Za skup A1 ⊂ A kažemo da je ograniˇcen sa gornje (donje) strane ako
postoji bar jedna majoranta (minoranta) skupa A1 . Skup je ograniˇcen ako je oganiˇcen
i s gornje i s donje strane.
Definicija 2..10. Neka je skup A ureden.
¯ Supremum skupa A1 ⊂ A je minimum skupa
majoranata skupa A1 . Oznaˇcava se sa sup A1 .
Infimum skupa A1 ⊂ A je maksimum skupa minoranata skupa A1 i oznaˇcava se sa
inf A.
4
2.3.
Preslikavanja
Preslikavanja
Definicija 2..11. Neka su X i Y neprazni skupovi. Pod preslikavanjem (iii funkcijom)
f skupa X u skup Y podrazumjeva se svaki postupak (zakon) kojim se svakom elementu
x iz X pridružuje jedan i samo jedan element y iz skupa Y .
ˇ
Cinjenicu
da je f preslikavanje skupa X u skupu Y oznaˇcavamo sa
f
f : X 7→ Y, x 7→ Y ili x 7→ f (x), x ∈ X ∧ f (x) ∈ Y.
Elementi skupa X nazivaju se originali, a elementi skupa Y slike preslikavanja f . Skup
X naziva se domen preslikavanja, i oznaˇcava sa D(f ), a skup slika f (x) kodomen
preslikavanja f i oznaˇcava sa R(f ).
Definicija 2..12. Neka je f : x 7→ Y . Ako je f (X) = Y , tj. ako je svaki y ∈ Y slika
bar jednog x ∈ X, kažemo da je preslikavanje sirjekcija ili preslikavanje “na”.
Definicija 2..13. Preslikavanje f : X 7→ Y naziva se injektivnim ili injekcija skupa X
u skup Y ako i samo ako se razliˇciti elementi skupa X preslikavaju u razliˇcite elemente
skupa Y .
Ovakvo preslikavanje se zove i “1 - 1”.
Po definiciji je stoga f injekcija ako
(∀x1 , x2 ∈ X) : x1 6= x2 ⇒ f (x1 ) 6= f (x2 ).
Definicija 2..14. Za preslikavanje f : X 7→ Y kažemo da je bijekcija skupa X i skupa
Y ako je f istovremeno i injekcija i sirjekcija.
Ako je za savko x ∈ X, i(x) = x, tada se preslikavanje i : X 7→ X zove jediniˇcno
ili identiˇcno preslikavanje u skupu X.
Ako pretpostavimo da u skupu Y kao kodomenu imamo definisane operacije sabiranja i množenja, onda možemo da definišemo zbir preslikavanja, množenje skalarom
(iz nekog skupa M ) i množenje preslikavanja. Ako su X, Y, Z neprazni skupovi i neka
postoje preslikavanja f : X 7→ Y i g : Y 7→ Z, tada možemo uvesti novu operaciju
Definicija 2..15. Kompozicija funkcija f : X 7→ Y i g : Y 7→ Z je preslikavanje
h = f ◦ g : X 7→ Z, definisano pomo´cu
(∀x ∈ X) : h(x) = g(f (x)),
tj.
def
(f ◦ g)(x) = g(f (x)).
Preslikavanje h se zove i složeno preslikavanje.
Stav 2..16. Ako su f : X 7→ Y i g : Y 7→ Z bijektivna preslikavanja, tada je i njihova
kompozicija bijektivna!
5
Definicija 2..17. Neka je f : X 7→ Y bijektivno preslikavanje. Inverzno preslikavanje
preslikavanja f je preslikavanje f −1 : Y 7→ X koje zadovoljava uslov:
(∀x ∈ X) : f −1 (f (x)) = x, tj.
f ◦ f −1 = i.
Svako inverzno preslikavanje je bijektivno.
6
Download

1. Skupovi - Front Slobode