From Injections to Equal Cardinality
To compare two sets, it is useful to find an injection from one into the other. An injection \(f:X\to Y\) sends distinct elements of \(X\) to distinct elements of \(Y\); it shows that \(X\) is no larger than \(Y\) in cardinality. But an injection in just one direction does not generally establish equal cardinality. For that conclusion, we use the Cantor–Schroeder–Bernstein theorem.
We will compare \(\mathbb{R}\), the open interval \((0,1)\), and the closed interval \([0,1]\). Every space here is being considered simply as a set for purposes of cardinality. The maps must be checked against their declared domains and codomains: a formula that is injective as a real-valued function need not take its values in the set named as its codomain.
A Bounded Injection from the Real Line
Worked Example: Injecting \(\mathbb{R}\) into \((0,1)\)
Define \(f:\mathbb{R}\to(0,1)\) by \[ f(x)=\frac12+\frac{x}{2(1+|x|)}. \] We check first that the formula takes every real input into the open interval. If \(x\ge0\), then \(0\le x/(1+x)<1\), so \(1/2\le f(x)<1\). If \(x<0\), then \(x/(1-x)\) is strictly between \(-1\) and \(0\), so \(0<f(x)<1/2\). In both cases \(f(x)\in(0,1)\).
To verify injectivity, set \(t=2f(x)-1\). The formula gives \(t=x/(1+|x|)\), so \(-1<t<1\). For \(t\ge0\), solving \(t=x/(1+x)\) gives \(x=t/(1-t)\). For \(t<0\), solving \(t=x/(1-x)\) gives \(x=t/(1+t)\). These two cases can be written \(x=t/(1-|t|)\). Thus \(x\) is determined by \(f(x)\), which proves that \(f\) is injective.
Check by substitution. For \(x=-2\), \(|x|=2\), so \(f(-2)=1/2-2/(2\cdot3)=1/6\). Then \(t=2(1/6)-1=-2/3\), and \(t/(1-|t|)=(-2/3)/(1/3)=-2\). For \(x=3\), \(f(3)=1/2+3/(2\cdot4)=7/8\); then \(t=2(7/8)-1=3/4\), and \(t/(1-|t|)=(3/4)/(1/4)=3\). Both substitutions recover the original input.
There is also an injection \(g:(0,1)\to\mathbb{R}\): take \(g(y)=y\). It is injective because \(g(y_1)=g(y_2)\) implies \(y_1=y_2\), and every output is a real number. The two injections now give precisely the hypotheses of Cantor–Schroeder–Bernstein.
Proof. The map \(f(x)=1/2+x/(2(1+|x|))\) is an injection from \(\mathbb{R}\) into \((0,1)\), as verified above. The inclusion \(g(y)=y\) is an injection from \((0,1)\) into \(\mathbb{R}\). The Cantor–Schroeder–Bernstein theorem therefore gives a bijection between \(\mathbb{R}\) and \((0,1)\). Hence \(|\mathbb{R}|=|(0,1)|\). \(\square\)
Changing the Endpoints
The open and closed unit intervals differ by their endpoints. To compare their cardinalities, we do not need to try to move each endpoint into the interior by a complicated rearrangement. It is enough to find injections in both directions. Inclusion gives one direction; a simple affine map gives the other.
Worked Example: Comparing \([0,1]\) and \((0,1)\)
First define \(h:[0,1]\to(0,1)\) by \(h(x)=(x+1)/3\). If \(0\le x\le1\), then \(1/3\le h(x)\le2/3\), and \([1/3,2/3]\subset(0,1)\). If \(h(x_1)=h(x_2)\), then \((x_1+1)/3=(x_2+1)/3\); multiplying by \(3\) and subtracting \(1\) gives \(x_1=x_2\). Thus \(h\) is an injection.
In the other direction, let \(j:(0,1)\to[0,1]\) be \(j(y)=y\). Its values lie in \([0,1]\), and equality \(j(y_1)=j(y_2)\) implies \(y_1=y_2\), so \(j\) is injective.
Check at the endpoints and an interior point. The domain endpoint \(x=0\) maps to \(h(0)=1/3\), and \(x=1\) maps to \(h(1)=2/3\); both are strictly between \(0\) and \(1\). The interior point \(x=1/2\) maps to \(h(1/2)=(3/2)/3=1/2\). Each output lies in the required codomain, as the bounds show for every \(x\in[0,1]\).
The two injections and Cantor–Schroeder–Bernstein give \(|[0,1]|=|(0,1)|\). Combining this with the result for \(\mathbb{R}\) shows that all three sets have equal cardinality.
Proof. The theorem above gives a bijection between \(\mathbb{R}\) and \((0,1)\), and the injections in the worked example give, by Cantor–Schroeder–Bernstein, a bijection between \((0,1)\) and \([0,1]\). Bijections compose: if \(F:\mathbb{R}\to(0,1)\) and \(H:(0,1)\to[0,1]\) are bijections, then \(H\circ F\) is a bijection from \(\mathbb{R}\) to \([0,1]\). Its inverse is \(F^{-1}\circ H^{-1}\). Therefore all three sets have equal cardinality. \(\square\)
This argument illustrates a useful feature of the theorem: the two injections used to establish equal cardinality do not have to be inverse functions, and their images do not have to cover their codomains. In the example, the image of \(h\) is only \([1/3,2/3]\), not the whole open interval. That is enough because injectivity, rather than surjectivity, is the requirement for each direction.
Where the Natural Numbers Fit
Worked Example: Injecting \(\mathbb{N}\) into Both Intervals
Recall that \(\mathbb{N}=\{1,2,3,\dots\}\). Define \(a:\mathbb{N}\to(0,1)\) by \(a(n)=1/(n+1)\). For every \(n\ge1\), \(n+1\ge2\), so \(0<a(n)\le1/2<1\). If \(a(m)=a(n)\), then \(1/(m+1)=1/(n+1)\); multiplying by the positive number \((m+1)(n+1)\) gives \(m+1=n+1\), hence \(m=n\). Thus \(a\) is an injection. The same formula, with codomain \([0,1]\), is also an injection into the closed interval.
Check the first three values. The inputs \(1,2,3\) map to \(1/2,1/3,1/4\), respectively. These are distinct, and each is greater than \(0\) and less than \(1\). The general inequalities and injectivity calculation above verify the claim for every natural number, not just these three inputs.
The inclusion \(i:(0,1)\to\mathbb{R}\), \(i(x)=x\), is an injection, so \(\mathbb{N}\) injects into \(\mathbb{R}\) as well: the composite \(i\circ a\) sends \(n\) to \(1/(n+1)\) and remains injective. These maps establish that the natural numbers are no larger than any of the three sets under comparison. They do not establish equal cardinality.
The earlier material on Cantor’s diagonal argument establishes that \(\mathbb{R}\) is uncountable. Here, “countable” means finite or in bijection with \(\mathbb{N}\). The earlier countability criteria also give the following implication: if a set injects into \(\mathbb{N}\), then it is countable. Consequently there is no injection \(\mathbb{R}\to\mathbb{N}\); such an injection would make \(\mathbb{R}\) countable, contrary to uncountability.
Proof. The map \(n\mapsto1/(n+1)\) injects \(\mathbb{N}\) into \((0,1)\) and into \([0,1]\), and composing it with inclusion injects \(\mathbb{N}\) into \(\mathbb{R}\). Thus each of these sets has cardinality at least that of \(\mathbb{N}\). If any one of them had equal cardinality with \(\mathbb{N}\), there would be a bijection between it and \(\mathbb{N}\). Since \(\mathbb{R}\), \((0,1)\), and \([0,1]\) have equal cardinality, this would imply that \(\mathbb{R}\) is countable. That contradicts the established uncountability of \(\mathbb{R}\). Hence none has equal cardinality with \(\mathbb{N}\), and each has strictly larger cardinality. \(\square\)
A Common Pitfall and a Practical Checklist
Common pitfall: checking injectivity but not the codomain. The identity formula \(x\mapsto x\) is injective on \(\mathbb{R}\), but it is not a function from \(\mathbb{R}\) to \((0,1)\): for example, the input \(x=2\) gives output \(2\), and \(2\notin(0,1)\). The correction is to use a bounded formula such as \(f(x)=1/2+x/(2(1+|x|))\). Its range check shows \(0<f(x)<1\) for every real \(x\), and the inverse expression \(x=t/(1-|t|)\), where \(t=2f(x)-1\), verifies injectivity.
A second error is to treat a one-way injection as proof of equal cardinality. The injection \(n\mapsto1/(n+1)\) puts \(\mathbb{N}\) into \((0,1)\), but it says nothing by itself about an injection back into \(\mathbb{N}\). In fact, no such reverse injection exists, because \((0,1)\) has the same uncountable cardinality as \(\mathbb{R}\). When applying Cantor–Schroeder–Bernstein, check that the maps go in both directions and that each map is injective.
| Comparison | Injection one way | Injection the other way | Conclusion |
|---|---|---|---|
| \(\mathbb{R}\) and \((0,1)\) | \(x\mapsto 1/2+x/(2(1+|x|))\) | Inclusion | Equal cardinality by Cantor–Schroeder–Bernstein |
| \([0,1]\) and \((0,1)\) | \(x\mapsto(x+1)/3\) | Inclusion | Equal cardinality by Cantor–Schroeder–Bernstein |
| \(\mathbb{N}\) and \((0,1)\) | \(n\mapsto1/(n+1)\) | No injection \((0,1)\to\mathbb{N}\) | The interval has strictly larger cardinality |
For these comparisons, the efficient strategy is to write down the proposed domain and codomain first, verify that every output belongs to the codomain, and then prove injectivity. Once injections in both directions have been checked, Cantor–Schroeder–Bernstein supplies the bijection without requiring us to construct that bijection explicitly.
Check Your Understanding
For each question, identify the domain and codomain of every map you use, then check both its range and injectivity.
- Verify directly that \(x\mapsto x/(1+|x|)\) is an injection from \(\mathbb{R}\) into \((-1,1)\). What is its inverse on its image?
- Give injections in both directions between \([2,5]\) and \((0,1)\), and use Cantor–Schroeder–Bernstein to state the resulting cardinality comparison.
- Explain why an injection \(\mathbb{N}\to(0,1)\) does not prove that \((0,1)\) is countable.
- In the map \(h(x)=(x+1)/3\), compute \(h(0)\), \(h(1)\), and \(h(1/2)\), and verify that all three outputs lie in \((0,1)\).
- Which fact rules out an injection \(\mathbb{R}\to\mathbb{N}\): the existence of an injection \(\mathbb{N}\to\mathbb{R}\), or the uncountability of \(\mathbb{R}\) together with the countability criterion for injections?