Mnoºice in podmnoºice

(b) {0,¹₂,−¹₂,²₂,−²₂,³₂,−³₂, . . .}, (c) {2,10},

(d) {1,2,3,4,5,6}. 2. (a) {√

n|n ∈N},

(b) {n∈N|(4|n)∨(n³ <30)}, (c) {n² |n ∈N} ∪ {n∈N|4-n}.

3. (a) A je mnoºica lihih ²tevil, B pa mnoºica kubov vseh lihih ²tevil.

Jasno B ⊂A in B 6=A.

(b) A inB sta mnoºici kubov vseh lihih ²tevil, B pa vsebuje vsa cela

²tevila in vse ulomke z imenovalcem 2.

(c) Opazi(2n)²−1 = 4n²−1 = 4(n²−1) + 3in izpeljiA⊂B,A6=B. (d) Opazi, da ²tevilo oblike (3k+ 2)² ostanek 1 pri deljenu s 3, zato

B ⊂A. Obratno ne velja, saj denimo 3∈A, vendar 3∈/ B. (e) ElementiAso oblikey=x³zax∈Q. Jasno je potemy³ =x⁹ ∈B

oziroma A⊂B. Obratno ne velja, da √³

2∈B\A. (f) Re²ujemo podobno kot primer (e).

(g) A in C sta mnoºici ulomkov z imenovalcem 2, B pa je mnoºica sodih ²tevil. SlediB ⊂A=C, B 6=A.

4. Matemati£na oblika izjave:

∀A: (∃B: (B ⊂A∧A6=B)⇒A6= 0).

Dokaz: Ker B ⊂ A in A 6= B, obstaja nek element v A \B, torej A6={∅}.

5. (a) Izjava z besedami: Za vsako mnoºico A velja: ƒe obstaja element poten£ne mnoºice A, ki ni ∅, potem tudi A ni prazna mnoºica.

Utemeljitev izjave: Elementi poten£ne mnoºice A so podmnoºice mnoºice A, zato je element poten£ne mnoºice, ki ni prazna mno-ºica, neprazna podmnoºica mnoºice A.

(b) Negacija izjave: ∃A: ((∀B: (B *A∨B =∅))∧A=∅) 6. (a) {∅} vsebuje element, zato to ni prazna mnoºica.

(b) Relacija A⊂ ∅pomeni, da so vsi elementi mnoºice Avsebovani v

∅. Torej je moºno leA =∅. 7. (a) elementi A: ∅, {1},

podmnoºiceA: ∅, {∅},{1}, {∅,1}, {{1}}, {1,{1}},

(b) elementi A: ∅, {{1}},

podmnoºiceA: ∅, {∅},{1}, {∅,1},

3.2.2 Unije in preseki

1. (a) A∪B ={n ∈N: 10|n ∨ 6|n}, A∩B ={n ∈N: 10|n ∧ 6|n}, A\B ={n∈N: 10 |n ∧ 6-n}, A^c={n∈N: 10 -n}

(b) A∪B = (−1,2], A∩B = [0,1),A\B = [1,2],A^c =R\[0,2], 2. Vse primere se da obravnavati enako. Natan£no si zato oglejmo le nakaj

primerov (a), (b), (f) in (i). Neenakost bomo obrgli s protiprimerom, vsake od enakosti pa se bomo lotili na druga£en na£in.

(a) Enakost v primeru (a) dokaºimo tako, da zapisa mnoºic v enakosti preoblikujemo enostavnej²ega, a seveda ekvivalentnega:

(A\B)\C = A\(B∪C) (A∩B^c)∩C^c = A∩(B∪C)^c (A∩B^c)∩C^c = A∩(B^c∩C^c) Vidimo, da enakost res velja.

(b) Enakost v primeru (b) v splosnem ne velja. Za A = {1,2,3}, B = {3,4} in C = {1,3} denimo dobimo (A\B)\C = {2} in A\(B\C) ={1,2}

(f) Pa pokaºimo primer (f). Enakost mnoºic bomo pokazali tako, da bomo pokazali obe vsebovanosti. Pri tem nam je v pomo£ tudi Vennov diagram.

Lotimo se najprej vsebovanosti ⊂, pokaºimo (A\(B∩C))∪(B\C)⊂(A∪B)\(B ∩C).

