L'inaccessible puissance!

christophe c
christophe c
dans Fondements et Logique
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)
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi

Réponses

  • Bruno
    Bruno
    Bonjour Christophe.

    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)$.
  • christophe c
    christophe c
    Je ne voulais pas être trop formel!

    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$
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Et j'autorise même {\bf tout axiome} non dans ZFC, mais crédible ou même assumé par son seul auteur qui le précisera {\bf du moment qu'il n'est pas écrit 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$...
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Bruno
    Bruno
    Acceptes-tu le principe de descente infinie de Fermat ?
  • christophe c
    christophe c
    J'accepte tout du moment que tu ne l'appliques pas à NNN. Autrement dit, tu ne peux pas appliquer quelque non évidence purement logique que ce soit au prédicat (à la propriété, à l'adjectif qualificatif) 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".
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Bruno
    Bruno
    Pardon.

    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.
  • christophe c
    christophe c
    tu viens "de me prouver"*** que tu pourrais prouver en $10^{50}$ étapes que $10^{50}$ est dans NNN. Entièrement d'accord!!!

    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...
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Une remarque à ce propos (assez subtil et à consommer dans un 3 étoiles, lol):

    {\bf pour n'importe quel entier $n$ (qu'il soit ou non dans NNN), il existe une preuve $d$ de l'énoncé $NNN(n)$}
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Bruno
    Bruno
    Beaucoup trop subtil pour moi.
  • christophe c
    christophe c
    jdois absolument partir, pas le tps de me reconnecter... Bah juste pense que quand tu utilises l'axiome de récurrence (ou tout autre axiome du même jus) tu {\bf affirmes} quelque chose purement et simplement, même si c'est une hypothèse pérenne et respectable, et tu l'affirmes à propos d'une propriété (dont tu prouves qu'elle contient 0 et qu'elle est stable par suc!)

    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)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • AD
    AD
    Ou l'art de rendre tout, très compliqué ...

    Alain
  • christophe c
    christophe c
    j'ai fait de mon mieux pour donner la présentation la plus simple possible de ce problème. Maintenant, si ce problème est compliqué, j'aurais pu ne pas le proposer.

    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...
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • L'Axone du Choix
    L'Axone du Choix
    christophe c a écrit:
    Lol je suis en train de parcourir "logique et fondement"
    Moi aussi et je m'aperçois que ce problème est toujours ouvert...
  • L'Axone du Choix
    L'Axone du Choix
    Soit $H(x)$ la propriété $\forall(y) NNN(y) \rightarrow NNN(x+y)$.
    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}$.
  • L'Axone du Choix
    L'Axone du Choix
    Pour la question 3, je suggère de prendre le modèle où $NNN = 2 \omega$
  • christophe c
    christophe c
    Bravo axone du choix tu as trouve la première partie

    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
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • samok
    samok
    Je n'ai pas compris (ma compilation aboutit à une erreur) votre preuve mêlant langage courant et langage formel (genre autrement dit) c'est pour cela que je vous demandais votre processeur (et le langage associé).

    S
  • L'Axone du Choix
    L'Axone du Choix
    Bon. Je suppose que si vous remplacez mes "implique" par $\rightarrow$ en ajoutant une quantification universelle sur la variable libre, vous obtenez une preuve à peu prés formelle (quoiqu'encore plus illisible probablement).
  • samok
    samok
    par quoi je remplace "Soit" ?

    S
  • L'Axone du Choix
    L'Axone du Choix
    Pour la deuxième partie, mon idée de prendre un modèle dans lequel NNN est interprété par $2 \omega$ ne marche pas? Si on pouvait définir un tel R alors on devrait avoir par exemple $2^\omega \in 2 \omega$?
  • L'Axone du Choix
    L'Axone du Choix
    Tu le vires et tu opère la substitution [x := y] partout où x est le membre gauche de l'opérateur Soit et y son membre droit.
  • christophe c
    christophe c
    @axone ce n'est NNN dont demande la non stabilité c'est R
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • L'Axone du Choix
    L'Axone du Choix
    J'ai une vague impression que si on pouvait faire ça on déciderait (une bonne partie de) l'arithmétique (c'est pour ça que je voulais en quelque sorte "prolonger" $\mathbb N$: ajouter des entiers non-standards). C'est par là qu'il faut chercher?
  • L'Axone du Choix
    L'Axone du Choix
    Bon. L'ensemble de formules $\{NNN(x) \land x > n \mid n \in \mathbb N \}$ est finiment consistant donc (par compacité) il est consistant.
    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?
  • L'Axone du Choix
    L'Axone du Choix
    Vu que ça marche aussi avec $2 \times x$, je dois me tromper...
  • christophe c
    christophe c
    Tu fais un HS.

    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
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • L'Axone du Choix
    L'Axone du Choix
    Ah... ckermann?
  • L'Axone du Choix
    L'Axone du Choix
    Est-ce que l'idée c'est:
    $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?
  • christophe c
    christophe c
    C'est pas bien défini comme question (dire si une idée est bonne ou non)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • L'Axone du Choix
    L'Axone du Choix
    Je peux reformuler de deux façons:
    1) est-ce que mon deuxième point est prouvable?
    2) est-ce l'argument auquel tu pensais lorsque tu as donné l'exercice?
  • L'Axone du Choix
    L'Axone du Choix
    Bon mon 1) est trivial puisque faux entraine n'importe quoi. Reste 2.
  • christophe c
    christophe c
    Non à 2
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • L'Axone du Choix
    L'Axone du Choix
    Est-ce qu'il s'agit d'un argument accessible, ou nécéssite-il un background que je n'ai pas forcément (au vu de mes réponses jusqu'ici)?
  • christophe c
    christophe c
    Ça passe par le théorème d'élimination des coupures
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • L'Axone du Choix
    L'Axone du Choix
    J'avais donc bien peu de chances face à ça.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 6

Lirone93Philippe Malot +4 Invités