Discrete-math 8

1

A≠∅≠BProve: f:A→B is surjective⟹πf={f−1[{b}]|b∈B} is a partition of AProof:Let f be surjectiveLet R={(a,b)|f(a)=f(b)},R⊆A×A∀a∈A:f(a)=f(a)⟹aRa⟹R is reflexiveaRb⟹f(a)=f(b)⟹f(b)=f(a)⟹bRa⟹R is symmetricaRb∧bRc⟹f(a)=f(b)=f(c)⟹f(a)=f(c)⟹aRc⟹R is transitive⟹R is an equivalence relationf is surjective⟹∀b∈B:∃c∈A:f(c)=bLet c∈A,b∈B:f(c)=b[c]R={a∈A|f(a)=f(c)=b}f−1[{b}]={a∈A|f(a)=b}⟹∀c∈A:[c]R=f−1[{b}]⟹πf=A/R

2a

f:N→NProve or disprove: ∀A≠B⊆N:f−1[A]≠f−1[B]⟹f is injectiveDisproof:Let f(n)=⌈n2⌉Meaning: f(2n−1)=f(2n)=nf(1)=f(2)⟹f is not injectiveLet A≠B⊆N⟹∃n∈N:n∈A∖B∀n∈N:f−1[{n}]={2n,2n−1}∀n≠m∈N:|n−m|≥1⟹|2n−2m|=2|n−m|≥2⟹2m≠2n≠2m−1⟹∀n≠m∈N:2n∉f−1[{m}]⟹{n∈A⟹2n∈f−1[A]n∉B⟹2n∉f−1[B]⟹f−1[A]≠f−1[B]∀A≠B:f−1[A]≠f−1[B] and f is not injective

2b

f:N→NProve or disprove: ∀A≠B⊆N:f−1[A]≠f−1[B]⟹f is surjectiveProof:Let ∀A≠B⊆N:f−1[A]≠f−1[B]Let f be not surjective⟹∃m∈N:m∉Im(f)Let A={m},B=∅A≠Bf−1[B]=∅f−1[A]={n∈N|f(n)=m}=∅⟹f−1[A]=f−1[B]−Contradiction!⟹f is surjective

3

Let R be a relation on ALet f:A→Af respects R if:∀a,b∈A:aRb⟹f(a)=f(b)Given f, define f^:A/R→A∀[a]R∈A/R:f^([a]R)=f(a)

3a

f respects RProve: f^ is well-defined (it is unique and complete)it actually should be called to-one, because unique means that there is only one function,not only one image for each sourceProof:∀a∈A:[a]R={b∈A|bRa}={b∈A|f(b)=f(a)}∀[a]R∈A/R:a∈A⟹∃f(a)⟹∃f^([a]R)=f(a)⟹f^ is completeLet [a]R,[b]R∈A/R:[a]R=[b]Rf^([a]R)=f(a)f^([b]R)=f(b)[a]R=[b]R⟹aRb⟹f(a)=f(b)⟹f^([a]R)=f(a)=f(b)=f^([b]R)⟹f^ is "unique" (to-one)f^ is "unique" (to-one) and complete⟹f^ is well-defined

3b

f respects RLet f be injective∀a,b∈A:aRb⟹f(a)=f(b)⟹a=b∀a,b∈A:aRb⟹a=b⟹R=IdaLet C,D⊆A/R, prove f^[C∪D]=f^[C]∪f^[D]Proof:Let a∈Af(a)∈f^[C∪D]⟺[a]R∈C∪D⟺[a]R∈C∨[a]R∈D⟺f(a)∈f^[C]∨f(a)∈f^[D]⟺f(a)∈f^[C]∪f^[D]⟹f^[C∪D]=f^[C]∪f^[D]Let C,D⊆A/R, show that it’s not necessarily true that f^[C∩D]=f^[C]∩f^[D]Solution:Let A={1,2,3}Let f(1)=f(2)=f(3)=1Let R=IdA∪{(1,2),(2,1)}⟹[1]R={1},[2]R={2}Let C={[1]R},D={[2]R}f^[C∩D]=f^[∅]=∅f^[C]={f^([1]R)}={f(1)}={1}f^[D]={f^([3]R)}={f(2)}={1}f^[C]∩f^[D]={1}≠∅⟹f^[C∩D]≠f^[C]∩f^[D]

3c

Let f,g:A→AProve or disprove: (g∘f) respects R⟹f respects RDisproof:Let A={1,2,3}Let ∀a∈A:g(a)=1Let f=IdALet R=IdA∪{(1,2),(2,1)}g(f(1))=g(f(2))⟹(g∘f) respects Rf(1)≠f(2)⟹f doesn’t respect RProve or disprove: f respects R⟹(g∘f) respects RProof:Let a,b∈ALet f respects RaRb⟹f(a)=f(b)⟹g(f(a))=g(f(b)) as g is to-one⟹(g∘f) respects R

4

X,Y,Z are setsf:X→Yg:Y→Zh=(g∘f)

4a

Prove or disprove: C⊆X,h is injective⟹f−1[f[C]]=CProof:h is injective⟹f is injectiveLet c∈Cc∈C⟹f(c)∈f[C]⟹c∈f−1[f[C]]⟹C⊆f−1[f[C]]Let c∈f−1[f[C]]c∈f−1[f[C]]⟹f(c)∈f[C]⟹⏟f is injectivec∈C⟹C=f−1[f[C]]

4b

Prove or disprove: C⊆Y,h is surjective⟹f[f−1[C]]=CDisproof:Let X={1,2},Y={3,4},Z={5}f(1)=f(2)=3g(3)=g(4)=5⟹h(1)=5,h(2)=5,h is surjectiveLet C={3,4}f−1[3,4]={1,2}f[f−1[C]]=f[{1,2}]={3}≠C⟹f[f−1[C]]≠C

4c

Prove or disprove: C,D⊆Y,h is surjective⟹g[C∩D]=g[C]∩g[D]Disproof:Let X={1,2,3},Y={4,5,6},Z={7,8}Let f(x)=x+3,g(4)=g(6)=7,g(5)=8h(1)=h(3)=7,h(2)=8,h is surjectiveLet C={4,5},D={5,6}g[C∩D]=g[{5}]={8}g[C]∩g[D]=g[{4,5}]∩g[{5,6}]={7,8}∩{7,8}={7,8}⟹g[C∩D]≠g[C]∩g[D]

5

f:A→AB⊆AB1=B,Bn+1=f−1[Bn]x is called a fixed point of f if f(x)=x

5a

Prove or disprove: ∀B⊆A:⋂n∈NBn=∅⟹f has no fixed pointsProof:Let ∃x0∈A:f(x0)=x0Let B={x0}Base case. B1=B={x0}⟹x0∈B1Induction step. Let x0∈Bnx0∈Bn⟹x0∈f−1[Bn]⟹x0∈Bn+1⟹By induction: x0∈⋂n∈NBn⟹⋂n∈NBn≠∅⟹∃B⊆A:⋂n∈NBn≠∅⟹∀B⊆A:⋂n∈NBn=∅⟹f has no fixed points

5b

Prove or disprove: f has no fixed points⟹∀B⊆A:⋂n∈NBn=∅Disproof:Let A={1,2}f(1)=2,f(2)=1f has no fixed pointsLet B={1,2}∀n∈N:Bn={1,2}⟹⋂n∈NBn={1,2}≠∅⟹∃B⊆A:⋂n∈NBn≠∅⟹f has no fixed points⟹⧸⟹∀B⊆A:⋂n∈NBn=∅

6

f:N→N is called periodic if∃p>1∈N:∀n∈N:f(n)=f(n+p)

6a

Prove or disprove: f is periodic⟹f is not surjectiveProof:Let f be periodic⟹∃p>1∈N:∀n∈N:f(n)=f(n+p)Let p>1∈NLet P=f[[p∥p]]={f(1),f(2),…,f(p)}|P|≤p⟹P is finiteLet n∈NIf n∈[p], then f(n)∈PIf n>p, then ∃n1,n2∈N:n1<p,n=n1+n2p⟹f(n)=f(n1+n2p)=f(n1)∈P⟹∀n∈N:f(n)∈P⟹Im(f)=P⟹Im(f) is finite⟹Im(f)≠N⟹f is not surjective

6b

Prove or disprove: ∀f:f2 is periodic⟹f is periodicDisproof:f={1n is oddn+1n is evenLet n∈NIf n is odd, then f(n)=1⟹f(f(n))=1If n is even, then f(n)=n+1⏟odd⟹f(f(n))=1⟹∀n∈N:f(f(n))=1⟹f2 is periodicLet p>1∈NLet n∈N be evenIf p is even, then f(n+p)=n+p+1≠n+1⟹f(n)≠f(n+p)If p is odd, then f(n+p)=1≠n+1⟹f(n)≠f(n+p)⟹∀p>1∈N:∃n∈N:f(n)≠f(n+p)⟹f is not periodic⟹∃f:f2 is periodic and f is not periodic