集合論導(dǎo)論部分習(xí)題

3.TheAxioms……Exercises3.5(p12)

(a)GiveA,B,andC,thereisasetPsuchthatx∈Pifandonlyifx=Aorx=Borx=C.

Answer:LetanyAandB,thereisasetDsuchthatx=Aorx=B.

∴D={A,B};letanyBandC;thereisasetEsuchthatx=Borx=C.

∴E={B,C};

∴D∪E={A,B,C}=P,bytheAxiomofpair.

4.ElementaryOperationsonSets……Exercises4.2(p15)

Prove:

(b)AB∩CifandonlyifABandAC.

Proof:Letx∈AB∩C,sox∈Bandx∈C.

∴ABandAC,bytheAxiomofUnion.

(d)A-B=(A∪B)-B=A-(A∩B)

Proof:Letx∈A-B;

∴x∈Aandxdonot∈B.

∵Ifx∈(A∪B)-B,sox∈(A∪B)andxdonot∈B.

∴x∈Aorx∈Bandxdonot∈B.

That’stosay,x∈Aandxdonot∈Borx∈Bandxdonot∈B.

∴x∈Aandxdonot∈B.Therefore,A-B=(A∪B)-B.

Andifx∈A-(A∩B),sox∈Aandxdonot∈(A∩B).

∴x∈Aandxdonot∈Aorxdonot∈B.

That’stosay,x∈Aandxdonot∈Aorx∈Aandxdonot∈B.

∴x∈Aandxdonot∈B.Therefore,A-B=A-(A∩B).

∴A-B=(A∩B)-B=A-(ACB),bytheAxiomofExtensionality.

PS:WealsocanprovethatA-(A∩B)=(A-A)∪(A-B)=?∪(A-B)=A-B

(f)A-(B-C)=(A-B)∪(A∩C)

Proof:Letx∈A-(B-C),sox∈Aandxdonot∈(B-C).

∴x∈A,andxdonot∈Borx∈C

Thatistosay,x∈A,xdonot∈Borx∈A,

X∈C.

∴A-(B-C)=(A-B)∪(A∩C).

4.5LetS≠?andAbesets.

(a)SetT1={Y∈ρ(A)|Y=A∩XforsomeX∈S},andprove

A∩∪S=UT1(generalizeddistributivelaw).

Proof:∵S≠?andsomeX∈S.

∴US=U{X1,X2,X3,…,Xi,…,Xn}=X1∪X2∪X3∪…∪Xi∪…∪Xn.

∵A∩∪S,soA∩(X1∪X2∪X3∪…∪Xi∪…∪Xn)

=(A∩X1)∪(A∩X2)∪(A∩X3)∪…∪(A∩Xi)∪…∪(A∩Xn)

=U{Y∈ρ(A)|Y=A∩XforsomeX∈S}=UT1.

(b)SetT2={Y∈ρ(A)|Y=A-XforsomeX∈S},andprove

A-US=∩T2

A-∩S=UT2

(generalizedDeMorganlaws).

Proof:∵US=U{X1,X2,X3,…,Xi,…,Xn}=X1∪X2∪X3∪…∪Xi∪…∪Xn(wecangetfrom(a)).

∴A-US=A-(X1∪X2∪X3∪…∪Xi∪…∪Xn)

=(A-X1)∩(A-X2)∩(A-X3)∩…∩(A-Xi)∩…∩(A-Xn).

=∩{Y∈ρ(A)|Y=A-XforsomeX∈S}=T2.

∴A-US=∩T2.

Chapter2Relations,Functions,andOrderings

1.OrderedPairs

Exercise(P18)

1.2Provethat(a,b),(a,b,c)existforalla,b,c,andd.

Proof:∵(a,b,c)=((a,b),c)=({{a},{a,b}},c)

∴(a,b,c)={{{{a},{a,b}}},{{{a},{a,b}},c}}

Ifa=b=c,

∴(a,b,c)={{{{a}}},{{a},a}}

If(a=b)∩c=?,

∴(a,b,c)={{{{a}}},{{a},c}}

Ifa∩(b=c)=?,

∴(a,b,c)={{{{a},{a,b}}},{{{a},{a,b}},b}}

Ifb∩(a=c)=?,

∴(a,b,c)={{{{a},{a,b}}},{{{a},{a,b}},a}}

Ifa∩b∩c=?,

∴(a,b,c)={{{{a},{a,b}}},{{a},{a,b},c}}

If(a=b)∩c=?,

∴(a,b,c)={{{{a}}},{{a},c}}

1.4provethat(a,b,c)=(a’,b’,c’)impliesa=a’,b=b’,c=c’.

Proof:

Ifa=a’,b=b’,c=c’,then,ofcourse,

(a,b,c)={{{{a},{a,b}}},{{a},{a,b},c}}

={{{{a’},{a’,b’}}},{{a’},{a’,b’},c’}}

=(a’,b’,c’).

Letusassumethat:

{{{a},{a,b}}},{{a},{a,b},c}}={{{a’},{a’,b’}}},{{a’},{a’,b’},c’}}

Ifa∩b∩c=?,{a}={a’}and{a,b}={a’,b’}.

So,firsta=a’andthen{a,b}={a,b’}impliesb=b’.

∵{{a},{a,b},c}={{a},{a,b},c’}

∴c=c’.

Ifa=b=c,{{{{a}}},{{a},a}}={{{{a’}}},{{a’},a’}}

∴{a}={a’},{a}={a’,b’}

∴a=a’=b’.

