Discrete Math (functions) help, please?

1) aRb ↔ a ≡ b (mod n). Test for reflexivity, symmetry, and transitivity.

2) Show that g(x) = e^x is one-to-one but not onto.

3) Composition of function is associative, i.e.,

If f: A → B, g: B →C, and h: C → D,

h ⁰ (g ⁰ f) = (h ⁰ g) ⁰ f.

Show that it is not commutative.


* In number 1, reflexivity is shown by aRa; symmetry by aRb ↔ bRa; transitivity by aRb ↔ bRc ↔ aRc (something like that) but I don't know how to apply it in the given problem.

* In number 2, a function f: A→B is said to be onto iff f(A)=B. A function f: A→B is said to be one-to-one iff f(x₁)=f(x₂) implies x₁=x₂.

* In number 3, I know that composition of function is associative. Please help me prove that is is not commutative.

Please experts, help me! Thank you very much in advance! Have a good day! :)

1 Answer

  • 9 years ago
    Favorite Answer

    1) a R b means "a and b have the same remainder when divided by n"

    Simple example:

    all the even numbers have remainder 0 when divided by 2

    and all the odd numbers have remainder 1 when divided by 2,

    so 3 R 5 (for n = 2)

    but not 3 R 4 since they have different remainders.

    For a R b ... the three properties all hold by virtue of their holding

    for equality.

    Reflexive: a R a since a (mod n) = a (mod n)

    Symmetric: a (mod n) = b (mod n) → b (mod n) = a (mod n)

    by reflexivity of equality,

    and similarly for Transitive:

    Let a' = a (mod n), b' = b (mod n), c' = c (mod n)

    a' = b' and b' = c' → a' = c' by transitivity of equals.


    e^x = e^y → x = y

    (the value of x and y being ln (e^x) or ln (e^y))

    but since 0 does not have a logarithm in any base, including e,

    there is no x such e^x = 0

    hence it is not onto.

    3) One simple counter example will suffice to show non-commutativity:

    Let f(x) = x^2

    Let g(x) = x+1

    Let x = 5

    f( g(5) ) = (5+1)^2 = 36

    g (f(5) ) = (5^2) + 1 = 26

    Or generally:

    f( g(x) ) = (x+1)^2 = x^2 + 2x + 1

    g( f(x) ) = x^2 + 1

    those are only equal for x = 0

Still have questions? Get your answers by asking now.