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?
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?
Well, C isn't recursively enumerable, so C (and, therefore, ~C) isn't recursive, if that's what you're getting at.
ReplyDeleteQuite 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.)
ReplyDeleteIf 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).
ReplyDeleteSince C has Hausdorff dimension log 2/log 3, this would mean C is not recursively enumerable and, hence, cannot be recursive.
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.
ReplyDeleteDoes anybody know the proof of this obvious(?) fact: "every recursively enumerable set is recursive"?
ReplyDelete