There is a one-to-one correspondence between the set of squares and the set of square roots. Simply map each number in the set of square roots to its square in the set of squares. So it looks as though the sets must have the same number of members. After all:

(1) If there is a one-to-one correspondence between S1 and S2, then S1 has the same number of members as S2.

And yet it is deeply intuitive that there are more square roots than there are squares. Take away the squares from the set of square roots, and you still have some numbers left over. Take away the square roots from the set of squares, on the other hand, and you are left with nothing. So it seems that there must be fewer squares than square roots. This suggests the following:

(2) If S1 is a proper subset of S2, then S1 has fewer members than S2

These two highly intuitive principles cannot both be correct. This was once known as Galileo’s paradox. Virtually no one seems to find it paradoxical anymore. There is a widespread confidence that, however counterintuitive the resolution might seem, the matter has been settled: (1) is true, so (2) must be false. But why reject (2) rather than (1)? What we have here is an intuitional conflict. Has anything actually happened, since Galileo, to make us think that the intuition that backs (1) is more likely to be correct than the intuition that backs (2)? Not that I know of. All that has happened is that there has been a decision to use one-to-one correspondence as a measure of equinumerosity.

In fact, it seems that there is positive reason to prefer (2) to (1). After all, we have clear, concrete-case intuitions to the effect that there are more natural numbers than even numbers, more multiples of three that multiples of six, more square roots than squares. One might even be so bold as to call these “counterexamples” to (1), which is the label we typically reserve for concrete-case intuitions that tell against a general principle, even when that general principle is itself intuitive. So, if anything, we should prefer (2) to (1).

Perhaps the best conclusion to draw is that there is a genuine paradox here, and that more work needs to be done in resolving the intuitional conflict. But it is hard to see why (1) is supposed to be sacrosanct, and why we ought to conclude that there are as many squares as square roots, given that our only evidence for (1) is intuitive, and that we have at least as much intuitive evidence for thinking that (1) is false as we do for thinking that it is true.

I'd be interested to know on what grounds I'm meant to believe 'our only evidence for (1) is intuitive'.

Posted by: Aidan McGlynn | December 04, 2006 at 12:28 AM

(A) Do we not have clear concrete case intuitions everytime we see a 1-1 correlation effected? If I believed in intuitions in the relevant sense, then I would say this.

(B) Can you tell me how to compare the numbers of mutually exclusive classes of things without appeal to a cardinal or ordinal notion of counting (both of which are incompatible w/ your subset thesis)? If you can't don't we have nifty theretical indispensibility for (1) in addition to intuition?

Posted by: Bryan Pickel | December 04, 2006 at 08:18 PM

The problem between the two principles emerges when you move from the finite to the infinite case. Most people's intuitions about the infinite case are informed by their intuitions about the finite case. The notion of having the same number of members is defined in terms of a one-one correspondence, which does generalize to the infinite case whereas (2) does not. That might be question begging...

In any case, what has happened since Galileo that would make (1) seem right over (2)? Frege and Cantor have provided good arguments to the effect that two sets having the same number of elements means that you can pair off each member of one set with a distinct member of the other. The rigorization (through axiomatization?) of math, allowed them to put together elegant theories of this counting, which has become the theory of cardinal numbers. The place to look for the Frege side of this is his Foundations of Arithmetic. I'm not sure about the Cantor side; although, I imagine most set theory books will mention it.

Posted by: Shawn Standefer | December 04, 2006 at 11:23 PM

Michael Hallett's book 'Cantorian Set-Theory and Limitation of Size' discusses Cantor's contribution at length.

Posted by: Aidan McGlynn | December 05, 2006 at 12:54 AM

Thanks for the comments.

Bryan: Perhaps you’re right that we do have concrete case intuitions that there are as many naturals as evens; for instance, we imagine as many people as there are natural numbers showing up at a hotel with as many rooms as there are even numbers, and we see that there’s a way for them to each have a room to himself. If so, intuitively, there must be at least as many hotel rooms as people. This seems a bit like an *inference* from the one-one equivalence of rooms to people, as opposed to an *intuition* that there are at least as many evens as naturals, though I admit it’s not obvious.

As for point B, I can tell you one way to compare the numbers of mutually exclusive classes of things without appeal to a cardinal or ordinal notion of counting: consult your intuitions. Intuitions probably won’t render a verdict on all cases. (That may be a deep fact about the limits of a priori knowledge, or it may just be a result of our limited intelligence.) Checking for 1-1 correction does, I take it, render a verdict in all cases, at least in principle. But to treat that as a reason for thinking that 1-1 equivalence suffices for sameness of size sounds a bit Vienna-circular.

