1. Determine whether each of the following rules are functions; for those that a

Question

1. Determine whether each of the following rules are functions; for those that are functions, find the image and decide whether the function is injective, surjective, bijective, or none of the above. Justify your answers.

(a) f : N N defined by f(n) = n + 1.

(b) g : N (where = {0, 1}) defined by g(x) equalling the number of 1s in the word x.

(c) h : Q N defined by h(p/q) = q.

2. Let H(x, y) be the Hamming distance function on n. Explain why, for any words a, b, c n, H(a, c) H(a, b) + H(b, c). What can you say about the case where equality holds?

3. Suppose that A, B, C are sets such that |A| = |B| and |B| = |C|. Show that |A| = |C|. (Hint: you can’t assume that the cardinalities are finite numbers. What does it mean in general for two sets to have the same cardinality?)

Explanation / Answer

3,

|A|=|B| then there exists a bijection from A to B say f

And |B|=|C| then there exists a bijection from B to C say g

Now I will show that the composition h=(g.f) from A to C is also bijective.

(g .f) is both one one and onto

For onto,

h=(g.f):A --------->C

h(A) =(g.f)A

= g(f(A)) ,by composition

= g(B) ,

as f is onto from A to B _ f(A)=B

And g from B to C is onto then g(B)=C

That is h(A)=C

Means h is onto

For one one ,

Let a,a' in A

Such that h(a)=h(a')

(g.f)(a)=(g.f)(a')

g(f(a))=g(f(a'))

Since g Is one one

f(a)=f(a')

a=a' , since f is one one

Hence h is one one

h is bijection from A to C

That is |A|=|C|.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.