Re: does sqrt(2) exist in CM?
From: Keith Ramsay (kramsay_at_aol.com)
Date: 02/21/05
- Next message: anon: "Re: From sign conventions to Galois Theory"
- Previous message: Alec Mihailovs: "Re: mod for floats"
- In reply to: r.e.s.: "Re: does sqrt(2) exist in CM?"
- Next in thread: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Messages sorted by: [ date ] [ thread ]
Date: 20 Feb 2005 23:34:21 -0800
r.e.s. wrote:
[...]
|> | Here's Troelstra's definition ...
|> | [1] Constructivism: A normative demand for EXPLICITNESS of the
|> | mathematical objects studied; concrete representability,
|> | or EXPLICIT definability, or presentable as mental constructions.
|>
|> I consider this misleading, since many proofs in
|> mathematics are what people would reasonably call
|> "explicit" without being constructive, and sometimes
|> vice-versa.
|
|While taking issue with the above definition, you have the
|distinct advantage of not having defined what *you* mean by
|"constructive" ;o)
Oh well, then, you don't realize just how lucky you are! ;-)
You're dealing with an old timer, who has both defined what
he means by "constructive", and over the years presented
arguments in favor of it, just not recently:
<1998072701052900.VAA23771@ladder01.news.aol.com>
As I see it, perhaps the crucial distinction between
constructive mathematics and other kinds is what we mean
when we say that an integer exists having a given property.
Bishop urged classical mathematicians to think about this.
In constructive mathematics, to prove that an integer exists
having a given property, one must be able in principle to
exhibit it (in decimal form, say).
What is meant in classical mathematics when one claims that
an integer exists is something weaker. It's sufficient to
prove that the nonexistence of such an integer leads to a
contradiction. Now in constructive mathematics, one can ask
whether the nonexistence of an integer with some property
leads to a contradiction too, but this kind of negative
claim is distinguished from the positive claim that such an
integer exists. This makes constructive mathematics richer
in distinctions than classical mathematics.
Certain principles very blatantly lead to results in which
one claims the existence of an integer that one knows no way
even in principle of exhibiting. In particular, the law of
excluded middle and the full axiom of choice do. (The axiom
of dependent choice does not.) Mathematical results that are
not dependent on the law of excluded middle, and use only the
axiom of dependent choice, have a natural family resemblance.
Now, there are those who sometimes say that being faithful
to the constructivist philosophy requires more, like
predicativity. I can appreciate their interest in such
distinctions, but my opinion is that they are much less
significant than the one between needing and not needing
the law of excluded middle or the axiom of choice. These
are relatively technical distinctions, ones that are
liable to be harder to respect in ordinary mathematical
work.
These other restrictions are also more of a substantial
impediment in some fundamental respects. One of the aspects
of the "strength" of an axiom system is which Turing
machines can be proven in the system to halt on all inputs.
Doing without the axiom of choice and the law of excluded
middle don't weaken the usual systems in this respect, but
requirements such as predicativity do.
I believe Troelstra's understanding of constructivism is
relatively good-- if I may say so myself!-- and I don't
claim the above definition of constructivism was made in
error. But I think I can make a solid case that the
definition is hard to interpret correctly unless one already
has some familiarity with constructive mathematics.
Suppose we have some mathematician unfamiliar with
constructive mathematics-- probably there are many thousands
who know essentially nothing about it. Suppose we are
considering a binary tree known to have infinitely many
nodes. According to Konig's lemma, it has an infinite
branch. It's easy to prove: at each node, go to the left if
there are infinitely many nodes in the tree on the left, and
to the right otherwise. By induction, one always has
infinitely many nodes above the node, hence the branch
defined this way is infinite. It's the "leftmost" infinite
branch in the tree.
If we asked our hypothetical mathematician whether this
counted as an "explicit" proof of the existence of an
infinite branch, they would surely say yes. In fact, I think
they should say yes. What does "explicit" mean, if this
kind of thing doesn't count as "explicit"? A classical
mathematician would be tempted, I think, to define
"explicit" to include any definition that uniquely specifies
the object being defined. To the extent that this is not
enough to make the definition "explicit", I think one has
to say that "explicit" is a little vague.
On the other hand, this "explicit" definition of a branch
in the tree is just as nonconstructive as the definition
N=3 if the Riemann hypothesis is true, N=4 if not. In fact,
one can define a computable infinite binary tree where the
infinite branch described above first turns to the left at
level 3 if the Riemann hypothesis is true, and at level 4
if it is not.
We could try to correct this misimpression by suggesting to
our mathematician that in this case, we mean "explicit" in
a sense related to computation. That seems often to lead to
errors on the other side, supposing that lots of proofs
don't count as constructive, because they don't fit in with
a superficial notion of what it might mean to "compute" a
mathematical object.
It's a recurring pitfall, for example, to get the idea that
the only sets "accepted" by constructivists are the ones
where membership is computable. One might think that the
set of primes would be "accepted" but the set of halting
Turing machines would not.
Neither Brouwer nor Bishop nor Markov (etc.) imposes such
a restriction on what counts as a set, however, and with
good reason. None of the virtues of constructivism depends
on such a restriction, and it makes one's constructive
mathematics more confined. In real analysis, the only sets
of reals where membership is computable are the empty set
and the real line itself, so it would mean essentially not
using sets of reals at all.
Keith Ramsay
- Next message: anon: "Re: From sign conventions to Galois Theory"
- Previous message: Alec Mihailovs: "Re: mod for floats"
- In reply to: r.e.s.: "Re: does sqrt(2) exist in CM?"
- Next in thread: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
