Talk:Arithmetical hierarchy

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Foundations, logic, and set theory

We need the following interesting facts:

  • The hierarchy does not collapse; which I think is from Kleene
  • possibly conflating this article with any analytical hierarchy article
Hmmm. Actually, I think the article is pretty broken at the moment. It's on my "to fix" list, but it'll take time because I'll need to re-read material on the subject. Feel free to beat me to it :) -- Pde 14:15 12 Jun 2003 (UTC)

Contents

[edit] article on the move again

Thanks to MathMartin for putting in some useful stuff. The big problem left with this article, and also with analytical hierarchy, is that when it talks about sets, it's not clear sets of what. I think MathMartin is thinking of sets of naturals, but the same concepts and notation are important for sets of reals (subsets of Baire space, Cantor space, general Polish spaces). Unfortunately finding good language for that is awkward. --Trovatore 17:10, 24 September 2005 (UTC)

I just noticed we were editing the page nearly in parallel :). Yes I am indeed thinking about sets of naturals and computable functions. What do you mean by arithmetical hierarchy for sets of reals ? Can you not just use a numbering (computability theory) to transfer the computability concept (an the arithmetical hierarchy) defined on the natural numbers to any other structure ? MathMartin 17:14, 24 September 2005 (UTC)
Not quite sure what you mean by that. The spaces I'm interested in are of course uncountable, though their topologies have countable bases. The idea is that a \Sigma^0_1 set of reals is "effectively open"; that is, there's a computable collection of indices for basic open sets, the union of which is the given set. A \Sigma^0_2 set is "effectively Fσ", and so on. --Trovatore 17:19, 24 September 2005 (UTC)

Are you saying you want to put the sets in a certain topological space in some sort of hierarchy according to how difficult they are to construct using the countable basis of the space ? In your hierarchy what are the \Sigma^0_0 sets (is this your basis ?) and the \Sigma^0_3 sets ?

The \Sigma^0_0 sets could be taken to be the basic clopen sets; in the real numbers strictly speaking there are only two of these, but in Baire space or Cantor space there are plenty. To make the discussion useful on the "real reals" it's better not to start with \Sigma^0_0, but with \Sigma^0_1.
The \Sigma^0_3 sets are the ones that are the effective counterpart of the Gδσ sets. That is, there's a computable way of putting indices for basic open sets into an infinite square matrix, intersecting the basic open sets in each row, and then unioning up all the resulting Gδ's. --Trovatore 18:45, 24 September 2005 (UTC)
Whoops--actually I skipped a step here. Along each row you need to intersect \Sigma^0_1's, not just basic opens. So we actually need to start by computably filling up an infinite cube with indices for basic opens. Details left as an exercise. --Trovatore 18:53, 24 September 2005 (UTC)

My understanding (what I meant to say) is you need a numbering

\nu: \mathbb{N} \to \mathcal{B}

where \mathcal{B} is the collection of open sets which forms the countable basis of your topology. This numbering has to be choosen in such a way that your \Sigma^0_1 sets are exactly the recursively enumerable set in the computability concept induced by ν on your topological basis.

Pretty much, but that doesn't take you past \Sigma^0_1. For example if you union up the basic open sets with indices in a \Sigma^0_2 set of naturals, you still get an open set of reals. --Trovatore 18:45, 24 September 2005 (UTC)
Ok, but ν induces a computability structure on \mathcal{B} which you can use to construct the collection of "effectively Fσ" sets (which corresponds to the collection of \Sigma^0_2 of naturals) as the B-computable sets for any B \in \mathcal{B}. The numbering does not directly induce the arithmetical hierarchy on the set \mathcal{B} but a computability concept, which then should allow you to build a new hierarchy similar to the arithmetical hierarchy. MathMartin 20:37, 24 September 2005 (UTC)
I'm not sure if I'm understanding you. By a "computability concept on \mathcal{B}", do you mean a notion of computable subsets of \mathcal{B}? That's not what we want; we're categorizing subsets of \mathbb{R}, not of \mathcal{B}. --Trovatore 20:47, 24 September 2005 (UTC)
Maybe an example would help focus things. Consider the set \mathbb{Q} of all rational numbers, as a subset of \mathbb{R}. For each rational q\in\mathbb{Q}, {q} is an effectively closed set, that is, \Pi^0_1, because there's a computable set of indices for basic open sets (these taken to be open intervals with rational endpoints) whose union is the complement of {q}. (Note that not every singleton is effectively closed; for example, if 0' is a real that codes the halting problem, then its singleton is not effectively closed (I think)).
The set \mathbb{Q}, as a subset of \mathbb{R}, is \Sigma^0_2, that is, effectively Fσ. That is, there's a computable way of assigning all at once a collection of "rows" of basic open sets whose union is the complement of each rational's singleton, and then unioning all those up.
But \mathbb{Q} is not the union of a \Sigma^0_2 collection of basic open sets, because \mathbb{Q} is not open. --Trovatore 21:01, 24 September 2005 (UTC)
Hmm, now I think I understand the problem. You want to construct a map f:2^{\mathbb{N}} \to 2^{\mathbb{R}} which maps the recursively enumerable sets in \mathbb{N} to the open sets in the basis \mathcal{B} of your topology. This map is not a numbering because it is not surjective. The problem consists in finding a countable subset X of 2^{\mathbb{R}} so that \forall B \in \mathcal{B} : B \in X and for a suitable numbering \nu : \mathbb{N} \to X, the elements of \mathcal{B} are exactly the recursively enumerable sets. Correct ? MathMartin 21:34, 24 September 2005 (UTC)
No, at least not literally. Maybe you made a typo, but of course such a countable X can't exist, because each of the B's is itself uncountable. But I still have the nagging suspicion that you're thinking of trying to define \Sigma^0_n sets of basic open sets. We want \Sigma^0_n sets of reals. And there isn't actually any problem; this is all completely standard and is standardly called the arithmetical hierarchy for sets of reals (see Moschovakis). The problem is how to convey the concepts in the article without making a mess of it. --Trovatore 21:42, 24 September 2005 (UTC)
Indeed, I made some typos which I corrected. But you are correct, I am a bit confused. I have not dealt with computability structure on uncountable sets before. What I was trying to get at was that there must be some sort of countable structure underneath the real number system (in some sense). Anyway thanks for the explanation. If you think the concepts you are talking about will mess up the article perhaps it would be best to start a new one. I would certainly like to read it. Cheers. MathMartin 22:02, 24 September 2005 (UTC)
I hardly think it needs a whole separate article. I'm coming to the conclusion that it probably needs a separate section, rather than just putting in a sentence about how the same concepts can be interpreted either on the reals or on the naturals. The thing is, I don't really think of this as computability, but as descriptive set theory, and I would have probably done the writeup for the concept on the naturals as descriptive set theory as well. But the computability-theory concepts are important and should be there, which complicates the presentation. --Trovatore 22:08, 24 September 2005 (UTC)

