The cardinality of a set \(A\) (denoted by \(\left|A\right|\)) refers to its size.
We say sets \(A\), \(B\) have the same cardinality (and write \(\begin{vmatrix}A\end{vmatrix}=\begin{vmatrix}B\end{vmatrix}\) ) when we can create a bijection \(f:A\to B\) between them.
A set \(A\) is called countable if it is finite, or infinite, but with the same cardinality as the natural numbers (i.e., \(\mathbb{N}\)). For example, the sets of integers and rational numbers are countable (i.e., \(\begin{vmatrix}\mathbb{N}\end{vmatrix}=\begin{vmatrix}\mathbb{Z}\end{vmatrix}=\begin{vmatrix}\mathbb{Q}\end{vmatrix}\)). To show that a set \(A\) is countable, create a bijection \(f:\mathbb{N}\to A\). Sets that can be arranged into an infinite sequence are countable \((A=\{a_1,a_2,...\}\)).
A set \(A\) is called uncountable if it is not countable. The set of real numbers \(\left(\mathbb{R}\right)\) is uncountable. All intervals are uncountable \((\left|\mathbb{R}\right|=\left|(a,b)\right|\) for \(a\), \(b\) real numbers and \(a\neq b)\). Creating a bijection \(f:\mathbb{R}\to A\) proves that set \(A\) is uncountable.
Example
Prove that the set of integers divisible by 3 is countable.
Solution
Let’s call this set \(A\). Since we are talking about the integers, we must include zero as well as negative numbers. Then \(A\) is:
\(A=\begin{Bmatrix}...,-6,-3,0,3,6,...\end{Bmatrix}.\)
To show \(\left|A\right|=\left|\mathbb{N}\right|\), we need a bijection \(f:\mathbb{N}\to A\). If \(A\) is countable, we should be able to write it as an infinite sequence. We can do this if we “fold” the set at zero:
\(A=\begin{Bmatrix}0,3,-3,6,-6,\ldots\end{Bmatrix}\)
It helps to think of creating \(f\) as making a rule for the diagram below:
\[\begin{array}
{ccccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & ... \\
& \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & ... \\
A & 0 & 3 & -3 & 6 & -6 & 9 & -9 & ...
\end{array}\]
When writing a formula, it helps to make \(f\) a piecewise function and splitting the naturals into evens and odds. Notice that in the diagram the evens go to positives and the odds to go zero and negatives.
It may take a few attempts to find the right function, it helps to do them one at a time. For example, we can perform \(2\to3\) by adding \(1\) but \(4+1\neq6\). For an even number, \(n\to3\frac{n}2\). For an odd number, \(n\to-3\frac{n-1}2\) works. Thus, we can make \(f\) like this: \[f(n)=\begin{cases}&3\frac n2;&n\mathrm{~even}\\&-3\frac{n-1}2;&n\mathrm{~odd}&\end{cases}\]
This function is a bijection by design, but it can be checked.
Example
Show \(\left|(-1,1)\right|=\left|(-5,15)\right|.\)
Solution
To show they have the same cardinality, we need to find a bijection \(f:(-1,1)\to(-5,15).\)
One way to think about how to create this function is to notice that \(( 1,1)\) is "2 units long" and \((5,15)\) is "20 units long". We will have to “stretch” \((-1,1)\) by 10, getting \((-10,10)\). Then, we can “move it right” by 5, giving us \((-5,15)\).
More formally, we can start with \(x\in(-1,1)\), which is:
\(\begin{gathered}
-1<x<1 \\
\Rightarrow-10<10x<10 \\
\Rightarrow-5<10x+5<15 \\
\Rightarrow(10x+5)\in(-5,15)
\end{gathered}\)
Thus, our function should be \(f(x)=10x+5\). This function is bijective; surjection is partly outlined and injection is straightforward.
Note that an alternative way to find \(f(x)\) is to compute an equation of the line going through the points \((-1,-5\)) and \((1,15)\).