Discrete-math 7

1a

If invertible, find the inverse of f:Z→N0,f(n)=|n|Solution:Let n∈N0N0⊆Z⟹n∈Z⟹∃(−n)∈Z:f(−n)=|−n|=n⟹f is surjectivef(1)=f(−1)⟹f is not injective⟹f is not bijective⟹f is not invertible

1b

If invertible, find the inverse of f:R→R+,f(x)=102−xSolution:Let f−1:R+→R,f−1(x)=2−log⁡(x)Let x∈R:(f−1∘f)(x)=f−1(f(x))=2−log⁡(102−x)=2−(2−x)=x⟹(f−1∘f)=IdR(1)Let x∈R+:(f∘f−1)(x)=f(f−1(x))=102−(2−log⁡(x))=10log⁡(x)=x⟹(f∘f−1)=IdR+(2)(1)∧(2)⟹f−1:R+→R,f−1(x)=2−log⁡(x) is an inverse of f

2

Let A=R∖{1}

2a

f:A→R,f(x)=x+1x−1Is f injective? Is it surjective?Solution:Let x1,x2∈Af(x1)=f(x2)⟹x1+1x1−1=x2+1x2−1⟹(x1+1)(x2−1)=(x2+1)(x1−1)⟹x1x2+x2−x1−1=x1x2+x1−x2−1⟹2x2=2x1⟹x1=x2⟹f is injective∀x∈R:x+1≠x−1⟹f(x)=x+1x−1≠1∈R⟹f is not surjective

2b

f:A→A,f(x)=x+1x−1Prove that f is invertible and find an inverseProof:Let y∈A:f(x)=yf(x)=x+1x−1⟹y=x+1x−1⟹yx−y=x+1⟹x=y+1y−1Let f−1:A→A,f−1(x)=x+1x−1(f−1∘f)(x)=x+1x−1+1x+1x−1−1=x+1+x−1x−1x+1−x+1x−1=2x2=x⟹(f−1∘f)=IdA(1)(f∘f−1)(x)=x+1x−1+1x+1x−1−1=x+1+x−1x−1x+1−x+1x−1=2x2=x⟹(f∘f−1)=IdA(2)(1)∧(2)⟹f−1=f

3

Let f:A→ALet fn=(f∘f∘⋯∘f)⏟n times where n∈NLet f0=IdA

3a

Prove: [∃n∈N:∀x∈A:fn(x)=x]⟹f is invertibleProof:∃n∈N:∀x∈A:fn=(fn−1∘f)=(f∘fn−1)=IdA⟹fn−1=f−1⟹f is invertible

3b

Prove: ∀x∈A:∃n∈N:fn(x)=x⟹f is invertibleProof:Let x1,x2∈A,f(x1)=f(x2)∃n,m∈N:fn(x1)=x1,fm(x2)=x2f(x1)=f(x2)⟹fn⋅m−1(f(x1))=fn⋅m−1(f(x2))fn⋅m−1(f(x1))=fn⋅m(x1)=(fn∘fn∘⋯∘fn⏟m times)(x1)=x1fn⋅m−1(f(x2))=fn⋅m(x2)=(fm∘fm∘⋯∘fm⏟n times)(x2)=x2⟹x1=x2⟹f is injectiveLet y∈A∃n∈N:fn(y)=yfn(y)=f(fn−1(y))=y⟹∀y∈A:∃x=fn−1(y):f(x)=y⟹f is surjective⟹f is bijective⟹f is invertible

4

Let g:N→NLet F:NN→NN,F(f)=(g∘f)Prove: F is injective⟺g is injectiveProof:Let g be injectiveLet f1,f2∈NNF(f1)=F(f2)⟹(g∘f1)=(g∘f2)⟹∀n∈N:g(f1(n))=g(f2(n))g is injective⟹∀n∈N:f1(n)=f2(n)⟹f1=f2⟹F is injective⟹g is injective⟹F is injective(1)Let F be injectiveLet x1,x2∈N:g(x1)=g(x2)Let f1,f2∈NN:f1(n)=x1,f2(n)=x2Let n∈NF(f1)(n)=(g∘f1)(n)=g(f1(n))=g(x1)F(f2)(n)=(g∘f2)(n)=g(f2(n))=g(x2)g(x1)=g(x2)⟹∀n∈N:F(f1)(n)=F(f2)(n)F(f1)=F(f2)⟹F is injectivef1=f2⟹∀n∈N:f1(n)=f2(n)⟹x1=x2⟹g is injective⟹F is injective⟹g is injective(2)(1)∧(2)⟹F is injective⟺g is injective

