Démonstration par l’absurde de « récurrence »

En fait la démo qui est dans ton papier est correcte... à condition de savoir qui c'est $\N$.

@Dom et Math Coss : oui, j'en parle un peu dans mon chap. 6, section 4 :
https://sites.google.com/view/martial-leroy

Les axiomes de Peano sont les suivants :
On se donne un triplet $(E,c,f)$ tel que
1) $E$ est un ensemble et $c$ est un élément de $E$ (il existe des entiers)
2) $f$ est une application de $E$ dans $E$ (le successeur d'un entier est un entier)
3) $f$ est injective (si deux entiers ont le même successeur ils sont égaux)
4) $c$ n'est pas dans l'image de $f$ (il existe un entier n'étant le successeur d'aucun autre)
5) Si $F\subset E$ contient $c$ et est stable par $f$ alors $F=E$. (axiome de récurrence)

Ici $E$ joue le rôle de $\N$, $c$ de $0$ et $f$ de l'application successeur ("+1"). Le dernier axiome est celui qui permet de faire des récurrences sur $\N$.

Prenons maintenant l'ensemble $\{0;1\}\times \N$ muni de l'ordre lexicographique et de l'application $f : (i,j)\mapsto (i,j+1)$. Le triplet $(\{0;1\}\times \N, (0,0), f)$ vérifie les 4 premiers axiomes de Peano mais pas le dernier puisque $\{0\}\times \N $ est stable par $f$, contient $(0;0)$ mais n'est pas $\{0;1\}\times \N$. Prenons maintenant $A$ une partie non vide de $\{0;1\}\times \N$, on la sépare en $A\cap \{0\}\times N$ et $A\cap \{1\}\times N$, chacune de ses parties est soit vide soit admet un plus petit élément, on en déduit que $A$ admet un plus petit élément. On voit donc que pour démontrer l'axiome de récurrence il faut utiliser plus que la propriété "toute partie non vide admet un plus petit élément".

En fait en plus de l'axiome "$vi$) toute partie non vide admet un plus petit élément" la démonstration utilise aussi l'axiome "$vii$) $\mathrm{Im}(f) = E\backslash \{c\}$" lorsqu'elle parle de $m-1$ où $m$ est le plus petit élément (non nul car différent de $n_0$) d'un certain ensemble. Bon et puis il faut aussi rajouter une notion d'ordre stricte compatible avec l'application $f$ : "$v)$ $\forall e\in E, e < f(e) $" puisqu'on parle de plus petit élément.

Prenons donc un triplet $(E,c,f, <)$ vérifiant les 4 premiers axiomes de Peano plus les trois axiomes du paragraphe précédent. Soit $A$ une partie de $E$ stable par $f$ et contenant $0$, supposons que $A\neq E$. Dans ce cas $B=E\backslash A$ est non vide et admet donc un plus petit élément $b$ d'après l'axiome $vi$). Par hypothèse on sait que $b\neq 0$ donc d'après l'axiome $vii$) il existe un élément $b-- \in E$ tel que $f(b--) = b$. D'après $v$) on a $b--<b$ et donc $b-- \notin B$ ce qui implique $b-- \in A$ et, par hypothèse $b=f(b--) \in A$, ce qui est absurde et ainsi $A=E$

On en déduit qu'un quadruplet $(E,c,f, <)$ vérifiant les axiomes 1) à 4) et $v$), $vi$) et $vii$) vérifie aussi l'axiome de récurrence 5).

On pourrait terminer en montrant que les axiomes 1) à 5) impliquent les axiomes $v$), $vi$) et $vii$) mais je le laisse en exercice au lecteur :)o Autre exercice : trouver un quadruplet $(E,c,f,<)$ vérifiant les axiomes 1) à 4) ainsi que $v$) et $vii$) mais pas l'axiome $vi$).

@ Corto
Exposé très intéressant. Si j'ai bien compris, l'axiome $v)$ est :« $\forall e\in E, e < f(e)$ » et l'axiome $vii) $ est : « $\mathrm{Im}(f) = E\backslash \{c\}$ », mais je ne comprends pas ce qu'est l'axiome $vi)$. Ce serait sympa de le préciser.
Bonne soirée.
Fr. Ch.

Franchement je n'arrive pas à comprendre comment un matheux averti comme Martial en vient à dire qu'il ne sait pas ce que c'est que $\N$ ! Alors les centaines de lignes de logique, interminables, contradictoires, incompréhensibles par le vulgaire, ne seraient même pas utiles à ceux qui sont versés dans cette discipline ?
Bah, même si nous ne savons pas ce que c'est que $\N$ - et encore ce n'est pas certain - en tout cas nous savons ce qu'on peut faire avec, et c'est l'essentiel pour ceux qui veulent faire des mathématiques, vous savez, arithmétique, algèbre, analyse, géométrie, et tout ça.
Bonne soirée.
Fr. Ch.

