Formules prouvables à partir de PA
Bonjour à tous.
Je m'intéresse aux résultats d'arithmétique élémentaires que l'on peut prouver à partir de PA. Par exemple on m'a dit que l'existence d'une infinité de nombres premiers (sous la forme "les premiers sont cofinaux") est prouvable à partir de PA mais que ce n'était pas facile à montrer. Connaîtriez-vous des références pour ce genre de résultats ?
Merci d'avance pour vos réponses.
Je m'intéresse aux résultats d'arithmétique élémentaires que l'on peut prouver à partir de PA. Par exemple on m'a dit que l'existence d'une infinité de nombres premiers (sous la forme "les premiers sont cofinaux") est prouvable à partir de PA mais que ce n'était pas facile à montrer. Connaîtriez-vous des références pour ce genre de résultats ?
Merci d'avance pour vos réponses.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Qu'est-ce qui cloche?
On définit $f(0)=1$ et $f(n+1)=(n+1)f(n)$ si $n+1$ est premier, et $f(n)$ sinon.
Alors pour tout $n$ si $m<n$ est premier, $m$ ne divise pas $f(n)+1$.
Donc pour tout $n$ il existe $m$ premier supèrieur à $n$.
Edit: plus simplement, $1$ est le seul entier plus petit que $n$ qui divise $n!+1$.
Cela dit ce n'est pas non plus "bien méchant".
Une suite est un triplet (a, b, c) et l'image de n par elle est le reste de à divisé par (b+cn)
Si vous connaissez des références où ce genre de choses est faite à partir de PA (par exemple le théorème de Wilson ou que sais-je), je suis preneur.
Mieux : tout PA théorème peut se prouver en utilisant une seule fois la récurrence sans paramètre (exercice pas si difficile , ne pas se laisser intimider)