Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:calculabilite:paradoxes [2023/02/06 12:34] – créée goupillwiki
+++ nsi:terminales:calculabilite:paradoxes [2023/02/06 19:58] (Version actuelle) – goupillwiki
@@ Ligne 3: / Ligne 3: @@
 ===== Le paradoxe du Barbier =====
-{{ :nsi:terminales:calculabilite:russell.jpg?nolink&200|}}
+{{ :nsi:terminales:calculabilite:russell.jpg?nolink&200|Bertrand Russel 1872 - 1970}}
 Bertrand Russel, grand logicien du début XXe siècle, propose le paradoxe suivant :
@@ Ligne 19: / Ligne 19: @@
 **$N$ est-il contenu dans $N$ ?** La réponse est ni oui, ni non...
+<WRAP tip>
+On réalise qu'on ne peut pas écrire ce que l'on veut, on ne peut pas définir un ensemble en toute liberté. Un premier garde-fou est de n'autoriser que les élément d'un ensemble bien défini. Ainsi on pourra noter $\{x\in\mathbb{R}, x^2 < 4\}$ car les $x$ sont choisis dans un ensemble bien défini, ici $\mathbb{R}$.
+</WRAP>
 ===== Construction axiomatique =====
-{{ :nsi:terminales:calculabilite:david_hilbert.jpg?nolink&200|}}
+{{ :nsi:terminales:calculabilite:david_hilbert.jpg?nolink&200|David Hilbert 1862 - 1943}}
 Les paradoxes comme celui de Russell conduisent à chercher un langage plus rigoureux qui empêcherait de les énoncer.
@@ Ligne 38: / Ligne 42: @@
   * Ainsi, on ne va pas se demander si une propriété est **vraie**, mais si elle est **démontrable**.
