The (Ultra)finitists

Infinity is a fascinating and seductive topic, but it is also a contentious one and, throughout intellectual history, has been attacked on religious, philosophical, and practical grounds. Today, we turn away from the vastness of infinity and toward those who deny its existence.

Consider the Pythagoreans, followers of the famous 6th century BC Greek philosopher. According to the Pythagoreans, numbers are the first of all beings the “dominant and self-produced bond of the eternal continuance of things.” Pythagoreans saw numbers in everything, from the motions of the planets to musical harmony. But they saw only rational numbers, i.e. ratios of finite integers; according to legend, the Pythagorean Hippasus was drowned at sea after proving that \sqrt{2} is irrational.

As we have mentioned in earlier posts, actual infinity did not establish a real foothold in mathematics until the late 19th century and the work of Dedekind and Cantor, which naturally engendered fierce opposition. Perhaps the most prominent opponent of Cantorian set theory was Leopold Kronecker, who is widely known for having said, “God made the integers, all else is the work of man” and thought that irrational numbers do not exist. I have given this exact quote before, but I will do so again now:

I don’t know what predominates in Cantor’s theory – philosophy or theology, but I am sure that there is no mathematics there.

Finitism, the philosophy of mathematics that denies the existence of infinite objects, is today a minority view but is nonetheless very much alive, and a number of mathematicians are doing work to remove infinities (and, hence, irrationalities) from mathematics. Among these is N.J. Wildberger, a professor at the University of New South Wales who is developing what he calls Rational Trigonometry, a reworking of trigonometry replacing the notions of ‘distance’ and ‘angle,’ which readily produce irrational numbers even when applied only to points with rational coordinates, with ‘quadrance’ and ‘spread’ to measure the amount of separation between two points and two lines, respectively.

(A related but separate movement, which we will return to in a later post, is the attempt by prominent scientists such as Max Tegmark and Raphael Bousso, to remove infinities from physics. The assertion that our physical universe is entirely finite is a weaker (and, in my opinion, much more plausible) assertion than the assertion that infinity does not exist mathematically, and we will devote attention to it in the future.)

There are some, though, for whom the finitists do not go far enough. These people, known as ‘ultra-finitists,’ not only deny the existence of mathematical infinity but even refrain from accepting the existence of very large finite integers. For example, let N be the largest integer less than e^{e^{e^{79}}}, a number known as Skewes’ number and that has appeared in proofs in number theory. An ultra-finitist will likely refrain from accepting the existence of N on the basis that this natural number has not actually been calculated and may in fact be too large to be physically calculated at all.

Ultra-finitism in its modern guise was initiated by Alexander Yessenin-Volpin, a mathematician who was a prominent human-rights activist in the Soviet Union, for which he was imprisoned in 1968. There is a wonderful anecdote about him from Harvey Friedman, who had occasion to confront him about his extreme ultra-finitist views.

I have seen some ultrafinitists go so far as to challenge the existence of 2100 as a natural number, in the sense of there being a series of “points” of that length. There is the obvious “draw the line” objection, asking where in 21, 22, 23, … , 2100 do we stop having “Platonistic reality”? Here this … is totally innocent, in that it can be easily be replaced by 100 items (names) separated by commas. I raised just this objection with the (extreme) ultrafinitist Yessenin-Volpin during a lecture of his. He asked me to be more specific. I then proceeded to start with 21 and asked him whether this is “real” or something to that effect. He virtually immediately said yes. Then I asked about 22, and he again said yes, but with a perceptible delay. Then 23, and yes, but with more delay. This continued for a couple of more times, till it was obvious how he was handling this objection. Sure, he was prepared to always answer yes, but he was going to take 2100 times as long to answer yes to 2100 then he would to answering 21. There is no way that I could get very far with this.

Harvey M. Friedman “Philosophical Problems in Logic”

Perhaps the most prominent ultra-finitist working today is Doron Zeilberger, a mathematician at Rutgers. Zeilberger, like many ultra-finitists, believe there is a largest natural number. When asked the inevitable question about what happens when you add 1 to it, he replies that, in a very elegant circularity, you go back to 0. Zeilberger also has a fascinating web page of his Opinions. I present to you in full Opinion 146: Why the “fact” that 0.99999999…(ad infinitium)=1 is NOT EVEN WRONG.

The statement of the title, is, in fact, meaningless, because it tacitly assumes that we can add-up “infinitely” many numbers, and good old Zenon already told us that this is absurd.

The true statement is that the sequence, a(n), defined by the recurrence

