Chapter  5, Functions
Section  5.2  Onetoone and Onto
Summary
 Suppose . We will say that is onetoone if:
.
We say that is onto if:
.
Onetoone functions are sometimes also called injections, and onto functions are sometimes called surjections.  Suppose . Then:
 is onetoone iff . Note that this statement is
the positive form of the statement given above for onetoone.
As can be seen here, this statement is easier to prove that a function is onetoone. We select two values such that . Now by doing so if we can conclude that then function is onetoone.  is onto iff .
 is onetoone iff . Note that this statement is
the positive form of the statement given above for onetoone.
 Suppose and . Then as we know by the definition of composition of functions: .
 If and are both onetoone,then so is .
 If and are both onto, then so is .
 If a function is onetoone and onto, the function is sometimes called bijective.
Soln1
(a) OnetoOne: False, Onto: True
(b) It is not a function, so question is not applicable.
(c) OnetoOne: True, Onto: False
Soln2
(a) It is not a function, so question is not applicable.
(b) is not a function. : OnetoOne: False, as . Onto: True.
(c) OnetoOne: True, Onto: True
Soln3
(a) OnetoOne: False, Onto: True
(b)
For , Also for . Thus for two values, there is only one image in the range. Thus function is not onetoone.
It is not onto. To prove it lets suppose is onto. Thus for , there must exist some such that .
Thus .
.
.
.
Now, clearly we can see that if , . Thus is not onto.
(c)
Onetoone: False, because .
Onto: True, For every , for , .
Soln4
(a) Onetoone: True. Onto: False as there are many cities which are not capital of any country.
(b) Onetoone: True, Onto: True.
(c) Onetoone: True, Onto: False because for , there is not value of such that .
Soln5
(a)
Onetoone:
Suppose such that . Thus we have:
.
.
.
.
.
.
Thus, if , then . Since are arbitrary, it follows that is onetoone.
Onto:
Suppose is an arbitrary number such that . Thus we have:
.
.
.
.
.
.
Since and , it follows that . Since is arbitrary, it follows that for every , there exists an such that . Thus is onto.
(b)
.
.
.
.
.
Thus .
Soln6
(a) .
(b) is not onetoone because . is onto because for any set , if , then .
Update:
Part(b) of this answer is wrong regarding the onto part(for onetoone it is correct). Please check here.
I define By this definition not every pair of belongs to or for same there can be multiple .
Now the correct answer(from stackoverflow) answer is, if then . Clearly there are many sets which do not fall in this category for eg: .
Soln7
(a) .
(b) It is not onetoone since . However it is onto.
Soln8
(a)
Suppose is onto. Suppose is any arbitrary number. Since is onto, it follows that there must exist an element such that . Thus . Since is arbitrary, it follows that for every element , there exist an element such that . Thus is onto.
(b)
Suppose is onetoone. Suppose such that . Since is a function, it follows that . It follows that . Since is a onetoone, it follows that . Thus if , then . Since are arbitrary, it follows that is onetoone.
Soln9
(a)
Since is not onetoone, suppose such that . Since is onto, it follows that there exist some such that and . Thus we have , or . Thus is not onetoone.
(b)
Since is not onto, suppose such that . Since is a function from to , it follows that for some , . We shall prove by contradiction. Thus suppose is onto. Thus for some , . Thus . Since , and is onetoone, it follows . But it contradicts that . Thus is not onto.
Soln10
(a)
Suppose is onetoone. Suppose such that . Thus there exist an element such that and . Since is onetoone and , it follows that . Thus if , then . Since are arbitrary, it follows that is onetoone.
(b)
Suppose is onto. Suppose is an arbitrary element. Since is onto, there must exist some element such that . It follows that . Since , and , it follows . Since is arbitrary, it follows that for every , there exist some . Thus is onto.
(c)
Converse of (a) is: if is onetoone, then is onetoone.
Suppose .
Clearly, is onetoone but is not onetoone.
Converse of (b) is: if is onto, then is onto.
Suppose .
Clearly, is onto but is not onto.
Soln11
(a)
Suppose contains more than one elements and suppose . Thus . Thus is not onetoone.
(b)
Suppose contains more than one elements and suppose and . Thus there exist an element such that it is not the image of any element in . Thus is onto.
Soln12
()Suppose is onetoone. We will prove by contradiction that . Suppose . Thus there exist atleast one element such that and . Since , thus there exist an element such that . Similarly since , there exist an element such that . Since , and is a function, it follows . Similarly . Since is a onetoone function, it follows that . But since and are disjoint, it is a contradiction. Thus .
()We shall prove this by contrapositive. Suppose . Thus we can suppose an element . Since , there must exist an element such that . Similarly since , there must exist an element such that . Since , it follows that . Since , . Since , . Since and and , it follows that is not onetoone. Thus if , then is onetoone.
Soln13
To prove , we need to prove two things:
 .
 if and , then .
