FOM: RE: Proper Names and the Diagonal Proof

[Dennis E. Hamilton]

Uh, I had thought he used the proof to show that there are more of the
things he wanted to name than the available supply of names.  For example,
with names drawn from N, there is no way to name (i.e., index) all of the
objects that theory says are in R.  And that can be used, for example, to
show that the set of reals is of a higher cardinality power than the
naturals.  I don't think duplicates are the issue.

I may be drawing a false comparision, but your illustration of an indexing
of functions relates to another famous problem (in my world).  If you use N
to label an enumeration of function definitions [these are non-unique names
for mathematical functions], there is a form of diagonal construction that
shows there is a function (actually very many, but you only need one) that
has no expression in that list.  This is the demonstration that there are
uncomputable functions.  That is to say, there are two many functions in the
set of all functions f: N -> N for them to all be computable, i.e., even
expressible in a form found anywhere in the enumeration, which essentially
has all of the computable ones almost by definition.

I'm not dealing with the nuances -- I'm not even sure I grasp all of them --
for example, you need to satisfy yourself that you're really getting
definitions for all the functions that can be enumerated (that is, the
subset of the expressions that are for entirely different functions is of
the same power as N) but I believe that is the gist of it.  (Davis describes
this differently, so I would consult his observations about this particular
proof if you have it available.)

One difference: it is (expressions of) functions themselves that are being
indexed in my example, rather than particular formulae with constant terms.
I haven't done the work to be certain your case of names does the job you
want it to.

It's probably dangerous to draw too strong an analogy between the case of
too many functions to what Cantor was after, but this is one kind of thing
that diagonalizations are good for.  It seems to me that the fact of
unending decimal expansion is not the problem, though I wouldn't bet
anything significant on that hunch.

Does this provide any better sense of how diagonalizations works?

[I love Harvey Friedman's response.  I don't know if we are staying very
on-topic for FOM here, and I'm willing to share what more I can via direct
e-mail huddle.]

-- Dennis

-----Original Message-----
From: owner-fom at math.psu.edu [mailto:owner-fom at math.psu.edu]On Behalf Of
Dean Buckner
Sent: Monday, June 24, 2002 13:39
To: fom at math.psu.edu
Subject: FOM: Proper Names and the Diagonal Proof



Let's think of numerals as a system of generating new proper names,
plus the assumption that each name designates a different thing.  I don't
really care about what kind of things these are.

[ ... ]

[ ... ]

Then, some interesting questions.  (i) Is the number of operations that we
can form strictly limited? (ii) Even if unlimited, is there a way of
matching up each operation with the sequence 1,2,3, ...? (iii) something
else?

1.  the square root of ---
2.  the length of the line whose distance from the same point = 1
3.  the definition of the number "e" which I can't remember
4.  Any other definitions of strange operations on numbers

If we can list all the (1-place) operators out like this, then it is simple
to prove that we can match the names formed by any
operator+any numeral, with the numerals.  Equally simple to extend
the proof to operators that have two or three or more places.  Hence, even
if different names signify different things, there are enough ordinary
names (i.e. numerals) to go round, to match the more complex names.

Cantor's proof has it otherwise.  It says that we cannot "match" a set of
ordinary names (numerals) to a set of names formed by infinite decimal
expansion.  Each row is "complete": it is a proper name formed out of an
"infinite" collection of digits.  It assumes not just an infinite collection
of names, but an infinite collection of names with infinite number of parts.
But it's not clear which object is named by any name in the the sequence,
since it is not clear what the name actually is.  Even if we suppose that
"the square root of two" names something, what does "1.23245467 ..."
name,when the dots signify not a specific method of carrying on the
sequence, but no specific method at all?

I'm happy to assume that, given that a meaningful expression of English can
formed using a finite sequence of expressions, using words drawn from a
finite vocabulary, we can signify a different thing with each different
expression.  I'm not happy to assume any more than that, unless I
know what I'm meant to assume.

I'm not arguing against Cantor's proof, I'm saying I don't understand what
it's meant to prove.




Dean Buckner
4 Spencer Walk
London, SW15 1PL
ENGLAND

Work 020 7676 1750
Home 020 8788 4273