Re: Why are reals uncountable yet algorithms countable (long)?

From: KRamsay (kramsay_at_aol.com)
Date: 11/19/04 

Date: 19 Nov 2004 04:51:10 GMT

In article <2vs5a8F2nf0jrU1@uni-berlin.de>, "robert j. kolker"
<nowhere@nowhere.net> writes:
|There is a school of mathematical thought that would require all kosher
|mathematical entitiies to be constructable according to a finite
|algorithm but such a diminished system of mathematics cannot prove some
|really cool useful stuff.

The Markov school in Moscow used to have such a view, but
as far as I know they're all gone. I don't know whether there
is another such school.

The Markov school was a particular kind of constructivism.
Constructivism doesn't require that all mathematical entities
be constructible according to an "algorithm", although it turns
out that in many contexts an object that can be constructively
proven to exist without additional hypotheses is guaranteed
to be computable.

It's probably fairly common to think that it's a matter of the
"kashrut" of mathematical objects. People seem to think
that constructivists decide somehow that they don't like
the noncomputable objects that are there. But it's not quite
as dopey a point of view as that. The motivation behind it
has more to do with trying to get more richly meaningful
theorems than with barring exotic mathematical objects.

Constructive mathematics is something like mathematics
done without using the law of excluded middle or the axiom
of choice. The law of excluded middle is a deductive rule
allowing one to conclude "p or not p" for a sentence p. It's
equivalent to the rule of double negation elimination, which
says that "p is true" is deducible from "p is not false".

It's quite true that there's a lot of useful and interesting
mathematics that depends upon the law of excluded middle
and the axiom of choice. But there are also a lot of ways
around using the law of excluded middle and the axiom of
choice. A constructivist might liken ordinary mathematical
practice to cooking with some favorite ingredient like beef.
There are lots of tasty meals to be cooked with beef, but
one doesn't really *need* beef, and some people would say
it's generally better to do without it. After getting spaghetti
with beef broth, peanut butter and jelly with beef sandwiches,
ice cream with beef fat garnish, hot and sour soup with beef
curd, and so on, one might feel like trying a few beef-free
meals once in awhile to see what it's like.

The axiom of choice was proven by Goedel to be consistent
with standard other axioms of set theory, if they are themselves
consistent, because there's a subclass of sets where the axiom
of choice is valid, as well as the other axioms. In a technical
sense, the axiom of choice can't be too completely vital to the
applications of mathematics. And there is an embedding of
the theory without the axiom of choice into the theory with the
axiom of choice and the law of excluded middle both removed.
To put it simply, the law of excluded middle is equivalent to
double negation elimination, and in a certain sense that's the
only job that it is needed for. If one is willing to leave enough
double negations in, any statement that can be proven with
the law of excluded middle can also be proven without it.

I can't claim to know how well the constructivist project of doing
mathematics constructively all or nearly all of the time would
work. I can say with confidence that it is at least not as much
of a straightjacket as many think it is. In some ways, assuming
fewer axioms gives one more freedom, even.

One of the criticisms that seems more plausible to me, in fact,
is the idea that constructivism forces one to work in more of a
refined way than one wants to. There are lots of different concepts
that are nonconstructively equivalent but constructively not
necessarily equivalent. Instead of having the one standard classical
result, it seems like one often winds up with a family of related
results.

Take the intermediate value theorem. As usually stated, it is
nonconstructive. Given a function f which is linear on the intervals
[0,1/3], [1/3,2/3], [2/3,1], with f(0)=-1, f(1)=1, and f(1/3)=f(2/3)=r,
to prove that there is a value of x for which f(x)=0 holds,
constructively, we have to prove that either r<=0 (in which case
x = 2/3 - r/3(1-r) works) or r>=0 (in which case x=1/3(1+r) does).
But r<=0 or r>=0 indirectly uses the law of excluded middle.

One standard substitute is the constructively valid result that
if f is continuous on [0,1], f(0)<0<f(1), then for each epsilon>0
there exists an x, 0<=x<=1, such that |f(x)|<epsilon.

But then there are various other results that might be useful
in various cases. If f is a continuous function on [0,1] with
f(0)<0<f(1), and if on each interval [a,b], with 0<=a<b<=1,
there is a value x, a<=x<=b, such that f(x)<>0, then there
exists a y such that 0<y<1, f(y)=0.

Keith Ramsay