Veky's MathLand -- EM1&2

Zadaci sa skupovnim inkluzijama i jednakostima

8Z Doka~zite da vrijedi

(A\B)u(B\A) =
(AuB)\(AnB)

Rj (C=) Neka je x@(A\B)u(B\A) proizvoljan. x je element unije dva skupa, pa vrijedi x@A\B V x@B\A. Sada bismo imali dvije grane u dokazu, ali zadatak je o~cito simetri~can s obzirom na zamjenu "A" i "B", pa BSOMP x@A\B. To zna~ci x@A i !(x@B).
Sad: kao prvo, A C= AuB, pa iz x@A slijedi x@AuB. Kao drugo, pretpostavka x@AnB vodi na x@B (&x@A), ~sto je u kontradikciji s !(x@B). Dakle, x nije u presjeku. To skupa s onim ~sto smo gore zaklju~cili (da je u uniji) daje jednu inkluziju.
(D=) Neka je x@(AuB)\(AnB). Po definiciji skupovne razlike, x@AuB, ali !(x@AnB). Sada s obzirom na prvi zaklju~cak (x je u uniji) imamo dvije grane, ali se opet mogu dobiti jedna iz druge samo zamjenom "A" i "B". Dakle BSOMP x@A. Tada pretpostavka x@B vodi na kontradikciju (s gornjim) x@AnB, pa mora biti !(x@B), ~sto zajedno s x@A daje x@A\B. No A\B je podskup od lijeve strane, pa zaklju~cujemo da je desna strana podskup lijeve.

D Ina~ce, taj skup (koji stoji i s lijeve i s desne strane u gornjem zadatku) naziva se simetri~cna razlika skupova A i B: AAB:=(AuB)\(AnB). Ona je karakterizirana time da je

x@AAB <=> x@A V x@B <=>
(E!_S@{A,B})(x@S)

~ dakle, njeni elementi su oni koji su u to~cno jednom od skupova A i B.

9Z Doka~zite:

A C= C & B C= C <=> 
AuB C= C

.
Rj(=>) Pretpostavimo A C= C & B C= C, i neka je x@AuB. To zna~ci x@A V x@B. BSOMP x@A. Zbog A C= C, x@C.
(<=) Pretpostavimo AuB C= C. Budu~ti da su A i B podskupovi od AuB, vrijedi (vidi sljede~ti zadatak) da su podskupovi i od C.

Z A C= B & B C= C => A C= C.
Rj Pretpostavimo A C= B i B C= C, i neka je x@A. Zbog prve pretpostavke je x@B, a po tome je zbog druge x@C. Dokazali smo da je svaki element od A ujedno i element od C, ~cime je tvrdnja zadatka dokazana.

10Z Doka~zite A\(BuC)=(A\B)\C.
Na Koristit ~temo karakterizaciju jednakosti skupova A=B <=> (A_x)(x@A<=>x@B). Za zada~tu mo~zete rije~siti zadatak pomo~tu inkluzij~a.
Rj Neka je x proizvoljan.

x@A\(BuC) <=>
x@A & !(x@BuC) <=> x@A & !(x@B V x@C) <=>

<=> x@A & !(x@B) & !(x@C) <=> x@A\B & !(x@C) <=>
x@(A\B)\C .

Na Presjek i unija su asocijativne operacije, ~sto zna~ci da je svejedno kojim redom ra~cunamo presjek ili uniju tri (ili vi~se) skupa: Au(BuC)=(AuB)uC i An(BnC)=(AnB)nC. Dz Doka~zite to.

Z Doka~zite da skupovna razlika nije asocijativna.
Rj Trebamo dokazati negaciju univerzalne tvrdnje, dakle tra~zi se kontraprimjer. Trebamo dokazati da op~tenito nisu jednaki skupovi A\(B\C) i (A\B)\C. Za ovaj drugi znamo po prethodnom zadatku da je jednak A\(BuC). BuC je nadskup od B\C, pa bi se o~cekivalo da A\ tog skupa bude podskup od A\ onog manjeg. (Dz Doka~zite sve te tvrdnje.) Dakle, jedino ~sto mo~ze pasti je druga inkluzija:

