Bijections, and why on a finite set either half implies the other

What to assume they know

• What one-one asks of distinct inputs, and what many-one allows — one-one and many-one, and how each is proved
• Onto as the demand that nothing in the codomain be left unhit — onto, range against co-domain, and how each is proved
• Parity of a natural number, and writing an even number as twice something
• Counting arrangements of a small number of distinct symbols
• Ordered pairs and the product of two sets
• Proof by contradiction

What they should be able to do

• State Definition 7 and check both halves separately for a stated function
• Give a function on the naturals that is one-one and not onto, and another that is onto and not one-one, and say what each shows
• Reproduce the counting argument that an onto map of a three-element set to itself must be one-one, and the argument in the other direction
• Extend both arguments to an arbitrary finite set and state the resulting equivalence in the chapter's own terms
• Explain exactly which step of the counting argument fails for an infinite set
• Exhibit a bijection between two different sets and verify both halves
• Use the finite-set equivalence to count the onto maps of a finite set to itself without listing them

Where it usually goes wrong

• "One-one and onto are two names for the same idea." Examples 8 and 10 sit one page apart on the same set precisely to refute this. One has each half without the other.
• "If a function is one-one it must be onto, because it uses up its inputs." True for a finite set mapped to itself, false in general. Doubling on the naturals is the counterexample and the chapter puts it on Part I p. 8 for exactly this reason.
• "The finite-set result holds for any function, so I can apply it whenever the domain is finite." The chapter states it for a function from a set to itself. Exercise 1.2 Q6 puts an injective map from a three-element set into a four-element one, and it is not onto; the sizes have to match. If the explanation states the equal-size generalisation it must say the generalisation is being supplied.
• "An infinite set can be put into one-one correspondence with a smaller infinite set, which is a paradox." It is not a paradox; it is what the word infinite is doing. The chapter says as much when it calls the failure of the equivalence characteristic of infinite sets.
• "Bijective is a third property beyond one-one and onto." It is a name for holding both, and every proof of bijectivity in the chapter is two proofs written one after the other.
• "Counting one-one maps and counting onto maps are different problems." On a finite set mapped to itself they are the same problem, which is the whole point of Miscellaneous Exercise Q4. A student who starts inclusion-and-exclusion on that question has missed the theorem sitting five pages earlier.
• "Example 13's contradiction shows the function has at most two outputs, so the co-domain has two elements." The co-domain has three; the range would have at most two. Confusing the two is what makes the proof feel like a trick.

Questions to check understanding

• Show that a stated function is bijective by proving each half separately
• Decide whether a stated function is bijective and justify the verdict — the form of Exercise 1.2 Q9
• Choose the correct classification of a function from four options
• Show a function between two different sets is bijective — the form of Exercise 1.2 Q8
• Count the one-one, or the onto, functions from a finite set to itself
• Explain why an implication that holds on a finite set fails on an infinite one, giving the counterexample

Examples worth working on the board

Values marked verified are worked out here on the chapter's own data; no answer key was consulted, and the chapter prints no answers to its exercises.

