Homework Help: Discrete Math: Sets/Functions/Proofs

1. Apr 8, 2008

opt!kal

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
alright?

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+$$\epsilon$$ and y = m+$$\delta$$, where n = [x] and m = [y] and 0 ≤ $$\epsilon$$, $$\delta$$< 1. Consider
dividing your proof into two cases: one where $$\epsilon$$ and $$\delta$$ 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 +$$\epsilon$$+m +$$\delta$$] however, since we know
that $$\epsilon$$,$$\delta$$ 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. Apr 8, 2008

Dick

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?

3. Apr 9, 2008

opt!kal

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.

4. Apr 9, 2008

HallsofIvy

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.