Talk:Arithmetical hierarchy

This is the talk page for discussing improvements to the Arithmetical hierarchy article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Tip: Anchors are case-sensitive in most browsers.

This article links to one or more target anchors that no longer exist.

[[Peano axioms#First-order theory of arithmetic|first-order arithmetic]] The anchor (#First-order theory of arithmetic) has been deleted by other users before.

Please help fix the broken anchors. You can remove this template after fixing the problems. | Reporting errors

Untitled

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)

I know it's a lot to read, but 13 years is a bit much ;) 91.66.2.94 (talk) —Preceding undated comment added 16:12, 1 October 2016 (UTC)[reply]

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)[reply]

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)[reply]

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 _{1}^{0}

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 _{2}^{0}

set is "effectively F_σ", and so on. --Trovatore 17:19, 24 September 2005 (UTC)[reply]

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 _{3}^{0}$ 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 _{1}^{0}

.

The

\Sigma _{3}^{0}

sets are the ones that are the effective counterpart of the

G_{\delta \sigma }

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_{\delta }

's. --Trovatore 18:45, 24 September 2005 (UTC)[reply]

Whoops--actually I skipped a step here. Along each row you need to intersect

\Sigma _{1}^{0}

'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)[reply]

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 _{1}^{0}$ sets are exactly the recursively enumerable set in the computability concept induced by $\nu$ on your topological basis.

Pretty much, but that doesn't take you past

\Sigma _{1}^{0}

. For example if you union up the basic open sets with indices in a

\Sigma _{2}^{0}

set of naturals, you still get an open set of reals. --Trovatore 18:45, 24 September 2005 (UTC)[reply]

Ok, but

\nu

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 _{2}^{0}

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)[reply]

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)[reply]

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 _{1}^{0}

, 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 _{2}^{0}

, 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 _{2}^{0}

collection of basic open sets, because

\mathbb {Q}

is not open. --Trovatore 21:01, 24 September 2005 (UTC)[reply]

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)[reply]

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 _{n}^{0}

sets of basic open sets. We want

\Sigma _{n}^{0}

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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

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)[reply]

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 Σⁿ_m, 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 Σⁿ_m 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 Πⁿ_m. Hope this helps, Trovatore 00:43, 25 February 2006 (UTC)[reply]

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)[reply]

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.

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)[reply]

When you do, please define \Delta _{n}^{0}, that would help make the article much more comprehensible. 76.254.27.203 (talk) 04:09, 8 September 2023 (UTC)[reply]

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).[reply]

See Kozen - Theory of Computation (pp. 239-246) for natural complete problems in the Arithmetic Hierarchy of sets of natural numbers. That is EMPTY for \Pi^0_1, the halting Problem for \Sigma^0_1, TOTAL for \Pi^0_2, FIN(ITE) for \Sigma^0_2 and COF(FINITE) for \Sigma^0_3. These are all index sets and their names are rather self-explanatory. The halting problem is well-known and the names of the other ones refer to the property of the domains of the functions with the respective index. 129.206.103.183 (talk) 20:11, 15 April 2011 (UTC)[reply]

logic hierarchy

There's apparently an alternate expression called the "logic hierarchy", described in Girard's "The Blind Spot" p. 45-46 [1]. I can't quite tell what it means, but it looks like $\Sigma ^{n}$ (with no subscript) in the logic hierarchy means the same thing as $\Pi _{n-1}^{0}$ from the arithmetic hierarchy, and $\Pi ^{n}$ means $\Sigma _{n-1}^{0}$ . I won't add this myself since probably I don't have it right, but maybe it's worth a mention. 66.127.55.192 (talk) 00:13, 18 February 2010 (UTC)[reply]

I don't understand Girard's description (Same as before [presumably referring to the projective hierarchy described in the previous paragraph], but the first order quantifiers are not numerical—WTF???), but one thing is certain, namely that it is a stratification of second-order formulas, it thus corresponds to the projective hierarchy rather than the arithmetical hierarchy. According to Girard's examples, every

\Pi _{n-1}^{1}

-formula is

\Pi ^{n}

for n > 1, while the next section suggests that

\Pi ^{1}=\Sigma _{1}^{0}

