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 17:00] – 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 112: 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.1675699225.txt.gz · Dernière modification : de goupillwiki