Validationsans
EnseignantPatrick Simonetta
Horaires hebdomadaires 18.0 h CM
Années Master Logique Mathématique et Fondements de l'Informatique

Syllabus

Calcul des prédicats:

- langages, structures, formules, satisfaction, équivalence logique, formes prénexes;
- morphismes, plongements, isomorphismes, préservation des formules;
- calcul des propositions, tables de vérité, formes normales disjonctives et conjonctives.

Cardinalité:

- ensembles finis, ensembles dénombrables, equipotence, subpotence, classes cardinales, arithmétique cardinale;
- théorèmes de Cantor et de Cantor Bernstein ;
- Applications de Zorn et de l'axiome du choix, trichotomie.

Introduction à la théorie des modèles:

- théories consistantes, théories complètes, équivalence élémentaire, classes élémentaires, sous-structures et plongements élémentaires, test de Tarski, va et vients;
- exemples de théories, complétude: ensemble sans structure, prédicat unaire, ordre, relation d'équivalence, bijection sans cycles, groupes, anneaux, corps algébriquement clos, espaces vectoriels; 
- théorème de compacité, différents énoncés et applications: modèles infinis d'une théorie, théories finiment axiomatisables, classes non élémentaires, constructions de modèles non-standards.

Topologie (bases):

- ouverts, fermés d'une topologie, topologie discrète topologie engendrée par une famille d'ensembles, base d'ouverts, topologie induite, topologie produit, voisinages, base de voisinages, axiomes de dénombrabilité, notion de limite, continuité, espaces séparés, adhérence, intérieur, parties denses,  espaces séparables, espaces compacts, Tychonov, Bolzano Weierstrass, Borel Lebesgue;
- espaces métriques, topologie de l'ordre, topologie de l'espace des théories complètes et closes par conséquence et lien avec le théorème de compacité du calcul des prédicats; conditions nécessaires de métrisabilité, espaces normaux;
- filtres, bases de filtres, filtre image, filtre principal, filtre de Fréchet. Comparaison de filtres, filtres compatibles, ultra-filtres. Applications à la topologie : filtre des voisinages d'un élément dans un espace topologique, convergence, valeur d'adhérence, application à la compacité, démonstration des théorèmes de Bolzano Weierstrass et de Tychonov, application : théorème de compacité du calcul propositionnel.

Systèmes de Hilbert, théorème de complétude

- axiomes, règles de déduction, démonstrations formelles , conséquence syntaxique. Cas du calcul propositionnel (théorème de complétude en devoir). Cas du calcul des prédicat, quelques preuves formelles, lemme de finitude, lemme de déduction, lemme fondamental, théories cohérentes, théories syntaxiquement complètes;
- témoins de Henkin, théorème de complétude, applications à la logique du premier ordre: théorème de compacité du calcul des prédicats, théorème de Lowenheim-Skolem, critère de Vaught.

  Introduction à la théorie des ensembles (en utilisant la théorie des modèles):

- présentation des axiomes de ZF; définitions: couples, relations, applications, familles d'ensembles;
- construction des entiers principe de démonstration et de définition par récurrence;
- axiome du choix, énoncés équivalents, équivalence de l'axiome du choix avec Zermelo, Zorn, trichotomie, Tychonov quasi-compact (ébauches de démonstrations).

Bibliographie

• R.CORI & D.LASCAR : Logique mathématique : cours et exercices (Dunod, 2 tomes, 2003).