cidur
audio

Editeur

cidur

Publications

( 214 )
icon

Filtres

0

icon sort

Trier

Resume Puisque ZF est une theorie du premier ordre on peut en considerer des modeles abstraits le theoreme de completude permet d utiliser une methode semantique de demonstration une formule ensembliste est prouvable a partir de ZF si et seulement si elle est vraie dans tous les modeles de ZF Faute de pouvoir l exprimer au premier ordre on ne peut exclure l existence d entiers non standards dans les modeles de ZF Le theoreme d incompletude de Godel interdit qu on puisse construire ex nihilo un modele de ZF On peut construire sur N une relation E telle que N E est modele de ZFfini les systemes ZFfini et PA2 ont la meme force Si M est un modele de ZF se placer dans M consiste a convenir que toutes les notions ensemblistes referent a M Partant d un modele de ZF on etudie les sous structures M ou M est un ensemble ou une classe transitive du modele alors V est extension finale de M et un grand nombre de notions ensemblistes sont absolues pour M c est a dire ont la meme interpretation dans les deux structures La structure V est modele de ZFC moins l axiome de l infini ceci entraıne que ZFC Inf ne prouve pas Inf et par le theoreme d incompletude de Godel que la consistance de ZFC Inf n entraıne pas celle de ZFC La structure V est modele de ZC mais pas de ZFC ceci entraıne que le systeme ZFC est strictement plus fort que le systeme de Zermelo ZC La consistance de ZFC moins l axiome de fondation entraıne celle de ZFC Un cardinal est inaccessible s il est regulier et fortement limite Si est inaccessible la structure V est modele de ZFC ceci entraıne que l existence d un cardinal inaccessible ne peut etre demontree a partir de ZFC ni meme sa consistance etablie Toute structure C R avec R bien fondee se projette sur une structure M avec M classe transitive ceci legitime de se concentrer sur les modeles de ZF de ce type icon
Category

Documents

Etudes supérieures

Resume Puisque ZF est une theorie du premier ordre on peut en considerer des modeles abstraits le theoreme de completude permet d'utiliser une methode semantique de demonstration une formule ensembliste est prouvable a partir de ZF si et seulement si elle est vraie dans tous les modeles de ZF Faute de pouvoir l'exprimer au premier ordre on ne peut exclure l'existence d'entiers non standards dans les modeles de ZF Le theoreme d'incompletude de Godel interdit qu'on puisse construire ex nihilo un modele de ZF On peut construire sur N une relation E telle que N E est modele de ZFfini les systemes ZFfini et PA2 ont la meme force Si M est un modele de ZF se placer dans M consiste a convenir que toutes les notions ensemblistes referent a M Partant d'un modele de ZF on etudie les sous structures M ou M est un ensemble ou une classe transitive du modele alors V est extension finale de M et un grand nombre de notions ensemblistes sont absolues pour M c'est a dire ont la meme interpretation dans les deux structures La structure V est modele de ZFC moins l'axiome de l'infini ceci entraıne que ZFC Inf ne prouve pas Inf et par le theoreme d'incompletude de Godel que la consistance de ZFC Inf n'entraıne pas celle de ZFC La structure V est modele de ZC mais pas de ZFC ceci entraıne que le systeme ZFC est strictement plus fort que le systeme de Zermelo ZC La consistance de ZFC moins l'axiome de fondation entraıne celle de ZFC Un cardinal est inaccessible s'il est regulier et fortement limite Si est inaccessible la structure V est modele de ZFC ceci entraıne que l'existence d'un cardinal inaccessible ne peut etre demontree a partir de ZFC ni meme sa consistance etablie Toute structure C R avec R bien fondee se projette sur une structure M avec M classe transitive ceci legitime de se concentrer sur les modeles de ZF de ce type

Resume Une logique formelle consiste en un ensemble de formules generalement des mots avec une notion syntaxique de preuves generalement des suites de formules obeissant a des regles de deduction et une notion semantique de valeur determinee a l aide de realisations convenables Les formules de la logique propositionnelle L sont des assemblages de variables X i a l aide de connecteurs L evaluation d une formule de L se fait inductivement a partir de l affectation de valeurs aux variables Une formule est dite valide resp satisfaisable si sa valeur est pour toute affectation resp pour au moins une affectation On dit que H se deduit par coupure a partir de F et G si G est la formule F H Une preuve par coupure est une suite de formules dont chacune est soit un axiome pris dans un liste fixee de types de formules soit obtenue par coupure a partir de formules anterieures de la liste Le theoreme de completude affirme qu une formule de L est valide si et seulement si elle est prouvable Le theoreme de compacite affirme qu un ensemble T de formules de L est satisfaisable c est a dire qu il existe une affectation de valeurs qui rende vraie chaque formule de T si et seulement si tout sous ensemble fini de T l est De nombreux problemes peuvent etre codes en un probleme de satisfaisabilite ou de validite pour un ensemble de formules propositionnelles Le theoreme de Cook et Levin affirme le caractere NP complet de l ensemble sat des formules satisfaisables icon
Category

Documents

Etudes supérieures

Resume Une logique formelle consiste en un ensemble de formules generalement des mots avec une notion syntaxique de preuves generalement des suites de formules obeissant a des regles de deduction et une notion semantique de valeur determinee a l'aide de realisations convenables Les formules de la logique propositionnelle L sont des assemblages de variables X i a l'aide de connecteurs L'evaluation d'une formule de L se fait inductivement a partir de l'affectation de valeurs aux variables Une formule est dite valide resp satisfaisable si sa valeur est pour toute affectation resp pour au moins une affectation On dit que H se deduit par coupure a partir de F et G si G est la formule F H Une preuve par coupure est une suite de formules dont chacune est soit un axiome pris dans un liste fixee de types de formules soit obtenue par coupure a partir de formules anterieures de la liste Le theoreme de completude affirme qu'une formule de L est valide si et seulement si elle est prouvable Le theoreme de compacite affirme qu'un ensemble T de formules de L est satisfaisable c'est a dire qu'il existe une affectation de valeurs qui rende vraie chaque formule de T si et seulement si tout sous ensemble fini de T l'est De nombreux problemes peuvent etre codes en un probleme de satisfaisabilite ou de validite pour un ensemble de formules propositionnelles Le theoreme de Cook et Levin affirme le caractere NP complet de l'ensemble sat des formules satisfaisables

Patrick Dehornoy