Hiérarchie analytique

Dans la logique mathématique et la théorie des ensembles descriptive , la hiérarchie analytique est un type plus élevé analogue de la hiérarchie arithmétique . Elle continue ainsi la classification des ensembles par les formules qui les définissent.

La hiérarchie analytique des formules

Le $de notation \ Sigma^1_0 = \ Pi^1_0 = \ Delta^1_0$ indique la classe des formules dans la langue de l'arithmétique de second ordre sans des quantifiers d'ensemble. Cette langue ne contient pas des paramètres réglés. Les lettres grecques ici sont des symboles du Lightface , qui indiquent ce choix de langue. Chaque symbole en caractères gras correspondant du dénote la classe correspondante des formules dans la langue prolongée avec un paramètre pour chaque vrai ; voir la hiérarchie projective pour des détails.

Une formule dans la langue de l'arithmétique de second ordre est définie pour être le $\ Sigma^1_ {n+1}$ si elle est logiquement équivalente à une formule du $de forme \ existe X_1 \ cdots \ existe X_k \ psi$ où le $\ psi$ est le $\ Pi^1_ {n}$ . Une formule est définie pour être le $\ Pi^1_ {n+1}$ si elle est logiquement équivalente à une formule du $de forme \ du forall X_1 \ cdots \ forall X_k \ psi$ où le $\ psi$ est le $\ Sigma^1_ {n}$ . Cette définition inductive définit le $de classes \ Sigma^1_n$ et le $\ Pi^1_n$ pour chaque nombre normal $n$ .

Puisque chaque formule a une forme normale de prenex, chaque formule dans la langue de l'arithmétique de second ordre est le $\ Sigma^1_n$ ou le $\ Pi^1_n$ pour un certain $n$ . Puisque des quantifiers sans signification peuvent être ajoutés à n'importe quelle formule, une fois qu'une formule est donnée le $de classification \ Sigma^1_n$ ou le $\ Pi^1_n$ pour un certain $n$ elle sera donnée le $de classifications \ Sigma^1_m$ et le $\ Pi^1_m$ pour tout le $m$ plus grand que $n$ .

Noter qu'il semble rarement raisonnable de parler d'une formule de du $\ Delta^1_n$ ; le premier quantifier d'une formule est existentiel ou universel.

La hiérarchie analytique des ensembles de nombres normaux

Un ensemble de nombres normaux est assigné le $de classification \ Sigma^1_n$ s'il est définissable par une formule du $\ Sigma^1_n$ . L'ensemble est assigné le $de classification \ Pi^1_n$ s'il est définissable par une formule du $\ Pi^1_n$ . Si l'ensemble est le $\ Sigma^1_n$ et le $\ Pi^1_n$ puis il est donné le $additionnel de classification \ Delta^1_n$ .

Les ensembles du $\ Delta^1_1$ s'appellent le hyperarithmetical. Une classification alternative de ces derniers place par des functionals calculables réitérés est fournie par la théorie de Hyperarithmetical de .

La hiérarchie analytique sur des sous-ensembles de l'espace de chantre et de Baire

La hiérarchie analytique peut être définie sur n'importe quel espace polonais efficace ; la définition est particulièrement simple pour l'espace de chantre et de Baire parce qu'ils équipent de la langue de l'arithmétique de second ordre ordinaire. L'espace de chantre de est l'ensemble de tous les ordres infinis de 0s et de 1s ; L'espace de Baire de est l'ensemble de tous les ordres infinis des nombres normaux. Ce sont les deux espaces de polonais de

L'axiomatisation ordinaire de l'arithmétique de second ordre emploie une langue placer-basée dans laquelle les quantifiers d'ensemble peuvent naturellement être regardés comme mesurant au-dessus de l'espace de chantre. Un sous-ensemble de l'espace de chantre est assigné le $de classification \ Sigma^1_n$ s'il est définissable par une formule du $\ Sigma^1_n$ . L'ensemble est assigné le $de classification \ Pi^1_n$ s'il est définissable par une formule du $\ Pi^1_n$ . Si l'ensemble est le $\ Sigma^1_n$ et le $\ Pi^1_n$ puis il est donné le $additionnel de classification \ Delta^1_n$ .

