At 16:37 29/11/03 -0500, Jesse Mazer wrote:
>But as I said earlier, the power set of a countable set would include
>plenty of sets that could not be defined using any sort of finite
>description, and I'm skeptical about the "existence" of such objects in a
>Platonic sense. Perhaps what I'm talking about would be a form of
>"mathematical constructivism", although I don't know how "constructible"
>is usually defined, and whether it would allow for noncomputable numbers
>that can still be defined in terms of some finite program of an
>oracle-machine whose "level" can itself be finitely defined (see my post
>at http://www.mail-archive.com/everything-list.domain.name.hidden/msg04809.html
>for what I mean by different 'levels' of oracle-machines, I'm not sure if
>my terminology is correct here although I've seen similar ideas expressed
>before).
You ask difficult question which could lead to subtle technical
distinction. Grosso modo, in your post
"
http://www.mail-archive.com/everything-list.domain.name.hidden/msg04809.html", you
seem to be climbing the "arithmetical hierarchy" and the classical degrees
of insolubility. I think you can do that indeed in some strong
intuitionistic arithmetic, using for exemple intuitionistic version of
Church thesis and the so-called
markov principle:
[(x) (P(x) or not P(x)) and not not ExP(x)] implies ExP(x)
Where (x) is the intuitionistic quantifier "for-all", Ex is the
intuitionistic quantifier "exists", and the "and", "or", "implies" are the
intuitionistic connector.
Markov principle is a weak but still rather strong form of "intuitionistic
exluded middle" But once you use the classical (full power) excluded middle
principle then forget about "constructivisme".
Note that Artemov has shown that Markov principle is not a theorem of the
quantified version of the arithmetical intuitionistic logic (the one
corresponding to the modal logic S4Grz which corresponds to the
arithmetical (self-referential) pure first person in my thesis. (This
confirms the fact that no machine can ever know to be some well-defined
machine).
I will think about books capable of helping here ...
I will comment the next paragraph once I have more time. But it seems to me
that the explanations are in the diagonalization posts
(see my URL). Just convince yourself first that "constructive real number"
and "computable function from N to N" are recursively equivalent.
The distinction you are searching, if I understand you correctly, is the
distinction between "countable and recursively countable", and
"countable but not recursively countable".
A recursively countable set can have countable subset which are not
recursively countable. This is no more strange than the fact that
a simple object like a white page can have complex subset like the
"Joconde" ....
Bruno
>On second thought though, if I am only willing to admit mathematical
>objects with finite descriptions, then I should probably not even
>distinguish between countable and uncountable sets, since the collection
>of all possible finite descriptions must be countable. But there is
>another sense in which it makes sense to distinguish two different types
>of infinity here. To prove that a set is countable, one must find a
>function mapping the positive integers to the members of the set, with
>every member corresponding to one integer. But if only mathematical
>objects with finite descriptions are permitted, this should go for
>functions mapping integers to mathematical objects as well; and it's
>relatively easy to see that no finitely-describable function would include
>*every* object with a finite description (but no meaningless descriptions
>which don't pick out mathematical objects at all), using a diagonal
>argument. Suppose we just want to come up with an exhaustive list of all
>the finitely-describable reals, and we have some candidate function which
>maps every positive integer to a real with a well-defined finite
>description ('well-defined' meaning that there is no ambiguity about what
>number the description picks out--'a number bigger than 4' would not be a
>well-defined description, for example, since it doesn't pick out a unique
>real). If the function F is itself clearly defined, so there is no
>ambiguity about what real a given integer is mapped to, then a description
>like "the real number formed by changing the nth digit of the binary
>expansion of the real number that maps to integer n under function F"
>should itself be a well-defined finite description which picks out a real
>number that differs from every number on the list by at least one digit.
>
>So, although the set of all well-defined finite descriptions must clearly
>be "countable" in the traditional sense where arbitrary mappings are
>allowed, it is not countable if only finite-describable mappings are
>allowed, although it can easily be shown to be smaller than another
>countable set, namely the set of all finite descriptions without regard
>for whether they are "well-defined" or not (just list all strings of
>english symbols in lexical order, although most of these will be
>completely meaningless like "xhh{we2lkjk4j5j", and will thus not pick out
>any particular real number). The basic problem here is that the notion of
>what it means for a description to be "well-defined" can never be stated
>in terms of a formal rule--this is reminiscent of the fact that no formal
>rules can encompass our understanding of arithmetic, that no matter what
>axioms we use there will always be theorems that we can prove to be true
>in ordinary-language proofs which cannot be proved true or false by the
>axiomatic system. These ordinary-language proofs will nevertheless be seen
>as quite rigorous by any mathematicians who are Platonists about
>arithmetic--I believe Godel used such a proof to show that the Godel
>statement G for the axioms of Peano arithmetic (or any other
>axiomatization of arithmetic) must in fact be a true theorem even though
>it's not provable using the axioms, as long as we interpret the symbols to
>refer to our mental model of arithmetic (see the discussion about Platonic
>'models' in math at
>http://www.mail-archive.com/everything-list.domain.name.hidden/thrd2.html#04463
>for more on this).
>
>Jesse Mazer
>
>_________________________________________________________________
>online games and music with a high-speed Internet connection! Prices
>start at less than $1 a day average. https://broadband.msn.com (Prices
>may vary by service area.)
http://iridia.ulb.ac.be/~marchal/
Received on Tue Dec 02 2003 - 06:58:09 PST