Proof for: .
Suppose . Since is a function from to , there must exist an element such that . Since , it follows that there exist an element such that and . Thus if then there exist an element such that . Thus .
Proof for: if and , then .
Suppose and such that and . Since is a function, there exist such that and . Since and , it follows . Similarly since and , it follows . Since is a function, it follows that . Since and and and is a onetoone function, it follows that . Thus if and , then .
Thus is a function from to .
Soln14
(a)
Suppose is reflexive and is onto. Suppose is an arbitrary element in . Since is onto function on , there exist an element such that . Since is reflexive and , it follows that . Thus . Thus . Since is arbitrary, it follows that is reflexive.
(b)
Suppose is transitive and is onetoone. Suppose and . Thus and such that and and and . Since is onetoone, it follows that or lets say . Thus and . Since is transitive, it follows . Since and and , it follows that . Thus is transitive.
Soln15
(a)
Suppose . Since is an equivalence relation, we know that is an equivalence class with respect to . Thus by definition of equivalence class as is an equivalence class, it follows . Thus for every element , . Thus is onto.
(b)
() Suppose is onetoone.
Since is equivalence relation, it follows that .
Now to prove . Suppose . Since is equivalence relation, . Also since is a function on , it follows and . Since , and since is onetoone, it follows . Thus . Since is arbitrary, it follows that .
Since and , it follows .
() Suppose . Suppose and suppose . Since is an equivalence class and , it follows that . Similarly . Thus and . Since is equivalence class, it follows . Now since , it follows that . Thus is onetoone.
Soln16
()Suppose is onetoone. Suppose such that . Since , then by the definition of , . Similarly . Since is onetoone and , it follows that . Thus , or . Since are arbitrary, it follows that .
()Suppose . Suppose such that . Since and , it follows that . Since , it follows that . Since is an equivalence relation and , it follows that . Thus $ is onetoone.
Soln17
(a)
()Suppose . Since is onto, there exist an element such that . Since , it follows that . Since , it follows . Thus there exist an element such that and . Since is a function, is a unique element, it follows that . Thus . Thus .
()Suppose . Since is onto, there exist an element such that . Since , it follows that . Since , it follows . Thus there exist an element such that and . Since is a function, is a unique element, it follows that . Thus . Thus .
Since and , it follows that .
(b)
I was not able to do it. Using the solution directly from the book.
Suppose such that . Suppose . Suppose and are functions from such that ,
, and . Then , so by assumption(by contrapositive) , and therefore we can choose some
such that . But by the way and were defined, the only for which is , so it follows that
. Since was arbitrary, it follows that is onto.
Soln18
(a) Suppose and such that . Since is a function frm to and , there exist an element say such that . Since and , it follows that . Since , it follows . Thus there exist element such that and . Since and and is onetoone, it follows that . Sicne and , it follows . Since is arbitrary, it follows that .
Similarly it can be seen that .
Thus we have and , it follows that .
(b)
Suppose such that . Suppose and are functions from such that ,
. Thus . Since it is given that if ,
then , it follows that . Thus . Thus is onetoone.
Soln19
(a)
Proof for :
Suppose is a function on . Thus . Thus we have . Thus there exist a function such that . Thus .
Proof for :
We can prove this by contradiction. Suppose that such that . Thus . Thus for , . Since , it follows that . Since , it follows that . Thus there is no value of such that . Thus at . This contradicts that is a function on . Thus .
(b)
A relation is preorder if it is reflexive and transitive.
Proof of is reflexive:
Suppose . Consider . Thus there exist a function such that . Thus . Since is arbitrary, it follows that is reflexive.
Proof of is transitive:
Suppose such that and . Since , there exist a function such that that . Similarly since , it follows that for there exist a function such that . Thus . Thus , where . Thus there exist a function such that . Thus . Since are arbitrary, it follows that is transitive.
Since is reflexive and transitive, it follows that is preorder.
(c)
Suppose . Consider . Thus there exist a function such that . Thus .
(d)
() Suppose . Suppose such that . Since , there exist a function such that . Thus . Since , it follows that and . Since , it follows that . Since are arbitrary, it follows that is onetoone.
() Suppose is onetoone. Suppose where . Now we will first prove that is a function.
To prove is a function, we need to prove existence and uniqueness. Suppose . Thus we have two possible cases:

Case 1: . Thus . It follows there exist an element such that . Thus . Also since is onetoone, thus is an image of only one element in . Thus for there is a unique element in . Thus exists as well as if then there is only one element(unique) such that .

Case 2: . Thus . Thus . Thus there is a unique value for every . Thus for , exists and there is only one value(unique) such that .
Thus is a function on .
Now suppose and . Since , then by definition of , . Thus .
Thus there exist a function such that . Thus .
(e)
Suppose . We have . Since is a function from to , it follows that . Since and , it follows that . Since , it follows . Thus .
(f)
() Suppose . Thus there exist a function such that . Thus . Since , it follows that . Since is a constant, thus is also a constant. Thus is a contant function.
() Suppose is a constant function such that . Consider . Thus . Thus , or .
(g)
Proof for largest element:
Suppose is set of all onetoone functions. Thus and is onetoone. Now to prove is the largest element, if
we prove . Since it is given that iff , it follows that we need to prove .
Now from part(c) of this solution, we have , or there exist a function such that .
Also since is onetoone, then form part(e) of the solution, there exist a function such that . Thus we have
, where . Thus . It follows that . Since
is arbitrary, it follows that is the largest element of in the partial order .
Proof for smallest element:
Suppose is set of all constant functions. Thus and is a contant function. Now to prove is the smallest element, if we prove . Since it is given that iff , it follows that we need to prove . Since is contant function, thus using part(e) of this solution, it follows that . Thus . Since is arbitrary, it follows that is the smallest element of in the partial order .