Example 12: Swapping neighbours on $\N$ is bijective

Basics you need

Solution

1. Check the outputs lie in $\N$⁠, and note their parity

   • If $x$ is odd, $f(x) = x + 1 \ge 2$ is a natural number, and it is even.
   • If $x$ is even, then $x \ge 2$⁠, so $f(x) = x - 1 \ge 1$ is a natural number, and it is odd.

   $x$	1	2	3	4	5	6	7	8
   parity	odd	even	odd	even	odd	even	odd	even
   $f(x)$	2	1	4	3	6	5	8	7

   The check $x - 1 \ge 1$ matters: subtracting 1 from a natural number can give $0 \notin \N$⁠, but only when $x = 1$⁠, and 1 is odd, so it uses the other piece. The parity observation (odd goes to even, even goes to odd) is the key to the one-one proof in the next step.
   The smallest even natural number is 2, so for even $x$ we have $x - 1 \ge 1$⁠.

2. One-one, mixed case: odd $x_1$⁠, even $x_2$ is impossible

   Suppose $f(x_1) = f(x_2)$⁠. First suppose $x_1$ is odd and $x_2$ is even. Then the equation reads

   $$\begin{aligned} x_1 + 1 &= x_2 - 1, \\ \text{that is}\quad x_2 - x_1 &= 2. \end{aligned}$$

   But $x_2 - x_1$ is an even number minus an odd number, which is odd, and 2 is even. An odd number cannot equal 2. So this case cannot happen. The case "$x_1$ even, $x_2$ odd" is ruled out the same way: it gives $x_1 - 1 = x_2 + 1$⁠, so $x_1 - x_2 = 2$⁠, with $x_1 - x_2$ again even minus odd, hence odd.

   The book says only that $x_2 - x_1 = 2$ "is impossible"; the reason is parity. A second way to see it: by Step 1, $f(x_1)$ is even and $f(x_2)$ is odd, and an even number cannot equal an odd number. Either way, when $f(x_1) = f(x_2)$⁠, the inputs $x_1, x_2$ must have the same parity.
   Even minus odd is odd: if $x_2 = 2a$ and $x_1 = 2b + 1$⁠, then $x_2 - x_1 = 2(a - b - 1) + 1$⁠, which is odd.

3. One-one, same-parity cases

   Now the inputs have the same parity, so the same formula applies to both.

   • Both odd: $f(x_1) = f(x_2)$ reads $x_1 + 1 = x_2 + 1$⁠, so $x_1 = x_2$ (subtract 1 from both sides).
   • Both even: $f(x_1) = f(x_2)$ reads $x_1 - 1 = x_2 - 1$⁠, so $x_1 = x_2$ (add 1 to both sides).

   All four parity combinations are covered: the two mixed ones cannot occur, and the two same-parity ones force $x_1 = x_2$⁠. Hence $f$ is one-one.

   Within one piece the function is just a shift ($x \mapsto x + 1$ or $x \mapsto x - 1$⁠), and a shift can be undone, so equal outputs give equal inputs. The danger in a piecewise function is a collision between pieces, which Step 2 excluded. Only after checking both kinds of case is the proof complete.
   Proof by cases: $x_1$ odd or even, $x_2$ odd or even, gives four cases that cover every pair. Basics: proving and disproving

4. Onto: every odd $y$ and every even $y$ has a preimage

   Take an arbitrary $y \in \N$⁠. It is odd or even.

   • $y$ odd, say $y = 2r + 1$ with $r \ge 0$⁠. Choose $x = 2r + 2$⁠. This is an even natural number, so the second piece applies: $f(2r + 2) = (2r + 2) - 1$⁠, which is $2r + 1 = y$⁠. ✓
   • $y$ even, say $y = 2r$ with $r \ge 1$⁠. Choose $x = 2r - 1$⁠. This is an odd natural number (it is at least 1), so the first piece applies: $f(2r - 1) = (2r - 1) + 1$⁠, which is $2r = y$⁠. ✓

   Every $y \in \N$ is an image, so $f$ is onto.

   Because $f$ swaps neighbours, the preimage of $y$ is simply its partner: $y + 1$ if $y$ is odd, $y - 1$ if $y$ is even. For each candidate we checked three things: it is in $\N$⁠, it has the parity that selects the formula we used, and the formula really gives $y$⁠. The condition $r \ge 1$ for even $y$ guarantees $2r - 1 \ge 1$⁠.
   For onto, take an arbitrary $y$⁠, construct $x$⁠, and verify both $x \in$ domain and $f(x) = y$⁠. Basics: one-one and onto

5. Conclude: $f$ is a bijection, and its own inverse

   $f$ is one-one (Steps 2 and 3) and onto (Step 4), so $f$ is both one-one and onto (bijective).

   A bonus fact: applying $f$ twice returns every number to itself. If $x$ is odd, $f(x) = x + 1$ is even, so $f(f(x)) = (x + 1) - 1 = x$⁠. If $x$ is even, $f(x) = x - 1$ is odd, so $f(f(x)) = (x - 1) + 1 = x$⁠. So $f$ undoes itself, which is another way to see that it is a bijection.

   If $f(f(x)) = x$ for every $x$⁠, then $f(x_1) = f(x_2)$ gives $x_1 = f(f(x_1)) = f(f(x_2)) = x_2$ (one-one), and every $y$ equals $f(f(y))$⁠, the image of $f(y)$ (onto). This idea becomes the inverse function in Section 1.4.

Every fact used, and where it comes from