GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:calculabilite:paradoxes

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:terminales:calculabilite:paradoxes [2023/02/06 16:54] – goupillwikinsi:terminales:calculabilite:paradoxes [2023/02/06 19:58] (Version actuelle) – goupillwiki
Ligne 3: Ligne 3:
 ===== Le paradoxe du Barbier ===== ===== 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 : Bertrand Russel, grand logicien du début XXe siècle, propose le paradoxe suivant :
Ligne 26: Ligne 26:
 ===== Construction axiomatique ===== ===== 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. Les paradoxes comme celui de Russell conduisent à chercher un langage plus rigoureux qui empêcherait de les énoncer.
Ligne 41: Ligne 41:
   * Les démonstrations sont des enchaînements déductifs **finis** construits à partir des axiomes.   * Les démonstrations sont des enchaînements déductifs **finis** construits à partir des axiomes.
   * Ainsi, on ne va pas se demander si une propriété est **vraie**, mais si elle est **démontrable**.   * 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 === === Axiomes de Peano ===
  
-{{ :nsi:terminales:calculabilite:peano.jpg?200|}}+{{ :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 : Pour définir l'ensemble des entiers naturels $\mathbb{N}$, Giuseppe Peano propose les axiomes suivants :
Ligne 56: Ligne 61:
 === Écriture formelle === === Écriture formelle ===
  
-{{ :nsi:terminales:calculabilite:boole.jpg?nolink&200|}}+{{: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. 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.
Ligne 68: Ligne 73:
  
 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. 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 ===== ===== Paradoxe de Richard =====
Ligne 100: Ligne 117:
 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é. 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.
nsi/terminales/calculabilite/paradoxes.1675698872.txt.gz · Dernière modification : de goupillwiki