Equal Cardinality Means a Complete Pairing
For finite sets, comparing how many elements two sets contain gives a familiar test for whether they have the same size. For infinite sets, a direct count may not be available. A useful test instead asks whether the elements of the sets can be paired, one by one, with no repetitions and no elements left over. The map that records such a pairing is a bijection.
Let \(A\) and \(B\) be sets. A function \(f:A\to B\) assigns to each element of \(A\) exactly one element of \(B\). It is injective if \(f(a_1)=f(a_2)\) implies \(a_1=a_2\). It is surjective if every \(b\in B\) equals \(f(a)\) for some \(a\in A\). A function that is both injective and surjective is a bijection.
The two conditions in a bijection do different jobs. Injectivity prevents two elements of \(A\) from being paired with the same element of \(B\). Surjectivity ensures that every element of \(B\) is paired with something. Together they say that each element of either set occurs in exactly one pair.
Proof. Suppose \(f\) is a bijection. Surjectivity says that for every \(b\in B\), there is at least one \(a\in A\) with \(f(a)=b\). If \(a_1,a_2\in A\) both satisfy \(f(a_1)=b=f(a_2)\), injectivity gives \(a_1=a_2\). Thus there is exactly one such \(a\). Conversely, suppose that every \(b\in B\) has exactly one preimage in \(A\). Having at least one preimage makes \(f\) surjective. If \(f(a_1)=f(a_2)=b\), then \(a_1\) and \(a_2\) are both preimages of \(b\); uniqueness gives \(a_1=a_2\), so \(f\) is injective. Therefore \(f\) is a bijection. \(\square\)
Finite Sets: Writing Down the Pairs
Worked Example: Pairing Two Three-Element Sets
Let \(A=\{a,b,c\}\) and \(B=\{2,4,6\}\). Define \(f:A\to B\) by \(f(a)=2\), \(f(b)=4\), and \(f(c)=6\).
To check the map, record all its values: the element \(a\) maps to \(2\), \(b\) maps to \(4\), and \(c\) maps to \(6\). The three outputs are distinct, so no two elements of \(A\) have the same image. Thus \(f\) is injective. Every element of \(B\) appears as an output: \(2=f(a)\), \(4=f(b)\), and \(6=f(c)\). Thus \(f\) is surjective.
Check: the reverse assignments \(2\mapsto a\), \(4\mapsto b\), and \(6\mapsto c\) recover each input. The map is a bijection, so \(|A|=|B|\). The labels themselves need not resemble one another; the bijection records the pairing, not a numerical similarity between elements.
For finite sets, this test agrees with the usual comparison by number of elements: a bijection uses each element on both sides exactly once. For infinite sets, the same definition still applies, even when there is no last element to count up to.
Bijections Between Infinite Sets
Worked Example: The Natural Numbers and the Positive Even Numbers
Let \(E=\{2,4,6,\dots\}\), the set of positive even integers. Define \(f:\mathbb{N}\to E\) by \(f(n)=2n\). For \(n=1\), \(f(1)=2\); for \(n=2\), \(f(2)=4\); and for \(n=3\), \(f(3)=6\).
If \(f(m)=f(n)\), then \(2m=2n\), and dividing both sides by \(2\) gives \(m=n\). Hence \(f\) is injective. Now take any \(e\in E\). By the definition of \(E\), \(e=2k\) for some \(k\in\mathbb{N}\), and \(f(k)=2k=e\). Hence \(f\) is surjective.
Check: the inverse assignment sends \(e\in E\) to \(e/2\), which is a positive natural number, and \(f(e/2)=2(e/2)=e\). Therefore \(|\mathbb{N}|=|E|\). The positive even numbers form a proper subset of \(\mathbb{N}\), yet this explicit pairing shows that they have the same cardinality.
In the next example, the same rule \(n\mapsto n+1\) has different success or failure depending on its codomain. The codomain is part of the function’s specification: to check surjectivity, one must ask whether every element of that particular codomain is reached.
Worked Example: Shifting the Natural Numbers
Define \(g:\mathbb{N}\to\mathbb{N}\) by \(g(n)=n+1\). Its first values are \(g(1)=2\), \(g(2)=3\), \(g(3)=4\), and \(g(4)=5\). If \(g(m)=g(n)\), then \(m+1=n+1\), so \(m=n\); thus \(g\) is injective. But \(1\in\mathbb{N}\) is not an output: the equation \(n+1=1\) would require \(n=0\), and \(0\notin\mathbb{N}\). So \(g\) is not surjective and is not a bijection onto \(\mathbb{N}\).
Keep the same rule, but change the codomain to \(\mathbb{N}\setminus\{1\}\). Then \(g:\mathbb{N}\to\mathbb{N}\setminus\{1\}\) is a bijection. Indeed, its outputs belong to that codomain, and every \(m\in\mathbb{N}\setminus\{1\}\) has \(m\ge2\) and is the image of \(m-1\in\mathbb{N}\). Injectivity was already checked.
Check: the inverse on the new codomain is \(m\mapsto m-1\): \(g(m-1)=(m-1)+1=m\) for every \(m\ge2\). Therefore \(|\mathbb{N}|=|\mathbb{N}\setminus\{1\}|\). The first map fails to be onto only when its codomain includes \(1\).
Worked Example: Two Copies of the Natural Numbers
Consider \(\mathbb{N}\times\{0,1\}\), whose elements are ordered pairs \((n,i)\) with \(n\in\mathbb{N}\) and \(i\in\{0,1\}\). Define \(h:\mathbb{N}\times\{0,1\}\to\mathbb{N}\) by \(h(n,0)=2n-1\) and \(h(n,1)=2n\). For \(n=1\), the two values are \(h(1,0)=1\) and \(h(1,1)=2\); for \(n=2\), they are \(h(2,0)=3\) and \(h(2,1)=4\); for \(n=3\), they are \(h(3,0)=5\) and \(h(3,1)=6\).
To see that every natural number is reached, take \(m\in\mathbb{N}\). If \(m\) is odd, write \(m=2n-1\), where \(n=(m+1)/2\in\mathbb{N}\); then \(h(n,0)=m\). If \(m\) is even, write \(m=2n\), where \(n=m/2\in\mathbb{N}\); then \(h(n,1)=m\). These cases include every natural number, so \(h\) is surjective.
For uniqueness, an odd output cannot equal an even output. Within the odd case, \(2n-1=2k-1\) implies \(n=k\); within the even case, \(2n=2k\) implies \(n=k\). Thus each output comes from exactly one ordered pair, and \(h\) is injective.
Check: \(1\) has the unique preimage \((1,0)\), \(2\) has the unique preimage \((1,1)\), \(5\) has the unique preimage \((3,0)\), and \(6\) has the unique preimage \((3,1)\), in agreement with the formula. Hence \(|\mathbb{N}\times\{0,1\}|=|\mathbb{N}|\).
A Bijection Between an Interval and Its Interior
A bijection need not preserve order, distance, or any other structure unless those properties are separately required. The following construction uses a shift on a selected sequence of points and leaves all other points fixed.
Worked Example: The Closed and Open Unit Intervals
Let \(I=[0,1]\), and let \(S=\{0\}\cup\{1/n:n\in\mathbb{N}\}\). The points \(1/n\) are distinct, and none equals \(0\). Define \(f:I\to(0,1)\) by \(f(0)=1/2\), \(f(1/n)=1/(n+2)\) for \(n\in\mathbb{N}\), and \(f(x)=x\) for \(x\in I\setminus S\).
Every value lies in \((0,1)\). For \(x\in I\setminus S\), the value \(x\) cannot be an endpoint, since both endpoints belong to \(S\); so \(0<x<1\). The other values are \(1/2\) and \(1/(n+2)\), which also lie strictly between \(0\) and \(1\).
To prove surjectivity, take \(y\in(0,1)\). If \(y=1/k\) for some integer \(k\ge2\), then \(y=f(0)\) when \(k=2\), and \(y=f(1/(k-2))\) when \(k\ge3\). If \(y\) is not of this form, then \(y\notin S\), so \(f(y)=y\). Thus every target point is reached. These preimages are unique: the shifted points \(f(0), f(1), f(1/2),\dots\) are distinct points of \(S\), while points outside \(S\) are fixed and cannot share an output with a point of \(S\). Hence \(f\) is bijective.
Check: \(f(0)=1/2\), \(f(1)=1/3\), \(f(1/2)=1/4\), and \(f(1/3)=1/5\). The omitted target point \(1/2\) under the identity rule is supplied by \(0\); each subsequent point \(1/k\), for \(k\ge3\), is supplied by \(1/(k-2)\). Therefore \(|[0,1]|=|(0,1)|\).
Basic Consequences and a Common Pitfall
Proof. The identity map \(\operatorname{id}_A:A\to A\), defined by \(\operatorname{id}_A(a)=a\), is a bijection, proving reflexivity. If \(f:A\to B\) is a bijection, define \(f^{-1}:B\to A\) by letting \(f^{-1}(b)\) be the unique \(a\in A\) with \(f(a)=b\). The existence and uniqueness of this \(a\) follow from surjectivity and injectivity of \(f\). By construction, \(f^{-1}\) reverses the assignments of \(f\), so it is a bijection and symmetry follows. Finally, let \(f:A\to B\) and \(g:B\to C\) be bijections. For \(a_1,a_2\in A\), if \(g(f(a_1))=g(f(a_2))\), injectivity of \(g\) gives \(f(a_1)=f(a_2)\), and injectivity of \(f\) gives \(a_1=a_2\). Thus \(g\circ f\) is injective. For every \(c\in C\), surjectivity of \(g\) gives \(b\in B\) with \(g(b)=c\), and surjectivity of \(f\) gives \(a\in A\) with \(f(a)=b\). Hence \((g\circ f)(a)=c\), so \(g\circ f\) is surjective. It is a bijection, proving transitivity. \(\square\)
Common pitfall. It is incorrect to say that \(n\mapsto n+1\) is not a bijection without naming its codomain. As shown above, \(g:\mathbb{N}\to\mathbb{N}\) misses \(1\), so it is not onto; but \(g:\mathbb{N}\to\mathbb{N}\setminus\{1\}\) is onto and is a bijection. Always check that the proposed function has values in its stated codomain, then check injectivity and surjectivity relative to that codomain.
The practical point is that cardinality is determined by whether a complete one-to-one pairing exists. A valid construction must define an image for every element of the domain, avoid assigning the same image to distinct elements, and reach every element of the codomain. Each of these checks is necessary.
Check Your Understanding
For each question, identify the domain and codomain before testing a proposed pairing.
- Define a bijection between \(\{p,q,r,s\}\) and \(\{1,3,5,7\}\), and verify injectivity and surjectivity.
- Is \(n\mapsto 3n\) a bijection from \(\mathbb{N}\) to the positive multiples of \(3\)? Justify your answer.
- For the rule \(n\mapsto n+2\), compare the codomains \(\mathbb{N}\) and \(\{3,4,5,\dots\}\). Which choice gives a bijection?
- In the map from \(\mathbb{N}\times\{0,1\}\) to \(\mathbb{N}\), find the preimage of \(9\) and the preimage of \(12\).
- State which part of the definition of a bijection prevents an element of the codomain from being missed, and which part prevents two domain elements from sharing an image.