(don't ask me why). In particular, all of arithmetical hierarchy fits inside

\Pi ^{2}\cap \Sigma ^{2}

.—Emil J. 12:49, 18 February 2010 (UTC)[reply]

Furthermore, it seems that what Girard calls the "projective hierarchy" is actually the analytical hierarchy (i.e., lightface), but that does not make much difference here.—Emil J. 12:53, 18 February 2010 (UTC)[reply]

The translation from the french is kind of rough, and the french version has either been taken offline (it was published as a printed book a couple years ago) or was never there, but anyway I can't compare the two as a result. Thanks for trying to decipher the english version. I thought maybe "logic hierarchy" was some standard term. 66.127.55.192 (talk) 13:32, 18 February 2010 (UTC)[reply]

Extensions and variations

I believe the "Extensions and variations" sections mentions two alternatives but it's not clear that these are in fact two different alternatives.

Moreover for the recursive/computable definition I believe it only differs from the usual definition for $n=0$ where the computable-definition version of the $\Delta _{0}^{0}$ sets are the same as the $\Delta _{1}^{0}$ ones.

Lastly doesn't the $\Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}$ property also hold for $n=0$ using the definition which is worked with in this article (it is not the case if one works with the other definition which might be why this result is quoted only for $n\geq 1$ . Catrincm (talk) 14:13, 30 September 2014 (UTC)[reply]

-al

I have a general sense that the "-al" versions of "arithmetical hierarchy" and "hyperarithmetical hierarchy" are more common. I don't think "analytic hierarchy" is used at all. So I have restored the original endings here. — Carl (CBM · talk) 20:14, 24 May 2018 (UTC)[reply]

I think the meaning of analytic has settled down to boldface

\Sigma _{1}^{1}

, but there is an older usage (possibly still current in French?) that makes it synonymous with "projective" (i.e. boldface

\Sigma _{<\omega }^{1}

). So it wouldn't surprise me if someone somewhere uses analytic hierarchy in the sense of "projective hierarchy".

There is a separate meaning for analytical, which I think is something like "lightface projective", but the risk of confusion is so great that it's probably better avoided. --Trovatore (talk) 20:35, 24 May 2018 (UTC)[reply]

Pronunciation

As someone with only passing familiarity of this area, I can't remember whether $\Sigma _{1}^{0}$ is pronounced “sigma one zero” or “sigma zero one”. I think saying which it is would be a helpful and easy addition. N4m3 (talk) 10:16, 21 September 2020 (UTC)[reply]

Bounded quantifiers versus quantifier-free

The article previously contained the claim that any formula with bounded quantifiers is equivalent to a quantifier-free formula. There was a "citation needed" comment questioning this claim, and it is indeed false, so I removed it. I just wanted to record a counter-example here (there may be simpler ones):

We claim that the $\Delta _{0}^{0}$ set $X=\{n\in \mathbb {N} \mid \exists k\leq n(2k=n)\}$ of all even numbers cannot be defined by a quantifier-free formula $\phi$ .

That is, writing $X_{\phi }$ for $\{n\in \mathbb {N} \mid \phi (n)\}$ , we are claiming that $X\neq X_{\phi }$ for all quantifier-free $\phi$ .

By putting $\phi$ in disjunctive normal form, we have that $X_{\phi }$ is a finite union of finite intersections of sets $X_{\psi }$ with $\psi (n)$ atomic. Such a $\psi (n)$ is equivalent either to the formula $p(n)=0$ or to $p(n)>0$ for some polynomial $p$ with integer coefficients.

Such a $p(n)$ is either constant or tends toward $\pm \infty$ as $n\to \infty$ . It follows that $X_{\psi }$ is either finite or has finite complement. Since this property is preserved by finite unions and intersections, it follows that $X_{\phi }$ has this property as well.

But $X$ does not have this property, and hence $X_{\phi }\neq X$ , as claimed. Jslam (talk) 06:32, 28 April 2023 (UTC)[reply]

Well done! Thanks for correcting the record. This claim looked very fishy to me as well but I didn't put in the time to find a counterexample. Caleb Stanford (talk) 21:57, 28 April 2023 (UTC)[reply]

hierarchies overview/NavBox

It would be great if we had a NavBox of all the different hierarchies: polynomial hierarchy, weak exponential hierarchy, arithmethical hierarchy, hyperarithmetical hierarchy, and the ones shown here. The current NavBox (at the bottom) could be expanded. Assuming P≠NP≠PH, a NavBox could look like this:

Polynomial H.			(Strong) Exponential H.			Arithmetical H.
$\Delta _{0}^{P}=$ P		${\overset {?}{\subseteq }}$ PSPACE	$\Delta _{0}^{EXP}=$ EXPTIME		${\Bigg \}}$	$\Delta _{0}$ =
$\Sigma _{1}^{P}=$ NP	$\Pi _{1}^{P}=$ CoNP		$\Delta _{1}^{EXP}$			$\Sigma _{1}=$ c.e.	$\Pi _{1}$
$\Delta _{1}^{P}$			$\Sigma _{1}^{EXP}=$ NEXP	$\Pi _{1}^{EXP}$		$\Delta _{1}$
$\Sigma _{2}^{P}$	$\Pi _{2}^{P}$		$\Delta _{2}^{EXP}$			$\Sigma _{2}$	$\Pi _{2}$
$\Delta _{2}^{P}$			$\Sigma _{2}^{EXP}$	$\Pi _{2}^{EXP}$		$\Delta _{2}$
$\Sigma _{3}^{P}$	$\Pi _{3}^{P}$		$\Delta _{3}^{EXP}$			$\Sigma _{3}$	$\Pi _{3}$
$\vdots$			$\vdots$			$\vdots$
$\Delta _{\omega }^{P}=$ PH			$\Delta _{\omega }^{EXP}$ =EXPH			$\Delta _{\omega }$
$\vdots$			$\vdots$			$\vdots$

(I've put the question mark above PSPACE since we could also consider ordinals larger than $\omega$ or $\omega _{1}^{CK}$ (for which it has been proven here)

CaffeineWitcher (talk) 09:40, 14 August 2023 (UTC)[reply]

Wouldn't it be more useful to have a navbox of the complexity classes adjacent to the specific hierarchy in question (e.g., P ⊆ PH ⊆ PSPACE on the PH page)? Beyond the fact that they are all hierarchies, PH, EXPH, and AH belong to very different positions in complexity space. Caleb Stanford (talk) 21:42, 14 August 2023 (UTC)[reply]

Baire Space

I was confused by the sentence "Every subset of Baire space or Cantor space is an open set in the usual topology on the space."

The Wikipedia entry on "Baire space" which is linked to here deals with the topological notion of a Baire space. Correct me if I am wrong, but I think the link should be to Baire space (set theory). Since the topological notion is probably more familiar to many readers, the sentence as it stands is likely to create confusion. Using the term "Baire space (set theory)" would alert readers to the fact that the topological notion is not the one being referred to here. Jrvarma (talk) 06:39, 30 November 2023 (UTC)[reply]