Takoj opazimo, da je A\(B ∩C) ⊂ (A∪B)\(B ∩C), saj je A ⊂ A∪ B. Velja pa tudi (B \C) ⊂ (A∪ B)\(B ∩C), saj B ⊂A∪B in B∩C ⊂C.

Pokaºimo sedaj ²e obratno vsebovanost⊃. Vzemimo poljubni element x ∈ A\(B∩C), t.j. x ∈ A in x /∈ B ∩C. Nato lo£imo dve moºnosti. ƒe je x ∈ A, potem je jasno x ∈ A \(B ∩ C).

ƒe pa x ∈ B, potem pa je x ∈ B \C. V obeh primerih velja x∈(A\(B∩C))∪(B\C).

(i) Dokaºimo ²e enakost (i). Tretja moºnost dokazovanja je tabela po zgledu resni£nostne tabele pri logiki. V tabeli bo z 1

ozna-£eno, £e element je vsebovan v mnoºici, sicer pa z0. Pa zapi²imo pripadajo£o resni£nostno tabelo:

Stolpca v tabeli sta enaka, kar implicira enakost mnoºic.

3. Vse primere se dokaze na podoben na£in, zato bomo natan£no dokazali le en primer z unijo in en primer s presekom, npr. (g) in (h).

Pokaºimo najprej, da je S∞

n=1[_n¹,2n+ 1] = (0,∞). Hitro opazimo, da so intervali[¹_n,2n+1]vsebovani v(0,∞)za vsen∈N, zato je potem unija teh intervalov vsebovana v(0,∞). Za dokaz obratne vsebovanosti pa izberimo poljubnix∈(0,∞)in pokaºimo, da je tudi element unije.

Za dovolj velik n bo jasno _n¹ < x < 2n+ 1, ter tako x ∈ [_n¹,2n+ 1].

(a) R\Z,

3.2.3 Poten£na mnoºica in kartezi£ni produkt 1. (a) P(A) ={∅,{1},{2},{1,2}},

(b) elementi P(A): ∅, {∅},{{1}}

podmnoºiceP(A): ∅, {∅},

(c) elementi P(A): ∅, {∅},{1, a}, {a}, podmnoºiceP(A): ∅, {∅}, {{1}},

(d) elementi P(A): ∅, {∅},{a},{a,{a}}, {{a,∅}}

podmnoºiceP(A): ∅, {∅}, {{a,∅}}. 3. elementi P(A): ∅, A,

podmnoºice P(A): ∅, {∅},{A},{∅, A}, elementi P(P(A)): ∅, {{∅}}, {A}, {∅, A}

podmnoºice P(P(A)): ∅,{∅}, {A}.

4. Spomni se, da je vsak element poten£ne mnoºice podmnoºica mnoºice N_n, ki bodisi vsebuje neko ²tevilo m ∈ N_n bodisi ga ne vsebuje. Po osnovnem izreku lahko tako podmnoºico mnoºice Nn izberemo na 2ⁿ na£inov.

5. (a) Velja.

Relacija P(A) ⊆ P(B) pomeni, da so vsi elementi mnoºice P(A) tudi elementi mnoºice P(B). Tudi mnoºica A je torej vse-bovana v P(A), kar pomeni, da jeA podmnoºica B.

Obratno, naj bo A ⊂ B. Potem so vse podmnoºice mnoºice A tudi podmnoºiceB, od koder ºe slediP(A)⊆ P(B).

(b) Velja. Sledi neposredno iz denicije prazne in poten£ne mnoºice.

(c) Velja. Opazi, da so elementi mnoºiceP(A)∩ P(B)natanko mno-ºice, ki so hkrati podmnoºice mnoºicA inB, torej presekaA∩B. (d) V splo²nem ne velja. Oglej si primerA ={1} inB ={2}.

(e) V splo²nem ne velja. Opazi naprimer, da je∅vsebovana v mnoºici P(A\B), vendar ni vsebovana v P(A)\ P(B).

6. (a) A×B ={(1,1),(1,∅),(2,1),(2,∅)},

(b) A×A×A={(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2), (2,2,1),(2,2,2)},

(c) A×C = ({1} ×[1,3))∪ {2} ×[1,3), (d) C×C={(x, y)|x, y ∈[01,3)}.

7. Vse enakosti oziroma vsebovanosti pokaºemo na enak na£in, zato si natan£neje oglejmo le primer (e).

Potrebno bo dokazati vsako vsebovanost posebej. Najprej poka-ºimo

