Effective descriptive set theory

Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptive set theory combines descriptive set theory with recursion theory.

An effective Polish space is a complete separable metric space that has a computable presentation. Such spaces are studied in both effective descriptive set theory and in constructive analysis. In particular, standard examples of Polish spaces such as the real line, the Cantor set and the Baire space are all effective Polish spaces.

The arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called "arithmetical".

More formally, the arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted ${\displaystyle \Sigma _{n}^{0}}${\displaystyle \Sigma _{n}^{0}} and ${\displaystyle \Pi _{n}^{0}}${\displaystyle \Pi _{n}^{0}} for natural numbers n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters.

If a formula ${\displaystyle \phi }${\displaystyle \phi } is logically equivalent to a formula with only bounded quantifiers then ${\displaystyle \phi }${\displaystyle \phi } is assigned the classifications ${\displaystyle \Sigma _{0}^{0}}${\displaystyle \Sigma _{0}^{0}} and ${\displaystyle \Pi _{0}^{0}}${\displaystyle \Pi _{0}^{0}}.

The classifications ${\displaystyle \Sigma _{n}^{0}}${\displaystyle \Sigma _{n}^{0}} and ${\displaystyle \Pi _{n}^{0}}${\displaystyle \Pi _{n}^{0}} are defined inductively for every natural number n using the following rules:

• If ${\displaystyle \phi }${\displaystyle \phi } is logically equivalent to a formula of the form ${\displaystyle \exists n_{1}\exists n_{2}\cdots \exists n_{k}\psi }${\displaystyle \exists n_{1}\exists n_{2}\cdots \exists n_{k}\psi }, where ${\displaystyle \psi }${\displaystyle \psi } is ${\displaystyle \Pi _{n}^{0}}${\displaystyle \Pi _{n}^{0}}, then ${\displaystyle \phi }${\displaystyle \phi } is assigned the classification ${\displaystyle \Sigma _{n+1}^{0}}${\displaystyle \Sigma _{n+1}^{0}}.
• If ${\displaystyle \phi }${\displaystyle \phi } is logically equivalent to a formula of the form ${\displaystyle \forall n_{1}\forall n_{2}\cdots \forall n_{k}\psi }${\displaystyle \forall n_{1}\forall n_{2}\cdots \forall n_{k}\psi }, where ${\displaystyle \psi }${\displaystyle \psi } is ${\displaystyle \Sigma _{n}^{0}}${\displaystyle \Sigma _{n}^{0}}, then ${\displaystyle \phi }${\displaystyle \phi } is assigned the classification ${\displaystyle \Pi _{n+1}^{0}}${\displaystyle \Pi _{n+1}^{0}}.

• Effective descriptive set theory
• Set theory stubs

• Articles with short description
• Short description matches Wikidata
• All stub articles