[PDF] Introduction à la Logique Mathématique et Théorème de Gödel





Previous PDF Next PDF



Une écriture du théor`eme dincomplétude de Kurt Gödel

du codage Gödel construit des formules qui parlent des formules. De surcro?t



Théorème de Gödel : quand les mathématiques rencontrent l

Ce codage systématique par des nombres entiers pose les bases de l'informatique. Aujourd'hui cette idée a fait du chemin : nos textes nos images



Informatique vérité

http://biaa.eu/-upload/articleno1001.pdf



Le théorème de GOËDEL

GÖDEL nait le 28 avril 1906 dans une famille aisée de la capitale de la GÖDEL s'installe à VIENNE (1924) pour y ... Le codage d'une suite de formules.







L« argument diagonal » de Cantor `a Turing en passant par Gödel

Feb 2 2016 Est-ce que le calcul s'arrête ? La logique du premier ordre est indécidable. Alan Turing démontre ensuite qu'on peut « coder » l'arrêt de ...



Machines `a registres

Apr 13 2019 Codage de Gödel. [ord(lettre) for lettre in texte] transforme un texte en une suite d'entiers [u0



Notes de cours Preuves et Types DEA MDFI

Jun 28 2015 1.3 Codage de Gödel. On va maintenant utiliser le petit langage de programmation des fonctions p.r. pour représenter le.



ATTENTION !

2 Codage de Gödel. On établit maintenant un codage des configurations par des entiers naturels. Cette repré- sentation compacte sera utile dans la 



[PDF] Les théorèmes dincomplétude de Gödel

Le premier théorème d'incomplétude de Gödel repose sur l'observation que toutes les structures syntaxiques de l'arithmétique de Peano (PA) — les termes les 



[PDF] La Tétralogique

arithmétiques d'émuler n'importe quel système y compris eux-mêmes au travers d'un codage bien choisi L'émulation et l'universalité au sens de Gödel



[PDF] Informatique vérité théorème de Gödel

L'application de ce calcul donne comme code un nombre de Gödel facile à calculer qu'on désignera par K On se demande alors quel est le code ou nombre de Gödel 



[PDF] Une écriture du théor`eme dincomplétude de Kurt Gödel - Irif

En fait l'énoncé de Gödel ne dit pas «je» mais «une représentation de moi- même» ou encore : «un codage de moi-même» En effet le théor`eme d'incomplétude 



[PDF] Introduction `a la Logique Mathématique et Théor`eme de Gödel

14 mar 2012 · Un langage L est un ensemble de symboles constitué : d'un ensemble de symboles logiques {¬;?;?;?;?;?;?; (; )} ; d'un ensemble de variables 



[PDF] Article Une preuve moderne du théorème dincomplétude de Gödel

Mots clés : logique incomplétude théorème de Gödel informatique calculabilité 1 Introduction En termes de cardinalité : bien peu car le code



[PDF] 1er théorème de Gödel Théorème dincomplétude

* Nous parlons d'arithmétique car le 1er théorème de Gödel sous sa forme rigoureuse et mathématique s'appuie sur un système de codage des propositions 



[PDF] Kurt GÖDEL (1906-1978) est le plus grand logicien du XXe siècle

système formel non sujet au théorème de Gödel serait donc au choix points suivants : (a) Le codage : on associe à chaque expression A du langage de T



[PDF] Le théorème de Gödel ou une soirée avec M Homais

Ceci relève évidemment de la partie A positive B du programme de Hilbert : pour réaliser le programme il est nécessaire de pouvoir coder les artefacts logiques 

:

Introduction a la Logique Mathematique

et Theoreme de Godel

Benjamin Druart

Institut Fourier

14 mars 2012

Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 1 / 30 Plan

1Logique Mathematique

2Calculabilite

3Le theoreme d'incompletude de Godel

Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 2 / 30 Plan

1Logique Mathematique

2Calculabilite

3Le theoreme d'incompletude de Godel

Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 3 / 30

Notion de Langage

Denition

UnlangageLest un ensemble de symboles constitue :d'un ensemble de symboles logiquesf:;_;^;);,;8;9;(;)g;d'un ensemble de variablesfx1;x2;::::;xn;::::g;d'un ensembleCde constantes (ex : 0, 1,e...) ;d'un ensembleFde fonctions (ex: +,,exp...) ;d'un ensembleRde relations (ex: =,... ).Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 4 / 30

Formule du premier ordre

On peut ainsi denir uneformule du premier ordrecomme une suite

