4.1k views

Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $f\left(f\left(i\right)\right)=i$, for all  $0 \leq i \leq 2014$. Consider the following statements:

$P$. For each such function it must be the case that for every $i,f(i) = i$.

$Q$. For each such function it must be the case that for some $i,f(i)=i$.

$R$. Each function must be onto.

Which one of the following is CORRECT?

1. $P, Q$ and $R$ are true
2. Only $Q$ and $R$ are true
3. Only $P$ and $Q$ are true
4. Only $R$ is true
retagged | 4.1k views
+1

Let $f(i) = j$. Now, we have $f(j) = i$, as per the given condition $f(f(i)) = i$.

For any $i \neq j$, we can have a mapping $f(i) = j, f(j) = i$ thus avoiding the condition $f(i) = i$. But the domain containing odd number of elements, at least for one element we must have $f(i) = i$. So, Q must be TRUE.

Since $f(i) = j$ and $f(j) = i$, and since $0 \leq i \leq 2014$ $i$ must take all 2015 possible values (since $f$ is a function, it must have a value for any element in the domain). We can easily see that $f(i)$ cannot be the same for two different $i$s- because suppose $f(2) = 5$, and $f(3) = 5$. Now as per given condition, $f(5) = 2$ and $f(5) = 3$, which is not allowed in a function. So, all $f(i)$ values are unique $\implies$ co-domain = range as there are only 2015 values in co-domain. So, R is true.

An identity function satisfies the given conditions. But that alone cant prove that P is true. We can also have a different function where all even numbers maps to the next odd number and all odd numbers map to the previous even number which satisfies the given conditions, except the last one as we have odd number in set. i.e.,
$f(0) = 1, f(1) = 0, f(2) = 3, f(3) = 2 \dots, f(2013) = 2012, f(2014) = 2014$.

This proves, P is false.

edited by
+7
how to get THIS thought in exam?
where to practice these questions on fns from?

"We can also have a different function where all even numbers maps to the next odd number and all odd numbers map to the previous even number"
+2
This is like an algorithm question. We do not need an exact proof or counter example in exam- as long as we see a counter example is there we can go for the choice. Such questions are asked many times in previous GATE..
+3
Sir , I didn't understand the first two lines of your answer. I think Q would be true here as we have odd no of elements in domain. if we were given (1-2014) as domain we do not need to have f(i)=i for any element. So in this case Q will be false. Am I right?
+1
@Hardi Yes, that's the exact reason :)
0
Had the total number of elements in the set considered been even like say {1,2,3,...,2014}, then Q would have been false because we could have a function where the mapping would have been like

1->2014

2->2013

.

.

.  1007-> 1008

Is this correct ?
+49
Two functions $f$ and $g$ are inverse of each other iff $f\circ g(x) = g\circ f(x) = x$.

Using this we can say that given function $f$ is inverse of itself. i.e. $f(x)=f^{-1}(x)$.
That means if $f(1)=2$ then $f(2)=1$. In genral if $f(i)=j$ then $f(j)=i$.
Likewise, I will pair each 2 elements. but one value will be left out (total values are odd), therefore I have to pair it with itself i.e.  $f(i)=i$ for some i.
0
good explanation
0
Is there any alternative method sir
0
@Arjun

I could not understand why P is false. Please explain again
0
Since domain has 0..2014 and f(f(i))=i . means whatever in the domain is needed in the range.so range 0..2014.Now as range becaomes same as codomain. Hence onto.Is this correct reasoning to prove is [email protected] sir?

Actually i did not understand how you prove it onto:(

I think if we see that if is is not onto,means some i from 0..2014 is not in output which cannot be the case

In you example above,even if the counter example you gave hold, f(2)=5f(2)=5, and f(3)=5,how can you prove it is not onto?
+5

Demystifying Arjun's explanation on "why each function must be onto":

1) Let f(i) = j. Now we have f(j) = i , as per the given condition f(f(i)) = i.

2) Since, f(i) = j  for 0 $\leq$ i $\leq$ 2014,

=> i must take all 2015 possible values.

(why?     ---   Recall,as per the definition of the function, each element in the domain

must be mapped to some element in  the codomain. )

3) From the definition of the function, we know that

this is not allowed.

|

|