(A\B)×(C\D) = (A×C)\((B×C)∪(A×D)).

Vzemimi torej poljuben element(x, y)∈(A\B)×(C\D), torejx∈A\B iny∈C\D. Zaradix∈Ainy∈B velja(x, y)∈A×D, zaradix /∈B in x /∈D pa velja(x, y)∈/ (B×C)∪(A×D).

Obratno vzemimo poljuben(x, y)∈(A×C)\((B×C)∪(A×D)). Jasno je potemx∈Ainy∈C. Ker(x, y)∈/ (B×C)∪(A×D), potem sledi x /∈B im y /∈D.

8. Enakost ne velja; P(A×B)vsebuje podmnoºice A×B, P(A)× P(B) pa so urejeni pari podmnoºic A oziroma B.

3.2.4 Relacije

4. (a) antisimetri£na, tranzitivna, sovisna.

(b) ireeksivna, sovisna.

(c) relacija delne urejenosti.

2. (a) asimetri£na, tranzitivna.

(b) asimetri£na.

(c) simetri£na.

(d) ekvivalen£na;

ekvivalen£ni razredi[x]_R ={x+n|n∈Z}, x∈[0,1).

(e) simetri£na. (aRb pomeni 3|(2a−b) oziroma 2a−b = 3k. Sledi 2b−a= 2(2a−3k)−a= 3a−3k, k∈Z, kar pomeni bRa.) (f) ekvivalen£na; ekvivalen£ni razredi [x]R ={±√

x²+n |n∈Z}. (g) ekvivalen£na; ekvivalen£ni razredi[n, n+ 1), n∈Z.

(h) ekvivalen£na; ekvivalen£ni razredi so premice v ravnini s koeci-entom ²₃.

(i) ekvivalen£na; ekvivalen£ni razredi[x]_R ={x+^√n₂ |n∈Z}. (j) simetri£na.

(k) asimetri£na.

(l) ekvivalen£na; ekvivalen£ni razredi so izhodi²£e, ter kroºnice s sre-di²£em v izhodi²£u.

(m) simetri£na.

(n) ekvivalen£na; ekvivalen£ni razredi so ravnine v prostoru z normalo (1,−1,1).

(o) simetri£na.

(p) reeksivna, simetri£na.

(q) ekvivalen£na;

ekvivalen£ni razredi[p(x)]_R ={q(x) +x⁵k(x)|k polinom }. (r) ekvivalen£na; ekvivalen£ni razredi so mnoºice polinomov z enakimi

ni£lami.

(s) nima nobene od na²tetih lastnosti.

3. (a) Vzemimo poljuben(a, b)∈ R ◦ R⁻¹. Potem obstajac∈X, da je

(d) Trditev dokaºimo indirektno. Naj torej R ne bo asimetri£na, ter naj obstajata a, b∈ X, da je aRb inbRa. Zaradi tranzitivnosti relacije je potm aRa in R ne more biti ireeksivna.

4. Naj bo najprej R◦T simetri£na. Vzemimo sedaj poljuben(a, b)∈ R◦ T, kar pomeni, da obstajac∈X, da je(a, c)∈ T in(c, b)∈ R. Zaradi simetri£nosti relacij R in T odtod dobimo (c, a) ∈ T in (b, c) ∈ R. To pa pomeni, da je (b, a)∈ T ◦ R. Pokazali smo R ◦ T ⊂ T ◦ R, obratno vsebovanost pa dokaºemo podobno.

3. Sledi neposredno iz denicij.

4. (a) V splo²nem ne. Oglejmo si primer mnoºice s tremi elementiX = {x, y, z}. Naj relacijama ∼₁ in∼₂ zaporedoma pripadata razbitji {{x},{y, z}} in {{x, y},{z}}. Odtod in iz denicije relacije R potem sledi, da je (x, y),(y, z) ∈ R in (x, z)6∈ R, ter zato R ni tranzitivna.

(b) Je ekvivalen£na, kar sledi neposredno iz denicij.

3.2.5 Funkcije in mo£ mnoºic

1. (a) R je funkcija; je surjektivna in ni injektivna,

R⁻¹ ={(3,−2),(1,0),(2,1),(2,−1),(3,2)} ni funkcija, R◦R⁻¹ ={(3,3),(1,1),(2,2)} je funkcija (bijektivna).

(b) R ni funkcija,

