# FOM: Re: Transfinite Logic

Richard G. Heck, Jr. heck at fas.harvard.edu
Wed Jun 5 15:47:00 EDT 2002

```>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

```