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.

Advertisements

Actions

Information

13 responses

11 12 2006
Aidan

“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.”

Does this proposal vindicate Dan’s original intuitions, that there are more square roots than squares and more naturals than evens? Incomparability doesn’t look like what Dan was after.

11 12 2006
Kenny

Since I’ve stipulated that a proper subset is smaller than the whole set, then it does. However, it does have some odd properties. If space is infinite in extent, then this notion of size isn’t translation invariant – pick some point, and consider the set of all points farther east than that one (extending out to infinity). If you translate this set to the east, then you get a proper subset of the original set, so it should be smaller.

Of course, if you’re talking about actual points of space, then you can’t move them, so the translation part doesn’t apply. And if you’re talking about object occupying those points, then the new set is not a proper subset of the original one, so it’s technically consistent. But now you can’t compare the size of a set of point-masses and the size of the set of points of space they occupy.

In some sense though, translation invariance relies on the intuition that replacement doesn’t change sizes, which is exactly what Gödel needs to complete his argument. So there are conflicting intuitions here.

12 12 2006
Shawn

That was an interesting post. I’ve got a question about one of the additional principles you suggest for Korman’s intuitive notion of size, namely the one that says “if the set of elements in S1 but not S2…”. This principle invokes a notion of size for sets with disjoint members. Does it not presuppose the bijection notion of size? If not, what sort of size did you mean?

The points about topology and analysis were good. It seems that if we ask what size a set is, it should be further specified what sort of size. Just leaving it at “size,” unless implicit from context, will leave it open. There’re different notions of size in normal conversation just as there are different notions of size in math.

12 12 2006
Kenny

Ah, right, I should have been more clear. I intended that to be a somewhat recursive clause. If x and y are different objects not in A, then we can use the singleton principle to see that {x} is the same size as {y}. This principle then lets us conclude that A u {x} is the same size as A u {y}. I suppose I should have also stated that we want to take the transitive closure of this relation. Then, we can use this sort of argument to show that sameness of size works just as we expect for finite sets. Thus, if two sets differ by only finitely many elements, then we can compare their sizes. (Similarly if only one has finitely many elements that don’t occur in the other.)

Of course, nothing I’ve said lets us compare two disjoint infinite sets (like the odds and evens). And if you’re really going to say that there are more evens greater than 0 than evens greater than 2, then that seems fine, since it’s not clear which of these sets (if either) should have the same size as the set of positive odds.

13 12 2006
Aidan

Is the claim really, though, that Dan’s intuitions are partially tracking the notion of number you’ve just defined?

13 12 2006
Bryan Pickel

I have a question:
There is supposed to be a conflict of intuitions between (i) the claim that the size of a set is larger than the size of its proper subsets and (ii) the claim that the size of two sets is the same if they can be put into 1-1 correspondence.
The conclusion we are supposed to draw is that the intuitive notion of number is as underspecified as the intuitive notion of set allegedly is. But why are we “blaming” the intuitive notion of number for this paradox rather than the intuitive notion of set which we already regard as defective? That is, the conflict between (i) and (ii) might arise as a result of an underspecification in our natural language use of the term “proper subset”. So one response to this would just be to say that in the infinite case the elements of the two sets – the odds and the natural numbers – don’t really stand in the relevant proper subset relation. This isn’t entirely crazy, I think, since it’s a bit weird to say that one infinite set is a proper subset of another. It at least stretches the image we have of sets as circles containing and intersecting with other circles.

13 12 2006
Andrew Bacon

Hi Kenny,

I take the point I made about the evens and the evens minus 2 being intuitively the same size as the odds to indicate that there is no way to extend a fine grained notion of size (until every set has a size) in a way that respects our intuitions. My instinct is to say that it is an analytic truth that sizes should be totally ordered, so the notion you’re defining just doesn’t seem like a notion of size to me.

You mentioned that this is a problem for the bijective conception of size too if we remove the WO property. But similarly removing extensionality puts a spanner in the works for the principle about proper subsets being smaller (ok, you might laugh at the comparison between extensionality and choice, but it feels like choice functions are as essential to the notion of 1-1 correlation as extensionality is to subset relations, and it would be unfair to remove either.) Even if we reject choice we have a fruitful notion of size for the well-orderable sets, whereas the proposed notion doesn’t seem to fair so well, even on the countable sets.