nie de symboles d'un langage obeissant a certaines regles, telle que :'8 _x1+ = ((9' ne soit pas une formule ;'8x(x0) 9y x=y2)' soit une formule.Dans une formule du premier ordre les quanticateurs ne portent que sur

les variables et pas sur des ensembles ou des nombres entiers :on ne peut pas dire, a priori, avec une formule du premier ordre qu'un

groupeGest simple, il faudrait pouvoir exprimer que tout

sous-groupe distingue est soitGsoitfeg.on ne peut pas dire, a priori, qu'un element d'un groupe est d'ordre

ni. Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 5 / 30

Formule du premier ordre

On peut ainsi denir uneformule du premier ordrecomme une suite

nie de symboles d'un langage obeissant a certaines regles, telle que :'8 _x1+ = ((9' ne soit pas une formule ;'8x(x0) 9y x=y2)' soit une formule.Dans une formule du premier ordre les quanticateurs ne portent que sur

les variables et pas sur des ensembles ou des nombres entiers :on ne peut pas dire, a priori, avec une formule du premier ordre qu'un

groupeGest simple, il faudrait pouvoir exprimer que tout

sous-groupe distingue est soitGsoitfeg.on ne peut pas dire, a priori, qu'un element d'un groupe est d'ordre

ni. Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 5 / 30

Structures

UneL- structureMest constituee d'un ensemble de baseM, ou l'on peut interpreter chaque symbole du langageL.Exemples :

hR;0;1;+;;;i;hR;hR;0;1;+;;;i;hR;hR;0;1;+;;;i;hR;

On dit qu'une theorieTest consistante si elle admet au moins un modele.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 7 / 30

Theorie

Denition

UnetheorieTest un ensemble de formules.Exemple :La theorie des groupesTdans le langageL=fe;gest

l'ensemble des 3 formules suivantes :8x8y8z(xy)z=x(yz)8x ex=xe=x8x9y xy=yx=eVocabulaire :SiMj=T, on dit queMest unmodeledeT.Denition

On dit qu'une theorieTest consistante si elle admet au moins un modele.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 7 / 30

Theorie

Denition

UnetheorieTest un ensemble de formules.Exemple :La theorie des groupesTdans le langageL=fe;gest

l'ensemble des 3 formules suivantes :8x8y8z(xy)z=x(yz)8x ex=xe=x8x9y xy=yx=eVocabulaire :SiMj=T, on dit queMest unmodeledeT.Denition

On dit qu'une theorieTest consistante si elle admet au moins un modele.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 7 / 30

Consequence semantique

Denition

SoitTune theorie et'une formule.

On dit que'est une consequence semantique deT, et on noteT`', si pour toutMj=T, on aMj='.Exemple :SiTest la theorie des groupes, on a

T` 8y(8x xy=yx=x)y=e)Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 8 / 30

Consequence semantique

Denition

SoitTune theorie et'une formule.

On dit que'est une consequence semantique deT, et on noteT`', si pour toutMj=T, on aMj='.Exemple :SiTest la theorie des groupes, on a

T` 8y(8x xy=yx=x)y=e)Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 8 / 30

Demonstration

SoitTune theorie, et'une formule.

On dit queTdemontre'si il existe une suite nie de formules

1; 2;:::; ntelle que n='et que iest :soit une formule deT;soit une tautologie ;

soit obtenue a partir a partir des j(pourjDemonstration

SoitTune theorie, et'une formule.

On dit queTdemontre'si il existe une suite nie de formules

1; 2;:::; ntelle que n='et que iest :soit une formule deT;soit une tautologie ;

soit obtenue a partir a partir des j(pourjDemonstration

SoitTune theorie, et'une formule.

On dit queTdemontre'si il existe une suite nie de formules

1; 2;:::; ntelle que n='et que iest :soit une formule deT;soit une tautologie ;

soit obtenue a partir a partir des j(pourjTheories completes

Denition

On dit qu'une theorieTestcompletesi elle est consistante et si elle verie l'une des deux conditions equivalentes suivantes : (i) Tous les modeles deTverient les m^emes formules.

(ii) Pour toute formule',T`'ouT` :'.Exemples:La theorie des corps algebriquement clos de caracteristique donnee est

complete.La theorie des groupes abelien inni divisible sans torsion est complete. Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 10 / 30

Theories completes

Denition

On dit qu'une theorieTestcompletesi elle est consistante et si elle verie l'une des deux conditions equivalentes suivantes : (i) Tous les modeles deTverient les m^emes formules.

(ii) Pour toute formule',T`'ouT` :'.Exemples:La theorie des corps algebriquement clos de caracteristique donnee est

complete.La theorie des groupes abelien inni divisible sans torsion est complete. Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 10 / 30

Le theoreme de compacite

Theoreme de compacite

1Test consistantessitoute partie nie deTest consistante.2Test inconsistantessiil existe une partie nieT0deTinconsistante.3T`'ssiil existe une partie nieT0Ttelle queT0`'.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 11 / 30

Plan

1Logique Mathematique

2Calculabilite

3Le theoreme d'incompletude de Godel

Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 12 / 30

Fonctions recursives primitivesDenition

On considereFl'ensembles des fonctionsf:Np!N.

L'ensemble desfonctions recursives primitivesest le plus petit

sous-ensemble deFqui contient :la fonctionnulle(0 :N!N);la fonctionsuccesseur(s:N!N) ;les fonctionsprojections(pik:Nk!Ntelles quepik(x1;:::;xk) =xi).

et qui est clos par :composition: sih:Np!Netg1;:::;gp:Nn!Nsont recursives primitives, alorsf:Nn!Ndenie par f(x1;:::;xn) =h(g1(x1;:::;xn);:::;gp(x1;:::;xn)) est recursive primitive.recurrence : sig:Np!Neth:Np+2!Nsont recursives primitives alorsf:Np+1!Nest recursive primitive ou : f(a1;:::;ap;0) =g(a1;:::;ap)

f(a1;:::;ap;x+ 1) =h(a1;:::;ap;x;f(a1;:::;ap;x))Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 13 / 30

Exemples :

1L'addition : on la denit par recurrence

x+ 0 =x x+ (y+ 1) = (x+y) + 1 =s(p33(x;y;x+y))2La multiplication : x0 = 0 x(y+ 1) = (xy) +y3Les fonctions polyn^omes ;

4La division euclidienne ;

5La fonction qui an2Nassocie laniemedecimale deou dee.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 14 / 30

Exemples :

1L'addition : on la denit par recurrence

x+ 0 =x x+ (y+ 1) = (x+y) + 1 =s(p33(x;y;x+y))2La multiplication : x0 = 0 x(y+ 1) = (xy) +y3Les fonctions polyn^omes ;

4La division euclidienne ;

5La fonction qui an2Nassocie laniemedecimale deou dee.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 14 / 30

Exemples :

1L'addition : on la denit par recurrence

x+ 0 =x x+ (y+ 1) = (x+y) + 1 =s(p33(x;y;x+y))2La multiplication : x0 = 0 x(y+ 1) = (xy) +y3Les fonctions polyn^omes ;

4La division euclidienne ;

5La fonction qui an2Nassocie laniemedecimale deou dee.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 14 / 30

Ensembles recursifs primitifs

Denition

Un ensemble (ou un predicat)ENpest dit recursif primitif si sa fonction caracteristique est recursive primitive.Exemples:1Les ensembles nis ;

2L'ensembles des nombres premiers ;

3Les predicats;;=;6=;:::(ie. les ensemblesf(x;y)2N2jxyg...)Proposition

L'ensemble des predicats recursifs primitifs est clos par:;^;_et par quantication bornee (ie siP(x1;:::;xn;y) est recursif primitif, alors le

predicatQ(x1;:::;xn) =8yk P(x1;:::;xn) est recursif primitif).Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 15 / 30

Ensembles recursifs primitifs

Denition

Un ensemble (ou un predicat)ENpest dit recursif primitif si sa fonction caracteristique est recursive primitive.Exemples:1Les ensembles nis ;

2L'ensembles des nombres premiers ;

3Les predicats;;=;6=;:::(ie. les ensemblesf(x;y)2N2jxyg...)Proposition

L'ensemble des predicats recursifs primitifs est clos par:;^;_et par quantication bornee (ie siP(x1;:::;xn;y) est recursif primitif, alors le

predicatQ(x1;:::;xn) =8yk P(x1;:::;xn) est recursif primitif).Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 15 / 30

