La partie C de ce cours, qui commence maintenant, prend un tournant décisif par rapport à ce qui précède. Même si on a rencontré précédemment des résultats non triviaux, on est restés dans le domaine de la théorie des ensembles basique. On va désormais s'intéresser à la théorie des ensembles avancée, celle qui jongle avec les modèles de ZFC. Pour ce faire nous allons devoir débuter par deux chapitres préliminaires, le premier concernant les théorèmes de complétude et de compacité, le second consacré aux théorèmes d'incomplétude.

A la section 1 on revient sur le calcul propositionnel. On commence par le théorème de compacité, qui dit qu'un ensemble de formules est satisfaisable ssi tout sous-ensemble fini l'est. On donne deux démonstrations de ce résultat, une basée sur la logique propositionnelle, l'autre sur la topologie et le théorème de Tychonoff. Ensuite, après quelques rappels sur l'axiomatique du calcul propositionnel, on démontre le théorème de complétude : toute tautologie est un théorème. En d'autres termes, si une formule F est vraie quelle que soit la distribution des valeurs de vérité des variables qui ont une occurrence dans F , alors il existe une démonstration de F à partir des axiomes et des règles du calcul propositionnel.

La section 2 est consacrée au calcul des prédicats du premier ordre. Après quelques rappels sur l'axiomatique et quelques préliminaires syntaxiques, dont le lemme de la déduction, on démontre le théorème de complétude généralisé : une théorie est consistante (c'est-à-dire non contradictoire) ssi elle a un modèle. Plus généralement, si σ est un énoncé vrai dans tous les modèles de T, alors il en existe une démonstration à partir des axiomes de T et du calcul des prédicats. On en déduit alors le théorème de complétude simple : un énoncé est vrai dans toutes les réalisations du langage ssi il est démontrable à partir des axiomes du calcul des prédicats. On en déduit également le théorème de compacité : une théorie T est consistante ssi toute sous-théorie finie de T l'est. Enfin, on montre comment le théorème de compacité permet de prouver l'existence de modèles non standards, par exemple pour l'arithmétique du premier ordre PA1.

A la section 3 on découvre les notions de produits réduits, ultraproduits et ultrapuissances. Le théorème de Los (prononcer Wosh) nous permet de donner une deuxième démonstration, topologique, du théorème de compacité du calcul des prédicats. On termine par une description des modèles non standards de l'arithmétique.

A la section 4 on donne quelques bases avancées de théorie des modèles. On commence par la notion d'équivalence élémentaire et de théorie complète. On donne un critère simple permettant d'affirmer qu'une théorie est complète, puis on en déduit quelques exemples. Viennent ensuite les notions de sous-structure élémentaire et de plongement élémentaire, qui vont nous permettre de démontrer les théorèmes de Löwenheim-Skolem et d'en donner une application.

Enfin, à la section 5 on fait une brève intrusion dans le monde des logiques d'ordre supérieur. L'essentiel de cette section porte sur la logique du second ordre. On en décrit la syntaxe, la sémantique et le pouvoir d'expression. On donne ensuite l'axiomatique de la logique du second ordre, et on en déduit qu'elle ne satisfait qu'un théorème de complétude faible. Pour des raisons assez évidentes, les théorèmes de compacité et de Löwenheim-Skolem y sont faux. On donne l'exemple de l'arithmétique du second ordre PA2, dont on montre qu'elle n'admet qu'un seul modèle à isomorphisme près. On termine par un bref descriptif des logiques du m-ième ordre et des logiques multisortées. Puis on conclut par une analyse des avantages et des inconvénients de chacune de ces logiques : en particulier la logique du second ordre a un pouvoir d'expression supérieur à celle du premier ordre et elle exclut l'existence de modèles non standard. En revanche, elle nous prive des théorèmes de compacité et de Löwenheim-Skolem, et le théorème de complétude y est fortement insatisfaisant.

Téléchargement du chapitre 14