Discrete Math: Sets/Functions/Proofs

[opt!kal]

I apologize for the title, I really don't know how to describe these problems, so I just listed the categories that they fall under. Anyways...

Homework Statement

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.

Homework Equations

Nothing comes to mind.

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"

Since the problem takes the form p iff q, we basically have two cases, p ->
q and q -> p, where p is f is an one-to-one function and q equates to f is
an onto function. CASE I - p->q:

First let us assume that p is true, in other words, f is an one-to-one
function. Since f is 1-1 we know that each element in the co-domain will be
mapped into either 0 or 1 times, depending on the size of both the domain,
and co-domain. However, since we know that |A|=|B|, we know that the number
of elements in the domain (A) is equal to the number of elements in the
co-domain (B). By our definition of what a 1-1 function represents, we know
that each element in the co-domain will be mapped into one time (we know
this because since the sizes are equal, and some element in the co-domain
was not mapped into, it would mean that were exists an a and b within A
such that f(a)=c and f(b)=c for some element in c, which would not make the
function 1-1). We also know that a function is onto if for every element b
that resides in the co-domain, there is an element a within the domain such
that f(a)=b. Since we know that every element in the domain (A) must map
once into an element in the co-domain (B), we see that the function is
onto. Therefore we have shown that if f is 1-1 then f is onto.

CASE II- q->p:(Basically what I am thinking of doing is proof by
contradiction, so something like q ^!p) Proof by contradiction: Let us
assume that the statement,"if f is onto, then it is 1-1" is false, so that
we end up with the form q ^!p. Therefore we have, "f is onto, and f is not
1-1." Since f is onto, then we know that for every element in the
co-domain, there is an element in the domain such that f(a)=b. This means
that every element in the co-domain is mapped into one or more times. We
know that if there are elements in the co-domain that are being mapped into
more than one time, then it would mean that the domain itself has a fewer
number of elements than the co-domain. However, we know that this cannot
happen, since it was stated that |A|=|B| Therefore we know the statement "f
is onto and f is not 1-1" is false, which would mean that if f is onto,
then f must be 1-1.

Basically I am not really confident in how I did the second case. I don't 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...

Homework Statement

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.)

Homework 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)

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,

 

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

 

[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.

 

[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.