Also, I wonder what exactly is theoretically indispensable about (1)? Is there anything of interest that set theorists (qua set theorists, vs. philosophers) can’t do if they deny (1)? Let’s just define cardinality in terms of 1-1 correspondence, and drop the informal gloss of sameness of cardinality as having the same number of members. Do the independence results fall apart? Are there any theorems that can no longer be established?

Shawn: You may be right that our intuitions about the infinite case are informed by our intuitions about the finite. But that’s just as much of a threat to the intuitions that underwrite (1) as to the ones that underwrite (2). Maybe the reason that we find (1) intuitive that 1-1 equivalent finite sets always have the same size. Infinity is weird, and we shouldn’t be too surprised if our intuitions go awry when we reflect on such matters. But it’s not as all obvious which intuitions are the ones that go wrong.

I’d be curious to hear more about Frege and Cantor’s arguments. Is the argument just that this is a more elegant means of counting? I certainly wouldn’t deny that. But lots of false theories are elegant (e.g., the JTB analysis of knowledge, individualism about mental content, Newtonian mechanics…)

If the argument is just that this gives an elegant and perfectly general means of comparing the sizes of infinite sets, it would take some kind of operationalism to get from there to the claim that 1-1 equivalent sets in fact are the same size.

Aidan: I had in mind a sort of argument from elimination that our only evidence for (1) is intuitive. Smelling and tasting don’t yield any evidence for (1). Nor do introspection or memory. Testimony is a source of evidence, I suppose, but then the question is what evidence the testifiers have. I’m not sure there’s any inductive or abductive evidence. (Are there really any data that can be better explained by a set theory that incorportates (1) than by a set theory that eliminates all mention of size-comparisons in favor of size*-comparisons, where size* is stipulatively defined in terms of 1-1 equivalence?) Intuitions seems to be all that’s left.

Then again, perhaps all set theorists mean when they talk about size is size*, and they don’t mean size by ‘size’. Is that what’s going on here?

Posted by: Dan Korman | December 06, 2006 at 01:44 PM

If you're going to rely on an argument from elimination, you'll need to persuade people you've eliminated all the options. Knocking down straw-men isn't likely to lend support to this (has anyone suggested that smelling and tasting were options? We want to know what the genuine proposals are, and why they fail). In the absence of some argument, I don't see why we should accept the relegation of (1) to having the same status as you claim for (2).

Brian had some nice points on equinumerosity yesterday, but I don't want to steal his thunder if he's hoping to post them, or put them online if he didn't want them to be public, so they'll have to wait.

Posted by: Aidan McGlynn | December 06, 2006 at 03:53 PM

"Then again, perhaps all set theorists mean when they talk about size is size*, and they don’t mean size by ‘size’. Is that what’s going on here?"

By 'talk about size', do you just mean use the word 'size'?

Posted by: Aidan McGlynn | December 06, 2006 at 04:02 PM

Frege's arguments are in the Foundations of Arithmetic sections 70-86. The 1-1 correspondence for Frege is conceptually prior to the notion of number. The latter can be constructed using the former. This also allows him to compare the size of sets which don't stand in proper subset relations. In the finite case, it also preserves (2). It is hard to see what intuitive pull (2) has over (1) when the intuitions that support (2), the finite cases, are conserved with (1) and (1) is more general.