13 12 2006
Dan Korman

Hi Kenny,

I’d like to hear more about your suggestion that our apparently conflicting intuitions about size are in fact consistent, since they track different notions. If that’s right, then we have a solution to Galileo’s paradox that doesn’t require discrediting any of the intuitions, which would be ideal from my point of view.

I wonder how plausible it is, though. Consider Kripke’s claim that there are two notions possibility, and that our intuition that it’s possible that water contains no hydrogen is consistent with our intuition that it’s impossible for there to be water that contains no hyrogen. Once the difference is pointed out, we can really hear the two different readings. We see, clearly, that there is a sense in which it is possible and a sense in which it’s not. By contrast, when we ask whether there are as many evens as naturals, we don’t hear two readings. I feel no comparable temptation to say: there’s a sense in which there are as many evens as naturals and a sense in which there aren’t. A good comparison might be Newcomb’s paradox. We feel the pull of saying it’s rational to choose the one box, and we feel the pull of saying it’s rational to choose both boxes. But do we really have two separate notions of rationality?

I don’t mean to deny that ‘as many as’ has one meaning in the mouths of set theorists and another in the mouths of the folk. That may be right; perhaps the set theorist just *means* sameness of cardinality (i.e., he hasn’t discovered, so much as stipulated, a definition of equinumerosity). But, even if that’s right, that doesn’t take us any way towards resolving the paradox: while the set theorist’s notion may be consistent, the folk notion still threatens to lead to paradox.

20 12 2006
Noah Snyder

The more I think about it the more I think that Dan’s idea is not only wrong, but somewhat pernicious.

The art of mathematics is the art of cleverly forgetting structure. Thus any time you want to define a notion it is crucial to fix which structure you are remembering and which structure you are forgetting. Intuitions that are inherited from forgotten structure must be ignored. It is only by forgetting structure that we are able to generalize and make progress.

In this example, clearly it makes sense to argue using this intuition that the even integers are smaller than the integers if we are remembering their structure as subsets of the integers. However, if we have explicitly forgotten that and are only remembering their set structure (which is the entire point of set theory), then it is total nonsense to make that claim. And worse, pernicious nonsense that attacks the fundamental idea of mathematics.

20 12 2006
Kenny

Noah – if it’s really all about forgetting structure, then everyone should be doing just set theory. So there’s obviously some times that you want to hold onto some structure. And I think you agree to that because you talk about cleverly forgetting structure. Now the question is just which structure is important to remember when. I think Dan wants to argue that for at least some purposes, when talking about size of a set, it’s important to remember the actual subset structure.

Just as there are times that we make progress by forgetting structure, I think there are times that we make progress by realizing that some level of structure is actually important. I think this is why complex analysis for instance often says much mor of interest than real analysis, because there’s an extra level of structure implied by differentiability that makes things manageable.

20 12 2006
Noah

Certainly I agree with your basic point that size can and should mean different things in measure theory, set theory, and manifold theory. I was just trying to argue that one needs to be very careful when applying intuitions that you don’t apply them in situations where you’ve forgotten the bit of information that is tied to the intuition.

That is to say, Z and 2Z being the same as sets just means that we must have forgotten the fixed inclusion between them when we say “as sets.” In fact, one could take this as a proof that one cannot reconstruct the inclusion after forgetting it (as opposed to, say, the fixed map from Z to a ring).

And my point was just that not paying attention to what you’ve remembered and what you’ve forgotten is very dangerous.

20 12 2006
Noah

So here’s another thing that really bothers me with Dan’s suggestion: it’s deeply non-categorical. If all I know is the category of sets, then there’s absolutely no way for me to know which morphisms are “inclusions” and which aren’t. Injections, on the other hand, are categorical.

2 01 2007
Dan P

3. The properties and relations of any set of physical objects may be changed arbitrarily.

This is an interesting condition to consider because without it I’d argue that the Euler number satisfies many of the properties you’d expect of a notion of ‘size’, surprisingly many in fact.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s




%d bloggers like this: