Post a New Question

Discrete Math

posted by .

Let A={0,1,2,3,4}. Define a function f from A to A by f(n)=2n mod 5.

a/ Is f one-to-one?
b/ Is f onto?

Could you show me how to solve this problem, please? I have no idea what this function is.

Your help is greatly appreciated.

  • Discrete Math -

    f(0)=2x0=0=0 mod 5
    f(1)=2x1=2=2 mod 5
    f(2)=2x2=4=4 mod 5
    f(3)=2x3=6=1 mod 5
    f(4)=2x4=8=3 mod 5,
    so f(A)={0,1,2,3,4}
    a/- yes
    b/- yes

  • Discrete Math -

    The function has been defined already:
    f : A -> A
    f(n) = 2n mod 5

    To determine if the function is one-to-one and onto, we can enumerate the values of x and f(x) and compare with the elements of A = {0,1,2,3,4}.

    x f(x)=2n mod 5
    0 0 [2*0 mod 5 = 0 mod 5 = 0]
    1 2 [2*1 mod 5 = 2 mod 5 = 2]
    2 4
    3 1 [2*3 mod 5 = 6 mod 5 = 1]
    4 3

    Recall the definition of "one-to-one" is
    "A function f from A to B is called one-to-one (or 1-1) if whenever
    f (a) = f (b) then a = b. No element of B is the image of more than one element in A."

    Since no element in B (=f(x)) can be mapped from more than one element in A, the function is one-to-one.

    Recall the definition of "onto".
    "A function f from A to B is called onto if for all b in B there is an a in A such that f (a) = b. All elements in B are used."

    Since every element of set B (=f(x)) maps to an element in A, the function is onto.

    Many links are available for the definition and explanation of the two terms, you can try the following as a start, as it explains with clear examples:

  • Discrete Math -

    Thank you so much for your replies.

    Could you also verify what I did on this problem please?

    The set of course numbers for a collection of math courses is:

    M = {0099,1111,1113,2200,2210,2220,2300,2450,2500,3500,4500,4900}
    Define a relation R on M by (x,y) in R if course numbers x and y start with the same number.

    a/ Verify that R is an equivalence relation

    Reflexive: yes, because course number x start with the number itself.

    Symmetric: yes, because if x starts with the same number as y, then y also starts with the same number as x.

    Transitive: Yes, because for all courses x,y, and z, if x starts with the same number as y and y starts with
    the same number as x, then x starts with the same number as z.

    R is an equivalence because it is reflexive, symmetric, and transitive.

    b/ Describe the distinct equivalence classes of R.

    There are 5 equivalence classes:
    [1] = {0099}
    [2] = {1111, 1113}
    [3] = {2200,2210,2220,2300,2450,2500}
    [4] = {3500}
    [5] = {4500,4900}

  • Discrete Math -

    Looks all good to me!

Answer This Question

First Name
School Subject
Your Answer

Related Questions

More Related Questions

Post a New Question