5

∽ on NNf∽g⟺∃k∈N:∀n>k:f(n)=g(n)

5a

Prove: ∽ is an equivalence relationProof:Let f∈NN∀n>1∈N:f(n)=f(n)⟹f∽f⟹∽ is reflexiveLet f,g∈NNf∽g⟹∃k∈N:∀n>k:f(n)=g(n)⟹∃k∈N:∀n>k:g(n)=f(n)⟹g∽f⟹∽ is symmetricLet f,g,h∈NN,f∽g,g∽hf∽g⟹∃k1∈N:∀n>k1:f(n)=g(n)g∽h⟹∃k2∈N:∀n>k2:g(n)=h(n)⟹∃k=max(k1,k2):∀n>k:f(n)=g(n)=h(n)⟹f∽h⟹∽is transitive∽ is reflexive, symmetric and transitive⟹∽ is an equivalence relation

5b

Find g∈NNsuch that ∀f∈[g]∽:f is not surjectiveSolution:Let g:N→N,g(n)=1f∽g⟹∃k∈N:∀n>k:f(n)=g(n)=1Let K=[k+1]f(k+1)=1⟹f[K]=f[[k∥k]]∪{1}∀n>k:f(n)=1⟹Im(f)=f[[k∥k]]∪{1}=f[K]f[K] is a finite set,f[K]⊆N⟹f[K]⊂N⟹Im(f)⊂N⟹f is not surjective

6

Let A=RRR,S,T are relations on A

6a

fRg⟺(f∘g)=(g∘f)Determine and prove whether R is an equivalence relationDisproof:Let f,g,h∈ALet f(x)=x+1Let g=IdRLet h(x)=x3(g∘f)=(f∘g)=f⟹fRg(h∘g)=(g∘h)=h⟹gRhLet x=1(h∘f)(x)=(x+1)3=8,(f∘h)(x)=x3+1=2⟹(h∘f)≠(f∘h)⟹fR̸h⟹R is not transitive⟹R is not an equivalence relation

6b

fSg⟺∀y∈R:∃x∈R:(x>y)∧(f(x)=g(x))Determine and prove whether S is an equivalence relationDisproof:Let f(x)=sin⁡(x)Let g(x)=0Let h(x)=sin⁡(x)−1∀y∈R:∃x∈R:x>y∧sin⁡(x)=0⟹fSg∀y∈R:∃x∈R:x>y∧0=sin⁡(x)−1⟹gSh∀x∈R:sin⁡(x)≠sin⁡(x)−1⟹fS̸h⟹S is not transitive⟹S is not an equivalence relation

6c

fTg⟺∃y∈R:∀x∈R:(x>y)→(f(x)=g(x))Determine and prove whether T is an equivalence relationProof:Let f∈A∀f∈A:∀x>0∈R:f(x)=f(x)⟹fTf⟹T is reflexiveLet f,g∈A:fTgfTg⟹∃y∈R:∀x∈R:(x>y)→(f(x)=g(x))⟹∃y∈R:∀x∈R:(x>y)→(g(x)=f(x))⟹gTf⟹T is symmetricLet f,g,h∈A:fTg,gThfTg⟹∃y1∈R:∀x∈R:(x>y1)→(f(x)=g(x))gTh⟹∃y2∈R:∀x∈R:(x>y2)→(g(x)=h(x))⟹∃y=max(y1,y2):∀x∈R:[(x>y)≡(x>y1∧x>y2)]→(f(x)=g(x)=h(x))⟹fTh⟹T is transitiveT is reflexive, symmetric and transitive⟹T is an equivalence relation

7

Let f:A→B

7a