R⁻¹ ={(−1,0),(0,1),(1,2),(2,3),(3,2)} je funkcija (niti surjek-tivna niti injeksurjek-tivna),

R◦R⁻¹ ={(−1,−1),(0,0),(1,1),(1,3),(2,2),(3,3)} ni funkcija.

2. (a) Niti surjektivna niti injektivna.

(b) Ni surjektivna, je injektivna.

(c) Ni surjektivna, ni injektivna.

(d) Je bijektivna; inverzna funkcija f⁻¹(x) = ^x+1_x−1. (e) Je bijektivna; inverzna funkcija f⁻¹(x) =

qx+3 x−2. (f) Je surjektivna, ni injektivna

(g) Je injektivna, ni surjektivna. (To£ka (2,1) ni v sliki funkcije.) (h) Ni surjektivna, je injektivna. (Predpisa funkcije sta injektivna in

slikata v soda oziroma liha ²tevila.)

(i) Ni surjektivna, je injektivna. (To£ka(0,0) ni v sliki funkcije, saj ena£bab³+ 2 = 0 nima racionalne re²itve.)

(j) Ni surjektivna, je injektivna.

(k) Je surjektivna, ni injektivna.

(l) Ni surjektivna, je injektivna. (Predpisa funkcije sta injektivna in slikata ²tevila, ki dajo pri deljinju s 3 ostanek 2oziroma 0.) (m) Ni surjektivna, ni injektivna. (To£ka (1,0) ni v sliki funkcije;

f(1,0) =f(2,0) = (0,0).)

(n) Ni surjektivna, je injektivna. (To£ka (−1,0) ni v sliki funkcije.) (o) Je surjektivna, ni injektivna

(p) Ni surjektivna, je injektivna.

(q) Ni surjektivna, ni injektivna. (To£ka 0 ni v sliki funkcije.)

(r) Je surjektivna, ni injektivna. (Za vsakn ∈Njemin({n}∩N) =n.) 3. Vse trditve se dokaºejo na podoben na£in, neposredno preko denicij.

Pokaºimo zato le trditev (c).

Naj bo najprej g ◦f surjektivna. Za poljuben z ∈ Z potem ob-staja x ∈ X, da je z = g(f(x)). Torej se x preslika v z, kar pomeni surjektivnost g. ƒe pa je g ◦f injektivna, potem za poljubna x, y z lastnostjo f(x) =f(y)oziroma g(f(x)) =g(f(y))takoj dobimax=y. 4. (a) f({1,2,3,4}) ={2,4,8}; f(N))so ²tevila, ki so deljiva s 4, ali pa

dajo ostanek2 pri deljenju s6.

f⁻¹({4,8,10})) ={2,3,4}; f⁻¹({(1,−1),(4,8)}) ni smiselno de-nirana.

(b) f({1,2,3,4}) ={2,4,8};f(N))so to£ke v ravnini s celo²tevilskimi kordinatami, ki leºijo na grafu funkcije y=√

x³.

f⁻¹({(1,−1),(4,8),(2,3)}) = {1,2}; f⁻¹({1,2,3,4}) ni smiselno denirana.

5. (a) Jasno je A ⊆ f⁻¹(f(A)). Za utemeljitev obratne vsebovanosti v primeru injektivnosti f pa vzemimo poljuben x ∈ f⁻¹(f(A)). Obstaja y ∈ f(A), da je f(x) = y, zaradi injektivnosti f pa je 6. Relacija je ekvivalen£na; ekvivalen£ni razredi so praslike mnoºic z enim

elementom.

(g) Najprej izberi bijekcijo med neko ²tevno podmnoºico M ⊂ (0,1) inM ∪ {0}, nato pa jo identi£no raz²iri na celoten interval(0,1), (h) Bijekcijo med P(Z)in P(N) dobi² iz bijekcije med Z inN,

(i) f: (0,1]×Z→R, f(x, n) = n+x.

7. Predpostavi nasprotno, da obstaja bijekcijaf:A→ P(A). Vzemi sedaj mnoºico B = {a ∈ A | a 6∈ f(a)}, ter element b, ki se z f preslika v B ⊂A, t.j. f(b) =B. Ali jef(b)∈B?

Literatura

[1] Batagelj, V., Klavºar, S., DS1. Logika in mnoºice. Naloge. DMFA, Lju-bljana 1997.

In document 1.1 Resni£nostne tabele (Strani 39-50)