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/[EMAIL PROTECTED]/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/[EMAIL PROTECTED]/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/[EMAIL PROTECTED]/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/


Reply via email to