Prove or disprove: ∀X⊆A:f[Xc]⊆(f[X])cDisproof:Let A=B={1,2,3,4},X={1,2},f(x)=1f[Xc]=f[{3,4}]={1}f[X]={1}⟹(f[X])c={2,3,4}⟹f[Xc]⊈(f[X])c

7b

Prove or disprove: ∀X,Y⊆A:f[X△Y]=f[X]△f[Y]⟺f is injectiveProof: Let ∀X,Y⊆A:f[X△Y]=f[X]△f[Y]Let a1,a2∈A:f(a1)=f(a2)Let X={a1},Y={a2}f[X△Y]=f[X]△f[Y]f[X]△f[Y]=f[{a1}]△f[{a2}]={f(a1)}△{f(a2)}=∅⟹f[X△Y]=∅⟹X△Y=∅⟹a1=a2⟹f is injective⟹∀X,Y⊆A:f[X△Y]=f[X]△f[Y]⟹f is injective(1)Let f be injectiveLet X,Y⊆ALet y∈f[X△Y]⟹∃x∈X△Y:f(x)=y⟹x∈(X∖Y)∪(Y∖X)Let x∈X∖Yx∈X⟹y=f(x)∈f[X]Let y∈f[Y]⟹∃x1∈Y:f(x1)=yf(x1)=y=f(x)⟹f is injectivex1=x∉Y−Contradiction!⟹x∉Y⟹f is injectivey=f(x)∉f[Y]⟹y∈f[X]∧y∉f[Y]⟹y∈f[X]△f[Y][1]Let x∈Y∖Xx∈Y⟹y=f(x)∈f[Y]Let y∈f[X]⟹∃x1∈X:f(x1)=yf(x1)=y=f(x)⟹f is injectivex1=x∉X−Contradiction!⟹x∉X⟹f is injectivey=f(x)∉f[X]⟹y∈f[Y]∧y∉f[X]⟹y∈f[X]△f[Y][2][1]∧[2]⟹f[X△Y]⊆f[X]△f[Y](2)Let y∈f[X]△f[Y]⟹y∈(f[X]∖f[Y])∪(f[Y]∖f[X])Let y∈f[X]∖f[Y]y∈f[X]⟹∃x∈X:f(x)=yy∉f[Y]⟹∀x∈Y:f(x)≠y⟹[f(x)=y→x∉Y]⟹∃x∈X∖Y:f(x)=y⟹y∈f[X△Y][3]Let y∈f[Y]∖f[X]y∈f[Y]⟹∃x∈Y:f(x)=yy∉f[X]⟹∀x∈X:f(x)≠y⟹[f(x)=y→x∉X]⟹∃x∈Y∖X:f(x)=y⟹y∈f[X△Y][4][3]∧[4]⟹f[X]△f[Y]⊆f[X△Y](3)(2)∧(3)⟹∀X,Y⊆A:f[X△Y]=f[X]△f[Y]⟸f is injective(4)(1)∧(4)⟹∀X,Y⊆A:f[X△Y]=f[X]△f[Y]⟺f is injective

7c

Prove or disprove: ∀X⊆A:X⊆f−1[f[X]]Proof:Let X⊆ALet x∈Xx∈X⟹f(x)∈f[X]⟹x∈f−1[f[X]]⟹X⊆f−1[f[X]]

7d

Prove or disprove: ∀X⊆A:X=f−1[f[X]]⟺f is injectiveProof:Let f is injectiveLet a∈f−1[f[X]]a∈f−1[f[X]]⟹f(a)∈f[X]Let a1∈A:f(a1)=f(a)f(a1)=f(a)∈f[X]⟹a1∈Xf is injective: f(a1)=f(a)⟹a1=a⟹a∈X⟹f−1[f[X]]⊆X∀X⊆A:X⊆f−1[f[X]]∧f−1[f[X]]⊆X⟹∀X⊆A:f−1[f[X]]=X(1)Let ∀X⊆A:f−1[f[X]]=XLet a1≠a2∈ALet X={a1}f[X]={f(a1)}f−1[f[X]]=X⟹a2∉f−1[f[X]]⟹f(a2)∉f[X]⟹f(a2)≠f(a1)⟹f is injective(2)(1)∧(2)⟹∀X⊆A:X=f−1[f[X]]⟺f is injective