Re: Zenkin's paper on Cantor (reply of Dr. Zenkin)

From: Chas Brown (cbrown_at_cbrownsystems.com)
Date: 11/15/04 

Date: 15 Nov 2004 02:26:17 -0800

examachine@gmail.com (Eray Ozkural exa) wrote in message news:<320e992a.0411140136.75b1a6fe@posting.google.com>...
> cbrown@cbrownsystems.com (Chas Brown) wrote in message news:<ba7dcfd7.0411131541.5975da42@posting.google.com>...
> > examachine@gmail.com (Eray Ozkural exa) wrote in message news:<320e992a.0411091141.38c7158b@posting.google.com>...
> > > "Shmuel (Seymour J.) Metz" <spamtrap@library.lspace.org.invalid> wrote in message news:<4181a33d$1$fuzhry+tra$mr2ice@news.patriot.net>...
> > > > In <320e992a.0410271136.4479a210@posting.google.com>, on 10/27/2004
> > > > at 12:36 PM, examachine@gmail.com (Eray Ozkural exa) said:
> > > >
> > > > >However, if he can settle the following metamathematical theorem:
> > > >
> > > > That's not a Metamathematical theorem absent definitions of
> > > > "infinitary reasoning" and "abstraction of actual infinity". Without
> > > > the definitions it's just Philosophy.
> > >
> >
> > Not even Philosophy - without definitions, it's just Wanking.
>
> If you understand the terms, it can be mathematics.
>

To ensure that we both understand a term to refer to the same thing,
we must agree on a definition of the term.

This is true in both philosophy and mathematics. If we want to have a
discussion about "God", and you are talking about an omniscient being,
while I'm talking about an omnipotent being, our discussion will
become confused and inchorent.

This is doubly true in philosophy of mathematics.

> > > The first is a piece of cake as it means that there is no halting
> > > program which can output a 0 or 1 for falsehood or truth of the
> > > proposition under consideration. (I cannot see why Brown thought it
> > > was hard)
> >
> > But Zenkin's claim is that _Cantor's proof_ is an _example_ of
> > "infinitary reasoning". Since Cantor's proof can easily be verified as
> > true (under the usual axiomatic system) in a finite number of steps,
> > this would contradict your (natural) definition, and his argument must
> > fail immediately.
>
> Hmmm. Given of course the truth of "the usual axiomatic system", by
> which you probably mean ZFC. Zenkin's argument is more like, well,
> this is a finite nonhalting program, that never says anything.
>

:)

> While the truth of Cantor's theorem follows from ZFC in a finite
> number of steps (this is easily seen!), I must admit that I cannot
> readily observe how Cantor's diagonal *proof* terminates in a finite
> number of steps.

In a mathematical context, the truth of a theorem is _equivalent_ to
the existence of a demonstration by a proof.

Cantor's Theorem is proven according to the following sketch: "if some
set S with property P actually exists, then its existence implies that
S lacks property P; contradiction. Therefore, such a set S cannot
exist." This only takes finite steps to demonstrate (the steps of the
proof).

The property P is that every real number is in the range of S; the
proof demonstrates that the existence of S implies that there then
exists a real x which is not in the range of S. Since x cannot be both
in the range of S and not in the range of S; then x cannot exist,
therefore S cannot exist.

> I think if you explained a bit, it would be
> interesting.

Tedium alert!! Tedium alert!!!

The argument below is the same, whether you consider "functions" to be
always constructible (Turing machine based algorithms), or whether you
allow a greater scope to "non-constructible" functions such as "an
enumeration of all non-halting Turing machines". All that is required
is that, when you assume a function exists, you accept that it obeys
whatever of these rules you prefer.

What is "a function which is a bijection"? A bijection is a function
(algorithm) has the particular property that f is a function f : A ->
B, such that for all a, a' in A, it is the case that f(a) = f(b)
implies a equals b, and for all b in B, exists a in A such that f(a) =
b.

