1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete mathematics (PMI, composition, onto)

  1. Dec 13, 2008 #1
    1. The problem statement, all variables and given/known data


    F = {(1, a), (2, b), (3, a), (4, c)}
    G = {(b, 1), (a, 2), (c, 3)}

    i. Find F o G
    ii. Find G o F


    A function F: N x N --> N is represented 2(m + n) + 1 for F(m, n)

    i. Is F one-to-one?
    ii. Is F onto?


    Prove by Mathematical Induction:

    1^3 + 2^3 + 3^3 + ... + n^3 = [(n(n + 1))/ 2]^2 for all n element N.

    2. Relevant equations


    3. The attempt at a solution


    i. {(1, (a, 2)), (2, (b, 1)), (3, (a, 2)), (4, (c, 3))}
    ii. {((2, b), 1), ((1, a), 2), ((4, c), 3)}


    I have no idea how to do this.


    Well testing the base case of 1 since 1 is an element of N (natural numbers) the base case fails since 1^3 + 2^3 + 3^3 + ... 1^3 = 37 and [(1(1 + 1))/ 2]^2 = 1. 37 != 1. Therefore, the original statement is false.
  2. jcsd
  3. Dec 13, 2008 #2


    User Avatar
    Homework Helper

    I only understand the mathematical induction question, so I can help with that.

    So we need to prove:

    This means for the base case n=1, [tex]1^3=(\frac{1(1+1)}{2})^2[/tex]

    For n=2, [tex]1^3+2^3=(\frac{2(2+1)}{2})^2[/tex]

    For n=k, [tex]1^3+2^3+3^3+...+k^3=(\frac{k(k+1)}{2})^2[/tex]

    Do you see how this works now?

    Now you must prove true for n=k+1

    i.e. [tex]1^3+2^3+...+k^3+(k+1)^3=(\frac{(k+1)((k+1)+1)}{2})^2[/tex]

    But we have assumed that it is true for n=k, so this can be simplified:


    Did you see how this worked? All you need to do is prove the left side of the equation is equal to the right side.
  4. Dec 13, 2008 #3
    a) F takes in a natural number and returns a letter. G takes in a letter and returns a number. Your solutions shows F compose G taking in a number and returning an ordered pair? How can you fix it?

    b) Start with the definition of one-to-one and onto. What are they?

    c) You are having trouble with the notation. Typically, the series is written out to 3^3 in order to make clear the pattern of summing up all the cubes of the integers from 1 to n. If n = 1, then you do not need to add to 3^3; you just stop at 1^3.
  5. Dec 13, 2008 #4
    a) I might have this reversed but is it F o G = {(1, 2), (2, 1), (3, 2), (4, 3)} and G o F = {(2, 1), ((1, 3), 1), (4, 3)}

    b) From my understanding one-to-one means that every element of set A is mapped to exactly one element is set B, and onto means that every element in set B has to be mapped.

    c) Ok thanks for the help. I guess I didn't know how to do PMI when dealing with summations. I knew you must prove the base case is true, then formulate an induction hypothesis, and then prove the induction step. I thought you always had to use 1^3 + 2^3 + 3^3 on the LHS.
    Last edited: Dec 13, 2008
  6. Dec 13, 2008 #5


    User Avatar
    Science Advisor

    You should not have to guess about whether you have them reversed if you undstand what FoG and GoF mean- which is the main point of this problem. G goes from {a, b, c} to {1, 2, 3, 4} and F from {1, 2, 3, 4} to {a, b, c}. FoG goes from {a, b, c} to {1, 2, 3, 4} and then back to {a, b, c}: from {a, b, c} to {a, b, c}. The pairs for F o G should have only "a", "b", "c" in each pair. Conversely, G o F goes from {1, 2, 3, 4} to {a, b, c} and then back to {1, 2, 3, 4}: from {1, 2, 3, 4} to {1, 2, 3, 4}. The pairs in G o F should have only "1", "2", "3", "4" in each pair.

    F o G(x) means F(G(x)). You are told that G(b)= 1 and that F(1)= a. Therefore FoG(b)= F(G(b))= F(1)= a. FoG(b)= 1 so (b, a) is in the "FoG" set. Follow that pattern to work out the rest.

    Yes, that is exactly right. Here, since F is from R2, "one-to-one" means that two different pairs, (m,n) and (x,y), say, cannot be mapped onto the same thing. So a good way to approach this is to say "suppose F(m,n)= F(x,y)" and try to show that m= x and n= y. Here, F(m,n)= 2(m + n) + 1 and F(x,y)= 2(x+ y)+ 1. F(m,n)= F(x,y) means that 2(m+n)+ 1= 2(x+y)+ 1. Can you show that m= x and n= y from that or can you find different values of (m,n) and (x,y) that satisfy that? (Hint: what if m+n= x+ y? That is, what if m= 3, n= 2, x= 4, y= 1?)

    "Onto" means that for any real number Y, there exist a pair (m,n) such that F(m,n)= 2(m+n)+ 1= Y. Can you solve that for (m, n)? Of course, if F is NOT one-to-one, there may be many such solutions.

    (One kind of problem that comes up a lot in mathematics is 'existence and uniqueness'- showing that given problem (1) has a solution and (2) has only one solution. "Onto" says the solution to the problem F(m,n)= Y exists for all y and "one-to-one" says that solution is unique.)

    It is not proof by mathematical induction you have misunderstood but what is being asserted.

    You are asked to prove that [itex]1^3 + 2^3 + 3^3 + ... + n^3 = [(n(n + 1))/ 2]^2[/itex] and seem to be under the impression that with n= 1 that is [itex]1^3 + 2^3 + 3^3 + ... + 1^3 = [(1(1 + 1))/ 2]^2[/itex] which is not at all true. The expression on the left means that you add cubes of consecutive integers up to n. If n= 1 you only have 13 with no sum. If n= 2, 13+ 23, if n= 3, 13+ 23+ 33, etc.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook