Andrew Cooper

We know that $\mathbb{N}$ is the smallest infinite set; this makes $\mathbb{N}$ a pretty good place to get started. But our ideas about size have to do just with bijections, so whatever we’d say about $\mathbb{N}$ we could also say about any set which is equivalent to $\mathbb{N}$.

Definition. If $X\approx \mathbb{N}$, we call $X$ denumerable, and we call any bijection $\psi:X\rightarrow \mathbb{N}$ a denumeration of $X$. We call $X$ countable if it is either finite or denumerable. Sometimes denumerable sets are called countably infinite.

E.g. $\mathbb{N}$ is denumerable.

Theorem. Any subset of a denumerable set is countable.

Proof. Let $X$ be denumerable and $A\subseteq X$. Assume that $A$ is not finite; we’ll show that $A$ is denumerable.

Since $X$ is denumerable, there is a bijection $\psi:X\rightarrow\mathbb{N}$. We’ll construct a denumeration of $A$ using induction.

For the base case: by the Well-Ordering Principle, there is a least element of $\psi_*(A)$. By injectivity, this element is the image of a unique element of $A$, call it $a_1$. Observe that $A\setminus\{a_1\}$ is not empty, so $\psi_*(A\setminus\{a_1\})$ is not empty.

Suppose we’ve denumerated $k$ elements of $A$ so far, say $a_1,\ldots, a_k$. Since $A$ is not finite, $A\setminus\{a_1,\ldots a_k\}$ is not empty. So $\psi_*(A\setminus\{a_1,\ldots,a_k\})$ is a nonempty subset of $\mathbb{N}$, hence by the Well-Ordering Principle has a least element. By injectivity, this element is the image of a unique $a_{k+1}\in A$, which is distinct from all the $a_1,\ldots, a_k$.

Proceeding in this way, we construct a bijection $\mathbb{N}\rightarrow \{a_1,\ldots, a_n,\ldots\}$. Moreover, any $a\in A$ will be one of the $a_k$, since $\psi(a)$ will occur in the list of values. So we have $\mathbb{N}\approx A$. $\Box$.

Corollary. The following sets are equivalent to $\mathbb{N}$:

• The set of prime numbers.
• The set of even natural numbers.
• The set of odd natural numbers.
• The set of positive powers of 2.
• The set of positive powers of 3.

Proof. These are all infinite subsets of $\mathbb{N}$. Since they’re not finite, they must be denumerable. $\Box$.

Theorem. Any subset of a countable set is countable.

Theorem. If $B$ is countable and there is an injection $g:A\rightarrow B$, then $A$ is countable.

Theorem. If $A$ is countable and there is a surjection $g:A\rightarrow B$, then $B$ is countable.

One weird thing about denumerable sets — actually any infinite set — is that if you add a single element, the set doesn’t get any larger.

Theorem. $\mathbb{N}\approx\mathbb{N}\cup\{0\}$.

Proof.  The bijection is given by sending $n\in\mathbb{N}$ to $n-1\in\mathbb{N}\cup\{0\}$. $\Box$.

Okay, but what if we tried to add an entire additional copy of $\mathbb{N}$ — say, the negative numbers.

Theorem. $\mathbb{Z}\approx \mathbb{N}$.

Proof. We’ll give a bijection $\mathbb{N}\cup\{0\}\rightarrow \mathbb{Z}$. Try \begin{align*}\mathbb{N}\cup\{0\}&\rightarrow \mathbb{Z}\\n&\mapsto\begin{cases}-\frac{n}{2} & \text{ if }n \text{ is even}\\\frac{n+1}{2} & \text{ if }n\text{ is odd}\end{cases}\end{align*}

As an exercise, show that this function is a bijection. Actually, givetwo proofs: one by showing it is injective and surjective, and one by building the inverse function.$\Box$.

Notice that this is a bit weird: $\mathbb{Z}=\mathbb{N}\cup(\mathbb{N}\cup\{0\})$ is the union of two disjoint sets, each of which is equivalent to $\mathbb{N}$. But it’s no bigger than $\mathbb{N}$.

Theorem. If $A$ is denumerable and $B$ is denumerable, then $A\times B$ is denumerable.

Proof. We’ll show first that $\mathbb{N}\times\mathbb{N}$ is denumerable.

We can represent $\mathbb{N}\times\mathbb{N}$ as a grid of points in the plane:

\begin{tikzpicture}

