In our previous post, we began a discussion of circularity, first in dictionary definitions and then in mathematics. Today, we dig a little bit deeper by considering what should be a rather straightforward mathematical notion, and certainly a foundational issue for this blog: the definition of the term “finite set”. (And hence, by negation, the definition of “infinite set”. Four years into a blog about infinity and we’re only now rigorously defining what it is we’ve been talking about. How embarrassing!)

We’ve talked about sets quite a bit here; all you need to remember today is that a set is simply a collection of objects. A set can, of course, either be finite or infinite. Most of you reading this probably think that you understand this distinction quite well and, when presented with a relatively simply defined set, you could quite reliably and accurately classify it as either finite or infinite. For example, the set of all real numbers is infinite, whereas the set \{\pi, e, 2\} is finite, as it contains only three elements. This intuitive understanding of “finite” and “infinite” works fine in everyday practice, but it does not amount to a definition, and if we want to study sets generally rather than specific instances of sets, or if we want to study the notion of “infinity”, then it will be important to have a solid definition of the concept “finite set”. And, considering that this is a concept that we are all quite familiar with, this turns out to be surprisingly tricky.

(Before continuing, take a moment to think about how you might try formally to define “finite set”. Can you think of multiple approaches to the task?)

Written 5-12-20, 16-17-1

When asked to define the term “finite set”, an immediate first attempt might be something like this:

Definition Attempt #1: A finite set is a set with only finitely many elements.

This is obviously a bad definition, though. When we’re defining the term “finite set”, what we’re really trying to do is define the word “finite”, so it’s unacceptable to use the word “finite” or “finitely” in its definition.

Let’s think about things a bit more carefully. Saying that a set is finite is making an assertion about its size, so let’s recall how we think about the size of a set. We say that two sets A and B have the same size if their elements can be put into a one-to-one correspondence with one another. Now, when you think about a finite set, you probably think about the act of counting the elements in the set, and eventually completing this count. What do you use to count the elements of the set? The natural numbers! (Recall that natural numbers are whole numbers of the form 0, 1, 2, \ldots.) A finite set should thus be a set whose size is the same as some natural number. This might lead us to formulate the following attempted definition:

Definition Attempt #2: A finite set is a set whose elements can be placed into a one-to-one correspondence with some natural number.

This is much better than Definition Attempt #1, and in fact this is exactly how “finite set” is often defined. When doing mathematics though, we need to make sure we’re being rigorous, so let’s examine this definition a little closer. Our definition makes crucial reference to the notion of a “natural number”, so if we are to declare success, then we should already have a solid definition of “natural number”.

But defining “natural number” is quite tricky in its own right. (Try it!) Notice that, when reminding you what a natural number is a few paragraphs ago, I did so by pointing to some examples, namely 0, 1, and 2, and saying, “it’s like those”. And this is a perfectly valid way of describing the natural numbers in conversational English, but it is certainly not precise enough to rigorously ground mathematics.

So let’s think more carefully about natural numbers. We can certainly talk about certain specific natural numbers, like 0 and 1. For example, 0 is the size of the empty set, and 1 is the size of the set \{\emptyset\}. We can also talk meaningfully about what it means to add 1 to a number: given a number x, find a set A of size x and an object b that is not an element of A, and then say that x + 1 is the size of the set A \cup \{b\} formed by adding b to A as an element.

Now notice that the natural numbers are precisely the numbers you can obtain by starting with 0 and then repeatedly adding 1. (For example, 4 = 0 + 1 + 1 + 1 + 1.) Great. It seems like we now have a fine definition of “natural number”, which in turn means that we have a fine definition of “finite set”. But wait a minute. When we say “repeatedly adding 1”, what do we really mean? How many times are we allowed to “repeatedly add 1”? Well, we want to specify that we’re only allowed to add 1 a finite number of times. But we haven’t defined “finite” yet, and, even worse, our current candidate for a definition of “finite” relies on the notion of “natural number”, so it would create a circle if we were to define “natural number” in terms of “finite”, and since we’re trying to be at least somewhat rigorous here, we definitely want to avoid that.

