FOM: Re: Transfinite Logic

[Richard G. Heck, Jr.]

>But this is where I started: with a textbook that defined a proper subset 
>as one with "fewer" members than its parent.  This was clearly wrong (does 
>Cooper disagree?).

Yes, of course, that was clearly wrong, if by "fewer" one means "not as 
many". Sometimes people do use the word "fewer" in a different way (so that 
"fewer" is a partial order). That's confusing, but not any more so than 
many ambiguities in ordinary language, so long as one is careful.

>On there being a remainder, why is this not contradictory or 
>mysterious?  If we define equinumerosity as one-one correspondence, there 
>cannot be a remainder. Doesn't the diagonal proof depend on there being 
>one (the diagonal itself)? It's clear you can correlate the even numbers 
>with themselves perfectly, as follows:
>     1,2,3,4,5, ...
>     *,2,*,4,*, ...
>This way, there is a whacking great remainder, as indicated by the 
>asterixes.  If equinumerosity is1-1 correlation without remainder, the 
>even numbers are not equinumerous with the integers.
>
>If on the other hand remainders are OK, what does the diagonal proof prove?

One needs to be very clear what "there being a remainder" means here. It is 
being used two ways.

Before I continue, I would like to urge people to take a moment to 
appreciate how conceptually complicated these issues are. (I spend some 
time urging the same thing in my paper "Finitude and Hume's Principle".) 
It's easy for we who are comfortable with these things to fail to see just 
what an incredible conceptual leap Cantor made when he extended the idea 
that equinumerosity is one-one correspondence to the infinite. It's worth 
taking the time to appreciate it, from time to time. Reading Bolzano is one 
good way.

OK, Cantor having been paid homage, let's get clear about what 
equinumerosity and one-one correlation are.

We are given two sets, S and T. We say that S is correlated one-one with T 
by the function f(x) iff:
         (i) f(x) is a one-one function
         (ii) for each x in S, there is a y in T such that y=f(x)
         (iii) for each y in T, there is an x in S such that y=f(x)
That is simply a definition. Note that there is no question of there being 
any "remainder" within the sets S and T: The whole of S is correlated by 
f(x) with the whole of T. In that sense, equinumerosity is one-one 
correlation without remainder.

Now here's another definition:

S is equinumerous with T iff there is a function f(x) that correlates them 
one-one.

Note again that that is simply a definition. Note further that what it says 
is that S is equinumerous with T iff there is a function f(x) that 
correlates them one-one. I'll come back to that. Now here's an important fact.

Fact: Equinumerosity, so defined, is an equivalence relation.
Proof: Easy exercise in set theory.

Amazingly, there's a sense in which this is the crucial theorem. For it 
follows from this fact that equimerosity acts, to a certain extent, like 
identity. That's why you can use what nowadays gets called "Hume's 
Principle" to characterize the cardinals, which Frege explicitly did and 
Cantor sort of did (and set-theorists still sort of do). Note that it 
follows from the consistency of HP that one isn't going to get any 
contradictions out of such a treatment of cardinality.

Theorem: The set of all natural numbers {0,1,...} is equinumerous with the 
set of all even numbers (0,2,...}.
Proof. Let S be the set of naturals; T, the set of evens; f(x)=2x. Plainly, 
the three conditions hold. So there is a function, namely, f(x)=2x, that 
correlates the naturals one-one with the evens.

There is no questioning this result. It is a totally straightforward, and 
extremely simple, theorem.

Now one might have the following worry. It's clear that there is also a way 
of correlating the natural numbers with the even numbers so that not every 
natural number is correlated with an even number: Just map each number to 
itself (i.e, f(x)=x). In that case, there is a huge "remainder", as 
indicated by the asterisks above, namely, the odds. So, one might say, then 
the naturals aren't equinumerous with the evens! But that's a mistake. Look 
at the definition: As I emphasized above, it says that S and T are 
equinumerous if there is a function that correlates them one-one. Of course 
there are lots of functions that do not so correlate them. What matters is 
whether there is a function that does. In the end, as with so many of the 
great discoveries of set theory, all of this confusion is distilled into a 
theorem:

Theorem: There are sets S and T with the following property: There is a 
function f(x) that correlates S one-one with T, and there is another 
function g(x) that maps S one-one properly into T, i.e. that correlates S 
one-one with only part of T.
Proof: Take S to be the evens; T to be the naturals; let f(x) be x/2; let 
g(x) be identity.

Again, that's just a theorem, and not a very hard one. There's no mistake 
in the proof. One might well have thought that if you can correlate S 
one-one with a proper part of T, you can not also correlate it one-one with 
all of T. But that, it turns out, is just wrong: If S and T are Dedekind 
infinite, then it is possible. That's what the theorem says.

Now, for the diagonal proof. What it shows is that there is no one-one 
correlation (and that means without remainder) between the naturals and the 
reals (or whatever). It works by assuming that there is such a correlation, 
and then deriving a contradiction. The fact that the naturals can be mapped 
one-one into the reals ("with remainder") is neither here nor there.

Richard

====================
Richard G. Heck Jr.
http://www.people.fas.harvard.edu/~heck