Notions de logique mathématique
[MAT1235]
[30h + 15h] 5 crédits
Cette activité se déroule pendant le 2e quadrimestre.
Enseignants : Christian Michaux, Cédric Rivière
Langue d'enseignement : Français
Niveau : Premier cycle
Objectifs (en termes de compétences)
Objet de l'activité (principaux thèmes à aborder)
On aborde alors l'étude générale des structures et langages algébriques finitaires. Du côté des structures, on n'oublie pas les homomorphismes. Du côté des langages, on regarde en particulier les substitutions, en exploitant la propriété universelle de l'algèbre des termes.
Le calcul des propositions suit alors, comme étude d'une algèbre particulière au sein de laquelle on va s'efforcer de repérer les formules valides. On élabore à cette fin un système axiomatique, dont on montre qu'il est sain (le démontrable est valide) et qu'il est complet (le valide est effectivement démontrable).
Dans la partie suivante, on étudie le calcul des prédicats, c'est-à-dire les structures et langages du premier ordre.
Langages plus complexes où il est à la fois question d'algèbre des termes et d'algèbre des formules. L'interprétation des symboles fonctionnels et relationnels se prolonge en association d'opérations finitaires dérivées aux termes et de relations finitaires dérivées aux formules. Ici aussi, on s'intéresse particulièrement aux formules valides, et on présente un système axiomatique qui va permettre de les obtenir. On va jusqu'au théorème de complétude, démontré à la façon de Henkin.
Les concepts sont illustrés par l'examen de structures algébriques ou du premier ordre familières, comme les groupes ou les corps ordonnés, par exemple.
En fonction du temps disponible on abordera éventuellement d'autres notions de théorie des ensembles, comme l'axiome du choix, les ordinaux, un peu d'arithmétique cardinale, ou on fera quelques pas en théorie des fonctions récursives.
Résumé : Contenu et Méthodes
Préliminaires ensemblistes (notions de base, définition de certains ensembles, les entiers naturels et l'induction, couples et produits cartésiens, relations, fonctions, applications, le dénombrable).
Partie "Prélogique": structures algébriques, langages algébriques, interprétations et valuations, propriété universelle des algèbres de termes.
Partie "Propositions" : point de vue sémantique (structure algébrique des valeurs de vérité, langage des propositions, interprétation standard, vérité, tautologies), point de vue axiomatique (calcul des propositions, théories consistantes, théories maximales consistantes) et lien entre les deux points de vue (adéquation et complétude).
Partie " Prédicats": point de vue sémantique (structures du premier ordre, interprétations, modèles, formules valides), point de vue axiomatique (calcul des prédicats, théories consistantes, fermées, riches, maximales) et lien entre ces deux point de vue (adéquation et complétude, à nouveau).
Partie "Egalité": adaptation de la partie précédente aux théories du premier ordre avec égalité.
Méthode:
le cours comprend des exposés théoriques et des séances d'exercices concernant exemples et applications.