We could certainly continue down this path if we wanted and isolate a definition of “natural number” that does not depend on the general notion of “finite”. For our purposes, though, I think there’s a shorter, more elegant approach, so let’s change tack slightly. Rather than trying to characterize finite sets, let’s try to characterize infinite sets and use this to arrive at a definition of finiteness.

One of the first observations we make when we start thinking about infinity mathematically is one that might initially be rather unintuitive and disorienting: there are infinite sets A and B such that B obviously contains “more” elements than A, and yet A and B have the same size. The first example you probably saw of this is that in which A is the set of even natural numbers and B is the set of all natural numbers. B obviously contains all of the elements of A plus many more elements that are not in A, and yet we can see that A and B have the same size via the one-to-one correspondence that matches the 0 from A with the 0 in B, the 2 from A with the 1 from B, the 4 from A with the 2 from B, and so on. (I know we made this pivot precisely because we haven’t rigorously defined the notion of “natural number”, but that’s fine. This is just an illustrative example, not a foundational part of what will eventually be our definition.)

When we reflect on this further, this phenomenon in fact seems to be a fundamental feature of what it means for a set to be infinite. Given any infinite set B, it is always possible to find a proper subset A of B such that A and B have the same size (remember that A is a proper subset of B if every element of A is also an element of B but B contains at least one element that is not in A). Indeed, if you start with an infinite set B and simply remove one element from B, you always end up with a set of the same size as B. This is certainly not the case with finite sets. If you have a set of size 6, for instance, and take an element out of it, you now have a set of size 5, which is strictly smaller than your original set. Since this phenomenon seems so characteristic of infinite sets, then, why don’t we take it as the definition of “infinite”, and hence take its negation as the definition of “finite”.

Definition Attempt #3: A finite set is a set with the property that there is no proper subset of the set that has the same size as the set itself. In other words, a set is finite if, whenever you take an element out of the set, you make the set strictly smaller.

This is now a non-circular, rigorous definition (for a certain definition of the word “rigorous”…) and, to my mind at least, it is quite elegant and matches up with our experience and intuition of finite sets.

This definition of “finite” in fact has a relatively long history. It was first proposed by the German mathematician Richard Dedekind in 1888 and was the first modern definition of “finite” that did not rely on the definition of “natural number”. Nowadays, a set satisfying our Definition Attempt #3 is said to be “Dedekind-finite”, while a set satisfying Definition Attempt #2 (after a rigorous definition of “natural number” has been made) is simply said to be “finite”.

Are these two definitions “the same”? Well, they both seem to match our intuition of “finite set”, and for a number of years after the introduction of “Dedekind-finite sets”, it was widely believed among mathematicians that they were the same. And, under the standard axioms of set theory, it is in fact the case that they are the same, i.e., that the finite sets are precisely the Dedekind-finite sets. However, one of these standard axioms of set theory is the sometimes controversial Axiom of Choice. Since the Axiom of Choice often leads to unintuitive consequences (the Banach-Tarski paradox, for instance), mathematicians often like to consider what happens if we don’t adopt the Axiom of Choice. And it turns out that, without the Axiom of Choice, it is impossible to prove that these two definitions of “finite” are the same. In fact, there are mathematical universes that satisfy all of the standard axioms of set theory except for the Axiom of Choice and in which there are sets that are Dedekind-finite and yet are not the same size as any natural number. Try to think about what such a set would be like!

I had meant to use this post to discuss hereditarily finite sets, which provide an example of a mathematical definition that at first glance looks circular but turns out not to be. It took us so much work simply to define finite sets, though, that I think we’ll save that for next time!

Cover image: “Still life, pitcher and fruit,” by Paul Cézanne

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s