a(n)=a(n-1)+9/10n   a(0)=0   ,

has the finitistic property that there exists an algorithm that inputs a (symbolic!) positive rational number ε and outputs a (symbolic!) positive integer N=N(ε) such that

|a(n)-1|<ε for (symbolic!) n>N   .

Note that nowhere did I use the quantifier “for every”, that is completely meaningless if it is applied to an “infinite” set. There are no infinite sets! Everything can be reduced to manipulations with a (finite!) set of symbols.

We end with the classic instructional video, “Look Around You (Maths),” which addresses ultra-finitism in its first segment. Enjoy!

Look Around You (Maths) from Numbers on Vimeo.

Measuring II: The limits of measurability

Last week, we considered the problem of measuring all subsets of a given finite or countably infinite set. Today, we will investigate the problem of measuring subsets of an uncountable set. In fact, we will focus on a particular uncountable set, which happens to be one of the most important sets in all of mathematics: the set of real numbers, \mathbb{R}.

There are certain subsets of \mathbb{R} which we have a very natural and well-behaved method for measuring: the intervals. Recall that, if a \leq b are real numbers, then:

  • (a,b) is the set of all real numbers x such that a < x < b. Such a set is called an open interval.
  • [a,b] is the set of all real numbers x such that a \leq x \leq b. Such a set is called a closed interval.
  • In either case, a and b are said to be the endpoints of the interval.

The most natural way to measure an interval is simply to subtract the lower endpoint from the upper one, i.e., if a \leq b, then m((a,b)) = m([a,b]) = b-a. Note that, as a result of this, any one-element subset of \mathbb{R} is assigned a measure of 0, since, if a \in \mathbb{R}, then m(\{a\}) = m([a,a]) = a-a = 0.

There’s no reason to stop at intervals, though. Consider a set A that consists of two disjoint intervals, i.e. intervals I_0 and I_1 such that I_0 \cap I_1 = \emptyset. The natural measure to assign to A is, of course, m(I_0) + m(I_1). Extrapolating, if n \geq 2 is a natural number and A consists of n pairwise disjoint intervals, i.e. intervals I_0, I_1, \ldots I_{n-1} such that, for all i < j < n, I_i \cap I_j = \emptyset, then we should set m(A) = m(I_0) + m(I_1) + \ldots + m(I_{n-1}).

There’s no reason to stop at finite unions of intervals, either. As those of you who have taken calculus courses will know, there is a well-developed theory of infinite sums of positive real numbers, so it makes sense to measure sets that are unions of countably infinitely many pairwise disjoint intervals in the same way. More precisely, if A is the union of countably many pairwise disjoint intervals I_0, I_1, \ldots , then we can let \displaystyle m(A) = m(I_0) + m(I_1) + \ldots = \sum_{k=0}^\infty m(I_k).

Note, in particular, that if A is a countable subset of \mathbb{R}, then m(A) = 0. This is because A can be considered to be a countable union of pairwise disjoint intervals, each consisting of precisely one element. Since one-element sets are given a measure of 0, we then have m(A) = 0 + 0 + \ldots = 0.

Let \mathcal{X} be the collection of all subsets of \mathbb{R} that can be written as countable unions of pairwise disjoint intervals. In other words, \mathcal{X} consists of precisely those sets to which we have assigned a measure. (Those of you with some prior knowledge might object here that, as I’ve made it this far, I may as well just keep going and define the measure on the collection of all Borel sets rather than this clearly unsatisfactory collection \mathcal{X}. You might be right.) This measure, m, that we have constructed has some very nice properties. We list some of them here.

  1. For all A \in \mathcal{X}, 0 \leq m(A) \leq \infty.
  2. m(\emptyset) = 0 and m(\mathbb{R}) = \infty.
  3. For any a \leq b, m((a,b)) = m([a,b]) = b-a.
  4. (Monotonicity) If A,B \in \mathcal{X} and A \subseteq B, then m(A) \leq m(B).
  5. (Countable additivity) If \{A_n \mid n \in \mathbb{N}\} is a collection of pairwise disjoint elements of \mathcal{X}, then \displaystyle m(\bigcup_{n \in \mathbb{N}}A_n) = \sum_{n \in \mathbb{N}} A_n.
  6. (Shift invariance) If A \in \mathcal{X} and r \in \mathbb{R}, then, if A + r is the set we get by “shifting” A over by r, i.e. A+r = \{a+r \mid a \in A\}, then m(A+r) = m(A).