De mon téléphone: en général on distingue premier et second ordre. Corto semblait vouloir dire un truc précis en réponse contextuee à dom mais il lui faudra préciser car il est rare qu'on parle de Peano second ordre en disant juste le mot Peano.

La théorie de Peano est une théorie du premier ordre qui fait intervenir les deux opérations. Sinon ça ne s'appelle pas Peano "sérieusement".

Si on est indifférent ces étapes historiques de toute façon, en revenant aux maths autrement dit à ZF, tout ceci est défini et non pas axiomatise. On ne part pas des entiers mais des ensembles. On définit les cardinaux et éventuellement même les ordinaux puis IN est défini ensuite.

Le fait que tous les IN sont isomorphes fait qu'on oublie comme pour IR la définition précise. Par contre il ne faut pas perdre de vue qu'on gère des cardinaux (même si représentés par des ordinaux) et qu'il est artificiel de retirer les cardinaux infinis tout comme il est artificiel de prouver les propriétés de + et de × par récurrence dans l'esprit Peano car ca a tendance à faire oublier aux gens que lesdites sont infinitaires (associativite distributivité commutativité infinies).

Par exemple la commutativité de × c'edt la bijection naturelle envoyant (x,y) sur (y,x). Etc.

@titi: pour information, la théorie (c'est-à-dire l'ensemble des formules vraies), du second ordre en plus, de $(\N, +)$ est RÉCURSIVE (ça s'appelle "arithmétique de Presburger"). Donc comme tu vois ... les opérations :-D

@Dom : non, un ensemble infini est simplement un ensemble qui ne peut pas être mis en bijection avec un ordinal fini (ou avec un entier naturel si tu préfères).
Il y a des gigatonnes d'ensembles infinis de cardinal minimal, $\omega$ n'est que l'un d'entre eux.
Pour la définition de $\omega$, voir mes 2 derniers posts.

Alors les 40782 messages de Christophe C n'ont pas même servi à faire connaître ce que sont les entiers naturels ? Vous me faites bien marrer...
Edit : correction de la faute de frappe suite à la remarque infra.

@Chaurien : sur les 40782 messages dont tu parles (je crois que tu sous-estimes un peu le chiffre, mais bref), il y en a un que j'ai particulièrement retenu, et que je cite souvent, de mémoire.
On discutait, un peu comme aujourd'hui, du fait que les maths sont infoutues de définir correctement $\N$. Et Christophe a écrit en conclusion :

"Kronecker disait que Dieu nous a donné les entiers et que l'homme a construit le reste. Ben dis don, ça commençait mal...".

Cette réflexion m'arrange d'autant plus que je voue une haine incommensurable à Kronecker, pour avoir été en grande partie responsable de la dépression de Cantor.

J'ai lu il y a très longtemps un bouquin de Ian Stewart : "Les mathématiques", traduit en français, chose rare. A un moment l'auteur cite cette maxime de Kronecker et dit, en termes un peu plus sophistiqués que moi, que ce n'est pas avec ce genre de réflexion à deux balles qu'on va faire avancer le schilimimi.

Bah moi je connais bien $\N$ : c'est un objet avec un point $0: 1\to \N$ et une flèche $s:\N\to \N$ et qui est initial parmi ces bazars. Comme tout truc défini par une propriété universelle, il est unique à isomorphisme unique près. :-D

Moi je m'intéresse à $\N$ pour faire des choses avec et non pour le contempler indéfiniment. Je précise que je n'ai rien contre ceux qui se complaisent dans cette contemplation prolongée, mais ce n'est pas mon truc, voilà tout. Simplement je les plains un peu puisqu'après des milliers de lignes de texte, ils ne savent toujours pas de quoi ils parlent.
Alors pour moi, le plus commode, c'est que $\N$ c'est $\Z_+$ : je l'ai déjà expliqué sur ce forum il y a un certain temps.
Bonne soirée.
Fr. Ch.

@Martial
Ce n'est pas la faute de Kronecker si Cantor était sujet aux troubles bipolaires. Dans ce monde cruel il faut savoir supporter les contradictions. Et de toutes façons, la haine c'est interdit, fais gaffe à la loi Avia.
Kronecker avait ses idées, il faut y réfléchir avant de les rejeter ou de les adopter, totalement ou partiellement. Moi je n'y ai pas réfléchi, je prenais cette phrase pour une boutade, mais voici un article qui dit des choses intéressantes à ce sujet :
https://images.math.cnrs.fr/Position-philosophique-et-pratique.html
Bonne soirée.
Fr. Ch.

@ Dom
Bonne question. J'ai déjà raconté sur ce forum que, il y a quelques années, je devais faire un cours d'arithmétique pour Terminale C+. Je voulais prendre les choses à leur début, non par manie logico-axiomatiste, mais simplement pour disposer d'une liste de propositions initiales desquelles tout découlerait, afin que tout soit clair. Axiomes si l'on veut, mais je répète mon but n'était pas de gloser à l'infini à leur sujet, de savoir s'ils étaient estampillés ZF ou que sais-je encore, s'ils étaient minimaux, non contradictoires ou autres questions analogues. Non, mon but c'était de les énoncer et de les utiliser immédiatement pour faire de l'arithmétique, divisibilité, PGCD-PPCM, congruences, et tout ça.

Alors je me suis dit, je connais deux présentations de $\N$, l'une par les cardinaux, l'autre par les axiomes de Peano. Toutes deux longues, et ensuite il faut symétriser pour avoir $\Z$. Trop long et pour tout dire, sans intérêt pour la suite. Le mieux c'est de partir de $\Z$, qui a une structure bien connue, anneau commutatif intègre ordonné, avec bon ordre sur $\Z_+$. Et vogue la galère.

J'ai trouvé au moins deux livres qui procèdent ainsi :
André Weil (avec Maxwell Rosenlicht), Number Theory for Beginners, Springer, 1979.
William J. LeVeque, Fundamentals of Number Theory, Addison-Wesley, 1977.

Maintenant, il me semble qu'il y a plusieurs ouvrages qui donnent des constructions de $\N$ et je ne pensais pas que c'était un problème ouvert. Peano et Cantor, ce ne sont pas vraiment des perdreaux de l'année 2020. Je n'arrive pas à comprendre comment nos amis logiciens, avec toute leur science se répandant en milliers de messages, ne savent toujours pas ce que c'est que $\N$. Ça n'encourage pas le profane à chercher à pénétrer les mystères de leur discours.

Bonne soirée.
Fr. Ch.

La raison pour laquelle des gens disent ne "pas savoir ce qu'est $\N$" provient de la théorie des modèles et des théorèmes de complétude et d'incomplétude de Gödel: étant donné n'importe quel ensemble récursif d'énoncés contenant ceux de l'arithmétique de Peano, s'il existe une structure qui satisfait ces énoncés, il en existe automatiquement plusieurs non isomorphes. Quel $\N$ est "le bon" parmi eux?

Salut,
Je profite du message de Corto qui rend le mien un peu à propos (la vérité c'est que je me suis majestueusement vautré en utilisant Peano dans le cadre ZFC, c'est d'un manque d'élégance sans nom!)
@christophe c: je suppose que ce qui suit va dans ton sens, mais n'en suis pas persuadé, dans la mesure où je ne suis pas sûr de ce qu'est une théorie du deuxième ordre, même si je crois que ça a un vague rapport avec la notion de schéma d'axiomes et que je n'ai pas la moindre idée de ce qu'est un ensemble récursif (oui! Pas bien! Pour ma défense, je ne suis pas logicien, je ne suis même pas mathématicien, alors pour ce que j'en fais, ce que je sais est déjà pas mal), .

