Is the Set Concept Intuitive?

10 12 2006

I’ve recently run into two arguments that there is no single intuition behind the notion of set. One was a talk by Tatiana Arrigoni in Berlin that I mentioned earlier, arguing that there may be multiple intuitions underlying set theory. Another was a talk by Jose Ferreiros at the Berkeley Logic Colloquium last week, arguing that there isn’t even one intuition underlying the notion of set.

Ferreiros started by pointing out that the 19th century founders of modern set theory (Cantor, Frege, and Dedekind) all seemed to be working with different notions. In particular, Cantor seemed to never consider a set as an element of a further set (his famous theorem was apparently proved about the set of functions on a given set, rather than using the modern notion of a power set). In addition, recognizing some paradoxes that would result from this theorem, he rejected the notion of a set of everything. His notion was fairly close to the intuitive notion of “collection” that we often introduce students to set theory with.

Frege (and Russell, following him) thought of sets as extensions of concepts, or as some way of dividing the universe into two parts. It’s a more “top-down” notion than the others, because of the sort of impredicativity involved in dividing a totality (including the set to be defined) into two parts. This notion is probably closest to our intuitive notion of “property” that the set concept seems to inherit some of from the separation axiom.

Dedekind had a slightly different conception from either. I didn’t quite get the details, but it sounds like it was the only notion that was relatively close to the modern “iterative conception” championed later by Gödel (among others).

The fact that our modern notion of set has inherited properties from each of these suggests that it is not a rigorization of any of these intuitive concepts. He also gave some other arguments, based on the fact that we have intuitions about the existence of “absolutely arbitrary” subsets of any given set, which aren’t successfully cashed out in any of our axioms, but are approximated by the axioms of separation and choice.

Size of a Set

9 12 2006

My good friend Dan Korman from UT Austin has now joined the blog at Close Range, starting with a provocative post arguing that the traditional analysis of “size of a set” as “equivalence class under bijections (one-one mappings)” is incorrect. I’d like to suggest that there is no fact of the matter as to what the “size of a set” is, and that our intuitions correspond to multiple distinct notions, rather than just one notion as Dan (and those who argue in favor of the bijection analysis) suggest.

I will start with an argument from the first page of Gödel’s “What is Cantor’s Continuum Problem?”

This question [Cantor’s continuum problem], of course, could arise only after the concept of “number” had been extended to infinite sets; hence it might be doubted if this extension can be effected in a uniquely determined manner … Cantor’s definition of infinite numbers really has this character of uniqueness. For whatever “number” as applied to infinite sets may mean, we certainly want it to have the property that the number of objects belonging to some class does not change if, leaving the objects the same, one changes in any way whatsoever their properties or mutual relations (e.g., their colors or their distribution in space). From this, however, it follows at once that two sets (at least two sets of changeable objects of the space-time world) will have the same cardinal number if their elements can be brought into a one-to-one correspondence, which is Cantor’s definition of equality between numbers. For if there exists such a correspondence for two sets A and B it is possible (at least theoretically) to change the properties and relations of each element of A into those of the corresponding element of B, whereby A is transformed into a set completely indistinguishable from B, hence of the same cardinal number.

There are two premises: 1. Changing the properties of the elements of a set doesn’t change the size of the set. 2. If two sets are “completely indistinguishable”, then they have the same size. One may also count a third premise: 3. The properties and relations of any set of physical objects may be changed arbitrarily.

Gödel doesn’t quite spell out what “completely indistinguishable” means. He can’t mean just that every sentence true of the elements of one set is true of the elements of the other (i.e., that they are elementarily equivalent as models), because the Löwenheim-Skolem Theorem guarantees that for every infinite set, we can find an elementarily equivalent model of every infinite cardinality. Thus, this interpretation of the term would collapse all infinite cardinalities, and not just the bijectable ones. (Presumably, the lack of a bijection between two sets should guarantee that they’re not the same size, so that any acceptably notion of size must be at least as fine-grained as the standard one, though it’s not absolutely clear why this is intuitive.)

But assuming that being “completely indistinguishable” makes sense, the argument goes through for sets of physical objects. To extend it to arbitrary sets, we either have to assume that the properties and relations of any set of objects can be changed arbitrarily (which seems false in the case of numbers), or else strengthen the first premise to say that replacing elements of a set by other objects doesn’t change the size of the set. This may be a reasonable strengthening, but it does seem dangerously close to assuming the bijection notion of size.

But if these concerns can be fixed, then it looks like the bijection notion is the correct notion of size for infinite sets. Even otherwise, it’s probably the coarsest-grained such notion that could possibly be correct.

Dan discusses another notion that is finer grained: “If S1 is a proper subset of S2, then S1 has fewer members than S2”. This notion conflicts with the bijection notion, but it doesn’t fully specify when two sets have the same size – after all, it doesn’t say anything about two distinct singletons, so we should specify, “any two singletons have the same size”. We can extend this to a consistent notion by saying in addition: “if the set of elements in S1 but not S2 is the same size as the set of elements in S2 but not S1, then S1 and S2 have the same size”. Now these three principles yield all the standard judgments about sizes of finite sets, but still leave many pairs of infinite sets incomparable in size. This may be a flaw, but it is a flaw that the bijection theory shares if one rejects the axiom of choice. I believe this is probably the finest-grained notion that is permissible.

I’d like to suggest that these two notions are both usable notions of size for sets, and the reason we seem to have conflicting intuitions is that our intuitive judgments don’t track one rather than the other. Just as there is no single intuitive notion of set, there is no single intuitive notion of size of a set.

And this shouldn’t be too surprising – mathematicians have come up with many other notions for size of sets that are finer-grained than cardinality, some of which have strong intuitive justifications like Dan’s. For sets of points in some sort of geometric space, the next coarsest-grained notion after cardinality is that of dimension – we say that a cube is in some sense “larger” than any rectangle, even though both have the same cardinality (equal to the continuum), because it is a higher dimension. (Of course, it’s quite unclear what our intuitions say about the relative size of a 1 mm cube and a 10 km square with absolutely no thickness.) To get even finer-grained, we can consider the notion of “measure”, which is a generalization of the notion of length/area/volume/whatever-is-appropriate-in-this-dimension. None of these notions is fine enough to say that an open interval is smaller than the corresponding closed interval (which Dan would like to say, I suppose), but they are all usable notions of size. There are some other problems some of them face, but they’re still all interesting.

I think Dan approaches this solution in the comments, but suggests that the honorific term “size” should be reserved for the finest-grained notion. I suggest instead that there’s no fact of the matter as to which should get that term, and set theorists have settled on cardinality as the basic one for technical and theoretical reasons, which are the only reasons that are applicable. However, topologists and analysts are more interested in the dimension and measure notions respectively, so these are also equally good notions. Whether there are enough technical advantages to the more fine-grained notion Dan suggests is unclear, but I don’t see that this should disqualify it from being an acceptable notion.