Re: A question about Caontor's proof of the uncountability of the reals
- From: "Keith Ramsay" <kramsay@xxxxxxx>
- Date: 4 Mar 2006 20:42:43 -0800
Michael Olea wrote:
|No. I thought I did but I was misunderstanding what I read - in
particular I
|failed to distinguish the rule above (which relies on the law of
|non-contradiction, but not on LEM) from the rule below (which relies
on
|both LNC and LEM). So I guess some forms of proof by contradiction are
|acceptable even to intuitionists. And Cantor's diagonalization
argument
|follows the pattern of the rule above, so it too should be acceptable
to
|intuitionists.
Correct.
In one form, the Cantor diagonal proof is not quite right
intuitionistically. He uses the lemma that each real has
a decimal expansion. However this is nonconstructive.
If a number is very close to 1, for example, in order for
it to have a units digit, it must be either <1 or >=1.
Intuitionists represent real numbers using converging
sequences much like anybody else does, but to say
that such a sequence either converges to a limit <1
or to a limit >=1 amounts to saying that any sequence
either does or does not have a term of a certain kind.
However precisely we may compute the number, we
may not necessarily show that it is <1 or >=1.
That is in a sense a minor problem, though.
Brouwer proved a lemma about negation, that the
triple negative is equivalent to the single negative.
~P. So likewise we can deduce ~~~P from ~P.From P we can deduce ~~P since P contradicts
Conversely, ~~~P contradicts P, because P implies
~~P and ~~~P directly contradicts ~~P. So from
~~~P we can also deduce ~P.
A lot of the point of intuitionist logic is that it allows
us to make express certain distinctions in a way
that's usually prevented by the identification of each
statement with its double negation. There's an
example from the theory of Thue equations that I
like to use. These are a kind of Diophantine equation,
an equation to be solved in integers. At a certain
point, it was proven (nonconstructively) that there are
finitely many solutions to a certain kind of Thue equation.
The way it was done was by assuming that there are
infinitely many solutions, and deriving a contradiction.
If there are infinitely many, the reasoning went, then
there is a sequence of solutions each of which is
sufficiently much greater than the previous ones, as
given by an inequality, and the bulk of the argument
was to show that this then leads to a contradiction.
In constructive terms, this is a perfectly fine proof that
the set of solutions is "not infinite". Of course, we might
also want to know if the set of solutions is finite. At least
we know that the answer isn't going to be "no, it's infinite",
but there's no guarantee that there's an answer at all.
So eventually it was also proven that the set of solutions
is finite, and this was considered important, significant
work.
In the terms used by nonconstructive mathematics, what
the later proof achieved that the first one didn't was to give
us an "effective bound" on the size of the solutions. So in
that case, one might say that there was just a difference
in terminology. But in general such a difference in terminology
can be a big deal. Intuitionist mathematics, and constructive
mathematics generally, makes a different set of questions
seem obvious to ask.
It's not obvious what the pros and cons
of this are. Sometimes nonconstructive mathematics makes
questions sound simple that if expressed in constructive
terminology would seem relatively ugly; you may for example
wind up with a lot of double negatives and the like. You might
think this was a good thing (to make it sound simple). Or
perhaps you might think it could be misleading to make the
more complicated thing sound as if it were entirely on par
with the more natural, straightforward construction.
Suppose I show that a sequence of reals a0,a1,a2,... has the
property that for each epsilon>0, there exists an N such that
there does not exist a subsequence a_i1,a_i2,a_i3,... such
that |a_i1-a_i2|,...,|a_i_{N-1}-a_i_N| > epsilon. It only moves
by epsilon a limited number of times for each epsilon>0, one
might say informally. If you think about it, probably you'll find
it easy to see that (nonconstructively) this means the same
thing as saying that the sequence a0,a1,a2,... converges
(is Cauchy). Constructively, though, convergence means
something stronger. Is it a good thing to ignore the distinction?
Don't we sometimes really want a series that converges in
the constructive sense? Is it easier to distinguish them using
constructive terminology, or is it easier to think of this as a
"theory of computation" issue to be considered afterward?
Keith Ramsay
.
- Prev by Date: Re: JSH: Issue of "counterexamples"
- Next by Date: Re: ? meanings of eigenspan and SVD
- Previous by thread: Re: JSH: Issue of "counterexamples"
- Next by thread: Interest compounded daily?
- Index(es):
Relevant Pages
|
Loading