+<WRAP important>
+  * Si on peut prouver, en une suite **finie** d'étapes, qu'une propriété est vraie ou fausse, alors la propriété est **décidable**
+  * Si on ne peut pas, elle est **indécidable**
+</WRAP>
+=== Axiomes de Peano ===
+{{ :nsi:terminales:calculabilite:peano.jpg?200|Giuseppe Peano 1858 - 1932}}
+Pour définir l'ensemble des entiers naturels $\mathbb{N}$, Giuseppe Peano propose les axiomes suivants :
+  * dans $\mathbb{N}$, il existe un élément, noté $0$ ;
+  * tout élément $n$ de $\mathbb{N}$ admet un **successeur** noté $s(n)$, élément de $\mathbb{N}$ ;
+  * aucun élément de $\mathbb{N}$ n'a $0$ pour successeur ;
+  * deux entiers naturels ayant le même successeur sont égaux ;
+  * si un ensemble d'entiers naturels contient $0$ et le successeur de chacun de ses éléments, alors c'est ensemble est $\mathbb{N}$ -- //il s'agit du raisonnement par récurrence//
+=== Écriture formelle ===
+{{:nsi:terminales:calculabilite:boole.jpg?nolink&200 |George Boole 1815 - 1864}}
+Boole énonce les règles de logiques formelles. On sait alors comment articuler des propriétés pour former de nouvelles propriétés. On peut aussi reformuler les énoncés dans un langage non ambigu.
+Dans ce nouveau langage, les axiomes de Peano prennent la forme :
+  * $0 \in \mathbb{N}$ ;
+  * $\forall x, x=0 \vee \exists y (x=s(y))$
+  * $\forall x \forall y, (sx = sy \Rightarrow x=y)$
+  * ...
+Une démonstration devra donc être une articulation de ces axiomes, utilisant les règles de l'algèbre de Boole, d'une longueur finie.
+===== Conjecture de Goldbach =====
+Le nouvel enjeu, dans cette approche axiomatique finitiste, est de démontrer des propriétés. Si on peut démontrer une propriété, c'est qu'elle est vraie. Mais pourrait-elle être vraie sans qu'on puisse la démontrer ?
+Goldbach propose la conjecture (//c'est à dire : on pense que c'est vrai mais on ne l'a pas encore démontré//) suivante : **Tout nombre paire supérieur à 2 est la somme de deux nombres premiers.**
+Par exemple : $10\,708 = 4\,967 + 5\,741$
+On a vérifié que c'est vrai jusqu'à $4\cdot 10^{18}$ mais on ne l'a pas démontré.
+Se pourrait-il que la conjecture soit toujours vraie mais qu'il soit impossible de le démontrer ?
+===== Paradoxe de Richard =====
+Jules Richard, professeur de mathématiques dans un lycée de Dijon, propose un paradoxe : Supposons que je construises une liste numérotées de **prédicats**, c'est à dire des fonctions $p(n)$ qui renvoient Vrai ou Faux selon la valeur de $n$.
+Par exemple $p_1(n) =$ « est divisible par 2 ». On peut dire alors que $p_1(1)$ est faux, mais $p_1(2)$ est vrai.
+Ce qui nous intéresse est de savoir si $p_n{n}$ est vrai. On dit que $n$ est richardien si $p_n(n)$ est vrai.
+^ $n$ ^ $p_n(n)$                 ^ $p_n(n)$ ^
+| 1   | $n$ est divisible par 2  | Faux     |
+| 2   | $n$ est premier          | Vrai     |
+| 3   | $n$ est un carré         | Faux     |
+| ... | ...                      | ...      |
+| $N$ | $n$ n'est pas richardien | ...      |
+Dans cette liste, 1 et 3 ne sont pas richardien. Mais 2 l'est.
+Le nombre $N$ est-il richardien ?
+<WRAP important>
+Comme dans le paradoxe de Russel, on retrouve une idée d'autoréférence. C'est au moment où l'énoncé porte sur lui-même que l'on rencontre des problèmes.
+Le paradoxe de Richard est plus subtile et nécessite plus de précautions.
+</WRAP>
+=== Problème méta ===
+Le paradoxe de Richard repose sur le fait qu'il faut d'abord construire la grille pour définir ce que c'est que d'être richardien.
+Les propriétés « normales » dans la grille sont des propriétés portant sur les nombre. La propriété d'être richardien porte sur la grille. C'est une propriété d'un niveau différent, c'est une propriété sur les propriété, c'est une méta-propriété.
+===== Théorème de Gödel =====
+{{ :nsi:terminales:calculabilite:kurt_godel.png?200|Kurt Gödel 1906 - 1978}}
+Alors que l'on refonde les mathématiques sur des bases axiomatiques, par exemple pour l'ensemble $\mathbb{N}$ qui est fondamental, on se pose les deux questions :
+  * est-on certains que les axiomes n'aboutissent pas à une contradiction (//cohérence//)
+  * peut-on démontrer toute propriété vraie (//complétude//)
+Gödel va prouver que si c'est cohérent, alors c'est incomplet. Et la cohérence est justement une chose que l'on ne peut démontrer !
+Pour arriver à ses fins, Gödel invente un codage :
+| $\sim$ | $\vee$ | $\supset$ | $\exists$ | = | 0 | $s$ | ( | ) | ,  | $x$ | $y$ |
+| 1      | 2      | 3         | 4         | 5 | 6 | 7   | 8 | 9 | 10 | 11  | 13  |
+Prenons une expression logique comme $(\exists x)(x = sy)$. On transforme l'expression en écrivant :
+$$2^8 \times 3^4 \times 5^{11} \times 7 ^9 \times 11^8 \times 13^{11} \times 17^5 \times 19^7 \times 23^{13} \times 29^9$$
+ce qui donne $38685626227668133590597632$
+L'important ici n'est pas le résultat. L'important est que toute expression logique intervenant dans une propriété ou une démonstration peut être transformée en un nombre, de façon univoque.
+//Remarque : tout entier ne correspond pas à une expression. Seuls certains entiers codent une expression.//
+<WRAP box>
+Voici en gros le principe :
+  * toute expression logique $E$ construite à partir des axiomes de $\mathbb{N}$ est une suite de symboles ;
+  * par le codage de Gödel, on peut calculer $n = Godel(E)$ qui est l'unique entier correspondant à $E$ ;
+  * pour un $n$ valable donné, on peut retrouver $E$ ;
+  * Soit $ME$ un méta-énoncé portant sur $E$.\\ Puisque l'on peut transformer $E \to n$, alors on peut transformer $ME$ en un énoncé portant sur $n$.
+Gödel arrive ainsi à produire des méta-énoncés tout en restant dans le cadre d'une démonstration formelle.
+Il arrive à produire le méta-énoncé $G$ : « je ne suis pas démontrable ».
+</WRAP>
+Par conséquent,
+  * soit $G$ est vrai et alors on a trouvé une propriété vraie qui n'est pas démontrable. $\mathbb{N}$ est incomplet.
+  * soit $G$ est faux et alors, donc $G$ est démontrable et on peut démontrer le faux, donc $\mathbb{N}$ est incohérent.