News

Loading...

Friday, March 21, 2008

Cantor set III

I think it’s time for Captain Recursive to take the podium. (If you don’t think so, but would like to, see Kleene, S. C., “Metamathematics” or any number of more recent texts, most having the word “computable” in their title.) To begin with, it is important (for reasons some of which will appear below) that recursive sets be defined in the context of a well defined superset. Always, recursive sets and other related kinds of sets are taken to be subsets of numbers (Mr. Goedel and others have convincingly demonstrated that pretty much everything can be realized as numbers of some sort or other), and we shall do so. We’ll use “~” to indicate the complement of a set.

A recursive set is one whose membership is computable, in the strong sense that, given a number n, there is an algorithm (a computer program, if you will) which, in finite time, outputs the answer to the question, is n a member of the set.

A recursively enumerable set is one whose membership is computable, in the sense that there is an algorithm which cranks out the members, and only the members, of the set, all in finite time each.

Obviously (?), a recursive set is recursively enumerable; the reverse is not true. (Can you find a recursively enumerable set that is not recursive?)

If S and ~S are recursively enumerable, then S and ~S are recursive. (Just keep grinding away until the number in question shows on one of the two lists, QED.)

If the recursive enumeration of a recursively enumerable set S follows a computable linear order, then S is recursive. (Grind away until you have passed the ordering of the number in question; either it has shown up, or it has not.)

OK, why have I gone through all this, other than to impress y’all how brilliant I am (or at least how well I remember my math courses)?

Let’s look at the Cantor set C. Clearly (?), ~C is recursively enumerable. So what else can we say?

7 comments:

  1. Well, C isn't recursively enumerable, so C (and, therefore, ~C) isn't recursive, if that's what you're getting at.

    ReplyDelete
  2. Quite right--but *is* C recursive? This is the formal way to ask the question that I asked in CsII, and is why I went through the stuff in CsIII. I admit that it looks like no, but maybe this is just a way of saying that the question is hard. (I do not know the answer, but I suspect that it is indeed No.)

    ReplyDelete
  3. If C were recursive, then of course it would be recursively enumerable. I haven't read it, but supposedly somewhere in this paper the authors note that any recursively enumerable set over the reals must have integral Hausdorff dimension (I say "supposedly" because I'm just taking the author of this paper at his word).

    Since C has Hausdorff dimension log 2/log 3, this would mean C is not recursively enumerable and, hence, cannot be recursive.

    ReplyDelete
  4. shonk: fascinating--thanks for the tip; I shall investigate. There is a catch here that I left out of everything, partly because I wasn't sure how to express it concisely, partly because I thought it woud help the ratiocination of you guys out there if I left it for you. Classically, recursive, creative, and other related properties of sets are defined in countable sets. Clearly ~C is r.e. because--even though it is uncountably infinite, we are defining it in a countably infinite number of uncountably infinite chunks. But my take on all this is highly unconventional: for example, it is no longer obvious that a recursive set is r.e.--the classical argument no longer applies when the set in question is uncountably infinite! Good luck, and let me hear from you again.

    ReplyDelete
  5. Does anybody know the proof of this obvious(?) fact: "every recursively enumerable set is recursive"?

    ReplyDelete
  6. We offer WoW power leveling,World of Warcraft power leveling,Warhammer Online Power Leveling & Warhammer Power Leveling & Warhammer Online Gold,if you want buy cheap wow power leveling & honor power leveling,please come here to choose. you could find any kinds of powerleveling you want. Please remember,we are your online game helper. Please remember,we are your online game helper.please come here to choose. you could find anything you want.wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,Warhammer Online Power Leveling,war leveling,Warhammer leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,WAR Power leveling,WAR Gold,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,wow gold,wow gold,wow gold,wow gold,wow gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,AOC Power Leveling,AGE OF CONAN Power Leveling,Warhammer Online Power Leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,2 Moons Dil,MapleStory Mesos,Maple Story Mesos,MS Mesos,WARHAMMER ONLINE GOLD,Cheap WARHAMMER ONLINE GOLD,RuneScape Gold,RS Gold,RuneScape Money,RS Money,SilkRoad Gold,SilkRoad Online Gold,SRO Gold,EVE ISK,EVE Online ISK,Gaia Gold,2 Moons Dil,WOTLK power leveling,AOC Gold,AGE OF CONAN Gold,LOTRO Gold,Lord of the Rings Online Gold

    ReplyDelete
  7. We offer WoW power leveling,World of Warcraft power leveling,Warhammer Online Power Leveling & Warhammer Power Leveling & Warhammer Online Gold,if you want buy cheap wow power leveling & honor power leveling,please come here to choose. you could find any kinds of powerleveling you want. Please remember,we are your online game helper. Please remember,we are your online game helper.please come here to choose. you could find anything you want.wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,Warhammer Online Power Leveling,war leveling,Warhammer leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,WAR Power leveling,WAR Gold,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,wow gold,wow gold,wow gold,wow gold,wow gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,AOC Power Leveling,AGE OF CONAN Power Leveling,Warhammer Online Power Leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,2 Moons Dil,MapleStory Mesos,Maple Story Mesos,MS Mesos,WARHAMMER ONLINE GOLD,Cheap WARHAMMER ONLINE GOLD,RuneScape Gold,RS Gold,RuneScape Money,RS Money,SilkRoad Gold,SilkRoad Online Gold,SRO Gold,EVE ISK,EVE Online ISK,Gaia Gold,2 Moons Dil,WOTLK power leveling,AOC Gold,AGE OF CONAN Gold,LOTRO Gold,Lord of the Rings Online Gold

    ReplyDelete