L'inaccessible puissance!
Celui-là il déchire tout...
Imaginons qu'on rajoute un "prédicat" (c'est à dire un adjectif qualificatif) unaire (à une place) que je noterai NNN (sans la double barre) avec interdiction absolue de lui appliquer quelque axiome que ce soit à part les 2 suivants:
(1)"0 est NNN"
(2)"n'importe quel entier qui soit NNN est suivi d'un entier qui est NNN"
En particulier, vous n'avez pas le droit, via une récurrence appliquée à NNN d'induire que tous les entiers sont NNN
1) Prouver (sans écrire un roman, en quelques lignes) que 1000000000 est NNN
2) Prouver que $10^{50}$ est NNN
3) (la 3 peut vous aider à faire les 2 premières) Prouver qu'on ne peut définir aucune propriété quelqu'elle soit (sans tricher) qui soit incluse dans NNN, qui contient 0 qui est stable par "successeur" et par puissance (ie si a et b sont NNN alors $a^b$ est NNN)
Imaginons qu'on rajoute un "prédicat" (c'est à dire un adjectif qualificatif) unaire (à une place) que je noterai NNN (sans la double barre) avec interdiction absolue de lui appliquer quelque axiome que ce soit à part les 2 suivants:
(1)"0 est NNN"
(2)"n'importe quel entier qui soit NNN est suivi d'un entier qui est NNN"
En particulier, vous n'avez pas le droit, via une récurrence appliquée à NNN d'induire que tous les entiers sont NNN
1) Prouver (sans écrire un roman, en quelques lignes) que 1000000000 est NNN
2) Prouver que $10^{50}$ est NNN
3) (la 3 peut vous aider à faire les 2 premières) Prouver qu'on ne peut définir aucune propriété quelqu'elle soit (sans tricher) qui soit incluse dans NNN, qui contient 0 qui est stable par "successeur" et par puissance (ie si a et b sont NNN alors $a^b$ est NNN)
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ai-je bien compris ? Nous avons une théorie écrite dans le langage du premier ordre suivant :
\begin{itemize}
\item Une constante individuelle $0$,
\item un symbole de prédicat binaire $N$,
\item un symbole de prédicat binaire $\leq$,
\item un symbole fonctionnel unaire $s$.
\end{itemize}
Tels que l'on ait les axiomes et schémas d'axiome du premier ordre de Peano écrits avec $(0,\leq,s)$ et tel que l'on ait de plus : $N(0)$ et $\forall\,x \quad \Big(N(x) \Longrightarrow \big(\exists\,y \quad (x < y) \wedge N(y)\big)\Big)$.
Bien entendu, $x < y$ signifie $(x \leq y) \wedge (x \neq y)$.
Non, on a plus que ça!!!
On est dans ZFC (avec le symbole binaire $\in$)! Pour éviter les lourdeurs, on rajoute aussi des symboles ptimitifs pour les opérations arithmétiques $+,\times, 0, suc$, mais on n'y serait pas spécialement obligé
On {\bf rajoute} un prédicat {\bf unaire} $NNN$ (je mets 3 lettres pour éviter la confusion avec $\N$, et en tout et pour tout, le concernant, 2 axiomes:
1) $NNN(0)$
2)$\forall x,\ (NNN(x)\to NNN(suc(x)))$
le symbole de fonction $suc$ désigne l'application $x\mapsto x+1$ (je ne sais plus faire le petit trait vertical)
[en LaTeX : \verb*=\mapsto=. AD]
Il faut faire bien attention de ne pas appliquer les schémas d'axiome de ZFC aux relations qui sont écrites avec le prédicat $NNN$
L'exercice peut être fait avec toute théorie plus forte que ZFC (mais raisonnable ou assumée par son auteur) en ce qui concerne $\in, +,\times, etc$ mais pas $NNN$...
Partant d'un éventuel entier $n$ qui n'est pas NNN, tu peux dire que $n-1$ n'est pas NNN, $n-2$ non plus, etc... Mais tu ne peux pas dire "donc contradiction".
Si $10^{50}$ n'est pas NNN, alors son prédécesseur non plus d'après l'axiome de passage de NNN au sucesseur ; mais puisqu'on n'a qu'un nombre fini d'entiers largement compris entre $0$ et $10^{50}$, on arrive au bout d'au plus $10^{50}$ étapes à un entier qui n'est pas NNN et dont le prédécesseur est NNN car il n'est pas $0$. ce qui contredit l'axiome du passage au successeur.
Mais la Q2 de l'exercice est de prouver (en pas trop d'étapes) que $10^{50}$ est NNN, pas juste de prouver l'énoncé {\it il existe une preuve que $10^{50}$ est NNN}
De plus, l'idée que $10^{50}$ est un nombre fini ne sert à rien puisque rien ne prouve que tous les nombres finis sont NNN.
*** plus précisément, tu m'as "signalé" que d'une preuve que $n$ n'est pas NNN, on peut passer à une preuve à peine plus longue que $n-1$ n'est pas NNN...
{\bf pour n'importe quel entier $n$ (qu'il soit ou non dans NNN), il existe une preuve $d$ de l'énoncé $NNN(n)$}
Là, on joue au jeu que tu ne peux pas faire ça avec NNN... Mais l'existence d'une preuve que $NNN(a)$ où $a$ est un entier (que tu as nommé) est un énoncé {\bf qui ne contient pas le prédicat NNN} (eh oui... lol)
Alain
Si quelqu'un pouvait le formuler plus simplement {\bf sans le changer*}?
* attention, il s'agit d'un problème de maths! Il y a un fil sur Godel, justement: un des corollaires de sa "méthode" est que justement on ne pourra jamais prouver l'énoncé suivant (dans les "bonnes" théories):
{\it Pour tout énoncé P, s'il existe une preuve qu'il existe une preuve de P alors il existe une preuve de P}
Et précisément, ici, on est dans ce cas!
Je trouve que ce thème est édifiant: l'opération puissance est la première ($+$ et $\times$ ne sont pas dans son cas) à avoir cette propriété de n'être pas "capturable" par NNN...
On a $H(x)$ implique $\forall(y) NNN(y) \rightarrow NNN(x+x+y)$ (puisque si $NNN(y)$ et $H(x)$ alors $NNN(y')$ où $y' = x+ y$ et donc par $H$ on a $NNN(x+y')$).
Autrement dit $H(x)$ implique $H(2 \times x)$ (1)
Soit $G(x)$ la propriété $NNN(x) \land H(x)$.
On a montré que $G(x)$ implique $G(2 \times x)$, et on a $G(2)$.
Soit $F(x)$ la propriété $\forall(y) G(y) \rightarrow G(x \times y)$.
De même que (1) $F(x)$ implique $F(x^2)$.
Soit $E(x)$ la propriété $G(x) \land F(x)$.
On a montré $E(x)$ implique $E(x^2)$, et on a $E(2)$
Donc on a aussi $E(4)$, $E(16)$, $E(256)$, $E(75536)$, $E(5705687296)$, $E(5705687296 \times 5705687296)$
Comme $E \rightarrow NNN$ on a $NNN(5705687296 \times 5705687296)$. Par une méthode similaire on obtient $10^{50}$.
Pour la deuxième l'exercice est de montrer qu'on ne peur définir aucun R stable par puissance et inclus demontreblement dans NNN
S
S
Donc on a un modèle avec un $NNN$ $x$ qui est plus grand que tous les entiers standards. Alors $2^x$ est plus grand que $x+n$ pour chaque entier standard $n$.
Par conséquent il est consistant que $\neg NNN(2^x)$.
Je me trompe?
JE te demande de prouver qui' il n'est pas possible de définir R prouvablement stable par puissance et prouvablement inclus dans NNN
Je ne te demande pas de prouver qu'il consistant que NNN n'est pas stable par puissance
Remarque dans la partie1 tu as réussi a définir R prouvablement stable par produit et inclus dans NNN ce qui t'a permis de prouver vite que 10^50 est dans NNN
$T : n \mapsto \text{le plus grand entier $k$ tel que $NNN(k)$ est prouvable en moins de $n$ symboles}$ est calculable.
Si on avait un tel $R$, alors cette fonction croitrait trop vite pour être calculable?
1) est-ce que mon deuxième point est prouvable?
2) est-ce l'argument auquel tu pensais lorsque tu as donné l'exercice?