Take a minute to think about these properties. I hope you will agree with me that they are all natural properties that one would like to require of a reasonable measure of subsets of \mathbb{R}.

There is a small problem, though. Our measure, m, does not measure all subsets of \mathbb{R}, only those in \mathcal{X}. And there are many subsets of \mathbb{R} that are not in \mathcal{X}. One can see this just by counting: there are only 2^{\aleph_0} members of \mathcal{X}, whereas the number of all subsets of \mathbb{R} is 2^{2^{\aleph_0}}, which is strictly larger than 2^{\aleph_0}. Compared with the vast expanses of the full power set of \mathbb{R}, our set \mathcal{X} looks positively puny.

So this raises a question: Can we extend our measure m so that it measures all subsets of \mathbb{R} while still maintaining the nice properties 1-6 listed above? Interestingly, the answer, discovered by Italian mathematician Giuseppe Vitali in the early 20th century, is no.

(You may be initially disappointed by this answer, but I would argue that this makes life much more interesting. Vitali’s discovery came in an era of great upheaval and progress in mathematics, and his discovery, along with others of the time, laid the groundwork for some of the most important and fascinating achievements of the 20th century.)

Let us reconstruct Vitali’s argument. Suppose for the sake of a contradiction that we have a measure m satisfying properties 1-6 that measures all subsets of \mathbb{R}. First, we will define an equivalence relation, \sim, on the interval (0,1) by setting r \sim s if and only if r - s is rational. I’ll leave it to the reader to check that this is an equivalence relation, recalling that an equivalence relation must satisfy the following requirements:

  1. (Reflexivity) For every r, we have r \sim r.
  2. (Symmetry) For every r and s, if r \sim s, then s \sim r.
  3. (Transitivity) For every r, s, and t, if r \sim s and s \sim t, then r \sim t.

For each r \in (0,1), let [r] denote the equivalence class of r, i.e. the set \{s \in (0,1) \mid r \sim s\}. Since \sim is an equivalence relation, the equivalence classes partition \mathbb{R} into pairwise disjoint sets. In particular:

  • For every r \in (0,1), r \in [r].
  • For every r and s in (0,1), either [r] = [s] or [r] \cap [s] = \emptyset.

Let \mathcal{C} be the set of equivalence classes, and pick a choice function on \mathcal{C}, i.e. a function F:\mathcal{C} \rightarrow (0,1) such that, for every D \in \mathcal{C}, F(D) \in D. Let A = \{F(D) \mid D \in \mathcal{C}\} and note that, for every D \in \mathcal{C}, |A \cap D| = 1. If q \in (-1,1) is a rational number, let A + q denote the set A shifted by q, i.e. the set \{r + q \mid r \in A\}.

Claim 1: If q_0 and q_1 are distinct rational numbers in (-1,1), then (A + q_0) \cap (A + q_1) = \emptyset.

Proof: Suppose for the sake of a contradiction that there is a real number s in (A + q_0) \cap (A + q_1). Then there are r_0, r_1 \in A such that r_1 + q_1 = s = r_0 + q_0. But then r_1 - r_0 = q_0 - q_1. Since q_0 and q_1 are rational, q_0 - q_1 is rational, so r_1 \sim r_0. Moreover, since q_0 and q_1 are distinct, q_0 - q_1 \neq 0, so r_0 \neq r_1. But then A contains at least two elements of [r_0] (namely, r_0 and r_1), contradicting the fact that A intersects each equivalence class in only one element and finishing the proof of the claim.

Claim 2: Let B = \bigcup_{q \in \mathbb{Q} \cap (-1,1)}( A + q). Then (0,1) \subseteq B \subseteq (-1,2).

Proof: We first show (0,1) \subseteq B. To this end, fix s \in (0,1). By construction, we can find a real number r in A \cap [s]. Let q = s-r. Since s\sim r, q is rational. Since r,s \in (0,1), we must have q \in (-1,1). But then s \in A + q and A + q \subseteq B, so s \in B. Since s was arbitrary, we have (0,1) \subseteq B.

To see that B \subseteq (-1,2), fix s \in B. There is r \in A and q \in \mathbb{Q} \cap (-1,1) such that s = r+q. Since r \in (0,1), this means -1 < s < 2. Thus, B \subseteq (-1,2). This ends the proof of the claim.