Un sous-ensemble de l'espace de Baire a un sous-ensemble correspondant de l'espace de chantre sous la carte qui prend chaque fonction du $\ omega$ au $\ omega$ à la fonction caractéristique de son graphique. Un sous-ensemble de l'espace de Baire est indiqué le $de classification \ Sigma^1_n$ , le $\ Pi^1_n$ , ou le $\ Delta^1_n$ si et seulement si le sous-ensemble correspondant de l'espace de chantre a la même classification. Une définition équivalente de la hiérarchie analytique sur l'espace de Baire est donnée en définissant la hiérarchie analytique des formules using une version fonctionnelle de l'arithmétique de second ordre ; alors la hiérarchie analytique sur des sous-ensembles de l'espace de chantre peut être définie de la hiérarchie sur l'espace de Baire. Cette définition alternative donne exactement les mêmes classifications que la première définition.

Puisque l'espace de chantre est homéomorphe à n'importe quelle puissance cartésienne finie de lui-même, et l'espace de Baire est homéomorphe à n'importe quelle puissance cartésienne finie de lui-même, la hiérarchie analytique s'applique également bien à la puissance cartésienne finie d'un de ces espaces. Une prolongation semblable est possible aux puissances comptables et aux produits des puissances de l'espace de chantre et des puissances de l'espace de Baire.

Prolongements

Comme cela est le cas pour la hiérarchie arithmétique , une version relativized de la hiérarchie analytique peut être définie. La langue est prolongée pour ajouter un constant A de symbole réglé. Une formule dans la langue prolongée est inductivement définie pour être $\ Sigma^ {1, A} _n$ ou $\ Pi^ {1, A} _n$ using la même définition inductive comme ci-dessus. Donné un ensemble $Y$ , un ensemble est défini pour être $\ Sigma^ {1, Y} _n$ s'il est définissable par un $\ formule de Sigma^ {1, A} _n$ dans lesquels le symbole $A$ est interprété comme $Y$ ; les définitions semblables pour le $\ Pi^ {1, Y} _n$ et le $\ Delta^ {1, Y} _n$ s'appliquent. Les ensembles qui sont $\ Sigma^ {1, Y} _n$ ou $\ Pi^ {1, Y} _n$ , pour tout Y de paramètre, sont classifiés dans la hiérarchie projective .

Exemples

l'ensemble de tous les nombres normaux qui sont des index des nombres ordinaux calculables est un $\ Pi^1_1$ réglé qui n'est pas le $\ Sigma^1_1$ .

l'ensemble d'éléments de l'espace de chantre qui sont les fonctions caractéristiques des orderings bons du $\ omega$ est un $\ Pi^1_1$ réglé qui n'est pas le $\ Sigma^1_1$ . En fait, cet ensemble n'est pas $\ Sigma^ {1, Y} _1$ pour aucun élément $Y$ de l'espace de Baire.

si l'axiome de du constructibility se tient alors il y a un sous-ensemble du produit de l'espace de Baire avec lui-même ce qui est le $\ Delta^1_2$ et est le graphique d'un de commande bon de l'espace de Baire. Si les prises d'axiome là est alors également une commande bonne du $\ Delta^1_2$ de l'espace de chantre.

Propriétés

Pour chaque $n$ nous prenons les retenues strictes suivantes : $de \ Pi^1_n \ sous-ensemble \ Sigma^1_ {n+1}$ , $de \ Pi^1_n \ sous-ensemble \ Pi^1_ {n+1}$ , $de \ Sigma^1_n \ sous-ensemble \ Pi^1_ {n+1}$ , $de \ Sigma^1_n \ sous-ensemble \ Sigma^1_ {n+1}$ .

Un ensemble qui est dans le $\ Sigma^1_n$ pour un certain n serait le analytique. Le soin est exigé pour distinguer cette utilisation de l'ensemble analytique de limite qui a une signification différente.

Random links: