Why can the old store's row count be the new store's row count only when the remapping between them is a bijection?

## Sizes are compared by maps, not by counting For small finite sets you can count both sides and compare. The general tool, and the one an interviewer is probing, is the map between them. Three statements carry all of it. | What you can exhibit from A to B | What it proves | Reading it in the migration | |---|---|---| | An injection | size of A is at most size of B | Distinct old rows land on distinct new rows, so the new store holds at least as many | | A surjection | size of A is at least size of B | Every new row has at least one old source, so the old store holds at least as many | | A bijection | the two sizes are equal | Each old row pairs with exactly one new row and vice versa; either count answers for both | The inequalities point in opposite directions because they constrain opposite ends. Injectivity forbids two inputs from sharing an output, so outputs cannot run short. Surjectivity forbids an output from going unclaimed, so inputs cannot run short. Neither alone gives you equality, and asserting equality from one of them is the defect this question is built to catch. ## The reconciliation step, restated Comparing row counts after a migration is not a sanity check bolted on at the end; it is the test of exactly these two properties. When the counts disagree, the direction of the disagreement tells you which property failed: 1. **The new store holds fewer rows.** Injectivity is gone somewhere: two or more old rows collapsed onto one. The old count is now an upper bound, and the gap is the number of collisions. 2. **The new store holds more rows.** Some new rows have no old source — records created after the cutover, a backfill, or a row split into several. The remap is not surjective onto the live set, and the old count is a lower bound. 3. **The counts match but the contents do not.** Two errors in opposite directions cancelled: a merge and a stray insert of equal size. This is why matching totals are weak evidence on their own, and why a comparison keyed on the identifiers beats a comparison of cardinalities. ## Counting by bijection as a technique The same idea works far outside migrations. When a set is awkward to enumerate, pair it exactly with one that is easy and count the easy one. Two conditions make the argument sound, and both are routinely fudged: - The pairing must be **defined on every element** of the hard set, not just the ones you looked at. - It must be **exact in both directions** — one partner each way. A correspondence that is merely "roughly one to one" proves nothing, and a correspondence that is one-to-one but leaves partners spare proves an inequality only. A common variant that is genuinely useful in review: to show a de-duplicated export has exactly as many rows as there are accounts, do not count both and compare. Exhibit the pairing — each exported row names one account, each account appears exactly once — and the equality follows without either count being trusted. ## Why the pairing, not the counting, is the definition For finite sets a bijection is a convenience. For infinite ones it is the **definition** of having the same size, and that is where intuition breaks in a way worth knowing about. Under this definition a proper subset can have the same size as the whole: the even positive integers pair off with all the positive integers (double each one), so the two sets are the same size even though one sits strictly inside the other. Nothing is wrong; it is simply that "strictly contains" and "is bigger than" stop coinciding once the sets are infinite, and the pairing is the notion that survives. That is also the bridge to the next question in this material: if a pairing with the positive integers is what "countable" means, then a set for which no such pairing can exist is genuinely, structurally larger — not merely large. ## Where the argument silently fails in practice - **Claiming equality from an injection.** The most common error. You have an upper bound; say so. - **Counting against a moving target.** A live store changes under the query, so both counts must come from a consistent snapshot or the comparison is noise. - **Pairing the wrong sets.** Comparing all old rows against non-deleted new rows, or including soft-deleted records on one side only, produces an honest count of the wrong thing. - **Trusting equal totals.** Equal cardinalities are consistent with a merge and an unrelated insert of the same size, so where the stakes justify it, reconcile on identifiers rather than on totals.