Editing Arithmetical hierarchy (section)

== Properties ==

The following properties hold for the arithmetical hierarchy of sets of natural numbers and the arithmetical hierarchy of subsets of Cantor or Baire space.

* The collections <math>\Pi^0_n</math> and <math>\Sigma^0_n</math> are closed under finite [[union (set theory)|union]]s and finite [[intersection (set theory)|intersection]]s of their respective elements.
* A set is <math>\Sigma^0_n</math> if and only if its complement is <math>\Pi^0_n</math>.  A set is <math>\Delta^0_n</math> if and only if the set is both <math>\Sigma^0_n</math> and <math>\Pi^0_n</math>, in which case its complement will also be <math>\Delta^0_n</math>.
* The inclusions <math>\Pi^0_n \subsetneq \Pi^0_{n+1}</math> and <math>\Sigma^0_n \subsetneq \Sigma^0_{n+1}</math> hold for all <math>n</math>. Thus the hierarchy does not collapse. This is a direct consequence of [[Post's theorem]].
* The inclusions <math>\Delta^0_n \subsetneq \Pi^0_n</math>, <math>\Delta^0_n \subsetneq \Sigma^0_n</math> and <math>\Sigma^0_n \cup \Pi^0_n \subsetneq \Delta^0_{n+1}</math> hold for <math>n \geq 1</math>.
:*For example, for a [[universal Turing machine]] ''T'', the set of pairs (''n'',''m'') such that ''T'' halts on ''n'' but not on ''m'', is in <math>\Delta^0_2</math> (being computable with an oracle to the halting problem) but not in <math>\Sigma^0_1 \cup \Pi^0_1</math>.
:*<math>\Sigma^0_0 = \Pi^0_0 = \Delta^0_0 = \Sigma^0_0 \cup \Pi^0_0 \subseteq \Delta^0_1</math>. The inclusion is strict by the definition given in this article, but an identity with <math>\Delta^0_1</math> holds under one of the variations of the definition [[Arithmetical hierarchy#Extensions and variations|given above]].