Competency-Based Questions (CBQ) · Question 73 of 80
A depot numbers its storage bins with the natural numbers N = 1, 2, 3, … .
Question 731 markHard
A depot numbers its storage bins with the natural numbers N={1,2,3,…}. A relabelling scheme is any function from N to N: bin n gets the new label h(n). The manager wants to know how badly a relabelling can behave on an infinite stock of bins.
Given below are two statements, one labelled Assertion and the other labelled Reason. Choose the option that correctly describes them.
Assertion: There is a function f:N→N which is one-one, is not onto, and whose range misses infinitely many natural numbers; and there is a function g:N→N which is onto and for which every natural number has exactly two preimages.
Reason: For every finite set X and every function h:X→X, if h is onto then h is one-one.
(A) Assertion is correct, reason is correct; reason is a correct explanation for assertion.
(B) Assertion is correct, reason is correct; reason is not a correct explanation for assertion.
(C) Assertion is correct, reason is incorrect.
(D) Assertion is incorrect, reason is correct.
Answer: (B) Assertion is correct, reason is correct; reason is not a correct explanation for assertion.
Explanation:
The Assertion asks for two constructions. Neither can be settled by quoting a rule; each has to be built and checked.
Step 1 — Build f and verify all three demands.
Take f(n)=3n.
One-one:f(n1)=f(n2)⇒3n1=3n2⇒n1=n2, dividing by 3.
Not onto:f(n)=4 would need n=34, which is not a natural number, so 4 has no preimage.
Misses infinitely many: the range of f is {3,6,9,12,…}, the multiples of 3. Any y that is not a multiple of 3 is missed, because 3n=y would force 3 to divide y. The missed set therefore contains 1,2,4,5,7,8,… — every natural number leaving remainder 1 or 2 on division by 3 — and that is an infinite set.
So the first half of the Assertion holds.
Step 2 — Build g, which is the harder demand.
A function that is onto with exactly two preimages everywhere must pair up the domain: the inputs must split into pairs, one pair per target. Halving suggests itself, with the two members of each pair being consecutive. Define
g(n)=⎩⎨⎧2n+1,2n,n oddn even
First check g really lands in N: if n is odd then n+1 is even so 2n+1 is a whole number, and it is at least 1 (taking n=1 gives 1); if n is even then 2n is a whole number and at least 1. Good.
The first few values:
n
1
2
3
4
5
6
7
8
g(n)
1
1
2
2
3
3
4
4
Exactly two preimages of each m∈N. Solve g(n)=m in the two cases.
n odd: 2n+1=m⇒n=2m−1. Since m≥1, 2m−1≥1, and 2m−1 is odd, so this is a valid solution.
n even: 2n=m⇒n=2m, which is even and at least 2, also valid.
These are the only solutions, and 2m−1=2m, so each m has exactly the two preimages 2m−1 and 2m — no more, no fewer.
Onto: each m has a preimage (two, in fact), so g is onto. It is of course badly many-one.
So the second half holds, and the Assertion is correct.
Step 3 — Test the Reason.
Let X be finite with ∣X∣=k, and let h:X→X be onto. Then all k elements of X appear as outputs. Those outputs are produced by only k inputs. If two inputs shared an output, the k inputs would yield at most k−1 distinct outputs, so some element of X would be missed — contradicting onto. Hence no two inputs collide, and h is one-one. The Reason is correct. (It is the finite-set property, and it is stated with the word finite present, which is what makes it true.)
Step 4 — Does the Reason explain the Assertion? No.
The Reason is a statement about finite sets. The Assertion is a statement about N, which is infinite. A true theorem about finite sets provides no evidence at all about an infinite one — and here it does not even point in the right direction: the Reason says onto forces one-one, while the Assertion's g is onto and spectacularly not one-one. Whatever the Reason establishes, it cannot establish the existence of f or of g; only the explicit constructions of Steps 1 and 2 do that.
So the answer is (B).
What the pair of statements really shows together. Read side by side, they mark the boundary between finite and infinite.
Setting
one-one ⇒ onto?
onto ⇒ one-one?
X finite, h:X→X
yes
yes
N, maps N→N
no — f(n)=3n
no — g above
This is not a flaw in the definitions; it is the characteristic difference between a finite and an infinite set. A common error is to treat the finite result as a general rule, then conclude that no function like g can exist. The right move is to notice the hypothesis and check whether it applies.
The two arrow diagrams show it directly. On the left, f sends the bins only to the multiples of 3 (1→3, 2→6, …), so labels such as 1,2,4,5 on the right receive nothing. On the right, g sends the bins in consecutive pairs onto each label, so every label receives exactly two arrows and none is missed.