[PDF] [PDF] CSE 20 Homework 5 Solutions

View - Download [PDF] CSE 20 Homework 5 Solutions

Previous PDF

Next PDF

CSE 20 Homework 5 Solutions

1.Recall that a functionf:X!Yis

(i)injectiveif for allx;x02X, (f(x) =f(x0))!(x=x0), (ii)surjectiveif for ally2Y, there existsx2Xsuch thatf(x) =y, and (iii)bijectiveif it is both injective and surjective.

For the following functions, determine if they are injective, surjective, or bijective. Prove your answer. If you claim that

a function is only injective, you must prove that it is injectiveandnot surjective. Similarly, if you claim a function is

only surjective, you must prove it is surjective and not injective. (a) Denef:Z!Zsuch thatf(x) = 3x. (b) Deneg:N!N[ f0gsuch thatg(x) =bx=2c. (For a real numbera2R,bacis the largest integerzsuch that za. You may use the fact that ifa=z+rwherez2Zand 0r <1, thenbac=z.) (a) Answer:fis injective but not surjective.

Proof thatfis injective:

Letx;x02Zand assume thatf(x) =f(x0). Then we have 3x= 3x0. Dividing both sides by 3, we havex=x0.

Proof thatfis not surjective:

Considery= 1. Note thaty2Z. We claim that there is nox2Zsuch thatf(x) =y. Suppose not. Then

3x=f(x) =y= 1:

But this implies thatx= 1=3, which is not an integer.(b) Answer:gis surjective but not injective.

Proof thatgis surjective:

Lety2N[ f0g. We want to nd anx2Nsuch thatg(x) =y. Considerx= 2y+ 1. Thenx2Nand g(x) =g(2y+ 1) =b(2y+ 1)=2c=by+ 1=2c=y; where the last equality comes from the fact aboutbcgiven in the problem. Thusgin surjective.

Proof thatgis not injective:

Considerx= 2 andx0= 3. Thenx6=x0, but

g(x) =g(2) =b2=2c=b1c= 1 and g(x0) =g(3) =b3=2c=b1 + 0:5c= 1: Thusg(x) =g(x0) butx6=x0. Thus,gis not injective.1

2.Recall that for setsAandB, thepower setofAis given by

P(A) =fXjXAg

and thecross productofAandBis given by

AB=f(a;b)ja2Aandb2Bg:

Finally, given (a;b);(a0;b0)2AB, we have (a;b) = (a0;b0) if and only ifa=a0andb=b0. For two setsAandB,

dene the functionfA;B:P(A[B)!P(A)P(B) as f

A;B(X) = (X\A;X\B):

(a) IsfA;Binjective, surjective, or bijective? Prove your answer. (b) Suppose now thatA\B=;. IsfA;Binjective, surjective, or bijective? Prove your answer. Hint: you may nd it useful to prove the following lemma: supposeXY, thenX\Y=X. (a) Answer:For general setsAandB,fA;Bis injective but not surjective.

We rst prove the lemma. LetXY.

We rst need to showX\YX. Letx2X\Y, by denition of intersection, this impliesx2X. Thus,X\YX. Now we need to showXX\Y. Letx2X. Then sinceXY, we additionally havex2Y. Thus we havex2Xand x2Y, which by denition meansx2X\Y. Thus,XX\Y. Since we have shownX\YXandXX\Y, we can concludeX\Y=X.

Proof thatfA;Bis injective:

LetX;X02P(A[B). By denition this meansXA[BandX0A[B. Then, suppose thatfA;B(X) =fA;B(X0). Then, (X\A;X\B) =fA;B(X) =fA;B(X0) = (X0\A;X0\B): From this we can deduce thatX\A=X0\AandX\B=X0\B. Taking unions, we have (X\A)[(X\B) = (X0\A)[(X0\B):

From the distributive law, we have

X\(A[B) =X0\(A[B):

By our lemma, we can nally concludeX=X0. Thus,fA;Bis injective.

Proof thatfA;Bis not surjective for generalAandB:

Consider the special case whereA6=;and whereB=A. Then we claim thatfA;Bis not surjective. To see this, look at

(A;;). Note thatAAand; B, therefore (A;;)2P(A)P(B). Assume by contradiction that there exists X2P(A[B) such thatfA;B(X) = (A;;). Then by denition, (A;;) =fA;B(X) = (X\A;X\B) = (X\A;X\A) where the last equality follows from the fact thatA=B. Then we have

A=X\A=;

but this contradicts our assumption thatA6=;, thus we havefA;Bis not surjective.2 (b) Answer:In this case,fA;Bis bijective. From part (a), we know thatfA;Bis injective. All that is left to prove is thatfA;Bis surjective.

Proof thatfA;Bis surjective.

Let (S;T)2P(A)P(B). We want to ndX2P(A[B) such thatfA;B(X) = (S;T). ConsiderX=S[T. By denition of power sets, we knowSAandTB. Therefore, we haveX=S[TA[B, which means that

X2P(A[B).

First note that becauseSAandA\B=;, we haveS\B=;. By symmetric reasoning, we also haveT\A=;. Thus, f

A;B(X) = (X\A;X\B)

= ((S[T)\A;(S[T)\B) (Denition of X) = ((S\A)[(T\A);(S\B)[(T\B)) (Distributive law) = (S[(T\A);(S\B)[T) (Lemma) = (S[ ;;; [T) (Reasoning above) = (S;T) (Identity) Thus,fA;Bis surjective.3.Recall that a relation is an equivalence relation if it is re exive, symmetric, and transitive. For the following

relations, determine whether or not they are equivalence relations. If they are equivalence relations, prove that they

satisfy all three properties. If they are not, nd the property that they do not satisfy and provide a counter example.

(a) LetR1be the relation overQsuch thataR1bif and only ifab2Z.

(b) LetR2be the relation overNNsuch that (a;b)R2(c;d) if and only ifad=bc. (Here, we sayNis the set of

positiveintegers, not including 0). (c) LetR3be the relation overZsuch thataR3bif and only ifjabj 5.

(Bonus points). For each equivalence relation, identify the equivalence classes. Explain your reasoning.

(a) Answer:R1is an equivalence relation. To see thatR1satises the identity property, leta2Q. Thenaa= 02Z.

To see thatR1satises the symmetry property, supposea;b2QsatisfyaR1b. Then there exists an integerz2Zsuch

thatab=z. But this impliesba=z, wherez2Z. Thus,bR1a.

To see thatR1satises the transitivity property, supposea;b;c2QsatisfyaR1bandbR1c. Then there exist integers

z

1;z22Zsuch thatab=z1andbc=z2. But then

ac= (ab) + (bc) =z1+z22Z:

Thus,aR1c.

Bonus step:Fora2Q, we have that the equivalence class ofais given by [a] =fb2QjaR1bg =fb2Qjab2Zg =fb2Qj9k2Zs.t.ab=kg =fb2Qja and b have the same fractional partg: Thus, the equivalence classes ofR1are all the rational numbers between 0 and 1.3 (b) Answer:R2is an equivalence relation. To see thatR2satises the identity property, let (a;b)2NN. Thenab=ab. Thus, (a;b)R2(a;b). To see thatR2satises the symmetry property, suppose (a;b);(c;d)2NNsatisfy (a;b)R2(c;d). Then we have ad=bc, which impliescb=da. Thus (c;d)R2(a;b). To see thatR2satises the transitivity property, suppose (a;b);(c;d);(e;f)2NNsatisfy(a;b)R2(c;d) and

(c;d)R2(e;f). Then we havead=bcandcf=de. Multiplying the rst equation through byfand the second byb, we

haveadf=bcfandbcf=bde. From these two equations, we haveadf=bde. Sinced6= 0, we can divide both sides byd

to getaf=be. Thus, (a;b)R2(e;f). Bonus step:For (a;b)2NN, we have that the equivalence class of (a;b) is given by [(a;b)] =f(c;d)2NNj(a;b)R2(c;d)g =f(c;d)2NNjad=bcg =n (c;d)2NNjab =cd o

Thus, the equivalence classes ofR2are the positive rational numbers.(c) Answer:R3is not an equivalence relation. AlthoughR3satises re

exivity and symmetry, it does not satisfy

transitivity. To see this leta= 0;b= 4;c= 8. Thenjabj= 45 andjbcj= 45, butjacj= 8>5.4.Recall that a setAis calledcountableif

(i)Ais innite and (ii) there exists a surjective functiong:N!A. Prove that ifAis a countable set andBis a countable set thenA[Bis countable.

Answer:We rst show thatA[Bis innite. To see this, note that by countability,Ais innite and furthermore

AA[B. Therefore, we havejAj jA[Bj. Thus,A[Bmust be innite. Now we need to nd a surjective functiong:N!A[B. By the countability ofAandB, we know there exist surjective functionsgA:N!AandgB:N!B. Then denegby g(z) =( g

A(k) ifx= 2kfor some integerk

g

B(k) ifx= 2k+ 1 for some integerk

Since each integer is either even or odd,gis a valid function. To see that it is surjective, letx2A[B. Then there are

two cases.

Case 1:x2A. Ifx2A, then by the surjectivity ofgA, there exists ak2Nsuch thatgA(k) =x. Takingz= 2k, which

is also inN, we haveg(z) =gA(k) =x.

Case 2:x62A. Ifx62A, butx2A[B, thenxmust be inB. By the surjectivity ofgB, there exists ak2Nsuch that

g B(k) =x. Takingz= 2k+ 1, which is also inN, we haveg(z) =gB(k) =x. Thereforegis surjective and we can conclude thatA[Bis countable.

5.(Bonus question) Suppose for eachn2Nthere exists a countable setSn. Show that the union of all suchSn, written

S=1[ n=1S n; is countable.

Hint: From the countability proof of the rationals in lecture, we actually saw that the setNNis countable. You may

use the fact thatNNis countable in your proof. 4

Answer:We will rst show thatSis innite. To see those, note that by countabilityS1is innite and we haveS1S.

Thus,jS1j jSjwhich implies thatSis innite.

Now we need to nd a surjective functiong:N!S. By countability, for eachn2Nthere exists a surjective function

g n:N!Sn; and from the hint, we know that there exists a surjective functiong:N!NN. Forn2N, let

1.g(n) = (n1;n2) and

2.g(n) =gn1(n2).

Then eachz2Nis mapped exactly once, sogis a well-dened function. To see thatgis surjective, letx2S. Then

there is somen12Nsuch thatx2Sn1. By surjectivity ofgn1, there is an22Nsuch thatgn1(n2) =x. By surjectivity

ofg, there is an2Nsuch thatg(n) = (n1;n2). By denition ofg, this means there is an2Nsuch thatg(n) =x.

Thusgis surjective.

Putting it all together, we haveSis countable.5

quotesdbs_dbs6.pdfusesText_12

[PDF] surjectivité

[PDF] surveillance and the fourth amendment

[PDF] surveillance of black bodies

[PDF] survival analysis multiple events

[PDF] suspended chords guitar chart pdf

[PDF] suspended drywall ceiling details

[PDF] sustainability in cosmetics industry

[PDF] sustainable cities

[PDF] sustainable city concept/pdf

[PDF] sustainable development goals 2019

[PDF] sustainable development goals 2030 pdf

[PDF] sustainable development goals pdf 2018

[PDF] sustainable development goals pdf india

[PDF] sustainable development goals report 2019

[PDF] sustainable development mechanism unfccc