Question

Consider the set of all functions f : (0,1, 2014} {0.1, ....2014} $\to$ such that f(f(i)) = i, for all 0 $\le$ i $\le$ 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 such function must be onto. Which one of the following is CORRECT?

• A. P, Q and R are true
• B. Only Q and R are true
• C. Only P and Q are true
• D. Only R is true

Answer 1

The correct option is B Only Q and R are true

Since it is given that $\forall$i f(f(i)) = It means f.f = I i.e. f = f${}^{-1}$ That is f is a symmetric function. Statement P means that every symmetric function is a identity function which is false, since there are many symmetric functions other than identity function. Example: {(0. 1). (1, 0), (2. 3), (3, 2),...(2012, 2013), (2013. 2012). (2014, 2014)) is a symmetric function but not the identity function. Statement Q means that in every such symmetric function at least one element is mapped to itself and this is true, since there are odd number of elements in the set {0, 1, 2, ... 2014}. Statement R means that every symmetric function is onto which is true, since it is impossible to make an into function symmetric. See below diagram for a into function shown with only 3 elements:

In the above function note that (2,1) exist in the function but not (1,2) and so it is not systemeric.