Since m measures every subset of \mathbb{R}, it must measure A + q for every q \in \mathbb{Q} \cap (-1,1) and B. By shift invariance of m (requirement 6), it must be the case that m(A+q) = m(A) for every q \in \mathbb{Q} \cap (-1,1). By countable additivity of m (requirement 5) and Claim 1, we must have m(B) = \sum_{q \in \mathbb{Q} \cap (-1,1)}m(A+q). By Claim 2 and monotonicity of m (requirement 4), we must have 1 \leq m(B) \leq 3.

But these things together yield a contradiction! Let x = m(A). Then m(B) = \sum_{q \in \mathbb{Q} \cap (-1,1)} x = x + x + x + \ldots. If  x = 0, this sum is 0, so m(B) = 0. If x > 0, this sum is infinite, so m(B) = \infty. In either case, m(B) is not in the interval [1,3], as it is supposed to be. Therefore, we have identified a set (namely, A), that cannot be measured by m, which is a contradiction to our assumptions.

Closing remark: Getting our set A required an application of the axiom of choice, and it turns out that this use of choice is necessary to find a non-measurable set. In one of the great achievements of modern set theory, Robert Solovay proved in 1970 that it is consistent with ZF (i.e. all axioms of set theory except the axiom of choice) that there is a measure satisfying requirements 1-6 and measuring all subsets of the reals. In fact, the measure that works is the one that has become the canonical measure on the reals: the Lebesgue measure, introduced by Henri Lebesgue in 1901 and the subject of the next installment of this series.

Measuring I: First steps

The development of much of the earliest mathematics in human civilization was driven by the need to measure certain quantities: the amount of food harvested, the distance between cities, the area of land in a plot. These measurements, grounded as they were in the physical world, were entirely finite in character: the practical result of a measurement is a rational number, expressible as a ratio of finite integers. And, being entirely finite, they posed no serious foundational problems. But what happens when we remove measurement from the practical world of the finite? As we will see, when we start venturing into the realm of the infinite (which we can’t help ourselves from doing…) things become more complicated and more interesting.

In this intermittent series, we will look at various instances of “measuring” in mathematics and the sciences, paying particular attention to their interactions with the infinite. We will visit fin de siècle France, Poland in the 1930s, and the edges of a young universe. We will consider the development of the Lebesgue measure, climb the hierarchy of large cardinals, and look into the measure problem of cosmology. Today, though, we will simply try to count things.

Let us look at a particularly simple type of measure, known suggestively as the counting measure. Suppose we have a large but finite collection of objects: 10,000 potatoes, say. And suppose we want to describe a way to measure subsets of this collection. And suppose also that, for either practical or aesthetic reasons, we want the measure of the entire collection to be 1. There is a very natural candidate for this. Let P denote the set of all 10,000 potatoes. Given a subset A \subseteq P, let its measure, which we denote m(A), simply be \frac{|A|}{10,000}. In other words, m(A) is simply the proportion of all potatoes in P that happen to lie in A.

This measure m has the following attractive properties.

  • For all A \subseteq P, 0 \leq m(A) \leq 1.
  • m(\emptyset) = 0.
  • m(P) = 1.
  • If A and B are disjoint subsets of P, i.e. A, B \subseteq P and A \cap B = \emptyset, then m(A \cup B) = m(A) + m(B).

This is all well and good, but, being the sophisticated mathematicians that we are, we might get bored with this and want to measure subsets of an infinite set. So, suppose we now have a countably infinite set P and we want a measure m on all subsets of P satisfying the following.

  1. For all A \subseteq P, 0 \leq m(A) \leq 1.
  2. m(\emptyset) = 0.
  3. m(P) = 1.
  4. For all p,q \in P, m(\{p\}) = m(\{q\}) (i.e. all one-element subsets of P get the same measure).
  5. If \{A_n \mid n \in \mathbb{N}\} is a collection of pairwise disjoint subsets of P (i.e., for all m < n in \mathbb{N}, we have A_m \cap A_n = \emptyset), then m(\bigcup_{n \in \mathbb{N}} A_n) = \sum_{n \in \mathbb{N}} m(A_n).

These seem like pretty natural requirements for a measure, and they generalize the attractive properties that do hold of the finite counting measure, but now we have a problem! For, suppose that we actually had such a measure, m. Let r be the unique real number, which exists by requirement 4, such that m(\{p\}) = r for all p \in P. Note that, by requirements 3 and 5 and the fact that P is countable, we must have:

1 = m(P) = m(\bigcup_{p \in P} \{p\}) = \sum_{p \in P} m(\{p\}) = \sum_{p \in P} r.

If r=0, then this sum is simply 0, so we obtain 0 = 1, which is a contradiction. If r > 0, though, things aren’t any better. In that case, the sum is r+r+r+\ldots = \infty, so we obtain \infty = 1, another contradiction.

