Sets, Relations & Functions
Idempotent functions
Grade 11
Question:
<p>The number of functions \(f: S \to S\), where \(S = \{1, 2, 3\}\), such that \(f[f(x)] = f(x)\) for all \(x \in S\) is:</p>
<p>7</p>
<p>8</p>
<p>9</p>
<p>10</p>
Step-by-Step Solution
Key Concept: The condition f[f(x)] = f(x) means every element in the range of f must be a fixed point of f. This severely restricts which functions are valid—the range can only contain elements that map to themselves.
<p><strong>Step 1: Interpret the condition</strong></p><p>The condition f[f(x)] = f(x) for all x ∈ S means that f(x) is a fixed point for every x. In other words, if y is in the range of f, then f(y) = y.</p><p><strong>Step 2: Identify constraints on range</strong></p><p>Let R = range of f. For every y ∈ R, we must have f(y) = y. The set R must be a non-empty subset of S where all elements are fixed points.</p><p><strong>Step 3: Count by cases based on |R|</strong></p><p><strong>Case 1: |R| = 1</strong> (single fixed point)</p><p>Choose 1 element from S to be the fixed point: C(3,1) = 3 ways. All elements of S map to this fixed point: 1 way per choice. Total: 3 functions.</p><p><strong>Case 2: |R| = 2</strong> (two fixed points)</p><p>Choose 2 elements from S to be fixed points: C(3,2) = 3 ways. These 2 elements must map to themselves. The remaining element can map to either of the 2 fixed points: 2 ways. Total: 3 × 2 = 6 functions.</p><p><strong>Case 3: |R| = 3</strong> (all three are fixed points)</p><p>All elements map to themselves (identity function): 1 way.</p><p><strong>Step 4: Add all cases</strong></p><p>Total = 3 + 6 + 1 = <strong>10</strong></p><p>∴ Answer: B</p>
Correct Answer: B