\foreach \n in {(1,1),(1,2),(2,1),(2,2),(1,3),(2,3),(3,3),(3,2),(3,1),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(1,5),(2,5),(3,5),(4,5),(5,5),(5,4),(5,3),(5,2),(5,1)}
\node at \n [circle,fill,inner sep=1.5pt]{};

\node at (5.5,3){$\cdots$};

\node at (3,5.5){$\vdots$};

\node at (1,5.5){$\vdots$};

\node at (5,5.5){$\vdots$};

\node at (5.5,1){$\cdots$};

\node at (5.5,5){$\cdots$};

\end{tikzpicture}

and then denumerate them in any order we like, starting perhaps from the origin and snaking around like so:

\begin{tikzpicture}

\foreach \n in {(1,1),(1,2),(2,1),(2,2),(1,3),(2,3),(3,3),(3,2),(3,1),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(1,5),(2,5),(3,5),(4,5),(5,5),(5,4),(5,3),(5,2),(5,1)}

\node at \n [circle,fill,inner sep=1.5pt]{};

\node at (5.5,3){$\cdots$};

\node at (3,5.5){$\vdots$};

\node at (1,5.5){$\vdots$};

\node at (5,5.5){$\vdots$};

\node at (5.5,1){$\cdots$};

\node at (5.5,5){$\cdots$};

\draw [thick, ->] (1,1) –(1,2);

\draw [thick, ->] (1,2) –(2,2);

\draw [thick, ->] (2,2) –(2,1);

\draw [thick, ->] (2,1) –(3,1);

\draw [thick, ->] (3,1) –(3,2);

\draw [thick, ->] (3,2) –(3,3);

\draw [thick, ->] (3,3) –(2,3);

\draw [thick, ->] (2,3) –(1,3);

\draw [thick, ->] (1,3) –(1,4);

\draw [thick, ->] (1,4) –(2,4);

\node at (.75,.75) [shape=circle,draw,inner sep=1pt]{$1$};

\node at (.75,2.25) [shape=circle,draw,inner sep=1pt]{$2$};

\node at (2.25,2.25) [shape=circle,draw,inner sep=1pt]{$3$};

\node at (1.75,.75) [shape=circle,draw,inner sep=1pt]{$4$};

\node at (3.25,.75) [shape=circle,draw,inner sep=1pt]{$5$};

\node at (3.25,2) [shape=circle,draw,inner sep=1pt]{$6$};

\node at (3.25,3.25) [shape=circle,draw,inner sep=1pt]{$7$};

\node at (2.25,3.25) [shape=circle,draw,inner sep=1pt]{$8$};

\node at (.75,3.25) [shape=circle,draw,inner sep=1pt]{$9$};

\node at (.75,4.25) [shape=circle,draw,inner sep=1pt]{$10$};

\node at (2.25,4.25) [shape=circle,draw,inner sep=1pt]{$11$};

 

 

\end{tikzpicture}

It’s clear that we’ll eventually get all the dots numbered (so our denumeration is onto), and that dot will only get one number (so our denumeration is one-to-one).

Now let’s go from this special case to the general case.

Lemma. If $A\approx B$ and $X\approx Y$, then $A\times X\approx B\times Y$.

Proof. This is homework.$\Box$.

To complete the proof: we know that $A$ and $B$ are denumerable, so we have $A\approx \mathbb{N}$ and $B\approx \mathbb{N}$. So by the lemma $A\times B\approx \mathbb{N}\times\mathbb{N}$. But we showed $\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$. So by transitivity of $\approx$, we have $A\times B\approx\mathbb{N}$. $\Box$.

Theorem. If $A$ is countable and $B$ is countable, then $A\times B$ is countable.

Proof. We have the cases when both sets are finite and both sets are denumerable. So we only need to handle the case when one set is finite and the other is denumerable. This is an exercise. $\Box$.

Theorem. $\mathbb{Q}$ is denumerable.

Proof. By the theorem above, $\mathbb{Z}\times\left(\mathbb{Z}\setminus\{0\}\right)$ is countable. There is a surjection from $\mathbb{Z}\times\left(\mathbb{Z}\setminus\{0\}\right)$ to $\mathbb{Q}$ given by $(m,n)\mapsto \frac{m}{n}$, so $\mathbb{Q}$ is countable. But we have an injection from $\mathbb{N}$ to $\mathbb{Q}$ given by $n\mapsto\frac{1}{n}$, so $\mathbb{Q}$ is infinite.$\Box$.

Grab some collection of objects and count it. How does that work?

