Number of Elements in Set of Functions with Injective Property

To determine the number of elements in the set $T$, we first analyze the condition for the existence of the function $g: B \rightarrow \mathbb{N}$.

Step 1: Injectivity of $f$

Let $A = \{1, 2, 3, 4, 5\}$ with $|A| = 5$, and $B = \{1, 2, 3, 4, 5, 6, 7\}$ with $|B| = 7$.

We are given that $T$ consists of functions $f \in S$ for which there exists a function $g: B \rightarrow \mathbb{N}$ satisfying: $g(f(x)) = 2^x \quad \text{for all } x \in A$

• Necessity: Suppose such a function $g$ exists. If $x_1, x_2 \in A$ such that $f(x_1) = f(x_2)$, then: $g(f(x_1)) = g(f(x_2)) \implies 2^{x_1} = 2^{x_2} \implies x_1 = x_2$ Thus, $f$ must be an injective (one-to-one) function.

• Sufficiency: If $f: A \rightarrow B$ is injective, then for each $y \in \operatorname{im}(f)$, there exists a unique $x \in A$ such that $f(x) = y$. We can explicitly define $g: B \rightarrow \mathbb{N}$ by: $g(y) = \begin{cases} 2^x & \text{if } y = f(x) \text{ for some } x \in A, \\ 1 & \text{if } y \in B \setminus \operatorname{im}(f). \end{cases}$ This function $g$ is well-defined and satisfies $g(f(x)) = 2^x$ for all $x \in A$.

Therefore, the set $T$ consists of all injective functions $f: A \rightarrow B$ such that $f(2) \neq 2$ and $f(4) \neq 4$.

---

Step 2: Counting via the Principle of Inclusion-Exclusion

Let $U$ be the set of all injective functions $f: A \rightarrow B$. The total number of such functions is: $|U| = {}^{7}P_{5} = 7 \times 6 \times 5 \times 4 \times 3 = 2520$

We define the following properties for functions $f \in U$:

• Let $E_1$ be the set of injective functions such that $f(2) = 2$.
• Let $E_2$ be the set of injective functions such that $f(4) = 4$.

We need to calculate $|T| = |U \setminus (E_1 \cup E_2)|$. By the Principle of Inclusion-Exclusion: $|T| = |U| - |E_1| - |E_2| + |E_1 \cap E_2|$

1. Calculating $|E_1|$: If $f(2) = 2$, the image of $2$ is fixed. The remaining 4 elements of $A$ (i.e., $\{1, 3, 4, 5\}$) must be mapped injectively to the remaining 6 elements of $B$ (i.e., $\{1, 3, 4, 5, 6, 7\}$). $|E_1| = {}^{6}P_{4} = 6 \times 5 \times 4 \times 3 = 360$

2. Calculating $|E_2|$: Similarly, if $f(4) = 4$, the image of $4$ is fixed. The remaining 4 elements of $A$ must be mapped injectively to the remaining 6 elements of $B$. $|E_2| = {}^{6}P_{4} = 6 \times 5 \times 4 \times 3 = 360$

3. Calculating $|E_1 \cap E_2|$: If $f(2) = 2$ and $f(4) = 4$, both images are fixed and distinct. The remaining 3 elements of $A$ (i.e., $\{1, 3, 5\}$) must be mapped injectively to the remaining 5 elements of $B$ (i.e., $\{1, 3, 5, 6, 7\}$). $|E_1 \cap E_2| = {}^{5}P_{3} = 5 \times 4 \times 3 = 60$

---

Step 3: Final Computation

Substituting these values into the inclusion-exclusion formula: $|T| = 2520 - 360 - 360 + 60 = 1860$

Thus, the number of elements in the set $T$ is 1860.