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...(adsbygoogle = window.adsbygoogle || []).push({});

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

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+[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,

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Discrete Math: Sets/Functions/Proofs

**Physics Forums | Science Articles, Homework Help, Discussion**