Let’s say we want to count the (living) former Presidents of the United States in this photograph:

We’re so good at counting that we’d probably just glance and say “5”. But if we were three or four years old, we’d probably have to count more carefully, which means doing something like placing our index finger on Obama and pronouncing “one”, shifting the index finger to W. Bush and pronouncing “two”, shifting the index finger to Clinton and pronouncing “three”, shifting it to H. W. Bush and pronouncing “four”, and finally shifting to Carter and pronouncing “five”.

In other words, we would construct the following explicit bijection:

Definition. We call the set A finite if either A is empty, or there is some and a bijection . The number is called the cardinality of A. The cardinality of the empty set is defined to be 0.

We’ve been dealing with finite sets our whole lives, and much of set theory is inspired by them. We’ll take the time to record some important facts, which may seem obvious but are worth noting.

Theorem. If $A$ is finite and there is a surjection $g:A\rightarrow B$, then $B$ is finite.

Proof. We’ll start with a lemma:

Lemma. If there is a surjection $g:A\rightarrow B$, then there is an injection $h:B\rightarrow A$.

Proof. Since $g$ is a surjection, for each $b\in B$, there is some $a\in A$ with $g(b)=a$. Pick one of them and call it $h(b)$.

We claim $h:B\rightarrow A$ is an injection. $\Box$.

So now we have an injection $h$ from $B$ to a finite set. Further, there is some bijection $\psi:A\rightarrow\{1,\ldots,n\}$. Then $\psi\circ h:B\rightarrow \{1,\ldots, n\}$ is an injection. But every function is a surjection onto its range, so $B$ is bijective with a subset of $\{1,\ldots,n\}$, hence must be finite. $\Box$

Corollary. If $A$ is finite and there is an injection $h:B\rightarrow A$, then $B$ is finite.

Corollary. Any subset of a finite set is finite.

Proof. If $X\subseteq Y$ and $Y$ is finite, consider the function $\iota_X:X\rightarrow Y$ given by $\iota_X:t\mapsto t$. This is an injection, so the previous corollary applies.$\Box$.

Definition. We call $B$ a proper subset of $A$ if $B\subseteq A$ but $B\neq A$; that is, if every element of $B$ is an element of $A$, but there is some element of $A$ which is not an element of $B$.

Theorem. If $A$ is finite, then $A$ is not equivalent to any of its proper subsets.

Proof. Suppose not. Then there is some finite set $A$ and a proper subset $B$ of $A$ with $B\approx A$. So there is some $a_0\in A$ with $a_0\notin B$.

Now let $\psi: A\rightarrow \{1,\ldots, n\} $ be the bijection which shows that $A$ is finite, and arrange so that $\psi(a_0)=n$. Then the range of $\psi|_B$ is a subset of $\{1,\ldots, n-1\}$. But then $\{1,\ldots, n\}$ would be equivalent to a subset of $\{1,\ldots, n-1\}$, which is absurd. $\Box$.

Perhaps the most surprising part of this theorem is that we have the assumption “$A$ is finite”. You might think that there’s no way a set could be equivalent to the set you get after you remove an element. But! Infinite sets are kind of weird; or at least we aren’t used to dealing with them so our intuitions are sometimes wrong.

Definition. We call a set $A$ infinite if it is not finite.

Theorem. If $A$ is equivalent to one of its proper subsets, then $A$ is infinite.

Proof. This is the contrapositive of the last theorem.

This theorem (though you might think its hypothesis never applies) turns out to be a very useful way to prove that a particular set is infinite.

Theorem. $\mathbb{N}$ is infinite.

Proof. Consider the function $f:n\mapsto n+1$. This is a function from $\mathbb{N}$ to $\mathbb{N}\setminus\{1\}$. Notice that there is a function $g:\mathbb{N}\setminus\{1\}\rightarrow \mathbb{N}$ given by $g(p)=p-1$, which has\begin{align*}g(f(n))&=g(n+1)=n+1-1=n\\f(g(p))&=f(p-1)=p-1+1=p\end{align*}so that $g$ serves as an inverse to $f$. Therefore $f$ is a bijection, and so $\mathbb{N}\approx\mathbb{N}\setminus\{1\}$. $\Box$

We can also give another proof, which is how most proofs that something is infinite go. Since infinite just means not finite, we challenge the reader to try and tell us how many elements the infinite set has. Then we show we can always defeat them, by finding an element they left out of their count.

Another proof that $\mathbb{N}$ is infinite.