A\(B\C) C=
(A\B)\C

. Za to nam o~cito treba situacija kad je B\C pravi podskup od BuC (jer ako su jednaki, tada su im i A\ovi jednaki), odnosno nije svejedno dodamo li Bu C ili mu ga oduzmemo. Dakle, C nije prazan. Recimo C:={1}. B mo~ze biti bilo kakav, pa ga mo~zemo staviti i praznog, a A mora biti takav da se "ispod" njega vidi situacija izme~du B i C. Najmanji takav je BuC. Dakle,

A:=C:={1} & B:=0

A\(B\C)={1}\(0\{1})={1}\0={1} !=

!= (A\B)\C=({1}\0)\{1}={1}\{1}=0

(Ovo je bio minimalni kontraprimjer, ali bilo kakav kontraprimjer je dobar kao rje~senje.)

Dz (Puno raspisivanja) Doka~zite da simetri~cna skupovna razlika jest asocijativna.
Dz Doka~zite da su unija, presjek i simetri~cna razlika komutativne operacije, a obi~cna skupovna razlika nije.

11Z Ispitajte vrijedi li (A\B)uC=(AuC)\B.
Rj Nije svejedno oduzmemo li prvo B pa onda dodamo C, ili obrnuto. Naime, ako se neki element nalazi i u B i u C, tada ~te biti u rezultatu ako je zadnja operacija bila dodavanje, a ne~te biti ako je zadnja operacija bila oduzimanje. Modelirajmo to: dakle, neki element (npr. 1 ) i u B i u C, a A uop~te nije bitan, pa ga mo~zemo ostaviti i praznog.

A:=0 & B:=C:={1}

(A\B)uC=(0\{1})u{1}=0u{1}={1} !=

!= (AuC)\B=(0u{1})\{1}={1}\{1}=0

Dz Ipak op~tenito vrijedi jedna inkluzija izme~du ta dva skupa. Koja? Doka~zite to.

Dz Doka~zite da je skupovna unija distributivna prema presjeku, a i presjek prema uniji:

Au(BnC)=(AuB)n(AuC)
& An(BuC)=(AnB)u(AnC)

.
Dz Ispitajte u kakvom su odnosu (inkluzije, jednakost, disjunktnost) op~tenito skupovi Au(B\C) i (AuB)\C.
Dz Doka~zite A=(AnB)u(A\B).
Dz Doka~zite A\(A\B)=AnB.
Dz Doka~zite

A C= B & A C= C 
<=> A C= BnC

Z (pismeni, 2002-06-21) Neka su A, B, C i D proizvoljni skupovi. Ozna~cimo S:=(A\B)u(C\D) i T:=(AuC)\(BuD). Ispitajte vrijedi li kakva inkluzija izme~du S i T.
Rj (S C=? T) Neka je x@S. Tada x@A\B ili x@C\D. Zamjenom "A" i "B" sa "C" i "D" (tim redom) te dvije grane prelaze jedna u drugu, a T (pa time i istinitost od x@T) ostaje isti. Dakle, BSOMP x@A\B. Tada lako x@AuC, ali o~cito ne mogu zaklju~citi !(x@BuD) (~sto bi mi trebalo za x@T), jer jo~s uvijek mo~ze biti x@D. Dakle, kontraprimjer: x@D & x@A & !(x@B). Za C je svejedno.

((x:=1)) A:=D:={1} & B:=C:=0

S = (A\B)u(C\D) = ({1}\0)u(0\{1})
= {1}u0 = {1} !C=

!C= T = (AuC)\(BuD) =
({1}u0)\(0u{1}) = {1}\{1} = 0 .

(T C=? S) Neka je x@T proizvoljan. Tada x@AuC i !(x@BuD), odnosno !(x@B) i !(x@D). Unija vodi na dvije grane, x@A i x@C. U prvoj grani, x@A i !(x@B) daju x@A\B C= S, a u drugoj x@C i !(x@D) daju x@C\D C= S. U svakom slu~caju x@S, pa je ta inkluzija dokazana.