There is a problem with dropping the gloss of having the same cardinality as having the same number of members. In the finite case, the finite numbers are (at least on a [the?] standard construction, e.g. in Jech's Set Theory) ordinals and they are cardinals. So saying that two sets have the same number of members is saying that they have the same cardinality. I'm not sure what it would mean to talk about size of sets apart from their cardinality, or how many members they contain. It seems like set theorists size* talk is the only thing that makes sense for the size of sets.

Could you explain how we have concrete-case intuitions that there are more natural numbers than even?

Posted by: Shawn Standefer | December 06, 2006 at 06:09 PM

I am not sure the intuitive notion of size is consistent. I take it that the intuitive notion of size has (2) as a consequence. But if we are taking such a fine grained notion of size, it seems equally intuitive to me that

(3) there are as many even numbers as odd numbers

Furthermore I cannot think of any motivation that would convince us to believe (3) that wouldn't similarly convince us of

(4) there are as many odd numbers as the even numbers minus {2}

(4) seems to be so similar to (3) (we have just shifted a set up by 1 in both cases) how could we hold (3) and not (4)? Yet clearly (3) and (4) are inconsistent with (2). It seems that one intuitive principle must give way to another and I can't see any reason to prefer (2) over (3). I think the conclusion is there is no fine grained notion of size which pays respect to our intuitions about size.

Posted by: Andrew Bacon | December 11, 2006 at 06:55 AM

Hmm... my trackback from this post didn't make it.

Posted by: Kenny Easwaran | December 12, 2006 at 11:19 AM

Andrew: Here’s one motivation for accepting (3) but not (4). Intuitively, there are as many even numbers as odd numbers. But intuitively, there are more odd numbers than there are even numbers other than 2. Intuitively, there is exactly one more odd number than there are even numbers other than 2. It may be hard to find *theoretical* motivations for accepting (3) and not (4); but there are clear intuitive reasons for accepting one but not the other.

Shawn: Intuitions about the infinite cases do support (2): whenever you consider a clear case in which one infinite set is a proper subset of another, there are clear intuitions to the effect that the former has fewer members than the latter. Of course, there may be intuitions telling in favor of their having the same number of member as well, but that’s compatible with the larger point I’m trying to make: that there is a genuine intuitional conflict that needs to be resolved, not just dismissed. And my suggestion is that favoring (1) and rejecting (2) on the grounds of theoretical fruitfulness (as Frege in effect does) is not a resolution; it’s a dismissal.

Also, even though cardinality and having the same number of members coincide in the finite case, that doesn’t show that to say that two sets have the same number of members just just to say that they have the same cardinality. (Compare: every creature with a kidney is a creature with a heart, but…).

When I said that we have a concrete-case intuition that there are more naturals than evens, that itself is meant to be the concrete-case intuition. The contrast was supposed to be to intuitions about general principles, like (1) and (2). Marc raises some interesting points about the difference between general-principle intuitions and concrete-case intuitions in his reply to John’s post on being aware of universals.

Posted by: Dan Korman | December 13, 2006 at 10:20 AM

Dan: I completely agree with you - there are intuitive reasons to believe (2) and (3) but not (4), namely that (2) and (3) are intuitive and (2) entails (4) is false. But this is exactly why I think the intuitive notion of size is inconsistent (at least when applied to infinite sets.)

If we imagine an omega sequence of apples, eating apple no. 1 seems to land us in exactly the same situation as shifting each apple up one place (without knowing the history we could not tell which was the shifted sequence.) So we have two sequences of apples that are alike in all respects. Yet on this proposal (assuming shifting does not disrupt identity) there are more apples in the even numbered place holders of the shifted sequence than in the non-shifted sequence. It is not a theoretical motivation for accepting [(3) iff (4)], I think there is a deeply rooted intuition that they should be the same.

Posted by: Andrew Bacon | December 13, 2006 at 12:06 PM

Yeah, the apples case is interesting. It’s hard to see how moving the apples down one should be any different from eating one, without visualizing the “end” of the series of apples being shifted (and of course there is no end to an infinite series!). I’m tempted to press on the fine distinction between something’s being unimaginable and something’s being intuitively impossible. I don’t get an intuition to the effect that results of shifting and the results of eating are the same; but I can’t imagine how it could make a difference. But, after your comment and some of the others, I get the feeling that not everyone shares my intuitions.

I’d like to hear more on your thought that the intuitive notion of size is inconsistent, when applied to finite sets. Something similar can be said about the intuitive notion of truth, when applied to liar sentences. But, in the case of truth, we cry: paradox! Do you take there to be a genuine paradox in the case of size as well? If not, what’s the difference?

Posted by: Dan Korman | December 13, 2006 at 03:42 PM

With finite sets I think that the intuitive notion of size pretty much coincides with the bijection account so there is no inconsistency. In particular if you can shift a set x up or down the numberline it will remain the same size, and if you can shift x so it properly contains y then x is larger than y. Since most of our every day experiences are with sizes of finite sets our intuitions may well include principles such as (2). And although I do not believe we can consistently extend those particular intuitions beyond finite sets, I do not think this causes a paradox. Zeno's paradox, Benardete's paradox, the paradox of Hilberts hotel etc... are not genuine paradoxes - just cases of our intuitions about finite sets breaking down for infinite sets.

I think the same problem applies to the intuitive notion of set (and possibly truth). Russell's paradox can be turned from a paradox into a theorem that not every property gives us a set. Surprising as it was, it's pretty much accepted that naïve set theory is inconsistent. If anything these are examples of how badly our intuitions can go wrong.

Posted by: Andrew Bacon | December 14, 2006 at 06:35 AM