Absence de contre-exemple comme argument
On se donne deux entiers $\ell$ et $N$.
Soit $V_{N,\ell}$ l'ensemble des formules de l'arithmétique de Péano $P$ de longueur au plus $\ell$ et telles $P^{(N)}$ est prouvable, où $P^{(N)}$ désigne la formule $P$ dans laquelle toutes les quantifications ont été remplacées par des quantifications bornées par $N$. On tire uniformément une formule $P$ dans $V_{N,\ell}$. Quelle est la probabilité que $(\mathbb N, +, \times)$ vérifie $P$?
Soit $V_{N,\ell}$ l'ensemble des formules de l'arithmétique de Péano $P$ de longueur au plus $\ell$ et telles $P^{(N)}$ est prouvable, où $P^{(N)}$ désigne la formule $P$ dans laquelle toutes les quantifications ont été remplacées par des quantifications bornées par $N$. On tire uniformément une formule $P$ dans $V_{N,\ell}$. Quelle est la probabilité que $(\mathbb N, +, \times)$ vérifie $P$?
Réponses
-
Tu peux commencer par calculer le cardinal de $V_{N,\ell}$.
Tout usage abusif de la liberté sera signalé à la modération. -
Cette proba est inconnaisable dans le sens que l'ensemble vérité de $\mathbb{N}$ est [large]T[/large]uring-réductible à son écriture décimale.
[Alan Turing (1912-1954) prend toujours une majuscule. AD]Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Oui j'ai réalisé qu'en fait pour $N$ suffisamment grand cette proba vaut $1$ mais on n'a aucun moyen de savoir à quel point grand est suffisamment grand.
Mais a-t-on des bornes inférieures prouvables ? -
Je ne vois pas pourquoi ça tendrait vers 1...
Il n'y a que très peu de rapport entre $\forall x\exists y$ et $\forall x\leq n\exists y\leq n$Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Si $\phi$ est une formule fixée et si $\mathbb N \models \phi$ alors pour $N$ suffisament grand $\mathbb N \models \phi^{(N)}$.
En effet, la réciproque ne doit marcher que pour les formules au plus $\Pi_2$, kêk chose kom ça. -
Euhhh... $\phi = \forall x, \exists y, y=x+1$ donne $\phi^{(N)} = \forall x\leq N, \exists y\leq N, y=x+1$, que faire de $x=N$ ? Ou bien j'ai manqué quelque chose ?
-
@Shah olalala non, tu es loin du compte. Les $P^{(N)}$ sont des énoncés vraiment simples et décidables qui bien souvent n'ont strictement rien à voir avec $P$ ni dans un sens, ni dans l'autre.
Par contre (mais ça s'éloigne beaucoup de ta question) t'amuser à ramener la vérité à du quantifié borné, tu as la spectaculaire (mais on ne triche pas, il y a un prix) application de Ramsey:
$P$ est vraie si et seulement si il existe un ensemble infini $A$ tel que pour tous éléments $(a_1,..,a_n)\in A^n$ formant une suite strictement croissante finie tu as $Q_1x_1<a_1Q_2x_2<a_2...Q_nx_n<a_n: R(x_1,..,x_n)$, après avoir noté :
$$P = Q_1x_1...Q_nx_nR(x_1,..,x_n)$$
la forme prénexe de $P$
Autrement dit, par Ramsey, la vérité de Peano se réduit à la connaissance des partitions très simples à calculer de $A^n$ qui admettent un ensemble homogène. Cela fait de Ramsey un énoncé "maximal" en quelque sorte.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Ah oui effectivement je suis allé un peu vite...
-
Du coup je repose ma question mais au lieu d'avoir un entier $N$ comme paramètre, je prend une suite croissante $a_n$ et les quantifications deviennent comme dans le poste de Christophe.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 2