The situation can be somewhat salvaged, though, if we weaken requirement 5 to only deal with finite collections of sets:

5*. If A and B are disjoint subsets of P, then m(A \cup B) = m(A) + m(B).

We first note that, if m is any measure satisfying requirements 1-4 and 5*, and r is the unique number such that m(\{p\}) = r for all p \in P, then in must be the case that r = 0. To see this, suppose it were not the case. Then there is some natural number n \in \mathbb{N} such that n \times r > 1. Let A be a subset of P of size n. Then, by repeated applications of requirement 5*, we obtain:

m(A) = m(\bigcup_{a \in A}\{a\}) = \sum_{a \in A}m(\{a\}) = n \times r > 1,

contradicting requirement 1.

This should make sense; in the context of an infinite set, any single element should seem exceedingly small. Negligible, even.

Ok, fine, but have we really gained anything by replacing requirement 5 with 5*. Is there a measure satisfying these new requirements? Yes, there is, and there’s even one that’s quite easy for us to describe. Simply let \mathcal{U} be a non-principal ultrafilter on P, and define a measure m by

m(A) = \begin{cases} 1 & \mbox{ if } A \in \mathcal{U} \\ 0 & \mbox{ if } A \not\in \mathcal{U}. \end{cases}

It is immediate that m satisfies requirements 1-3. Also, as \mathcal{U} is non-principal, \{p\} \not\in \mathcal{U} for all p \in P, so m(\{p\}) = 0 for all p \in P and m thus satisfies requirement 4.

It remains to verify requirement 5*. To do this, suppose A and B are disjoint subsets of P. Note first that it cannot be the case that A and B are both members of \mathcal{U}, for, if they were, then, by the definition of ultrafilter, we would also have A \cap B \in \mathcal{U}. But, as A and B are disjoint, A \cap B = \emptyset, and \emptyset \not\in \mathcal{U} (again by the definition of ultrafilter). Therefore, one or both of A and B is not in \mathcal{U}.

Suppose first that neither A nor B is in \mathcal{U}. Then P \setminus A and P \setminus B are both in \mathcal{U}, since \mathcal{U} is an ultrafilter. Therefore, (P \setminus A) \cap (P \setminus B) = (P \setminus (A \cup B)) \in \mathcal{U}, so A \cup B \not\in \mathcal{U}. Therefore, m(A \cup B) = 0 = 0+0 = m(A) + m(B).

Suppose next that one of the sets is in \mathcal{U} and the other is not. Since the two situations are symmetric, we may assume that A \in \mathcal{U} and B \not\in \mathcal{U}. Then, since A \subseteq A \cup B, we have A \cup B \in \mathcal{U}, so m(A \cup B) = 1 = 1+0 = m(A) + m(B). Therefore, we have verified requirement 5* in all possible situations.

Exercise for the reader: Suppose P = \mathbb{N}, E is the set of even natural numbers, and O is the set of odd natural numbers. Construct a measure m on the subsets of P satisfying requirements 1-4 and 5* and such that m(E) = m(O) = \frac{1}{2}.

Reading Assignment I

I mean how could you get them all to stay still?

-Billy Collins, “Cosmology”

Remember Bertrand Russell and his infinite stack of turtles? So does Billy Collins, whose poem “Cosmology” appeared in the September 5 issue of The New Yorker.

Over at Nautilus, Trevor Quirk addresses “The Problem With Science Writing” and the difficulties of accurately and appealingly communicating scientific ideas to the public without being overly reductive (writing this blog has given me some first-hand experience of these difficulties).

One of the works Quirk brings up is David Foster Wallace’s Everything and More: A Compact History of Infinity, a book that I read at the very outset of my graduate study and about which I have very conflicted feelings. On the one hand, I am a big fan of Wallace’s writing, the book’s attempt to explain technical material in a way that is both accessible and integrated into a historical narrative is admirable, and there is some good stuff in the book (particularly the material early on about the Greeks). On the other hand, the book contains a huge number of technical errors and misleading statements, a fact made more egregious by the at times irritatingly arrogant tone of the prose. It sometimes feels as if Wallace is saying, “This is really complicated stuff, and not many people can truly understand it. Let me explain it to you.” before getting something completely wrong. It is a testament to Wallace’s writing and the book’s ambitions that, despite this, I still would not necessarily attempt to dissuade someone from reading it.

Really, though, you should just go read Infinite Jest.