Chapter - 5, Functions

Section - 5.2 - One-to-one and Onto


Summary

  • Suppose . We will say that is one-to-one if:
    .
    We say that is onto if:
    .
    One-to-one functions are sometimes also called injections, and onto functions are sometimes called surjections.
  • Suppose . Then:
    • is one-to-one iff . Note that this statement is the positive form of the statement given above for one-to-one.
      As can be seen here, this statement is easier to prove that a function is one-to-one. We select two values such that . Now by doing so if we can conclude that then function is one-to-one.
    • is onto iff .
  • Suppose and . Then as we know by the definition of composition of functions: .
    • If and are both one-to-one,then so is .
    • If and are both onto, then so is .
  • If a function is one-to-one and onto, the function is sometimes called bijective.

Soln1

(a) One-to-One: False, Onto: True

(b) It is not a function, so question is not applicable.

(c) One-to-One: True, Onto: False


Soln2

(a) It is not a function, so question is not applicable.

(b) is not a function. : One-to-One: False, as . Onto: True.

(c) One-to-One: True, Onto: True


Soln3

(a) One-to-One: False, Onto: True

(b)

For , Also for . Thus for two values, there is only one image in the range. Thus function is not one-to-one.

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)

One-to-one: False, because .

Onto: True, For every , for , .


Soln4

(a) One-to-one: True. Onto: False as there are many cities which are not capital of any country.

(b) One-to-one: True, Onto: True.

(c) One-to-one: True, Onto: False because for , there is not value of such that .


Soln5

(a)

One-to-one:

Suppose such that . Thus we have:

.
.
.
.
.
.

Thus, if , then . Since are arbitrary, it follows that is one-to-one.

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 one-to-one because . is onto because for any set , if , then .

Update:

Part(b) of this answer is wrong regarding the onto part(for one-to-one 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 one-to-one 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 one-to-one. Suppose such that . Since is a function, it follows that . It follows that . Since is a one-to-one, it follows that . Thus if , then . Since are arbitrary, it follows that is one-to-one.


Soln9

(a)

Since is not one-to-one, suppose such that . Since is onto, it follows that there exist some such that and . Thus we have , or . Thus is not one-to-one.

(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 one-to-one, it follows . But it contradicts that . Thus is not onto.


Soln10

(a)

Suppose is one-to-one. Suppose such that . Thus there exist an element such that and . Since is one-to-one and , it follows that . Thus if , then . Since are arbitrary, it follows that is one-to-one.

(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 one-to-one, then is one-to-one.

Suppose .

Clearly, is one-to-one but is not one-to-one.

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 one-to-one.

(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 one-to-one. 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 one-to-one function, it follows that . But since and are disjoint, it is a contradiction. Thus .

()We shall prove this by contra-positive. 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 one-to-one. Thus if , then is one-to-one.


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 one-to-one 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 one-to-one. Suppose and . Thus and such that and and and . Since is one-to-one, 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 one-to-one.

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 one-to-one, 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 one-to-one.


Soln16

()Suppose is one-to-one. Suppose such that . Since , then by the definition of , . Similarly . Since is one-to-one 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 one-to-one.


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 one-to-one, 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 one-to-one.


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 pre-order.

(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 one-to-one.

() Suppose is one-to-one. 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 one-to-one, 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 one-to-one functions. Thus and is one-to-one. 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 one-to-one, 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 .