• Support PF! Buy your school textbooks, materials and every day products Here!

Discrete Math: Sets/Functions/Proofs

  • Thread starter opt!kal
  • Start date
19
0
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. 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.


2. Homework 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"

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

2. Homework 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:

Answers and Replies

Dick
Science Advisor
Homework Helper
26,258
618
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?
 
19
0
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
Science Advisor
Homework Helper
41,736
894
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.
 

Related Threads for: Discrete Math: Sets/Functions/Proofs

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
6K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
2K
Replies
8
Views
924
Top