I am not an expert on this topic so I might be missing something. MathMartin

[edit] co-A-recursive set

The link to co-A-recursive set is a redirect to Relative computability, which doesn't actually define the term.--Bcrowell 22:36, 24 February 2006 (UTC)

I presume it means 'complement of A-recursive'. Charles Matthews 22:49, 24 February 2006 (UTC)

[edit] superscript 0

The article doesn't explain the meaning of the zero superscript. Even if you are lucky enough to click through to the article on Analytical hierarchy, there's still not much explanation of the relationship between the two articles or the meaning of the superscripts 0 and 1.--Bcrowell 22:36, 24 February 2006 (UTC)

Yep. There are all kinds of problems with this article. It's one of the ones I've got on my fix-up-someday list, but it looks like sort of an unpleasant job, so the expected time before I get to it is long.
Just in case you're asking what the superscript means, rather than merely complaining about something you know how to fix yourself, here's a quick-and-dirty explanation: When we write Σnm, the subscript m tells you the number of alternating quantifiers (starting with existential if it's Σ or universal if it's Π). The superscript n tells you the type of the objects you're quantifying over: Type 0 objects are naturals, type 1 objects are sets of naturals, or functions from the naturals to the naturals, or reals; type 2 objects are sets of sets of naturals, or functions from the reals to the reals, or sets of reals, or.... In general a Σnm set can be defined by a Σm formula in the structure Vω+n (which is a stage of the von Neumann hierarchy), and mutatis mutandis for Πnm. Hope this helps, Trovatore 00:43, 25 February 2006 (UTC)
Thanks for the explanation -- no, I did not know the answer or how to fix it. I've tried to fix it based on your explanation.--Bcrowell 00:05, 26 February 2006 (UTC)

[edit] Major edit 2006-6-13

I took some time this morning to substantially rework this article. I tried to fix the following problems.

  • The article was not precise about the fact that the AH classifies sets of natural numbers.
  • The article was not precise about what language the formulas come from.
  • The article had factual errors, such as the claim that Sigma^0_0 is the same as recursive.
  • I added a reference to Rogers' book.

Please feel free to change the stuff I wrote.

[edit] See analytical hierarchy

I am planning to edit this page like analytical hierarchy to mention both subsets of N and subsets of Baire space. CMummert 11:32, 26 June 2006 (UTC)

[edit] Content Request

Would someone include some natural complete problems for the Arithmetic Hierarchy (of sets of natural numbers)? Same goes for Analytic Hierarchy.

Examples: Sigma_1-complete to determine halting/looping of encoded Turing machines. Pi_2 complete to determine if encoded TMs accept an infinite set. Sigma_3-complete to determine if TM accepts a recursive set. Pi_3-complete to determine if TM encodes a walk that diverges properly to infinity.

I worked these out and they need checking. They are important to have around, because classifying the hierarchy level of a set almost invariably involves showing it complete for that level, and one needs a variety of target problems to work with just like with NP-completeness.

Thanks, Andy D. —The preceding unsigned comment was added by 66.117.149.88 (talk) 04:03, 23 December 2006 (UTC).