If f : A -> B exists and is a bijection, then it follows that there
exists another function (algorithm), f^-1, with the property for all b
in B, f(a) = b if, and only if, f^-1(b) = a. In other words there
exists a function with f^-1(f(a)) = a for all a in A.

Do these definitions coincide with your understanding of the meaning
of "f is a function which is a bijection"?

By "a real number" r in R, I mean here a function (algorithm)
r:N->{0,1} which we can understand as the binary decimal expansion of
"the real number r"; i.e., with r(i) being the "ith" digit in r's
binary expansion.

(It is beyond the scope of what I'm prepared to detail as to the exact
meaning of "understand as... the real number r", but there _is_ an
exact meaning which can be ascribed to this statement which meets
every natural, intuitive concept of what we require from the term
"real number".)

We _define_ the following term: the statement "two real numbers r and
s are equal" is equivalent to saying "for all naturals m, r(m) =
s(m)". It follows that, if there exists a natural m with r(m) not
equal to s(m) then r does not "equal" s.

Do you agree that this definititon of "equal" real numbers is sensible
(granted, perhaps not useful for _every_ purpose)?

The claim (Cantor's Theorem) is that there does not exist a function
S: N->R having the property of being a bijection.

Now to start, let's assume that such a function (algorithm) S _does_
exist.

Since S is a function (algorithm) that "returns" a real numner
(function/algorithm), sometimes it will be easier to write S as if it
took one input, n, and as such S(n) returns the nth real number; and
sometimes it will be easier to write S as if it took two inputs, n and
m; and S(n,m) is the mth digit in nth real number of the list.

What's important to keep in mind here is that we have _assumed_ that
the given S actually _exists_, and has these properties: S(n,m) is
well-defined (exists for all naturals n, m) and S is a bijection -
therefore it follows that there exists a function (algorithm) S^-1,
such that for any real number (algorithm) r, there exists a natural k
= S^-1(r) with the property that S(k,m) = r(m) for all m.

More importantly to our argument, this is equivalent to saying: there
exists S^-1 which, given any real number r as input, returns a natural
k with the property that there does _not_ exist a natural m with
S(k,m) not equal to r(m).

Is that not a valid implication of the statement "Exists S : N -> R
such that S is a bijection"? Check it out.

Now if it turns out that we can prove a contradiction, say 1=0, from
the assumption that "Exists S such that ...", then S cannot exist;
because by "exists", we mean "is consistent with our axioms regarding
existence (typically, ZF)".

The diagonal construction can then be understood as an algorithm C
(for "Cantor") which takes as its input any function (algorithm) S of
the above type, and "returns" a real number (algorithm) D such that
D(n) = 1 - S(n,n) (assuming we're working in binary).

We can easily describe C: For any finite n and m, S(n,m) is given in a
single step ("execution of algorithm S for inputs n and m"); so if S
exists, then S(n,n) exists for all naturals n, and so 1 - S(n,n) =
D(n) exists for all naturals n.

C certainly exists; we just described it. Then _if_ S exists (as we've
assumed), then D = C(S) exists. Agreed?

Since D exists, it is a real number in R, the range of S. Then by
definititon of "S is a bijection", there exists a natural number n
such that there does not exist a natural number m with S(n,m) not
equal to D(m) - that is, after all, what we meant by "D is in the list
of reals, S".

But this is contradicted by our construction - the nth digit of D,
D(n) = 1 - S(n,n) is _never_ equal to the nth digit of S(n).

The existence of D follows from the existence of S whether S is a
bijection or not; if S exists then D _must_ exist. So assuming the
existence of S with the property "bijection" leads to a contradiction.

Therefore no such set S can exist.

Badda bing badda boom. One big, finite step: Existence implies
contradiction; therefore, not-existence. End of proof.

Note that I haven't postulated anything about "infinity" - I have made
a finite series of statements and inferences about the existence or
non-existence of certain integers and certain algorithms, given the
existence of certain algorithms with particular properties.

This logic is really not so different from the logic that there is no
greatest number in the set of all integers: If you claim there is such
a greatest integer, n; then n+1 is also in the set of all integers,
and n+1 > n; contradiction.

Substitute "there exists a (halting) algorithm A which generates the
largest integer" for "n"; and substitute "the algorithm B which
produces the next greater integer than that returned by any (halting)
algorithm T given as input" for "n+1".

To respond to the above argument by saying, "yeah, but what if I had
chosen n+1 instead of n?" is to miss the point. The idea is that n is
not some _specific_ number, but instead _any_ example of a number
which has a property - that of being the largest integer. The proof
then shows that such a number cannot exist, because such a number
would have to simultaneously be both greater than, and less than, n+1,
and this is a contradicition.

If you can see how _this_ proof does not require an infinite number of
steps, then apply the same logic to the diagonal construction
argument.

The fact that you can turn around and say, "yeah, but what if I add D
to the list S to make S'?" is to miss the point - S wasn't some
_specific_ function, it was _any_ example of a function having the
property of being a complete list.

The diagonal proof then shows such a function cannot exist, because it
would then simultaneously have the property of being a complete list
and having the property of not being a complete list, and this is a
contradiction.

And all this proven in a finite number of steps! Because step 1 is
"Assume exists S with properties...".

> (The argument others made was something like, "I can
> finish reading the proof in finite time", which is not quite relevant.
> I can finish reading "Let A be 0. Add infinity to A, infinite times.
> Return A." in a finite number of reading steps, but unfortunately the
> algorithm it describes never ends, therefore it is not an algorithm.)

It is true that when one deals with infinity one needs to be careful;
particularly with statements like "do (something) an infinite number
of times". Otherwise, contradictory statements like "infinity + 1 =
infinity, therefore 1 = 0" spread all over the place; and statements
like "let x = (-1)^(infinity); does x = 1?" become unresolvable. That
is because they don't "make sense" - by definition, infinity is not
just "another integer", it is a different animal entirely; and you
cannot assume that it has the properties of an integer.

Cheers - Chas

> Just to be painstakingly precise.
>
> Regards,

Relevant Pages

  • Re: Zenkins paper on Cantor (reply of Dr. Zenkin)
    ... What is "a function which is a bijection"? ... exists another function (algorithm), f^-1, with the property for all b ... well-defined (exists for all naturals n, m) and S is a bijection - ... of reals, S". ...
    (sci.math)
  • Re: Uncountable sets in CZF?
    ... a trivial surjection from R onto any subset of N there is a bijection. ... I don't base my arguments (that the reals and naturals are equivalent) ... from some proper subset of the naturals to the reals, ...
    (sci.math)
  • Re: Uncountable sets in CZF?
    ... It doesn't follow that there's a bijection. ... > naturals to the reals. ... What that means is that one of the reasons that people call the reals ... That implies it is not a mathematical fact and to promote the other ...
    (sci.math)
  • Re: Cardinality of Real Numbers
    ... Cantor's first assumes the existance of a bijection between the ... >> natural numbers and the reals. ... From this, a contradiction is reached ... >naturals to the reals, and shows that there is some real not in the ...
    (sci.math)
  • Re: Gregory Chaitin: "Randomness is the true foundation of mathematics."
    ... So then there must an algorithm somewhere that will give us access to any future knowledge even before it is discovered. ... But only reals cannot be computed. ... If you do want to hide something well, though, and don't care to find it again even yourself, then the Southern Ocean is a better bet, no matter how cunning your maze. ... Those who know anything about the matter are aware that every writer, from Epicurus to Bentham, who maintained the theory of utility, meant by it, not something to be contradistinguished from pleasure, but pleasure itself, together with exemption from pain; and instead of opposing the useful to the agreeable or the ornamental, have always declared that the useful means these, among other things. ...
    (uk.philosophy.humanism)