V 4) As per the given condition,

this is not allowed.

|

| (Why??  ---- Let's take an example:    let f(2) = 3 and f(5) = 3   and f(3) = 2

then,      f( f(2) )  = f( 3) = 2   (which is ok)

but        f ( f(5) )  = f(3) = 2   (violation of the given condition.)

( as per given condtion,  f (f(5) ) should be 5 )

)

//Refer pt. 3 if you are wondering why f(3) = 2 and f(3) = 5 both can't be true.

5) Taking conditions mentioned in pt. 3 and pt. 4 into consideration, only possibility left is of one-to-one mapping.

6) So, this is what we know:

domain has 2015 elements.

Codomain has 2015 elements.

only one-to-one mapping is allowed.

Do you smell bijection??

0

@Arjun

sir i dont think option Q is necessary

here is counter example 0

@mehul

f( f(1) ) = f(3) = 2

i.e. the condition f( f(i) ) = i, doesnot holds.

Actually, you have applied 2 functions in your example.

/\                    /\                   /\

/ 1   \     f1       / 1  \     f2      / 1  \

| 2   |  -------> | 2   |  ------->|  2  |

\ 3  /               \ 3 /                 \ 3 /

\/                     \/                    \/

as per your example:       f2( f1(1) ) = f2( 3) = 1

But we have to apply a single function say f1 twice:

/\                    /\

/ 1   \     f 1       / 1  \

| 2   |  -------> | 2   |

\ 3  /               \ 3 /

\/                     \/

see as per your example  f1 ( f1 ( 1) )  = f1( 3) = 2

i.e. Condition f( f(i) ) means something like this:

1  ---------->3

2------------>2

3------------>1

f( f(1) ) = f(3) = 1

f( f(3) ) = f(1) = 3

f( f(2) = f(2) = 2

+1
thank you for clarification
0

Can anybody tell why mapping should be like

" all even numbers maps to the next odd number and all odd numbers map to the previous even number"

Why it cant be random like f(0)=10 and f(10)=0 ??

0
Yes I smell  bijection as ff(i) = i

It means  function  is invertible here that implies bijection hence  on to
0
I think  it would  be valid  for random number as well but they would  exist in pairs as numbers are odd for at least one f(i) = I would  be there
0

For each such function it must be the case that for some i,f(i)=i

Q say for each such function it should hold.what if I map each element i to (i+1) mod 2015? This function does not follow Q as for every i will be mapped to j such that (i != j).

plz help :(

0

@tusharp

see the above comment of

what will be the differnce between

f(f(i)) and f1(f2(i))

i think ans is B)

yes this function is into and onto .

as the P says for each i there must be a f(i)= i its may true but not the essential condition . as there must be like this f(0)=2014 and f(2014)= 0  so , f(f(0))=0

for Q its true , there must be atleast one element have to satisfy this condition f(i)= i .

and R is also true .

This kind of functions are called identity functions.

We assume f(i) = k. So, f(k) = i. Now, since the values of ‘ i ‘ and ‘ j ‘ would be same for atleast some values if the domain and co – domain intersect, which is true for the given question, Q is definitely true. But this might not happen for all the values of ‘ i ‘, hence, P is not always true.

Now, ‘ i ‘ ranges from 0 to 2014, so, it takes 2015 possible values. From the definition of a function, we know that for each input to the function, we have a unique output. Also, in the given question, domain and co – domain are exactly same. Therefore, the function is onto and hence, R is definitely true.
0
I could not understand why P is false. Please explain again
+1 vote
This kind of functions are called identity functions. We assume f(i) = k. So, f(k) = i. Now, since the values of ' i ' and ' j ' would be same for atleast some values if the domain and co - domain intersect, which is true for the given question, Q is definitely true. But this might not happen for all the values of ' i ', hence, P is not always true. Now, ' i ' ranges from 0 to 2014, so, it takes 2015 possible values. From the definition of a function, we know that for each input to the function, we have a unique output. Also, in the given question, domain and co - domain are exactly same. Therefore, the function is onto and hence, R is definitely true.   Thus, the correct option is B.
answered by Loyal (9.3k points) 1 flag:
0
how  can u  ensure onto property if domain  and codomain are exactly same it is not necessary always

1