Suppose $\mathbb{N}$ had finitely many elements, say $K$ of them. Then there would be a bijection $\psi:\{1,\ldots,K\}\rightarrow \mathbb{N}$.

Let $L=\psi(1)+\psi(2)+\cdots+\psi(K)$. Then $L$ is strictly greater than any of the $\psi(i)$. Therefore $L\notin \operatorname{Range}(\psi)$. so $\psi$ is not onto. This contradiction establishes the theorem. $\Box$.

The following proof of this type is the oldest recorded reductio ad absurdum.

Theorem. (Euclid, ca. 300 BCE) There are infinitely many prime numbers.

Proof. Suppose there were finitely many prime numbers, say $K$ of them. List them all: $p_1,\ldots, p_K$. Consider the numbers \begin{align*}L&=p_1p_2\cdots p_K\\M&=L+1 \end{align*}

Now we know that $M$ has at least one prime factor; call that factor $q$. Observe that $q$ could not be 2, because $L$ is even, so $M$ is odd. Further, $q$ could not be 3, because $L$ is a multiple of 3, so $M$ has remainder 1 when we divide by 3. Proceeding in this way, we find that $q$ cannot be any of the prime numbers we listed.

So we have found a prime that was not on our list, which we supposed to be complete. This contradiction establishes the theorem.$\Box$.

We can also show that a set is infinite by finding an infinite subset:

Theorem. If $A\subseteq B$ and $A$ is infinite, then $B$ is infinite.

Proof. Assume $A\subseteq B$. We will show that if $A$ is infinite, then $B$ is infinite. The contrapositive of this claim is: If $B$ is finite, then $A$ is finite, which we already showed.$\Box$

E.g. $\mathbb{R}$ is infinite.

Actually this can be souped up:

Theorem. If $A$ is infinite and there is an injection $\psi:A\rightarrow B$, then $B$ is infinite.

E.g. $\mathbb{N}\times\mathbb{N}$ is infinite.

Proof. Consider the function $\psi:\mathbb{N}\rightarrow \mathbb{N}\times\mathbb{N}$ given by $\psi(k)=(k,k)$.

If $\psi(k_1)=\psi(k_2)$, then $(k_1,k_1)=(k_2,k_2)$, so $k_1=k_2$. This shows that $\psi$ is an injection, so the above theorem shows that $\mathbb{N}\times \mathbb{N}$ is infinite. $\Box$

$\mathbb{N}$ is in fact the smallest infinite set, in the following sense:

Theorem. Any infinite set has a subset which is equivalent to $\mathbb{N}$.

Proof. Let $X$ be an infinite set. We’ll show, by induction, that we can pick a distinct element $x_n\in X$ for each $n\in\mathbb{N}$.

For the base case, pick $x_1\in X$. Note that $X\setminus\{x_1\}$ is not empty (otherwise $X$ would have had only one element to begin with).

For the inductive step, suppose we’ve picked $x_1,\ldots,x_k$ distinct elements of $X$ already. Then $X\setminus\{x_1,\ldots, x_k\}$ is not empty (otherwise $X$ would have only $k$ elements), so there is some $x_{k+1}\in X$ which is distinct from $x_1,\ldots,x_k$.

Mathematical induction allows us to continue this way to define $x_n$ for any $n\in\mathbb{N}$, thus building a bijection $\mathbb{N}\rightarrow \{x_1,\ldots,x_n,\ldots\}$. $\Box$.

Consider the following question:

Are there more Horsemen of the Apocalypse, or teams in the American Football Conference – East Division?

The standard way to answer this question would be to count each collection. First let’s do the Horsemen of the Apocalypse.

With the help of artist Viktor Vasnetsov, we form a bijection like

We can make a bijection to count the teams of the AFC – East, for example

So the two sets both have four elements, hence are the same size. This is one utility of cardinality: we can check whether two sets are the same size by counting each set, then comparing the resulting numbers.

But what if we didn’t know how to count? You may not remember what it was like not to be able to count (don’t worry, you’ll soon be experiencing that same feeling again), but there was a time when nobody could count.

Overview of Cardinality

• Counting without Counting (this page).
• Finite Sets and Infinite Sets
• Denumerable Sets
• Are All Sets Denumerable? (gosh, it sure seems like it!)
• Cantor’s Little Theorem and Cantor’s Big Theorem

 

One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, … One Hundred

Here are the ways to say some numbers in a few languages of the Indo-European language family:

	French	Latin	Irish	Serbian	German	English
