L’argument diagonal selon Wikipédia

JLapin

Quand tu parles de << linterventiondelinfinienacte >>, tu parles de l'ensemble $\N$, c'est ça ?

Alain24

Sneg a dit :
Cela m’intrigue que ce soient précisément les étranges nombres réels non calculables qui soient non dénombrables. S’agit-il d’une pure coïncidence ?

Il y a un ensemble de nombres réels qui peut être construit à partir des nombres rationnels, eux-même construits à partir des nombres entiers, par complétion topologique de l'ensemble des nombres rationnels. L'ensemble $\mathbb{R}$ est dit constructible. Maintenant je ne comprends pas comment @Sneg définit un nombre réel calculable puisqu'on peut toujours dire qu'un nombre réel est une limite de nombre décimaux (on construit une suite de décimaux en prenant seulement  n chiffres après la virgule du réel représenté par l'écriture b,a1a2a3... avec b et la suite ai dans l'ensemble $\lbrace 0,1,2,3,4,5,6,7,8,9\rbrace$ : 10 entiers comme les 10 doigts des 2 mains (d'autres choix de bases de numération sont intervenues au cours de l'histoire de l'humanité) : à ce sens (limite d'une suite décimale) on peut toujours affirmer que tout nombre réel est calculable par approximation successive.

Sneg

@JLapin : 
Je définis « l’infini en acte » comme « le pouvoir de maîtriser l’infini qui, sans ce pouvoir, est non maîtrisable ».
Plus prosaïquement, Wikipédia le définit comme la capacité de considérer un ensemble infini comme une entité achevée (et non pas en éternelle construction).

@Alain24 : 
La notion de nombre réel calculable que j’utilise à été mise en place par Alan Turing en 1936 (Voir Wikipédia, Nombre réel calculable).

Dom

C’est encore des choses non mathématiques. 

« Une entité achevée » n’est pas une définition (sauf si on me dit ce que cela veut dire). 

Ne pas confondre la philosophie, des fantasmes ou des névroses et les maths. 

raoul.S

Sneg a dit :

Voici les faits : 
$\bullet$ Il existe des nombres réels calculables et des nombres réels non calculables.
$\bullet$ L’ensemble des nombres réels calculables est dénombrable, tandis que l’ensemble des nombres réels non calculables est non dénombrable.

C'est correct.

Sneg a dit :

Par définition, les nombres réels calculables peuvent être représentés au moyen d’une quantité finie de symboles. Donc, pas besoin de faire intervenir l’infini en acte pour représenter un nombre réel calculable.

Ça dépend de ce que tu veux dire par "quantité finie de symboles". Si tu veux dire : "un nombre fini de décimales" alors c'est faux. Par exemple le nombre réel 0.11111... (que des 1) est calculable mais contient une infinité de décimales. Le nombre réel $0.\overline{01}$:=0.01010101... (on répète le motif 01) est également calculable. Les nombres réels $\sqrt{2}$ et $\pi$ sont calculables aussi.
Donc tu dois préciser.

Sneg a dit :

- d’autre part, la construction de chacun des éléments de l’ensemble des nombres réels non calculables demande l’intervention de l’infini en acte.

De toute façon la majeure partie des mathématiques est basée sur la théorie des ensembles ZFC qui répugnerait tout défenseur de l'infini potentiel... Bref si tu n'es pas prête à accepter de considérer des ensembles infinis (qui contiennent une infinité d'éléments) comme "des entités achevées" alors tu passes à côté de la majeure partie des mathématiques modernes. 

Sneg

Je suis d’accord avec toi, Dom. Mais ce n’est pas moi qui ai inventé ce concept, dont il est dit que Cantor l’a lui-même utilisé.
Sans ce concept, comment imaginer représenter un nombre réel non calculable dans le fameux tableau de l’argument diagonal ? J’ai l’impression de ne pas arrêter de poser la même question depuis un an que je parle de mes « nombres non parfaitement déterminés » (qui ne sont autres que les nombres réels non calculables de Turing). 

Math Coss

L'argument (Cantor je ne sais quoi) est fallacieux !
J'explicite : que Cantor ait tenu des discours non mathématiques, fût-ce au milieu de textes mathématiques, n'oblige personne à les reprendre comme mathématiques ! 

Dom

Et si Cantor invente une recette avec des haricots blancs et de la crème de marrons, on en parle aussi ou on se dit que ça sort des maths ?

Par contre je lis de la lucidité : il s’agit bien de la même question depuis le début.

Médiat_Suprème

@Sneg : et si vous répondiez à mes questions ...

Sneg

C’est curieux, inouï même , certains disent ici que l’infini actuel fait partie inhérente des mathématiques contemporaines, et d’autres disent que ce n’est pas un concept mathématique ! Moi, je ne suis pas contre du tout : C’est la seule façon que j’aie trouvée de me représenter un nombre réel non calculable. Mais impossible pour moi de vous faire dire comment, vous, vous faites ! Si vous ne voulez pas répondre à cette question toute simple, dites-le moi. Tout le monde gagnera du temps.

raoul.S

@Sneg moi je suis curieux de savoir comment toi tu te représentes un nombre réel calculable. C'est quoi pour toi un réel calculable (explique-le avec le plus de rigueur possible) ?

raoul.S

Sneg a dit :

C’est curieux, inouï même , certains disent ici que l’infini actuel fait partie inhérente des mathématiques contemporaines, et d’autres disent que ce n’est pas un concept mathématique !

L'un empêche pas l'autre. Le concept d'infini actuel n'est pas mathématique.

Dom

« Se représenter un réel calculable » , ça ne veut rien dire non plus. Sauf si tu parles de vulgariser éventuellement.  
Les caractériser, oui, ça pourrait être une bonne question mathématique.

Par contre je ne sais pas qui dit que « l’infini » n’est pas un concept mathématique. Ce sont parfois les termes que tu utilises qui ne sont pas mathématiques. Et tu parles surtout d’impression, de « se représenter », de ressenti et de ce qui touche à l’humain. C’est en ce sens où ça sort des maths. Ce n’est pas honteux. Je ne me moque pas. Mais ces questions là sortent du caractère universel inhérent aux maths. 

Médiat_Suprème

Difficile de prendre au sérieux, quelqu'un qui ignore totalement les questions qui lui sont posées 

Dom

Médiat_Suprème, tu exagères. Tes questions sont mathématiques…

JLapin

Sneg a dit : Mais impossible pour moi de vous faire dire comment, vous, vous faites !

Soit $x$ un réel. On peut considérer la suite de ses décimales définie par $u_n = \lfloor 10^n x\rfloor - 10 \lfloor 10^{n-1}x\rfloor$.

Ce n'est pas un secret.

raoul.S

Personnellement lorsque je pense à un réel de $[0,1]$ je le vois comme la suite de ses décimales, mais c'est totalement subjectif.

Par contre l'argument diagonal de Cantor te dis (Sneg) que tu ne peux pas t'imaginer l'ensemble $[0,1[$ comme un tableau de chiffres s'étendant à l'infini à droite et en bas.

Pour finir, la façon de visualiser dans sa tête les objets mathématiques est quand même subjective et ne fait pas partie de ce qu'on nomme "mathématique". Le fait de "visualiser" aide à trouver le chemin qui conduira à la démonstration d'un résultat par exemple, mais c'est tout. On pourrait tout ramener à une application de règles syntaxiques sans aucune interprétation.  

Dom

Le jeu du dé : expérience philosophique. 
On jette un dé à dix faces numérotées de 0 à 9. 

On ne s’arrête pas. Et on crée alors un réel dans $[0;1]$ (je ferme en $1$ au cas où 🤣). 

Vais-je tomber sur un entier ? Sur un décimal ? Sur un rationnel ?

C’est avec cette idée que j’ai « compris » la première fois que les rationnels étaient très peu présents (ce serait ultra super rare de tomber sur un dé qui sort la même séquence à partir d’un certain moment !) dans les réels.

Georges Abitbol

@Sneg : moi je ne réponds pas à tes histoires d’infini en acte, actuel, potentiel, parce que je ne sais pas ce que c’est (à part que c’est de la philosophie à côté de la plaque). Je ne pense pas être seul…
Par contre, tu n’arrêtes pas de parler d’un tableau et je ne sais pas qui c’est. Si je te dis « tous les hommes sont mortels », tu penses que je parle d’un homme en particulier ? Ici, c’est pareil, l’argument diagonal est de la forme « pour tout tableau,il existe un truc pas dans le tableau ». Il ne parle donc pas d’un tableau particulier…

raoul.S

Georges Abitbol a dit : 

Par contre, tu n’arrêtes pas de parler d’un tableau et je ne sais pas qui c’est.

On est à la deuxième page du fil et tu ne sais toujours pas qui c'est "le" tableau... ?

Foys

Un petit rappel de ce que l'argument diagonal n'a rien à voir avec une quelconque notion d'infini. Etant donnée une fonction $f$ de $\{0,1,2,3\} $ dans $\{0,1\}^{\{0,1,2,3\}}$, $y \mapsto 1 - f(y)(y)$ est une fonction de $\{0,1,2,3\}$ dans $\{0,1\}$ qui n'est pas dans l'image de $f$.

Dom

Coquille, Foys ? Ou je n’y comprends rien 🧐🤨

Foys

Dom a dit :

Coquille, Foys ? Ou je n’y comprends rien 🧐🤨

je l'ai réécrit, ça devrait aller mieux maintenant

Alain24

[*** Modéré. Hors sujet. AD]

PetitLutinMalicieux

Sneg, on n'a pas besoin de l'infini. Une formulation qu'on utilise souvent, en math, quand on travaille les suites, c'est "Il y a un rang à partir duquel blablabla". Ici, il y a un rang à partir duquel le nombre inventé par Cantor sort nécessairement de la liste. À quel rang ? Celui pour lequel la décimale diffère. Quelque soit le réel que tu choisisses, il existe une disqualification. On ne construit rien. Ni tableau fini, ni tableau infini.

Dom

Dans le cas fini ou dans le cas infini (suite de suites) le nombre sort du tableau à chaque rang (pas seulement à partir d’un certain rang).

Le cas infini contient une légère différence (subtilité ?). 

En général, on prend la base $3$ on n’a alors que les chiffres $0$, $1$ et $2$ dans ce tableau. 

Il faut juste s’arranger pour ne pas retrouver un développement impropre (que des $2$ à partir d’un certain rang). 

Sneg

Bonjour
Si vous le voulez bien, concentrons-nous sur l'essentiel : 
$\bullet$ Commençons par laisser tomber l'infini actuel, qui dérange.
$\bullet$ Ensuite, me fondant sur la théorie des "nombres réels calculables" d'Alan Turing, j'affirme que dans l'intervalle des réels $[0, 1[$ il existe des nombres réels calculables et des nombres réels non calculables (pour faire simple, on dira que les décimales de ces derniers nombres s'égrènent à l'infini de façon totalement aléatoire).
En effet : 
D'une part, l'intervalle des réels $[0, 1[$ contient une infinité de nombres rationnels, qui sont des nombres réels calculables.
D'autre part : 
- l'ensemble des nombres réels calculables est dénombrable,
- l'ensemble des nombres réels non calculables est non dénombrable,
- l'intervalle des réels $[0, 1[$ est non dénombrable. Donc, ce dernier intervalle contient des nombres réels non calculables.

Maintenant, à propos de l'argument diagonal, vous dites : 
"Quand on veut mettre l'intervalle des réels $[0, 1[$ en bijection avec $\mathbb{N}$, on aboutit à une contradiction. Donc, l'intervalle précité n'est pas dénombrable."
C'est évidemment ce que je dirais moi aussi à un examen pour avoir un minimum de points. Mais, vous l'aurez remarqué, les nombres réels non calculables me chiffonnent l'esprit.
Alors, à propos de l'argument diagonal, je dis plutôt : 
"A supposer que je puisse connaître l'infinité des décimales de chacun des nombres réels appartenant à l'intervalle $[0, 1[$,
alors,
je peux démontrer que l'intervalle précité n'est pas dénombrable."

Je sais que ma supposition est fausse puisqu'on ne pourra jamais connaître l'infinité des décimales des nombres non calculables, vu qu'elles s'égrènent à l'infini de façon aléatoire et que l'on ne maîtrise pas le hasard (sinon, ce ne serait plus du hasard).
Mais, au fond, ça n'a aucune importance que ma supposition soit fausse puisque, en matière d'implication, "quand l'antécédent est faux, l'implication est vraie quel que soit le conséquent".

Voilà.

Un avis en tant que mathématicien ?
Merci d'avance.

JLapin

Pour la millième fois, on connais les décimales de n'importe quel réel $x$ car la formule $u_n = \lfloor 10^n x\rfloor - 10\lfloor 10^{n-1} x\rfloor$ existe.

Dom

Que signifie « connaître l’infinité des décimales de chaque des réels » ?
Je sais comment sont les décimales de tous les réels entre $0$ et $1$. 

Je ne sais pas quelles sont les décimales du nombre $\pi$. 

Dom

Sur wiki on trouve cela. 

Désolé, j’ai peut-être oublié, est-ce que ça a déjà été évoqué dans ce fil ?

Il n’y a pas de contradiction : 
- si le nombre de Cantor construit avec la suite des calculables est calculable alors il y a contradiction (et les calculables ne sont pas dénombrables). 
- si ce nombre n’est pas calculable, alors il n’y a aucun problème. 

Par contre je suis incapable de démontrer que ce nombre n’est pas calculable malgré le commentaire à la fin. 

Foys

Le mot "connaître" n'appartient pas au vocabulaire mathématique (formel). Je ne pense pas que quiconque puisse livrer la $n$-ième décimale de $\pi$ lorsque mettons $n = 10^{10^{10^{10^{1000}}}}$ même avec les meilleurs algorithmes existants. L'argument diagonal ne parle pas de ce qui est "connaissable" ou non mais exhibe constructivement une fonction qui est en dehors de l'image d'une autre.

JLapin

Dom a dit :

Sur wiki on trouve cela. Désolé, j’ai peut-être oublié, est-ce que ça a déjà été évoqué dans ce fil ?

...

Par contre je suis incapable de démontrer que ce nombre n’est pas calculable malgré le commentaire à la fin. 

Le nombre diagonal n'est pas calculable puisqu'il n'est pas dans la liste des nombres calculables.

L'attribution n'est pas calculable sinon on pourrait fabriquer un nombre à la fois calculable et non calculable.

J'espère ne pas dire de bêtise

Dom

Oui, JLapin, je me suis mal exprimé.
L'argument diagonal montre que le nombre (Cantor) n'est pas calculable.
Je m'interrogeais sur une preuve directe que ce nombre diagonal n'est pas calculable. Mais j'ai des carences énormes sur le sujet de ces nombres là, ça explique cet écueil de ma part.

JLapin

Il est tautologiquement non calculable, ou alors je n'ai pas compris ta question.

Foys

A nouveau, une fonction est un ensemble de couples et non pas un procédé donc l'existence de fonctions parfaitement définies mais non calculables par un algorithme ne devrait pas poser plus de problèmes que ça.

Dom

Foys, 
c’est ma méconnaissance de « être calculable », il faut que je fasse plus que lire…
ça fait penser aux élèves qui ne connaissent rien du cours et qui posent de questions en mettant des mots de la leçon bout à bout sans les comprendre 🤣
j’arrête donc pour le moment.

Thierry Poma

Bonjour

Je n'ai pas lu l'intégralité du fil, mais je vous propose ce texte bourbakiste extrait de leur livre Topologie générale, chapitre IV (i.e. chapitre 4, sait-on jamais). Les concepts abordés auraient pu faire l'objet d'un bon sujet de CAPES ; je ne sais même pas si un tel sujet existe ou pas.

Foys

@Dom pour une définition de fonction calculable bien faite mais en anglais (ils appellent ça des "general recursive functions" mais la terminologie disons savante française est "fonction récursive partielle"), consulter https://en.wikipedia.org/wiki/General_recursive_function

Malheureusement toutes les sources non lourdement techniques en français sont pédagogistes (jamais de définition précise mais des centaines de pages d'exemples).

Médiat_Suprème

Puisque Sneg ne veux pas répondre : 

1. Est-ce que $x$ existe ?                                                    Oui (trivial)
2. Est-ce que $x$ est un réel ?                                             Oui (trivial)
3. Est-ce que $x\in [0,1[$ ?                                                  Oui (trivial, avec une microscopique subtilité pour éliminer 1)
4. Est-ce que $x\in \operatorname{Im}(\varphi)$?                                                 Non(trivial)
   
   

Il s'agit bien de l'argument diagonal, sans tableau, sans infini actuel, (l'infini potentiel apparaît dans la limite), la calculabilité ne pose pas de problème (que $x$ soit calculable ou non n'a pas d'impact), il n'est pas question de représentation décimale (ou autre)

raoul.S

Médiat_Suprème a dit :
4. Est-ce que $x\in \operatorname{Im}(\varphi)$ ?                                                 Oui (trivial)

Tu veux dire Non plutôt...

Médiat_Suprème

Merci, c'est corrigé

Sneg

Bonjour, c'est re-moi.
Je vais m'employer à rendre précis les termes que j'ai employés dans mon message précédent. 

J'espère que le pauvre Alan Turing ne se retournera pas dans sa tombe si je dis que chaque décimale d'un nombre réel calculable est elle-même calculable, en ce sens qu'elle peut être déterminée avec précision parmi les dix valeurs possibles $\{0, 1, 2, \dots, 9 \}$ au moyen d'un algorithme (et cela, ne serait-ce qu'en pure théorie). 

A titre d'exemple, $\pi$ est un nombre calculable : Bien sûr, on n'en connaîtra jamais chacune des décimales puisqu'il y en a une infinité, mais chaque décimale est calculable au sens donné ci-dessus.

Cela dit, quand on applique le procédé diagonal à l'ensemble des nombres réels calculables, on construit à partir de la diagonale du fameux "tableau $T$" un nombre $D$ dont chaque décimale est calculable (l'algorithme déterminant la valeur de chaque décimale de ce nombre n'est autre que le tableau $T$ lui-même, chaque valeur obtenue étant par exemple simplement augmentée d'une unité, le $9$ donnant $0$). Ce nombre $D$ est-il alors calculable ? Voici ma réponse : 
Comment donc définir ce nombre $D$ autrement qu'en disant : "C'est le nombre que l'on obtient au moyen du tableau $T$" ? C'est à mes yeux l'histoire du serpent qui se mord la queue. C'est la raison pour laquelle je ne reconnais pas à ce nombre le titre de "nombre calculable". Heureusement pour moi, la théorie d'Alan Turing ne me contredit pas. Ouf ! 
Par conséquent, l'ensemble des nombres réels calculables est dénombrable.

Quant aux nombres réels non calculables, j’espère qu’Alan Turing ne m’en voudra pas de dire que ce sont des nombres pour lesquels il n’existe pas d’algorithme capable de calculer la suite de leurs décimales. 
On remarquera que le procédé diagonal appliqué à l'ensemble des nombres réels non calculables ne produit que des décimales non calculables au sens donné plus haut. Par exemple, cela donne un nombre tel que $0, a_{11} a_{22} a_{33} a_{44} a_{55} \dots$ où la valeur de chaque $a_i$ n'est pas calculable au sens donné plus haut.
Le procédé diagonal appliqué à l'ensemble des nombres réels non calculables produisant encore une fois un nombre non calculable, l'ensemble des nombres réels non calculables n'est pas dénombrable.

Cette distinction entre "nombres réels calculables" et "nombres réels non calculables" étant faite (j'espère convenablement), je reprends mon raisonnement du message précédent : 
A supposer qu'il existe un algorithme (autre que le tableau $T$) permettant de calculer (au sens donné plus haut) chaque décimale de chaque réel appartenant à l'intervalle $[0, 1[$,
alors,
il existe un raisonnement, l'argument diagonal, démontrant que l'intervalle précité est non dénombrable.

Comme je l'ai déjà écrit dans mon message précédent, je sais que ma supposition est fausse. Mais cela n'a pas d'importance puisque, en matière d'implication, "quand l'antécédent est faux, l'implication est vraie quel que soit le conséquent".

Est-ce tenable, mathématiquement ?

Merci à tous pour vos interventions, notamment @Thierry Poma qui intervient pour la première fois dans un de mes fils, me semble-t-il.
@Médiat_Suprème : Je ne l'ai effectivement écrit nulle part, mais dans ce fil, j'introduis les notions de nombres réels calculables/non calculables dans l'argument diagonal tel qu'il est généralement présenté au novice, c'est-à-dire avec le fameux tableau $T$.

Médiat_Suprème

Encore les mêmes erreurs, pourtant déjà signalées !

Sneg

c'est-à-dire, si ce n'est pas trop demander ?

JLapin

Sneg a dit :
Est-ce tenable, mathématiquement ?

Désolé, mais ce ne sont pas des mathématiques. Seulement un discours un peu confus. Peux-tu clarifier ce que tu cherches à nous dire ?

Médiat_Suprème

Ce n'est pas la seule erreur (il suffit de relire ce fil), mais, exercice trivial : montrer qu'il existe des nombres non calculables dont toutes les décimales en position paires sont égales à 0.

Foys

Sneg a dit :

Parlons maintenant des nombres réels non calculables.
Encore une fois, j'espère que Alan Turing ne m'en voudra pas de dire qu'aucune des décimales d'un nombre réel non calculable n'est calculable, en ce sens que, pour chacune d'elles, il n'existe aucun moyen d'en connaître la valeur précise parmi les dix valeurs possibles $\{0, 1, 2, \dots, 9 \}$.

Il ne pourra pas t'en vouloir parce qu'il est mort. Par contre je pense que ce message (parmi d'autres) peut incommoder les lecteurs. Soit $x$ un nombre réel non calculable et $n$ un entier tel que $10^n > x$. Alors la première décimale de $y:=0,1+\frac x {10^{n+1}}$ est calculable et vaut $1$. $y$ est-il calculable ?

JLapin

@Médiat_Suprème
On peut prendre $x$ non calculable et intercaler un $0$ entre chaque décimale de $x$, c'est ça ?

Médiat_Suprème

Plus simple : les compter.

JLapin

Suis-je bête !