Avec ZFC: on peut montrer qu'un couple $(E,f)$ ($f$ une application de $E$ dans $E$, au sens d'une partie de $E\times E$ telle que blablabla) qui respecte les 5 premiers axiomes vérifie bien que $E$ est muni d'un bon ordre qui a la "compatibilité qu'il faut" avec $f$ (mais il y avait une stratégie bien plus directe que ce celle que j'avais proposée :-D). On peut même montrer dans ce cadre l'existence de deux lois de composition interne respectant les quatre axiomes supplémentaires (et puis avant tout ça, on peut construire les isomorphisme entre ces couples $(E,f)$, mais on s'éloigne du sujet).

Mais en fait le but de Peano est d'être une théorie complètement indépendante (j'avoue que je n'y avais pas fait attention avant), du coup on ne parle pas de partie ou de quoi que ce soit, mais on se contente de mettre des quantificateurs universelles devant des formules plus ou moins longues. C'est cette absence de notion de partie et de schéma de compréhension qui impose d'utiliser un schéma d'axiome de récurrence plutôt qu'un axiome de récurrence (qui a cette tête là: soit $F(x)$ une formule, $[F(c)\wedge \forall x, F(x)\rightarrow F(f(x))]\rightarrow \forall x, F(x)$), sinon on arrive pas à déduire grand chose. Effectivement, il semble vachement difficile (je n'ai pas les moyens de dire impossible, parce que je ne sais pas le prouver) de montrer l'existence du bon ordre à l'aide d'un langage ne contenant que le symbole "0" et la fonction "s" et 5 axiomes, sachant qu'on ne sait pas ce que c'est qu'un ensemble (alors vas-y pour expliquer ce qu'est une clôture transitive) et qu'on va être un peu limité pour fabriquer des formules (on y rencontrera souvent les symboles $s$ et $=$ et ça va vite être casse-bonbons). Donc en effet, il semble nécessaire d'étendre le langage et de donner un sens au nouveaux symboles pour montrer l'existence de ce bon ordre, ce rôle est classiquement joué par l'addition.

@Titi le curieux : je n'ai pas lu tout ce qu'il y a d'écrit dans ce fil, mais j'ai l'impression que tu commets une confusion.

Si tu travailles en logique du 1er ordre, la propriété "toute partie non vide admet un plus petit élément" ne peut pas être déduite des axiomes de Peano, pour la bonne raison qu'elle ne peut même pas être écrite dans le langage (puisque tu quantifies sur des parties de la structure). La seule chose qu'on puisse dire, vue de l'extérieur, c'est qu'il y a $2^{\aleph_{0}}$ (c'est-à-dire autant que de nombres réels) modèles dénombrables de PA1 deux à deux non isomorphes, dont un seul vérifie la propriété du bon ordre. C'est celui-là qu'on appelle le modèle standard, et qu'on note $\N$. Les autres sont "non standard" au sens où ils contiennent des entiers infiniment grands. Il est assez facile de montrer que tout modèle non standard commence par une copie de $\N$, suivie de tout un tas d'entiers non standard. Et un tel modèle ne peut pas être bien ordonné pour une raison simple : la "collection" de tous les entiers non standard n'a pas de plus petit élément (exercice). J'ajoute que d'après Löwenheim-Skolem tu as aussi des modèles de PA1 en toute cardinalité infinie, en plus de ceux, dénombrables, déjà cités.