• Definition 7 and Fig 1.2 panel (iv) (Part I p. 8). The definition asks for both properties at once and offers bijective as a one-word alternative. Read off the page image, panel (iv) has a source holding 1, 2, 3, 4 and a target holding a, b, c, d, with the arrows running 1 to b, 2 to c, 3 to a and 4 to d. Verified: four distinct arrowheads on four target elements, so both demands hold and this is the only panel of the four that qualifies. The chapter says the same on p. 8.
• The two independence witnesses, both on N (Part I pp. 8–9). Example 8 sends x to 2x and is one-one without being onto; Example 10 sends 1 and 2 both to 1 and every x above 2 to x – 1, and is onto without being one-one. Verified: the doubling map misses every odd natural; the folding map is collides at 1 and 2, yet reaches every natural, since y + 1 exceeds 2 and maps to y for any y above 1. Both witnesses live on the same infinite set, which is exactly what makes them the right pair for section 7.
• Example 13 (Part I p. 10). An onto function from {1, 2, 3} to itself must be one-one. The chapter argues by contradiction: suppose two of the three inputs collided; the third input has one image; so the outputs number at most two, which cannot cover a three-element co-domain.
• Example 14 (Part I p. 10). An injective map of {1, 2, 3} to itself has to be onto. The chapter's argument is direct: three inputs go to three distinct outputs, and three distinct elements of a three-element set are all of it.
• The general counting argument to supply (not in the book; the chapter states the general result as a Remark without repeating the proof). Let X be finite with n elements. If f from X to X is one-one, its outputs are n distinct elements of a set that has only n, so they are all of X and f is onto. If f is onto, then every one of the n elements of X is an output, so at least n distinct outputs are used; only n inputs are available; so no two inputs can share an output and f is one-one. Both halves rest on the same fact — that a finite set holding n elements cannot also hold n distinct elements that leave any of it out — and this is the pigeonhole principle wearing two hats.
• The Remark (Part I p. 10). The chapter records that the results of Examples 13 and 14 hold for any finite set, points back to Examples 8 and 10 as the infinite counterexamples, and states that this difference is characteristic of finiteness. The Summary on p. 16 repeats the statement in a single bullet, phrased as an if-and-only-if. This is the most conditional claim in the chapter and must not be flattened — the equivalence holds for a finite set and for no infinite one.
• Where the argument fails on an infinite set (not in the book). The counting step says n distinct outputs inside a set of size n exhaust it. On N the doubling map produces infinitely many distinct outputs inside an infinite set and still misses half of it, because "as many as" carries no information when the count is not a number. Section 6 should show this concretely: pair each natural with its double and observe that the pairing never runs out on either side.
• Example 12 (Part I pp. 9–10). f from N to N sends an odd x to x + 1 and an even x to x – 1; the chapter proves both halves. Its onto argument names the input for each kind of target: an odd target 2r + 1 comes from 2r + 2, and an even target 2r comes from 2r – 1. Verified: the function exchanges 1 with 2, 3 with 4, 5 with 6 and so on, so it is a bijection of an infinite set that can be drawn in full — and applying it twice returns every input unchanged, which is worth a single line here and is taken up properly in Invertibility as a two-sided undo, and why bijective is exactly the condition.
• Exercise 1.2 Q8 (Part I p. 11). For sets A and B, the function from A × B to B × A that swaps the two entries of a pair is bijective. Verified: if two swapped pairs are equal then their entries match slot by slot, so the originals were equal; and any pair of B × A is the swap of the corresponding pair of A × B. This is the chapter's only bijection between two different sets, and it is the one that explains why the two products have the same size.
• Exercise 1.2 Q9 (Part I p. 11). f from N to N sends an odd n to half of n + 1 and an even n to half of n; the question asks whether f is bijective, with justification. Verified: it is not. 1 and 2 both map to 1, so the injective half fails. The onto half holds — any natural m is the image of 2m. So this is a third witness of the same shape as Example 10, arriving in the exercise where the student has to find the collision themselves.
• Exercise 1.2 Q11 and Q12 (Part I p. 11). Two multiple-choice items on functions from R to R: the fourth power, and tripling. Verified: the fourth power collides at 1 and –1 and misses every negative, so it is neither; tripling is one-one and onto, so it is bijective and the correct option says so.
• Exercise 1.2 Q10 (Part I p. 11). The reals with 3 removed, to the reals with 1 removed, sending x to the quotient of x – 2 by x – 3. Verified: both halves hold, so this is a bijection, and it is the chapter's best example of a bijection manufactured by removing exactly one point from each side.
• Miscellaneous Example 22 (Part I p. 14). Every injective map of {1, 2, 3} onto itself is a rearrangement of the three symbols, so they number 3 factorial, that is 6.
• Miscellaneous Exercise Q4 (Part I p. 15). Count the onto functions from {1, 2, 3, ..., n} to itself. Verified: by the Remark on p. 10, an onto map of a finite set to itself is one-one, so the onto maps are exactly the one-one maps, and those are the rearrangements of n symbols — n factorial of them. This is the exercise that is answered by the theorem rather than by counting, and it is the single best argument for why sections 3 to 5 are worth their runtime. For n = 3 it agrees with the six of Miscellaneous Example 22.
• Miscellaneous Exercise Q1 and Q2 (Part I p. 15). A bijection from R onto the open interval between –1 and 1, and the injectivity of cubing on R. Use them as after-the-fact practice; the first is worked in Onto as the demand that nothing in the codomain be left unhit.

Figures to have open

• A redraw of Fig 1.2 panel (iv) (Part I p. 8) with the arrows exactly as listed, since it is the only bijection in the chapter's own diagrams.
• A box of four slots being filled one at a time, for section 3. An added device and the visual carrier of the counting argument.
• A strip of the naturals drawn twice — once with each element joined to its double, once with consecutive elements joined in pairs. Carries sections 6 and 8. Standard schematic.
• A side-by-side of the doubling and folding maps as arrow diagrams over the first six or eight naturals, for section 7. The chapter states both functions and draws neither.

Where this sits in the book

• NCERT Class 12 Mathematics, Part I, Chapter 1 "Relations and Functions", §1.3 Types of Functions, Definition 7, p. 8
• Fig 1.2 panel (iv), p. 8; Examples 8 and 10, pp. 8–9
• Examples 12, 13 and 14 and the Remark that follows them, pp. 9–10
• Exercise 1.2, questions 8, 9, 10, 11 and 12, p. 11
• Miscellaneous Example 22, p. 14, and Miscellaneous Exercise questions 1, 2 and 4, p. 15
• The Summary's bullet naming this equivalence as what marks a finite set out, p. 16