Finite Sets Have a Number of Elements
To say informally that a set has “a certain number of elements” is to say that its elements can be listed without omissions or repetitions. Initial segments of the natural numbers provide a precise model for such lists. They include the special case of the empty set, and they let us prove that the number assigned to a finite set does not depend on which list we choose.
Write \(\mathbb{N}_0=\{0\}\cup\mathbb{N}\), where \(\mathbb{N}=\{1,2,\dots\}\), and define \([n]=\{1,\dots,n\}\) when \(n\geq 1\), with \([0]=\varnothing\). A function is a bijection if it is both one-to-one (distinct inputs have distinct outputs) and onto (every element of the target is an output).
For \(n=0\), the only set bijective with \([0]=\varnothing\) is the empty set, so \(|\varnothing|=0\). For \(n=1\), the initial segment \([1]\) contains one element, so a set bijective with it is a singleton. The definition itself does not yet show that a set cannot be bijective with initial segments of two different sizes. We establish that next.
Why the Cardinality Is Unique
Proof. We use induction on \(n\). When \(n=0\), the list has one entry, but \([0]\) has no elements, so no such list exists; the assertion holds. Suppose \(n\geq 1\) and the assertion holds for \(n-1\). Consider a list of \(n+1\) elements of \([n]\). If \(n\) occurs at least twice, the list has a repetition. If \(n\) occurs exactly once, remove its one occurrence. The remaining \(n\) entries lie in \([n-1]\), and the induction hypothesis says that these \(n\) entries contain a repetition. If \(n\) does not occur, the first \(n\) entries lie in \([n-1]\); the induction hypothesis again gives a repetition. These cases cover all possibilities, proving the assertion for \(n\). \(\square\)
Proof. Suppose \(m>n\). Then the first \(n+1\) elements of \([m]\) have distinct images under the bijection, giving a list of \(n+1\) distinct elements of \([n]\). This contradicts the finite pigeonhole principle. Hence \(m\leq n\). If \(n>m\), the inverse of the bijection is a bijection from \([n]\) to \([m]\); applying the same argument gives a contradiction. Therefore neither \(m>n\) nor \(n>m\), so \(m=n\). \(\square\)
This theorem makes the definition of \(|X|\) unambiguous. If \(X\) is bijective with both \([m]\) and \([n]\), composing one bijection with the inverse of the other gives a bijection between \([m]\) and \([n]\). The theorem then gives \(m=n\).
Bijections Preserve Finiteness and Cardinality
Proof. Since \(X\) is finite, there is an \(n\in\mathbb{N}_0\) and a bijection \(g:[n]\to X\). The composition \(f\circ g:[n]\to Y\) is a bijection: it is one-to-one because both \(g\) and \(f\) are one-to-one, and it is onto because \(g\) reaches every point of \(X\) and \(f\) reaches every point of \(Y\). Thus \(Y\) is finite with cardinality \(n\). By definition \(|X|=n\), so \(|Y|=|X|\). \(\square\)
The converse also holds: if \(Y\) is finite and \(f:X\to Y\) is a bijection, the inverse \(f^{-1}:Y\to X\) is a bijection, so the theorem applied to \(f^{-1}\) shows that \(X\) is finite with the same cardinality. Thus a bijection cannot turn a finite set into an infinite one or change the size of a finite set.
Worked Example: The Empty Set and a Singleton
Verify the cardinalities of \(E=\varnothing\) and \(S=\{\text{oak}\}\) directly from the definition.
For \(E\), the unique function from \([0]=\varnothing\) to \(E=\varnothing\) has no inputs and no outputs. It is one-to-one, since there are no distinct inputs to check, and onto, since there are no elements of \(E\) left uncovered. Therefore it is a bijection and \(|E|=0\).
For \(S\), define \(f:[1]\to S\) by \(f(1)=\text{oak}\). The only two possible requirements are that distinct inputs have distinct outputs and that every element of \(S\) is an output. The first holds because \([1]\) has no pair of distinct inputs; the second holds because \(S\) contains only \(\text{oak}=f(1)\). Thus \(f\) is a bijection and \(|S|=1\).
Check: A bijection from \([0]\) to the nonempty set \(S\) cannot exist: its image would be empty and would not contain \(\text{oak}\). This confirms that the two cardinalities differ.
Worked Example: Listing a Four-Element Set
Let \(X=\{\text{north},\text{south},\text{east},\text{west}\}\). Show explicitly that \(X\) has cardinality \(4\).
Define \(g:[4]\to X\) by \(g(1)=\text{north}\), \(g(2)=\text{south}\), \(g(3)=\text{east}\), and \(g(4)=\text{west}\). These four outputs are distinct, so \(g\) is one-to-one. They are exactly the four elements of \(X\), so \(g\) is onto. Hence \(g\) is a bijection and \(|X|=4\).
For a second listing, define \(h:[4]\to X\) by \(h(1)=\text{west}\), \(h(2)=\text{east}\), \(h(3)=\text{south}\), and \(h(4)=\text{north}\). Its outputs are again distinct and include every element of \(X\), so \(h\) is also a bijection. The two lists give the same cardinality, as the uniqueness theorem requires.
Check: The composite \(h^{-1}\circ g:[4]\to[4]\) sends \(1\mapsto4\), \(2\mapsto3\), \(3\mapsto2\), and \(4\mapsto1\). Its outputs are precisely \(1,2,3,4\), each once, so it is a bijection from the initial segment to itself.
Subsets of Finite Sets
Proof. Choose a bijection \(g:[n]\to X\) and let \(J=g^{-1}(A)=\{i\in[n]:g(i)\in A\}\). It is enough to show that every subset \(J\) of \([n]\) is bijective with \([k]\) for some \(k\leq n\). We prove this by induction on \(n\). If \(n=0\), then \(J=\varnothing=[0]\), so take \(k=0\). Suppose \(n\geq1\) and the assertion holds for \(n-1\). If \(n\notin J\), then \(J\subseteq[n-1]\); by induction there is a bijection \([k]\to J\) for some \(k\leq n-1\), and hence \(k\leq n\). If \(n\in J\), then \(J_0=J\setminus\{n\}\) is a subset of \([n-1]\). By induction there is a bijection \(u:[k]\to J_0\) for some \(k\leq n-1\). Extend it to \([k+1]\) by sending the new element \(k+1\) to \(n\), while retaining \(u\) on \([k]\). The extended function is one-to-one because \(u\) is one-to-one and \(n\notin J_0\); it is onto \(J\) because its outputs are \(J_0\cup\{n\}=J\). Thus \(J\) is bijective with \([k+1]\), and \(k+1\leq n\). Finally, restricting \(g\) to \(J\) gives a bijection from \(J\) to \(A\). Composing with the bijection from an initial segment to \(J\) proves the proposition. \(\square\)
Worked Example: A Subset of a Five-Element Set
Let \(X=\{p,q,r,s,t\}\) and \(A=\{q,s,t\}\). Use a listing of \(X\) to verify the size of \(A\).
Define \(g:[5]\to X\) by \(g(1)=p\), \(g(2)=q\), \(g(3)=r\), \(g(4)=s\), and \(g(5)=t\). The preimage of \(A\) is \(g^{-1}(A)=\{2,4,5\}\). Define \(u:[3]\to\{2,4,5\}\) by \(u(1)=2\), \(u(2)=4\), and \(u(3)=5\). Its three outputs are distinct and exhaust its target, so \(u\) is a bijection. The restriction \(g|_{\{2,4,5\}}\) maps \(2\mapsto q\), \(4\mapsto s\), and \(5\mapsto t\), also bijectively. Therefore the composition maps \([3]\) bijectively to \(A\), and \(|A|=3\).
Check: The three outputs of that composition are \(q,s,t\), with no repetitions, and together they are exactly \(A\). In particular \(3\leq5=|X|\), as the proposition predicts.
An Infinite Set and a Common Pitfall
Worked Example: The Natural Numbers Are Infinite
Show that \(\mathbb{N}\) is not finite. Suppose instead that it were finite, so there were a bijection \(f:[n]\to\mathbb{N}\) for some \(n\in\mathbb{N}_0\). If \(n=0\), the image is empty, so \(f\) cannot be onto the nonempty set \(\mathbb{N}\). If \(n\geq1\), the outputs \(f(1),\dots,f(n)\) are natural numbers. A finite nonempty list of natural numbers has a largest value; call it \(M\). Then \(M+1\in\mathbb{N}\), but \(M+1\) is larger than every output of \(f\), so it is not in the image. This contradicts that \(f\) is onto. Both possibilities for \(n\) lead to a contradiction, so \(\mathbb{N}\) is infinite.
Check: The argument rules out every possible initial segment \([n]\): the empty one fails to cover \(\mathbb{N}\), and every nonempty one has a finite list of outputs with a largest value that is smaller than some natural number.
Common pitfall: confusing boundedness with finiteness. A bounded set need not be finite. For example, suppose \([0,1]\) had cardinality \(m\in\mathbb{N}_0\). The \(m+1\) numbers \(0/(m+1),1/(m+1),\dots,m/(m+1)\) all belong to \([0,1]\). They are distinct: if \(j/(m+1)=k/(m+1)\), multiplying by the positive number \(m+1\) gives \(j=k\). Thus \([0,1]\) contains a subset of \(m+1\) distinct points. The subset proposition says that any subset of a set of cardinality \(m\) has cardinality at most \(m\), a contradiction. In particular, the case \(m=0\) already fails because the displayed list then consists of the single point \(0\). So \([0,1]\) is infinite despite being bounded.
The definition gives a practical test: find an explicit bijection from some \([n]\) to prove a set finite; to prove it infinite, show that no such bijection can exist. Once a bijection with an initial segment is established, the uniqueness theorem guarantees that the resulting cardinality is independent of the chosen listing.
Check Your Understanding
For each question, use the definition and the proved results above.
- Write a bijection from \([3]\) to \(\{a,b,c\}\) and verify that it is one-to-one and onto.
- Why can no bijection exist from \([2]\) to \([4]\)? Identify the result that rules it out.
- If \(X\) is finite with \(|X|=6\) and \(A\subseteq X\), what are the possible values of \(|A|\)?
- Give a bijection showing that \(\{2,4,6\}\) has cardinality \(3\).
- In the proof that \(\mathbb{N}\) is infinite, why must the case \(n=0\) be considered separately?