Le but de ce chapitre est de présenter un cadre logique formel adéquat pour faire de la théorie des ensembles. On a vu au Chapitre 3 (paradoxe de Berry) qu'une partie des ennuis auxquels on est confrontés quand on essaie de faire une théorie axiomatique simplifiée des ensembles provient du fait qu'on n'a pas défini clairement la notion de propriété. Il s'agit donc de donner un sens à la formule ϕ(x) , et d'expliquer ce que signifie ϕ(x) est vraie quand on remplace x par tel ou tel objet.

A la section 1 on précise quelles sont nos exigences par rapport à une logique formelle. Il y a essentiellement 3 points : adéquation des règles énoncées avec l'intuition que l'on a acquise de par la pratique mathématique usuelle, cohérence de la logique (que les règles ne permettent de démontrer que des propriétés universellement vraies) et, ce qui est plus difficile à réaliser, la propriété de complétude : qu'une propriété vraie dans tous les modèles d'une théorie T admette une démonstration à partir des axiomes de T et des règles élémentaires de la logique considérée. Il existe plusieurs méthodes pour réaliser nos exigences, selon le type de quantifications que l'on s'autorise. Nous en présentons essentiellement trois dans cet ouvrage (dont deux dans ce chapitre), en allant de la plus simple à la plus sophistiquée.

La section 2 est consacrée au calcul propositionnel. On décrit rapidement le langage, puis les règles de constitution des formules. C'est là l'aspect syntaxique. Le côté sémantique consiste en la satisfaisabilité et en l'universelle validité d'une formule. On propose ensuite une axiomatisation du calcul propositionnel, couplée avec des règles de démonstration. Les nouvelles formules obtenues par application stricte de ces règles sont appelées des théorèmes. On montre que tout théorème est une tautologie (ou formule universellement valide), ce qui prouve au passage la cohérence (en anglais : soundness) du calcul propositionnel, puis on donne quelques exemples canoniques de tautologies. On termine par l'énoncé du théorème de complétude, dont la démonstration est reportée au Chapitre 14.

A la section 3 on découvre les bases du calcul des prédicats du premier ordre. La syntaxe y est plus complexe que dans le cas du calcul propositionnel. Il faut d'abord définir le langage. En plus des symboles logiques habituels (connecteurs et quantificateurs), ce dernier comporte des symboles spécifiques à chaque théorie : symboles de constante, de fonctions et de relations. Viennent ensuite les termes, qui sont les objets sur lesquels va porter notre étude, puis la notion générale de formule. Dans chaque formule interviennent un certain nombre de variables, dont certaines sont libres et d'autres liées. Une formule sans variable libre est appelée un énoncé, ou une formule close, et une théorie est un ensemble (fini ou infini) d'énoncés. Du point de vue de la sémantique, une structure, ou réalisation du langage, est un ensemble non vide sur lequel on a privilégié certains éléments, fonctions et relations qui vont servir d'interprétations aux symboles du langage. On est alors en mesure de définir la satisfaction des formules dans une structure. Un modèle d'une théorie T sera une structure dans laquelle tous les axiomes de T sont satisfaits. On précise alors le vocabulaire de base de la théorie des modèles, puis on donne les principes de démonstration en logique du premier ordre : il y a des tautologies, des axiomes logiques, des axiomes extra-logiques et des règles. Cette section se termine par l'énoncé du théorème de complétude, et par quelques exemples de théories axiomatiques.

Enfin, à la section 4 on donne, à titre de complément, une introduction à la logique intuitionniste, variante de la logique classique dans laquelle on refuse la loi du tiers exclu, ou, ce qui revient au même, le raisonnement par l'absurde. On explique qu'une légère modification de l'axiomatique du calcul propositionnel conduit à la logique intuitionniste (LI), puis on montre, dans le cadre de LI, l'équivalence entre un certain nombre de principes.

Téléchargement du chapitre 4