En revanche, si tu travailles en logique du second ordre, là tu as un seul modèle à isomorphisme près, et c'est évidemment $\N$.

Hosanna !!!
Enfin un texte qui a l'imprimatur des autorités logiques de ce forum et qui semble intelligible par tout un chacun matheux.

@Chaurien, ce n'est pas "que" de la logique que de s'intéresser aux équations diophantiennes ayant "en apparence" des solutions dans des modèles de Peano (premier ordre: les 8 axiomes), alors qu'elles n'en ont pas. On en connait beaucoup.

Un exemple très simple est le fait que l'énoncé du théorème de Ramsey (Peanistement démontrable) ne l'est plus quand on demande "en plus" en conclusion que les parties finies aient un cardinal dépassant leur minimum.

Un autre est une suite de Goodstein qui ne s'arrête pas.

@Titi le curieux, ton dernier message m'a inspiré la remarque suivante.
Aux signes 0 et s de la théorie primitive de Peano (c'est-à-dire sans addition, ni multiplication) on pourrait rajouter un signe relationnel binaire < et introduire les trois axiomes suivants de la relation x < y (que l'on pourrait lire "x est avant y" ou "y suit x") :

cette relation est une relation d'ordre (strict) :

$\neg $ $ (x < y \wedge y < x)$
$ (x < y \wedge y <z ) \Rightarrow x < z$

le successeur s(x) de x suit x :

$x < s(x)$

Après tout, ces axiomes ne sont ni plus, ni moins intuitifs que "s(x) est injective", etc. et font voir que cette relation d'ordre n'est pas intrinsèquement subordonnée aux propriétés algébriques de l'addition (lorsqu'on définit la relation d'ordre (large) par "il existe n tel que x + n = y).

On montre alors facilement que x < y est une relation de bon ordre (et total).
C'est d'ailleurs un bon exercice pour entraîner la récurrence. :-)

P.S. Je viens de me rendre compte que ma démonstration n'est pas correcte. J'essaie de la réparer. Sinon, oublie ce message ..

@dom: bin le problème qu'alesha à raison de signaler est que l'énoncé rouge du milieu de la page 3 est tout simplement faux. Comme je suis sur mon téléphone, je te laisse voir. Bon le caractère erroné du document c'est une erreur parmi d'autres.