Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete Math: Sets/Functions/Proofs

  1. Apr 8, 2008 #1
    I apologize for the title, I really dont know how to describe these problems, so I just listed the categories that they fall under. Anyways...

    1. The problem statement, all variables and given/known data
    Let f: A->B be a function, where A and B are finite sets and |A| =|B| (they have the same size I believe). Prove that f is one-to-one if and only if it is onto.

    2. Relevant equations
    Nothing comes to mind.

    3. The attempt at a solution
    I apologize in advance for the length, apparently writing it out into 2 giant paragraphs was the only way I could get through this problem"

    Basically im not really confident in how I did the second case. I dont know
    if I can do proof my contradiction, and if I can't, then what method should
    I think about in order to show this? Also, does the first half seem

    Anyways, on to the second problem...

    1. The problem statement, all variables and given/known data
    Prove that, for any reals x and y, [x] + [y] + [x + y] ≤ [2x] + [2y] (I apologize, the brackets are supposed to represent the floor symbol, I tried using latex, but it said the right floor was an invalid image, and made everything look weird, so I figure this should be a bit less confusing.)

    2. Relevant equations
    Hint: Let x = n+[tex]\epsilon[/tex] and y = m+[tex]\delta[/tex], where n = [x] and m = [y] and 0 ≤ [tex]\epsilon[/tex], [tex]\delta[/tex]< 1. Consider
    dividing your proof into two cases: one where [tex]\epsilon[/tex] and [tex]\delta[/tex] are both less than 1/2 and the other
    where they are not (i.e., at least one is greater than or equal to 1/2)

    3. The attempt at a solution
    As of now I have:

    CASE I: So basically I have [x] + [y] + [x + y], which
    would be something like: n + m + [n +[tex]\epsilon[/tex]+m +[tex]\delta[/tex]] however, since we know
    that [tex]\epsilon[/tex],[tex]\delta[/tex] is less than 1/2, they should become 0 due to the floor function,
    so basically we have n + m + [n + 0 +m +0]= n + m + n + m = 2n + 2m, right?
    and since the right hand side is equal to [2x] +[2y], we will have
    something like 2n + 2m meaning that our equation is 2n + 2m <= 2n + 2m. Is
    that what I have to do for the first case? I'm kinda confused as to what our end result is supposed to be for each case. In addition, do you have any tips on how to tackle the second
    case? Any help would be appreciated. Thanks in advance,
    Last edited: Apr 8, 2008
  2. jcsd
  3. Apr 8, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    For the first part, nothing you have written is false in the case of finite sets. But it's sort of mushy and vague. Because it never explicitly uses the fact that the sets are finite. Reread it, thinking about the case where A and B are infinite, in which case the conclusion is FALSE, and try to figure out what to do about it. What's the definition of finite and infinite?
  4. Apr 9, 2008 #3
    Do I have do consider the infiite case? I just thought since it stated within the problem that the sets were finite, that was what I should focus. In any case, I will give it some thought and get back to you.
  5. Apr 9, 2008 #4


    User Avatar
    Science Advisor

    Dick's point is that you don't use the fact that your sets are finite. And, since the statement is false for infinite sets, any proof that doesn't use the fact that the sets are finite can't be correct.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook