Theoreme de compacite


Theoreme de compacite

Théorème de compacité

Préambule

Il s'agit d'énoncer et de prouver le théorème de compacité du calcul des propositions. Ce théorème a un rôle très important pour la logique du premier ordre, notamment pour la preuve du théorème de complétude de Gödel. Sa preuve est basée (dans le cas dénombrable) sur le lemme de König, tout arbre infini à branchement fini a une branche infinie.

On dit qu'une proposition (c’est-à-dire une formule sans quantificateurs) est satisfiable s'il existe un modèle dans lequel la formule est vérifiée. Autrement dit, si il est possible de donner des valeurs de vérité aux atomes constituant la proposition de façon à ce que celle-ci prenne la valeur vraie. On dit qu'un ensemble de formules est non contradictoire s'il existe un modèle où toutes les formules de cet ensemble sont simultanément satisfaites.

Énoncé du théorème de compacité

Le théorème de compacité s'énonce comme suit :

Si tout sous-ensemble fini d’un ensemble quelconque de propositions est non contradictoire, alors l’ensemble complet est aussi non contradictoire.

On va simplement en donner une preuve dans le cas où l'ensemble de propositions (et donc l'ensemble des littéraux) est dénombrable:

Si tout sous-ensemble fini d’un ensemble infini dénombrable de propositions est non contradictoire, alors l’ensemble complet est aussi non contradictoire.

Preuve

Soit A un ensemble infini dénombrable de propositions et P(n) une suite infinie dénombrable des propositions de A.

Soit p(n) une suite infinie dénombrable de propositions atomiques avec lesquelles les propositions de A sont construites.

Considérons l’arbre construit de la façon suivante.

Il y a un seul nœud initial, vide, de niveau 0.
S’il y a modèle dans lequel p(1) et P(1) sont tous les deux vrais, alors p(1) est un nœud de niveau 1 rattaché à l’unique nœud de niveau 0.
S’il y a un modèle dans lequel (non p(1)) et P(1) sont tous deux vrais, alors (non p(1)) est aussi un nœud de niveau 1 rattaché à l’unique nœud de niveau 0.
Quand un nœud y est rattaché à un autre x, alors x précède y. Cette relation est transitive : si un nœud x précède y et que y précède z, alors x précède z.
À un nœud de niveau n, on rattache p(n+1) au niveau n+1 s’il y a un modèle dans lequel p(n+1), tous ses prédécesseurs, et tous les P(i) pour i de 1 à n+1 sont vrais.
À un nœud de niveau n, on rattache (non p(n+1)) au niveau n+1 s’il y a un modèle dans lequel (non p(n+1)), tous ses prédécesseurs, et tous les P(i) pour i de 1 à n+1 sont vrais.

On engendre de cette façon un arbre. Comme tout sous-ensemble fini de propositions de A est non contradictoire, cet arbre peut être indéfiniment poursuivi, il est donc infini, il a un nombre infini de nœuds. Comme chaque nœud ne peut avoir que deux successeurs au plus, il est à branchement fini. D’après le lemme de König, il a donc une branche infinie. Cette branche définit un modèle dans lequel tous les P(i) sont vrais. Cela termine cette preuve du théorème de compacité.


  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Th%C3%A9or%C3%A8me de compacit%C3%A9 ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Theoreme de compacite de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Théorème de compacité — ● Théorème de compacité théorème essentiel de la logique mathématique, dû à Gödel (1930) et A. I. Maltsev (1936), et selon lequel un ensemble de formules a un modèle si et seulement si chaque sous ensemble fini a un modèle …   Encyclopédie Universelle

  • Théorème de compacité — Préambule Il s agit d énoncer et de prouver le théorème de compacité du calcul des propositions. Ce théorème a un rôle très important pour la logique du premier ordre, notamment pour la preuve du théorème de complétude de Gödel. Sa preuve est… …   Wikipédia en Français

  • compacité — [ kɔ̃pasite ] n. f. • 1752; de compact ♦ Didact. Qualité de ce qui est compact. ● compacité nom féminin État, qualité de ce qui est compact : La compacité d un sol. Propriété d un espace topologique compact. Rapport entre le volume total des… …   Encyclopédie Universelle

  • Theoreme de Lowenheim-Skolem — Théorème de Löwenheim Skolem Le théorème de Löwenheim Skolem fait partie de la théorie des modèles. Sa simplicité et sa puissance en font un théorème majeur avec le théorème de compacité. Sommaire 1 Théorème 2 Variante 3 Corollaires …   Wikipédia en Français

  • Théorème de löwenheim-skolem — Le théorème de Löwenheim Skolem fait partie de la théorie des modèles. Sa simplicité et sa puissance en font un théorème majeur avec le théorème de compacité. Sommaire 1 Théorème 2 Variante 3 Corollaires …   Wikipédia en Français

  • Compacite — Compacité Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. La compacité est le caractère de ce qui est compact. Ce terme prend un sens particulier dans certains domaines : en topologie… …   Wikipédia en Français

  • Theoreme de completude de Godel — Théorème de complétude de Gödel Le théorème de complétude du calcul des prédicats du premier ordre a été démontré par Kurt Gödel (1929, thèse de doctorat, sur la complétude du calcul logique). Il affirme que le calcul des prédicats est complet au …   Wikipédia en Français

  • Théorème de complétude — de Gödel Le théorème de complétude du calcul des prédicats du premier ordre a été démontré par Kurt Gödel (1929, thèse de doctorat, sur la complétude du calcul logique). Il affirme que le calcul des prédicats est complet au sens où toute… …   Wikipédia en Français

  • Théorème de complétude de gödel — Le théorème de complétude du calcul des prédicats du premier ordre a été démontré par Kurt Gödel (1929, thèse de doctorat, sur la complétude du calcul logique). Il affirme que le calcul des prédicats est complet au sens où toute proposition qui… …   Wikipédia en Français

  • Compacité séquentielle — Pour les articles homonymes, voir Compacité. La compacité est une propriété topologique importante qui se définit en topologie générale, à partir de la notion de recouvrement ouvert. Toutefois dans le cadre des espaces métriques (comprenant… …   Wikipédia en Français