Try
Imagine a set A that already contains distinct objects a₀,a₁,a₂,… . There may be many other objects in A as well. Now add a separate collection b₀,b₁,b₂,… . Can every old and new object receive a different destination in A, with every destination used?
For finite sets, adding new elements increases cardinality. Here an infinite sequence of existing destinations lets us rearrange assignments. The objective is not to fit infinitely many objects into finitely many places: A already contains infinitely many places. We must give a precise bijection, not appeal to a picture of endless empty space.
Assume throughout that N starts at zero, the a entries are pairwise distinct, and the b entries are pairwise distinct and outside A. If the new collection contains copies of old objects, attach tags first so the copies really are different elements. The sequence is supplied data; it need not enumerate all of A.
Predict
Try sending every old aₙ to aₙ₊₁ and every new bₙ to a₀. This creates a collision among the new objects. Sending bₙ to aₙ while leaving old objects fixed also creates collisions. Predict a division of the existing sequence into two infinite, disjoint sets of destinations.
Even and odd indices provide such a division. Before continuing, write where a₃ and b₃ should go. Then identify the input that should reach destination a₉. What should happen to an old object outside the supplied sequence?
Experiment
Use the rule aₙ→a₂ₙ, bₙ→a₂ₙ₊₁, and fix every other element of A. “Fix” means map that element to itself. The table is a finite window into a formula defined for every nonnegative integer, not a finite verification of the whole theorem.
| Index n | Old input | Its destination | Added input | Its destination |
|---|
| 0 | a₀ | a₀ | b₀ | a₁ |
| 1 | a₁ | a₂ | b₁ | a₃ |
| 2 | a₂ | a₄ | b₂ | a₅ |
| 3 | a₃ | a₆ | b₃ | a₇ |
| 4 | a₄ | a₈ | b₄ | a₉ |
| Any x outside the a sequence | x | x | not an added element | not applicable |
Read the table backward as well as forward. Destination a₉ comes from b₄, not b₃. Destination a₆ comes from a₃. A destination outside the sequence comes from itself. Those backward rules are the key to proving that no destination is omitted and none is used twice.
For a concrete instance, take A to be the real numbers and aₙ=n. Keep every negative real and every noninteger real fixed. Move the nonnegative integer inputs to the even integers, and send the added b entries to odd integers. This does not enumerate the real numbers: all the other reals are simply handled by the identity case.
Understand
Write S for the set of all aₙ. The input domain splits into three disjoint pieces: S, the added collection B, and A outside S. Our rule gives one value on each piece, so it is well defined. Pairwise distinctness ensures that an element of S has exactly one index.
Define the inverse on A as follows. Send a₂ₙ back to aₙ, send a₂ₙ₊₁ back to bₙ, and fix points outside S. Every index is uniquely even or odd, and points outside S belong to neither indexed case. Thus the inverse is also well defined and covers its whole domain. Applying forward then backward returns each input in all three cases; applying backward then forward returns each target. These two checks prove bijectivity.
For finitely many new elements c₀ through cₘ₋₁, there is a simpler shift. Put cⱼ into destination aⱼ for the first m positions, move aₙ to aₙ₊ₘ, and fix the rest of A. The inverse sends an initial position back to its new element and subtracts m from every later sequence index. No objects are “pushed off the end”: every index n+m remains a finite natural number and names an existing element.
This also repairs interval endpoints. To map [0,1) onto (0,1), use aₙ=1/(n+2). Send 0 to a₀=1/2, send aₙ to aₙ₊₁, and fix all other interior points. The inverse sends 1/2 to 0, sends aₙ₊₁ to aₙ and fixes everything else. All images are strictly positive and below one. Although the chain approaches zero, zero is not one of its destinations. Limits of sequences and membership in their ranges are different questions.
There is a foundational assumption here. We proved absorption given an injection from N into A. We did not prove that every infinite set comes equipped with one. Under usual choice-based foundations such a sequence can be obtained; in a choice-free development that step needs a separate justification or an explicit hypothesis. Even with choice, enumerating every element of an arbitrary infinite A is a much stronger and generally false assertion. Our proof avoids that assertion entirely. Explicit sequences such as n in the reals need no arbitrary selection process.
Apply
Map the interval (0,1] onto (0,1) by absorbing its extra endpoint 1. Choose the distinct interior sequence cₙ=1−1/(n+2). Write the forward and inverse maps completely. Find the images of 1, 1/2, 3/4 and 1/3 before opening the check.
Check the endpoint shift
Send 1 to c₀=1/2 and cₙ to cₙ₊₁, fixing interior points outside this sequence. Thus 1/2 goes to 2/3, 3/4=c₂ goes to c₃=4/5, and 1/3 stays fixed. The inverse sends c₀ to 1, sends cₙ₊₁ to cₙ and fixes other interior points. The sequence approaches 1 but never contains it, so the endpoint input does not collide with an indexed input. These cases prove the bijection rather than merely matching four examples.
Now distinguish ordinary and tagged unions. If A and B are both N as actual sets, their union is just N. A rule assigning two different outputs to n depending on whether you “regard” it as old or new is not a function. Tags such as (n,old) and (n,new) resolve that ambiguity. For an ordinary overlapping union, first identify which members of B are genuinely outside A; only those need new destinations.
Continue
Return to finite descriptions and countable encodings for examples of explicit enumerations and decoding. In the practice, give both directions of the proposed bijection and account for untouched elements. The two-endpoint problem requires disjoint shift chains, while the overlapping-union problem requires removing shared members before defining cases. A cardinality argument succeeds because its map is defined, injective and onto—not because its notation contains an ellipsis.