1	un	unus	haon	jedan	ein	one
2	deux	duo	do	dva	zwei	two
3	trois	tres	tri	tri	drei	three
4	quatre	quattuor	ceahtair	četri	vier	four
5	cinq	quinque	cuig	pet	funf	five
6	six	sex	se	šest	sechs	six
7	sept	septem	seacht	sedam	sieben	seven
8	huit	octo	hocht	ossam	acht	eight
9	neuf	novem	naoi	devet	neun	nine
10	dix	decem	deich	deset	zehn	ten
20	vingt	viginti	fiche	dvadeset	zwanzig	twenty
27	vingt sept	viginti septem	fiche seacht	dvadeset sedam	siebenundzwanzig	twenty-seven
81	quatre-vingts un	octoginta unus	ochto a haon	ossamdeset jedan	einundachtzig	eighty-one
100	cent	centum	cead	sto	hundert	one hundred
1000	mille	mille	mile	hiljada	tausend	one thousand

 

There are some interesting patterns here: the word for three is almost identical across all these languages, as are the words for four (sometimes the initial sound is k, sometimes ch, sometimes f, but it always ends in r) and seven. In fact, the numbers 1-10 are what linguists call cognate: they appear to all descend from the same word in the original Proto-Indo-European language, which was spoken somewhere in what’s now Iran or Afghanistan.

Another word that is common across all the languages is the word for one hundred. This one is a little less obvious, but the linguists tell us the Proto-Indo-European word was kmtom. (In some languages that k became a c or s; in others it became an h). So you might be tempted to think that the languages just all have basically the same ways to count.

. . . until you look at the words for 20. In English and German, the word for 20 is derived from the word for 2, but with some decoration. In Serbian, it’s just two tens. The Latin word viginta is derived from the word ginta, which means a group of 10 (which is different from the number 10, sort of like the difference between dozen and twelve), and vi, which is an old word for two (that sounds like the Serbian dva). French vingt is the same as in Latin. In Irish, the word for 20 is just its own thing unrelated to any other numbers.

When we get to 81, each language has its own completely different way to express the number:

French	quatre-vingt un	four-twenty one
Latin	octoginta unus	eight-groups-of-ten one
Irish	ochto a haon	eight+decoration and one
Serbian	ossamdeset jedan	eight-ten one
German	einundachtzig	one and eight+decoration
English	eighty-one	eight+decoration one

 

So what’s going on here? The linguists tell us that the Proto-Indo-Europeans knew how to count to ten, and had a word for one hundred, but didn’t have words for anything in between. The theory is that kmtom didn’t actually mean 100 anyway, just a big number, which the English word hundred sort of still does sometimes — I’ve told you a hundred times rarely means precisely 100. There are also other uses of the word hundred that don’t mean 100 of anything, just some kind of vaguely large number:

• In England and Wales, counties were divided into hundreds: administrative subdivisions which ranged from 50 to 200 households.
• Several units of measurement from medieval English law: a hundredweight is either 108 or 112 pounds, depending; a hundred of herring is 120 fish; a hundred of spices is 108 pounds; a hundred of garlic is 225 bulbs.

From archaeological evidence, we also know that this people-group were pastoralists: they herded sheep and/or goats.  (Archaeologists can’t tell the difference between sheep bones and goat bones.) It takes a lot more than 10 sheep-goats to sustain a family. So how did the Proto-Indo-Europeans manage to keep track of their flocks without being able to count them?

They used bijections, in a way that’s still used to this day by shepherds all around the world. The equipment used is simple: a container and a pile of pebbles. In the morning, as the sheep-goats are leaving their pen, drop a pebble into the container every time a sheep-goat passes you. This is a bijection between the flock and the pebbles in the container. At the end of the day, as the sheep-goats come back into their pen, remove one pebble for each sheep-goat that passes you on its way in. If the container is empty, you know you haven’t lost any animals; if there’s still pebbles left in the container, you know you have lost one.

One needn’t use pebbles; one could instead make marks on a stick with a knife, for example (this method of recordkeeping persisted in Europe through the 1800s, though it ultimately resulted in the destruction of the Houses of Parliament). This is one theory of the origin of the Ishango Bone, one of the world’s oldest surviving mathematical artifacts (dating from before 18,000 BCE):

All of this is to say: if what we’re interested in is comparing the sizes of two sets, we don’t actually need to compute the size of each set and compare them; instead, we can look for bijections between the two sets.