Friday, 28 March 2014

Counting Infinities

(Cross-posted at NewAPPS)

In his Two New Sciences (1638), Galileo presents a puzzle about infinite collections of numbers that became known as ‘Galileo’s paradox’. Written in the form of a dialogue, the interlocutors in the text observe that there are many more positive integers than there are perfect squares, but that every positive integer is the root of a given square. And so, there is a one-to-one correspondence between the positive integers and the perfect squares, and thus we may conclude that there are as many positive integers as there are perfect squares. And yet, the initial assumption was that there are more positive integers than perfect squares, as every perfect square is a positive integer but not vice-versa; in other words, the collection of the perfect squares is strictly contained in the collection of the positive integers. How can they be of the same size then?

Galileo’s conclusion is that principles and concepts pertaining to the size of finite collections cannot be simply transposed, mutatis mutandis, to cases of infinity: “the attributes "equal," "greater," and "less," are not applicable to infinite, but only to finite, quantities.” With respect to finite collections, two uncontroversial principles hold:

Part-whole: a collection A that is strictly contained in a collection B has a strictly smaller size than B.

One-to-one: two collections for which there exists a one-to-one correspondence between their elements are of the same size.

What Galileo’s paradox shows is that, when moving to infinite cases, these two principles clash with each other, and thus that at least one of them has to go. In other words, we simply cannot transpose these two basic intuitions pertaining to counting finite collections to the case of infinite collections. As is well known, Cantor chose to keep One-to-one at the expenses of Part-whole, famously concluding that all countable infinite collections are of the same size (in his terms, have the same cardinality); this is still the reigning orthodoxy.

In recent years, an alternative approach to measuring infinite sets is being developed by the mathematicians Vieri Benci (who initiated the project) Mauro Di Nasso, and Marco Forti. It is also being further explored by a number of people – including logicians/philosophers such as Paolo Mancosu, Leon Horsten and my colleague Sylvia Wenmackers. This framework is known as the theory of numerosities, and has a number of theoretical as well as more practical interesting features. The basic idea is to prioritize Part-whole over One-to-one; this is accomplished in the following way (Mancosu 2009, p. 631):

Informally the approach consists in finding a measure of size for countable sets (including thus all subsets of the natural numbers) that satisfies [Part-whole]. The new ‘numbers’ will be called ‘numerosities’ and will satisfy some intuitive principles such as the following: the numerosity of the union of two disjoint sets is equal to the sum of the numerosities.
Basically, what the theory of numerosities does is to introduce different units, so that on these new units infinite sets comes out as finite. (In other words, it is a clever way to turn infinite sets into finite sets. Sounds suspicious? Hum…) In practice, the result is a very robust, sophisticated mathematical theory, which turns the idea of measuring infinite sets upside down.

The philosophical implications of the theory of numerosities for the philosophy of mathematics are far-reaching, and some of them have been discussed in detail in (Mancosu 2009). Philosophically, the mere fact that there is a coherent, theoretically robust alternative to Cantorian orthodoxy raises all kinds of questions pertaining to our ability to ascertain what numbers ‘really’ are (that is, if there are such things indeed). It is not surprising that Gödel, an avowed Platonist, considered the Cantorian notion of infinite number to be inevitable: there can be only one correct account of what infinite numbers really are. As Mancosu points out, now that there is a rigorously formulated mathematical theory that forsakes One-to-one in favor of Part-whole, it is far from obvious that the Cantorian road is the inevitable one.

As mathematical theories, Cantor’s theory of infinite numbers and the theory of numerosities may co-exist in peace, just as Euclidean and non-Euclidean geometries live peacefully together (admittedly, after a rough start in the 19th century). But philosophically, we may well see them as competitors, only one of which can be the ‘right’ theory about infinite numbers. But what could possibly count as evidence to adjudicate the dispute?

One motivation to abandon Cantorian orthodoxy might be that it fails to provide a satisfactory framework to discuss certain issues. For example, Wenmackers and Horsten (2013) adopt the alternative approach to treat certain foundational issues that arise with respect to probability distributions in infinite domains. It is quite possible that other questions and areas where the concept of infinity figures prominently can receive a more suitable treatment with the theory of numerosities, in the sense that oddities that arise by adopting Cantorian orthodoxy can be dissipated.

On a purely conceptual, foundational level, the dispute might be viewed as one between Part-whole and One-to-one, as to which of the two is the most fundamental principle when it comes to counting finite collections – which would then be generalized to the infinite cases. They are both eminently plausible, and this is why Cantor’s solution, while now widely accepted, remains somewhat counterintuitive (as anyone having taught this material to students surely knows). Thus, it is hard to see what could possibly count as evidence against one or the other


Now, after having thought a bit about this material (prompted by two wonderful talks by Wenmackers and Mancosu in Groningen yesterday), and somewhat to my surprise, I find myself having a lot of sympathy for Galileo’s original response. Maybe what holds for counting finite collections simply does not hold for measuring infinite collections. And if this is the case, our intuitions concerning the finite cases, and in particular the plausibility of both Part-whole and One-to-one, simply have no bearing on what a theory of counting infinite collections should be like. There may well be other reasons to prefer the numerosities approach over Cantor’s approach (or vice-versa), but I submit that turning to the idea of counting finite collections is not going to provide relevant material for the dispute in the infinite cases. In fact, from this point of view, an entirely different way of measuring infinite collections, where neither Part-whole nor One-to-one holds, is at least in principle conceivable. In what way the term ‘counting’ would then still apply might be a matter of contention, but perhaps counting infinities is a totally different ball game after all.

4 comments:

  1. Nice ideas. Maybe they could also find an application in formal semantics, where most of the models are restricted to finite universes? It is usually justified but sometimes we also want to talk about natural numbers, e.g., say "There are more non-primes than primes among integers" with an intention that the sentence is actually true. There is not much literature treating that problem, that I'm aware of. One existing proposal is to treat quantifiers in such sentences as measure quantifiers (so-called ambiguous quantifiers): in infinite universes we can compare quantities by a proper measure functions. For instance, a proper measure function would make the above sentence true as primes become less common as the numbers become larger (asymptotic distribution from Prime Number Theorem). However, that is not a very satisfactory solution as measures are non-logical and context dependent.

    ReplyDelete
  2. Sigh, so now that NF has turned out (or is very likely) to be a "vanilla" logical system, one needs to come up with new shiny 'alternatives' somehow?

    ReplyDelete
  3. Interesting. I Googled the subject and found this quote from one of the key papers:

    "Extending this property to uncountable sets seems to be a difficult problem"

    http://www.ams.org/journals/tran/2010-362-10/S0002-9947-2010-04919-0/

    So let's not hold that wake for Cantor's theory just yet.

    ReplyDelete
    Replies
    1. Correction, "this property" seems to refer to an attribute of their measure (if I can call it that) and not to the entire idea. It's not clear whether they have extended their ideas to uncountable sets or not. Catarina, can you give a summary of the technical ideas? That was missing from your article.

      Delete