Re: Why? [was Re: Cantor`s powerset theorem is false?]
- From: stevendaryl3016@xxxxxxxxx (Daryl McCullough)
- Date: 5 Jun 2006 03:52:43 -0700
Pietro says...
Daryl McCullough wrote:
I agree. It is consistent with constructive mathematics to
assume that there are no real numbers other than computable
reals. However, it is still the case that Cantor's theorem
holds: there is no bijection between the reals and the naturals.
If it is the case that no bijection exists between reals and
naturals, I would expect it to be in the sense of it not being
definable / computable.
We're talking about the case in which one assumes that no functions
exist other than computable ones. In that case, if there is no
computable bijection, then there is no bijection, period.
One would not say that there are "more" reals, since the above is
an injection from a substet of N into [0,1].
Yes, that's right. The classical notion of cardinality as
a measure of size is not very useful in constructive mathematics.
Is it really the case, though, that there is no bijection? In
systems of constructive math in general? If one takes "function" to
mean "recursive function", and tries to carry out Cantor's proof on my
enumeration, it doesn't go through.
Yes, it does. If F is the set of all total recursive functions from
N to N, then Cantor's proof shows that there is no recursive surjection
from N to F.
(It is an enlightening exercise, for those that haven't tried it.)
I'm not sure what you are talking about. The Cantorian proof
goes like this:
Let F be the set of all total functions from N to N.
Let m be any function from N to F.
Now consider f defined as follows:
f(x) = m(x)(x) + 1
Clearly, f is an element of F, and clearly
f is not in the image of m. So m is not a surjection.
This proof works perfectly fine if we restrict F to recursive
functions as long as we also restrict m to be a computable
functional.
I know close to nothing about this,
and your assertion is a bit of a surprise. Can you provide a reference?
I posted some references earlier on this very thread.
You are completely right that it is often more complicated to do
things constructively. However, it could be contended that this refers
to a purely operational definition of "complicated", e.g. harder to
derive theorems, harder to define stuff etc.
That's what I usually mean when I say something is complicated.
And that this should not (and is not) be the primary criterion
on which to judge mathematics.
I agree. Constructive mathematics offers insight into mathematics
that is glossed over by classical mathematics.
For example, the mathematical community as whole seems to think the
19th-century reformulation of real analysis was a positive step, though
the infinitesimals and infinities were immensely easier to work with.
Just look at some of the stuff Euler did in analytic number theory.
Once, I redid some of it on the basis of limits and whatnot, which
would now be considered rigorous, and it was a *major* pain.
Might there not be some sort of parallel between those "ghosts of
departed quantities" and today's more wildly infinitary set theories?
If there was, wouldn't that be at least as important a consideration as
"ease of use", in deciding whether to switch to constructive math? And
if there is not, what important differences are there between
infinitesimals and uncountable sets?
Well, it's possible, but in the case of infinitesimals, the
problem was the lack of *rigor*. If you tried to formalize
how to reason about infinitesimals, then either you ended
up with something inconsistent, or else you ended up with
a complicated ad hoc collection of rules of thumb.
So to me, the analogy is not with modern set theory, but with
Frege set theory, which was inconsistent. You could use Frege
set theory to do interesting and useful mathematics, but it was
formally inconsistent. Russell's theory of types was an attempt
to do set theory in a more rigorous way, and although it was
consistent, it was more complicated and harder to work with
than Frege's theory. ZFC, in contrast, seems as consistent as
Russell's theory, but is not much more complicated than Frege's
theory.
--
Daryl McCullough
Ithaca, NY
.
- Follow-Ups:
- References:
- Prev by Date: Re: FO logic without equality
- Next by Date: Re: FO logic without equality
- Previous by thread: Re: Why? [was Re: Cantor`s powerset theorem is false?]
- Next by thread: Re: Why? [was Re: Cantor`s powerset theorem is false?]
- Index(es):
Relevant Pages
|
Loading