∵{{a},c}={a’},c’}

∴c=c’.

Ifa∩(b=c)=?,

{{{{a},{a,b}}},{{a},{a,b},b}}={{{{a’},{a‘,b’}}},{{a’},{a‘,b’},b’}}

∵{a}={a’}

∴a=a’.

∵{a,b}={a,b’}

∴b=b’.

∵b=c,{{a},{a,b},c}}={{a},{a,b},c’}}

∴c=c’.

If(a=b)∩c=?,

{{{{a}}},{{a},c}}={{{{a’}}},{{a’},c’}}

∵{a}={a’}

∴a=a’.

∴{a}={a,b’},a=b=b’.

∵{{a},c}={{a},c’}

∴c=c’

If(a=c)∩b=?,

{{{{a},{a,b}}},{{{a},{a,b}},a}}={{{{a’},{a’,b’}}},{{{a’},{a’,b’}},a’}}

∵{a}={a’}

∴a=a’.

∵{a,b}={a,b’}

∴b=b’

∵a=c,{{a},{a,b}},c}={{a},{a,b}},c’}

∴c=c’.

2.Relations

Exercises(p22)

2.1LetRbeabinaryrelation;letA=U(UR).Provethat(x,y)∈Rimpliesx∈Aandy∈A.ConcludefromthisthatdomRandranRexist.

Proof:∵(x,y)∈R

∴{{x},{x,y}}∈R

∴{x},{x,y}∈UR

∴x,y∈U(UR)

∵A=U(UR)

∴x∈Aandy∈A

∴(x,y)∈Rimpliesx∈Aandy∈A.

2.2(a)ShowthatandSRexist.[Hint:(ranR)x(domR),SR(domR)x(ranS).]

Show:∵ranR={y|thereexitsxsuchthatxRy}.

domR={x|thereexitsysuchthatxRy}.

∴(ranR)x(domR)={(y,x)|thereexitsxandysuchthaty∈ranRandx∈domR}.

And∵R={(x,y)|thereexitxandysuchthatxRy}

∴={(y,x)|thereexit(x,y)suchthat(x,y)∈R}.

∴(ranR)x(domR)andexits.

Andwecansee(domR)x(ranS)={(x,z)|thereexitxandzsuchthatx∈domRandz∈ranS}.

SR={(x,z)|thereexitsyforwhich(x,y)∈Rand(y,z)∈S}.

∴SR(domR)x(ranS)andexits.

2.3LetRbeabinaryrelationandAandBsets.Prove:

(a)R[A∪B]=R[A]∪R[B].

(b)R[A∩B]R[A]∩R[B].

(c)R[A-B]R[A]-R[B].

Proof:(a)Ifx∈AUB,sox∈Aorx∈B.

∴R[x]=R[A]orR[x]=R[B],that’stosayR[x]=R[A]UR[B]

And∵R[x]=R[AUB]

∴R[AUB]=R[A]UR[B].

(b)Ifx∈A∩B,sox∈Aandx∈B.

∴R[x]=R[A]andR[x]=R[B],that’stosayR[x]=R[A]∩R[B].

And∵A∩BAandA∩BB

∴thereexitsatleastonexsuchthatx∈Aandxdon’t∈A∩B;inotherwords,therealsoexitsR[x]R[A]∩R[B]butR[x]don’tR[A∩B].

∴R[A∩B]R[A]∩R[B]

(c)∵(A-B)U(A∩B)=A

∴R[(A-B)U(A∩B)]=R[A-B]UR[A∩B]=R[A].

∴R[A-B]UR[A∩B]-R[B]=R[A]-R[B]

∵A∩BB,

∴R[A∩B]R[B]

∴R[A-B]UR[A∩B]-R[B]R[A-B]

∴R[A]-R[B]R[A-B]

2.4LetRXxY.Prove:

(a)R[X]=ranRand[Y]=domR.

Proof:(a)∵RXxY={(x,y)|thereexitsxandyforwhichthatx∈Xandy∈Y}.

and∵ranR={y|thereexitsxforwhichthatxRy}.

x∈X,andXdomR,sothatR[X]={y|thereexitsxforwhichthatxRy}=ranR.

And∵domR={x|thereexitsyforwhichthatxRy}.

AndYranR

∴[Y]={x|thereexitsyforwhichthatyx}=domR

2.6ProvethatforanythreebinaryrelationsR,S,andT

T(SR)=(TS)R.

(Theoperationisassociation.)

Proof:If(x,y)∈R,SR={(x,z)|thereexityforwhich(x,y)∈Rand(y,z)∈S}.

∴T(SR)={(x,p)|thereexitzforwhich(x,z)∈(SR)and(z,p)∈T}.

∴(x,y)∈R,(y,z)∈Sand(z,p)∈T.

and∵(TS)={(y,p)|thereexitzforwhich(y,z)∈Sand(z,p)∈T}.

∴(TS)R={(x,p)|thereexityforwhich(x,y)∈Rand(y,p)∈(TS)}.

∴T(SR)=(TS)R

3.Functions

3.9Exerices3.1p28

Prove:Ifranfdomg,thendom(gf)=domf.

Proof:∵dom(gf)=domf∩(domg)

And∵ranfdomg,

∴(ranf)(domg)

and∵(ranf)=domf

∴domf∩(domg)=domf

∴dom(gf)=domf.

3.13Provethefollowingformofthedistributivelaw:

Assumingthat=Фforalla∈Aand∈B,≠.

Proof:LetLbethesetontheleftandRthesetontheright.