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.
