STRATEGIES FOR THINKING UP BIJECTIONS BETWEEN EQUINUMEROUS SETS
I'll answer your final question first, then give my own answers to Parts (a) through (d) together with a little clarifying explanation. To come up with these functions yourself ex nihilo, for example on a test or whatever, I'd suggest the following two strategies.
Visualize: Imagine the $xy$-plane, with the two sets you want to think of a bijection for along the $x$-axis and $y$-axis. Then, think about the shapes of some bijective functions you already know, and ask yourself if their domain and range match your sets, or if you could maybe make a minor adjustment or two to get them to match.
- For example, maybe you want to show $(-\infty, \infty) \sim (0, \infty)$; that is, that the set of all real numbers is equinumerous to the set of strictly positive real numbers. You could try to build some complicated bijection yourself... or, you could just use the function $f(x) = \mathrm{e}^x$ which is a bijection from $(-\infty, \infty)$ to $(0, \infty)$.
- As another example, what function could you use to show $(0, 1) \sim (-\infty, \infty)$? Perhaps you remember that (a section of) the function $f(x) = \tan(x)$ has the right basic shape. But the tangent function has asymptotes at $x \in \{..., -\tfrac{3\pi}{2}, -\tfrac{\pi}{2}, \tfrac{\pi}{2}, \tfrac{3\pi}{2}, ...\}$; you need to shift and stretch it so that instead there are asymptotes at $x \in \{..., -1, 0, 1, 2, ...\}$. Use $f(x) = \tan(\pi(x-\tfrac{1}{2}))$; when defined only on $0<x<1$ this function is a bijection between these two intervals.
- One more item of note: if you are trying to think of common functions you've come across before, such as logarithms, exponentials, trigonometric functions, polynomials, etc., then most likely, you will be envisioning continuous functioins. And the only continuous functions that are also bijections, are also strictly monotone - in other words, they go only up or only down, with no flat sections. Don't bother with functions like parabolas, cosines, etc. that don't have this property as they will not be bijective.
Use Infinity: Sometimes, try though you might, you won't be able to visualize a bijective function for two equinumerous sets, and sometimes, it won't even be possible to do so. In these cases, your best bet is to lean on the strange properties of infinity to build a function (often piecewise) that does what you need. This is the strategy that I will use in Parts (a) - (d).
- Let's think a bit more about what Part (a) is asking. It wants us to show that the intervals $(0, 1]$ and $(0, 1)$ have the same "number" (well, in a loose sense) of elements in them. This is counterintuitive, though, because $(0, 1] = (0, 1) \cup \{1\}$, i.e. is literally just the exact same set as $(0, 1)$, plus one additional point, $\{1\}$. How can two sets possibly have the same number of elements while one also has 1 more element than the other? The answer comes in realizing that this is only possible with infinite sets like these. In fact, we might even think of Part (a) as the "set-based" version of the idea that adding one or any other finite value does not change infinity: $\infty + 1 = \infty$.
- Understanding the deep connections between sets, cardinality/equinumerosity, and infinity, will help you realize how to construct bijections that show two intervals to be equinumerous. For example, in Part (a), we realize that we are doing a form of $\infty + 1 = \infty$. We start building our bijection, by mapping the endpoint $1 \mapsto 1/2$. But now that means we need something for $1/2$ to map to, so we map $1/2 \mapsto 1/4$. Now the same thing is true of $1/4$, so we map $1/4 \mapsto 1/8$, and so on.
- If these were finite sets, we'd never be able to get away with this: these numbers would just keep shoving each other out of the way like dominos, and in the end, no matter how clever we were, we wouldn't be able to get around the fact that two finite sets can't be equinumerous if one has 1 more element than the other. But they're not finite - they're infinite. We can stick an extra ${1}$ in one end, and using the geometric series $(1, 1/2, 1/4, 1/8, ...)$ as nothing more really than a formality to keep some kind of consistent track of how we're adjusting our bijection, we can show that nothing comes out the other end... the extra point gets absorbed "into infinity", in a sense.
- Using a geometric series of powers of 2 is surely convenient: it's a way to build a bijective function by creating a finite number of "extra spaces" in an infinite set, and it's a good example of the "using infinity" strategy as a whole. Sometimes, though, there are other considerations that come into play. For example, let's say you want to show that $(0, 1) \sim (0, 2)$. It feels like $(0, 2)$ should have "twice as many" points as $(0, 1)$, but in fact this is not true: the function $f(x) = 2x$ is a very simple bijection from $(0, 1) \to (0, 2)$ which serves to show that indeed these two sets are equinumerous.
Combine: Suppose $f : A\to B$ is a bijection, and $g : B\to C$ is also a bijection. Then their composition, $g\circ f: A\to C$, is also a bijection. To compose two functions $f, g$ just means to chain them, such that the first one's codomain is the second one's domain. In other words, the composition is defined by $(g\circ f)(x) = g(f(x))$. This is very useful, because it allows us to construct a bijection between two sets, by breaking it up into steps and using intermediate sets.
- For example, suppose you want to show $(0, 1] \sim (0, 2)$. You could construct some new function from scratch, say, perhaps using a geometric series. Or, alternatively, you could show this in two steps: 1st, by using $f$ from Part (a) to show $(0, 1] \sim (0, 1)$, and 2nd, by taking $g : (0, 1) \to (0, 2)$ defined by $g(x)=2x$. Because $f, g$ are both bijections, with the codomain of $f$ equal to the domain of $g$, then the function $h(x) = g(f(x))$ a.k.a. $h = g\circ f$ will be a bijection from the domain of $f$ to the codomain of $g$. By using composition, we can often skip the work of building minor variations on the same function over & over again.
ANSWERS TO PARTS (a) THROUGH (d)
Part (a): Take the function $f : (0, 1] \to (0, 1)$ defined by
$$
f(x) =
\begin{cases}
x/2, & \text{if $\exists k \in \mathbb{N}\cup\{0\}$ s.t. $x = 2^{-k}$} \\
x, & \text{otherwise}
\end{cases}
$$
Then $f$ is a bijection. This is true because the map $x\mapsto x/2$ is a bijection on the set $A=\{2^{-k} : k\in \mathbb{N} \cup \{0\}\}$, and because the identity map is trivially a bijection on $(0, 1]\setminus A$.
In other words, $f$ maps $1\mapsto 1/2,\,$ $1/2 \mapsto 1/4,\,$ $1/4 \mapsto 1/8,\,$ and so forth, while for any other number $x$ that isn't a power of $2$, $f$ maps $x\mapsto{x}$, e.g. $1/3 \mapsto 1/3,\,$ $4/7 \mapsto 4/7,\,$ $\mathrm{e}/\pi \mapsto \mathrm{e}/\pi,\,$ etc.
The existence of a bijective function $f$ implies that $(0, 1] \sim (0, 1)$, i.e. that $(0, 1]$ is equinumerous to $(0, 1)$.
Part (b): Just define a new function $g$, by extending the domain of the same $f$ that was defined in Part (a) to $[0, 1]$. Then $g : [0, 1] \to [0, 1)$ is a bijection for the same reasons as $f$, which implies $[0, 1] \sim [0, 1)$.
Part (c): In Part (a), we showed that removing the right endpoint of a half-open interval to make it an open interval does not change the cardinality. In Part (b), we showed that removing the right endpoint of a closed interval to make it a half-open interval does not change the cardinality, either.
The only thing we did not explicitly establish is that these conclusions aren't unique to our choice of the right endpoint, that they hold equally well for removal of the left endpoint. However, this is easily established by composing $f$ and $g$ with the bijective map $x \mapsto 1-x$ that reverses the order of the interval.
Chain the results from each part together, to show that all four intervals are equinumerous with each other:
- Part (b) implies $[0, 1] \sim [0, 1) \sim (0, 1]$, and
- Part (a) implies $[0, 1) \sim (0, 1] \sim (0, 1)$.
Part (d): The original function $f$ from Part (a) almost works already: it has the correct range of $(0, 1)$, but it does not have $x=0$ in its domain. If we want to add $x=0$ to the domain, but without extending the range, then we need to tweak $f$ to find a point to map $0$ to.
Take the function $h : [0, 1] \to (0, 1)$ defined by
$$
h(x) =
\begin{cases}
1/2, & \text{if $x=0$} \\
x/4, & \text{if $\exists k \in \mathbb{N}\cup\{0\}$ s.t. $x = 2^{-k}$} \\
x, & \text{otherwise}
\end{cases}
$$
Then $h$ is a bijection, for essentially the same reasons that $f$ was: the map $x\mapsto x/4$ is a bijection on the set $A=\{2^{-k} : k\in \mathbb{N} \cup \{0\}\}$, the map $0\mapsto 1/2$ is a trivial bijection between the singleton sets ${0}$ and ${1/2}$, and the identity map is a trivial bijection on $(0, 1]\setminus A$.
All I've done, is add a skip to our whole powers-of-two map, to make room for $x=0$. The first few values make this clear: $h$ maps $0\mapsto 1/2,\,$ $1\mapsto 1/4,\,$ $1/2 \mapsto 1/8,\,$ $1/4 \mapsto 1/16,\,$ and so forth, and does the same thing as $f$ or $g$ everywhere else.
BONUS!
Has the preceding discussion gotten you thinking that perhaps, all infinite sets are in fact equinumerous to one other? If that were true, then it would mean that we were splitting hairs by messing with all these bijections. After all, why bother making a bijection from one set to another, when you can just check if it's infinite and then say that its "size" is $\infty$?
The answer, and the reason for these nitpicky bijections, is that it's entirely possible for two sets both to have infinitely many elements, yet at the same time, not be equinumerous. Here's an example: let $A = \mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$ be the set of all integers of any sign, and let $B = \mathbb{R}\cap (0, 1)$ be the open unit interval on the real number line. These two sets are not equinumerous. $A \nsim B$, and in fact, $|A| < |B|$ - that is, there are "more" numbers in $B$ than in $A$!
What this means is that there are actually multiple different infinities out there and some of them are bigger than others.
