in Set Theory & Algebra retagged by
15,319 views
78 votes
78 votes

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
in Set Theory & Algebra retagged by
15.3k views

4 Comments

...

1
1

@GO Classes , @Deepak Poonia  Please sir explain 

0
0
0
0

6 Answers

105 votes
105 votes
Best answer
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 since the domain set contains 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.

So, (B) is the answer.
edited by
by

4 Comments

Need one clarification for option A) what if we map 0 to 0, 1 to 1, 2 to 2 ....2014 to 2014. In that case f(f(i))=is satisfying and for every i, f(i) = i also.....
0
0

, yes but p is not necessary.

without p also we can achieve that.

0
0
I understood the explanation given above but I have one doubt.

Generally speaking, if f(x)=f inverse(x) then they intersect at y=x line as they are symmetric about this line.

f(i) = f inverse(i) = i.

Question says ff(i) = i for all i between 0 to 2014 then f(i) should be equal to i for all i b/w 0 to 2014.

Then why P is wrong it does not matter whether the domain is odd or even.
0
0
11 votes
11 votes

An involution is a function $f : A \rightarrow  A$ where $f(f(x)) = x.$ An involution is a function that, when applied twice, brings one back to the starting point.

Such functions are called involution or involutory function, or self-inverse function. 


Understanding such functions:

An involution is a function $f : A \rightarrow  A$ where $f(f(x)) = x.$

Example: $f : \{1,2,3 \} \rightarrow \{1,2,3 \} $ such that $f(1) = 2 ; f(2) = 1 ; f(3 ) = 3$

Example: $f : \{1,2, 3,4 \} \rightarrow \{1,2 \} $ such that $f(1) = 2 ; f(2) = 1; f(3) = 4; f(4) = 3$

Example: $f : \{1,2, 3,4 \} \rightarrow \{1,2 \} $ such that $f(1) = 2 ; f(2) = 1; f(3) = 3; f(4) = 4$

Example: $f : \{1,2, 3,4 \} \rightarrow \{1,2 \} $ such that $f(1) = 1 ; f(2) = 2; f(3) = 3; f(4) = 4$


Understanding Statements $P,Q$ given in the question:

Note that; in involutory function $f : A \rightarrow A,$ for any $a \in A$, Only two cases are possible:

Case 1: $f(a) = a$ i.e. $a$ maps to itself. [Note that $f(f(x)) = x$ is satisfied]

Case 2: $f(a) = b$ and $f(b) = a$ ; i.e. If $a$ maps to $b$ then $b$ maps to $a.$ [Note that $f(f(x)) = x$ is satisfied]

Basically, in involutory function, either an element maps to itself Or two elements map to each other. So, involutory function partitions the domain such that each part has either 1 or 2 elements in it. 

So:

  • if $|A| = Odd;$ At Least One element Must map to itself. Also,  An Odd number of elements map to themselves. 
  • if $|A| = even;$ An even number of elements map to themselves. 

In the given question, $|A| = 2015 = Odd$ ; So, At Least One element Must map to itself. Hence, statement $Q$ is True.

Statement $P$ is false because the following type of mapping is possible: $f : \{1,2,3 \} \rightarrow \{1,2,3 \} $ such that $f(1) = 2 ; f(2) = 1 ; f(3 ) = 3$


All involutions are bijections.

1. Involutory function $f: A \rightarrow A$ is an Injective function: 

Proof by contrapositive: Assume $f(a) = f(b)$ ; So, $f(f(a)) = f(f(b))$ ; So, $a = b.$

2. Involutory function $f: A \rightarrow A$ is a Surjective function:

Proof by contradiction: Note that domain & co-domain of $f$ are same i.e. set $A.$ Assume $f$ is not surjective. So, some element $y \in co-domain$ doesn’t have any pre-image in the domain. Since domain & co-domain are same, So, $y$ is also in the domain. Assume $f(y) = X$ ; Now $X$ is also in domain, So, $f(X) = f(f(y)) = y$ ; which is a Contradiction because we had assumed that $y$ didn’t have a pre-image but it turns our that $y$ has at least one pre-image in the domain.

3. Involutory function $f: A \rightarrow A$ is a Bijective function:

Proof: We have already proven that $f$ is injection & surjection. So, $f$ is bijection. 

So, Statement $R$ is True. 

NOTE that; A bijection may or may not be Involution.

Example: $f : \{1,2,3 \} \rightarrow \{1,2,3 \} $ such that $f(1) = 2 ; f(2) = 3 ; f(3 ) = 1$ is bijection But not involution.


Counting the number of Involutions:

The number of involutions on a set with n elements, $S_n,$ is given by a recurrence relation:

$S_n = S_{n-1} + (n-1)S_{n-2}$ ; where $S_1 = 1, S_2 = 2$

Proof: Let $A = \{ 1,2,3, \dots, n \}$ where $n \geq 3$ 

Take element $n.$ Either $n$ maps to itself Or $n$ maps to some other element $a$ where $1 \leq a \leq n-1.$

If $n$ maps to itself, then we need to count $S_{n-1}.$

If $n$ maps to some other element $a,$ then $a$ will map to $n;$ hence we need to count $S_{n-2}$ for every choice of $a.$ $a$ can be any element from $1$ to $n-1;$ So, $n$ can map to any of these $n-1$ elements. 

So,  $S_n = S_{n-1} + (n-1) S_{n-2}$ ; ; where $S_1 = 1, S_2 = 2$

NOTE: There is NO simple formula to count number of involutions. So, don’t worry about it. 

edited by
7 votes
7 votes

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 .

1 comment

You mean one-one and onto...
0
0
4 votes
4 votes

This is one other way to solve easily,

Ram_Chran

Hence, we can note that Statement P can be eliminated, and Q and R are true.

So, Option (B) will be the answer.

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true