Ensembles recursifs primitifs

Denition

Un ensemble (ou un predicat)ENpest dit recursif primitif si sa fonction caracteristique est recursive primitive.Exemples:1Les ensembles nis ;

2L'ensembles des nombres premiers ;

3Les predicats;;=;6=;:::(ie. les ensemblesf(x;y)2N2jxyg...)Proposition

L'ensemble des predicats recursifs primitifs est clos par:;^;_et par quantication bornee (ie siP(x1;:::;xn;y) est recursif primitif, alors le

predicatQ(x1;:::;xn) =8yk P(x1;:::;xn) est recursif primitif).Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 15 / 30

Fonction d'Ackermann

On considere la fonctionA:N2!Ndenie par :

A(0;x) =x+ 2

A(1;0) = 0 etA(n+ 2;0) = 1

A(n+ 1;x+ 1) =A(n;A(n+ 1;x))On peut demontrer que :

A(0;x) =x+ 2

A(1;x) = 2x

A(2;x) = 2x

Cette fonction est a priori calculable...... MAIS ELLE N'EST PAS RECURSIVE PRIMITIVE ! Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 16 / 30

Fonction d'Ackermann

On considere la fonctionA:N2!Ndenie par :

A(0;x) =x+ 2

A(1;0) = 0 etA(n+ 2;0) = 1

A(n+ 1;x+ 1) =A(n;A(n+ 1;x))On peut demontrer que :

