h1

Cardinality and the intuitive notion of size

January 1, 2009

According to mathematicians two sets have the same size iff they can be put in one-one correspondence with one another. Call this Cantor’s principle:

  • CP: X and Y have the same size iff there is a bijection \sigma:X\rightarrow Y

Replace ‘size’ by ‘cardinality’ in the above and it looks like we have a definition: an analytic truth. As it stands, however, CP seems to be a conceptual analysis – or at the very least an extensionally equivalent charaterisation. In what follows I shall call the pretheoretic notion ‘size’ and the technical notion ‘cardinality. CP thus states that two sets have the same size iff they have the same cardinality.

Taken as a conceptual analysis of sizes of sets, as we ordinarily understand it, people often object. For example, according to this definition the natural numbers are the same size as the even numbers, and the same size as the square numbers, and many more sets even sparser than these. This is an objection to the right to left direction of CP.

I’m not inclined to give these intuitions too much weight. In fact, I think the intuitive principles behind these judgements are inconsistent. Here are two principles that seem to be at work: (i) if X is a proper subset of Y then X is smaller than Y, (ii) if by uniformly shifting X you get Y, then X and Y have the same size. For example (i) is appealed to when it’s argued that the set of evens is smaller than the set of naturals. (ii) is appealed to when people argue that the evens and the odds have the same size. Furthermore, both principles are solid when we are dealing with finite sets. However (i) and (ii) are clearly inconsistent. If the evens and the odds have the same size, so do the odds and the evens\{2}. This is just an application of (ii), but intuitively, the evens\{2} stand in exactly the same relation to the odds, as the odds to the evens. By transitivity, the evens and the evens\{2} are the same size – but this contradicts (i) since one is a proper subset of the other.

In fact Gödel gave a very convincing argument for the right to left direction: (a) changing the properties of the elements of a set does not change its size, (b) two sets which are completely indistinguishable have the same size and (c) if \sigma:X \rightarrow Y , each x \in X can morph its properties so that x and \sigma(x) are indistinguishable.  Thus, if \sigma is a bijection, X can be transformed in such a way that it is indiscernable from Y, and must have the same size. (Kenny has a good discussion of this at Antimeta.)

The direction of CP I think there is a genuine challenge to is the left to right. And without it, we cannot prove there is more than one infinite size! (That is, if we said every infinite set had the same size, that would be consistent with the right to left direction of CP alone.)

What I want to do here is justify the left to right direction of CP. The basic idea is to do with logical indiscernability. If two sets have the same size, I claim, they should be logically indiscernable in the following sense: any logical property had by one, is had by the other. Characterising the logical properties as the permutation invariant ones, we can see that if two sets have the same cardinality, then they are logically indiscernable. Since we accept the inference from having the same cardinality to having the same size, this partially confirms our claim.

But what about the full claim? If two sets have the same size, how can they be distinguished logically? There must be some logically relevant feature of the set which is distinguishing them, but has nothing to do with the size. But what could that possibly be? Surely size tells us everything we can know about a set without looking at the particular characteristics of  its elements (i.e. its non-logical properties.) If there is any natural notion of size at all, it must surely involve logical indiscernability.

The interesting thing is that if we have the principle that sameness in size entails logical indiscernability we get CP in full. The logical properties over the first layer of sets of the urelemente are just those sets invariant under all permutations of the urelemente. Logical properties of these sets are just unions of collections sets of the same size. Thus logically indiscernable sets are just sets with the same cardinality!

Ignore sets for a moment. The usual setting for permutation invariance tests is on the quantifiers. A variant of the above argument can be given. This time we assume that size quantifiers are maximally specific logical quantifiers. There are two ways of spelling this out, both of which will do:

  • For every logical quantifier, Q, Sx\phi \models Qx\phi or Sx\phi \models \neg Qx\phi
  • For every logical quantifier, Q, if Qx\phi \models Sx\phi then Qx\phi \equiv Sx\phi

The justification is exactly the same as before: the size of the \phi‘s tells us everything we can possibly know about the \phi‘s without looking at the particular characteristics of the individuals phi‘s – without looking at their non-logical properties. Since the cardinality quantifiers have this property too, we can show that every size quantifier is logically equivalent to some cardinality quantifier and vice versa.

I take this to be a strong reason to think that cardinality is the only natural notion of size on sets. That said, there’s still the possibility that the ordinary notion of size is simply underdetermined when it comes to infinite sets. Perhaps our linguistic practices do not determine a unique extension for expressions like ‘X is the same size as Y’ for certain X and Y. One thing to note is that the indeterminacy view seems to be motivated by our wavering intuitions about sizes. But as we saw earlier, a lot of these intuitions turn out to be inconsistent, so there won’t even exist precisifications of ‘size’ corresponding to these intuitions. On the other hand, if we are to think of the size of a set as the most specific thing we can say about that set, without appealing to the particular properties of its members, then there is a reason to think this uniquely picks out the cardinality precisification.

Advertisements

2 comments

  1. See: http://arxiv.org/pdf/math/0106100

    Sets and Their Sizes, Fred M. Katz


    • Following on the first comment, see a new article in the Review of Symbolic Logic, which heavily references the Katz article (as well as others).



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: