Matching two sets one to one

Matching two finite families without counting them

Let S = \{1, 2, 3, 4, 5, 6\}. Show that the set of 2-member subsets of S and the set of 4-member subsets of S have the same size, without listing either.

Send each 2-member subset X to its complement c(X) = S \setminus X. Removing 2 members from the 6 in S leaves 4, so c(X) is a 4-member subset and c is a function between the two families. Taking the complement twice gives back the set you started with: S \setminus (S \setminus X) = X.

Proof that c is a bijection. Injective: if c(X) = c(Y), take complements of both sides to get X = Y. Surjective: for a 4-member subset Z, the set S \setminus Z has 2 members and c(S \setminus Z) = Z. \square

By Result 1 the counts agree, and indeed \binom{6}{2} = \binom{6}{4} = 15.

The natural numbers and the even natural numbers

Prove that \lvert \mathbb{N} \rvert = \lvert E \rvert, where E = \{0, 2, 4, \dots\} is the set of even natural numbers.

Use the matching of Figure 1, f : \mathbb{N} \to E, f(n) = 2n, which lands in E.

Proof. Injective: if 2a = 2b, dividing by 2 gives a = b. Surjective: a member m of E is even, so m = 2k for some integer k, and k \ge 0 because m \ge 0. Then k \in \mathbb{N} and f(k) = m. \square

So \mathbb{N} is the same size as its proper subset E.

A full hotel takes one more guest

A hotel has one room for each natural number, numbered 0, 1, 2, \dots, and every room is occupied. Mizuki arrives and asks for a room. Show that everyone can be housed, one guest to a room, and conclude that \mathbb{N} is infinite.

Ask each guest to move from room n to room n + 1. This is the function s : \mathbb{N} \to \mathbb{N} \setminus \{0\}, s(n) = n + 1, and n + 1 \ge 1, so every guest lands in a room other than 0.

Proof that s is a bijection. Injective: if a + 1 = b + 1 then a = b, so no two guests share a room. Surjective: each room m \ge 1 receives the guest from room m - 1, which is a natural number. \square

Room 0 is free for Mizuki. So \lvert \mathbb{N} \rvert = \lvert \mathbb{N} \setminus \{0\} \rvert, and by Result 3 the set \mathbb{N} is infinite. A hotel with 50 full rooms cannot do this: 50 guests moved into the 49 rooms numbered 1 to 49 would put two in one room.

Any two closed intervals

Show that \lvert [0, 1] \rvert = \lvert [0, 5] \rvert, and more generally that \lvert [a, b] \rvert = \lvert [c, d] \rvert whenever a < b and c < d.

The map x \mapsto 5x stretches [0, 1] onto [0, 5]. In general, slide and stretch:

Proof. Into [c, d]: if a \le x \le b then \displaystyle 0 \le \frac{x - a}{b - a} \le 1, and multiplying by d - c > 0 and adding c gives c \le g(x) \le d. Injective: if g(x_1) = g(x_2) then \displaystyle \frac{d - c}{b - a}(x_1 - x_2) = 0, and the factor \displaystyle \frac{d - c}{b - a} is not zero, so x_1 = x_2. Surjective: given y \in [c, d], solve g(x) = y to get

As before \displaystyle 0 \le \frac{y - c}{d - c} \le 1, so a \le x \le b, and substituting gives g(x) = c + (y - c) = y. \square

With a = 0, b = 1, c = 0, d = 5 the formula is g(x) = 5x. Size by matching is not length.

A bounded interval and an unbounded one

Prove that \lvert (0, 1) \rvert = \lvert (0, \infty) \rvert.

As x falls toward 0, \displaystyle \frac{1}{x} grows without bound, which suggests \varphi : (0, 1) \to (0, \infty), \displaystyle \varphi(x) = \frac{1}{x} - 1.

Proof. Into: if 0 < x < 1 then \displaystyle \frac{1}{x} > 1, so \varphi(x) > 0. Injective: if \displaystyle \frac{1}{x_1} - 1 = \frac{1}{x_2} - 1 then \displaystyle \frac{1}{x_1} = \frac{1}{x_2}, so x_1 = x_2. Surjective: given t > 0, put \displaystyle x = \frac{1}{1 + t}. Since 1 + t > 1, we have 0 < x < 1, and \varphi(x) = (1 + t) - 1 = t. \square

The open interval and the whole line

Prove that \lvert (0, 1) \rvert = \lvert \mathbb{R} \rvert, and give one explicit bijection (0, 1) \to \mathbb{R}.

By Example 5 and transitivity (Result 2) it is enough to match (0, \infty) with \mathbb{R}. Try k : (0, \infty) \to \mathbb{R}, \displaystyle k(t) = t - \frac{1}{t}.

Proof that k is a bijection. Fix y \in \mathbb{R}. For t > 0, multiplying by t (allowed both ways, since t \neq 0) shows

The discriminant is y^2 + 4 > 0, so there are two real roots, and their product is -1, so one is positive and one is negative. Hence exactly one t > 0 has k(t) = y, namely \displaystyle t = \frac{y + \sqrt{y^2 + 4}}{2}. At least one such t for every y makes k surjective; at most one makes it injective. \square

So \lvert (0, 1) \rvert = \lvert (0, \infty) \rvert and \lvert (0, \infty) \rvert = \lvert \mathbb{R} \rvert, and transitivity gives \lvert (0, 1) \rvert = \lvert \mathbb{R} \rvert. The composite k \circ \varphi is an explicit bijection, and with \displaystyle \varphi(x) = \frac{1 - x}{x},

Check: \displaystyle x = \frac{1}{2} goes to 0, and \displaystyle x = \frac{1}{3} goes to \displaystyle \frac{1/3}{2/9} = \frac{3}{2} = k(2), with \displaystyle \varphi(\frac{1}{3}) = 2.

Removing one endpoint

Prove that \lvert [0, \infty) \rvert = \lvert (0, \infty) \rvert, and conclude that \lvert [0, \infty) \rvert = \lvert \mathbb{R} \rvert.

Run the hotel of Example 3 on the natural numbers inside [0, \infty) and leave every other point where it is:

Proof. Into: for x \in \mathbb{N}, h(x) \ge 1 > 0; for x \notin \mathbb{N} with x \ge 0, we have x \neq 0, so h(x) = x > 0. Injective, by cases: if x, y \in \mathbb{N} then x + 1 = y + 1 gives x = y; if neither is in \mathbb{N} then h(x) = h(y) says x = y; if x \in \mathbb{N} and y \notin \mathbb{N}, then h(x) \in \mathbb{N} and h(y) = y \notin \mathbb{N}, so h(x) \neq h(y). Surjective: let y > 0. If y \in \mathbb{N} then y \ge 1 and y - 1 \in \mathbb{N} has h(y - 1) = y. If y \notin \mathbb{N} then h(y) = y. \square

With Example 6, transitivity gives \lvert [0, \infty) \rvert = \lvert \mathbb{R} \rvert.