A(0;x) =x+ 2

A(1;x) = 2x

A(2;x) = 2x

Cette fonction est a priori calculable...... MAIS ELLE N'EST PAS RECURSIVE PRIMITIVE ! Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 16 / 30

Fonction d'Ackermann

On considere la fonctionA:N2!Ndenie par :

A(0;x) =x+ 2

A(1;0) = 0 etA(n+ 2;0) = 1

A(n+ 1;x+ 1) =A(n;A(n+ 1;x))On peut demontrer que :

A(0;x) =x+ 2

A(1;x) = 2x

A(2;x) = 2x

Cette fonction est a priori calculable...... MAIS ELLE N'EST PAS RECURSIVE PRIMITIVE ! Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 16 / 30

Fonctions recursivesDenition

On considereFl'ensembles des fonctionsf:Np!N.

L'ensemble desfonctions recursivesest le plus petit sous-ensemble deF

qui contient :la fonctionnulle(0 :N!N);la fonctionsuccesseur(s:N!N) ;les fonctionsprojections(pik:Nk!Ntelles quepik(x1;:::;xk) =xi).

et qui est clos par :composition: sih:Np!Netg1;:::;gp:Nn!Nsont recursives, alorsf:Nn!Ndenie par

f(x1;:::;xn) =h(g1(x1;:::;xn);:::;gp(x1;:::;xn)) est recursive.recurrence: sig:Np!Neth:Np+2!Nsont recursives alors

f:Np+1!Nest recursive ou : f(a1;:::;ap;0) =g(a1;:::;ap) f(a1;:::;ap;x+ 1) =h(a1;:::;ap;x;f(a1;:::;ap;x))operateur: sig:Np+1!Nest recursive alors la fonction f:N!Nest recursive, ou

f(a1;:::;ap) =t[g(a1;:::;ap;t) = 0] = le plus petitttel queg(a1;:::;ap;t) = 0Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 17 / 30

Ensembles recursifs

Denition

Un ensembleENpest dit recursif si sa fonction caracteristique est une fonction recursive totale (ie. denie partout). Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 18 / 30

Ensembles recursivement enumerables

Denition

Un ensembleENpest ditrecursivement enumerablesi il est vide ou si il est l'image d'une fonction recursive totale (ie. il existe une fonction

recursive totalef:N!Nptelle queE=ff(x)jx2Ng).Remarque :Tout ensemble recursif est recursivement enumerable.Proposition

Un ensembleENpest recursifssi EetEcsont recursivement enumerables.Proposition Un ensembleENest recursivement enumerablessiil est denie par une

formule de la forme9x1:::9xk'ou'est sans quanticateur non borne.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 19 / 30

Ensembles recursivement enumerables

Denition

Un ensembleENpest ditrecursivement enumerablesi il est vide ou si il est l'image d'une fonction recursive totale (ie. il existe une fonction

recursive totalef:N!Nptelle queE=ff(x)jx2Ng).Remarque :Tout ensemble recursif est recursivement enumerable.Proposition

Un ensembleENpest recursifssi EetEcsont recursivement enumerables.Proposition Un ensembleENest recursivement enumerablessiil est denie par une

formule de la forme9x1:::9xk'ou'est sans quanticateur non borne.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 19 / 30

Ensembles recursivement enumerables

Denition

Un ensembleENpest ditrecursivement enumerablesi il est vide ou si il est l'image d'une fonction recursive totale (ie. il existe une fonction

recursive totalef:N!Nptelle queE=ff(x)jx2Ng).Remarque :Tout ensemble recursif est recursivement enumerable.Proposition

Un ensembleENpest recursifssi EetEcsont recursivement enumerables.Proposition Un ensembleENest recursivement enumerablessiil est denie par une

formule de la forme9x1:::9xk'ou'est sans quanticateur non borne.Benjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 19 / 30

Machines de Turing et these de Church

De son c^ote, A. Turing a donne un modele de machine abstraite pour denir ce qui calculable. Ce sont des machines capables de n'eectuer que certaines operations tres elementaires. On entre les donnees initiale et on obtient le resultat.Proposition Ce qui est calculable a partir de fonction recursive est calculable avec des machines de Turing et vice-versa.These de Church

fFonctions calculablesg=fFonctions recursivesg=fMachine de TuringgBenjamin Druart (Institut Fourier)Logique et theoreme de Godel14 mars 2012 20 / 30

Machines de Turing et these de Church

De son c^ote, A. Turing a donne un modele de machine abstraite pour denir ce qui calculable.quotesdbs_dbs45.pdfusesText_45
[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale

[PDF] prime prof principal contractuel

[PDF] evaluation anglais 6ème description physique

[PDF] indemnité prof principal agrégé terminale

[PDF] indemnités vacances éducation nationale