Théorème de Löwenheim-Skolem

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant la logique image illustrant les mathématiques
Cet article est une ébauche concernant la logique et les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En théorie des modèles, le théorème de Löwenheim-Skolem (de Leopold Löwenheim et Thoralf Skolem) dit, pour résumé, que si une formule de la logique du premier ordre qui admet un modèle infini, alors il admet un modèle de n'importe quelle cardinalité infinie. Le résultat est souvent présenté sous la forme de deux théorèmes ː le théorème de Löwenheim-Skolem ascendant et le théorème de Löwenheim-Skolem descendant.

Formulations[modifier | modifier le code]

Cas d'un langage dénombrable[modifier | modifier le code]

Le théorème de Löwenheim-Skolem lorsque le langage est dénombrable (c'est souvent une hypothèse raisonnable notamment en informatique et c'est une hypothèse faite dans certains ouvrages de logique en informatique[1]) peut s'énoncer par ː si une formule est satisfiable alors elle est satisfiable dans un modèle au plus dénombrable[1]. Ou plus généralement ː si un ensemble T (dénombrable) de formules closes est satisfiable alors T est satisfiable dans un modèle au plus dénombrable[1].

Théorèmes de Löwenheim-Skolem pour tout cardinal[modifier | modifier le code]

A partir de M, il existe un modèle N de cardinal κ tels que M et N soient élémentairement équivalents et si κ est plus petit que le cardinal du domaine de M, alors N est un sous-modèle de M et sinon M est un sous-modèle de N.

Soit σ une signature pour un langage du premier ordre qui contient l'égalité. Soit κ un cardinal tel que |σ| ≤ κ. Soit M un modèle infini sur la signature σ. Alors il existe un modèle N de cardinal κ tel que M et N sont élémentairement équivalents[2] et tels que ː

  • (théorème de Löwenheim-Skolem descendant) N est un sous-modèle[3] de M si κ < |M| ;
  • (théorème de Löwenheim-Skolem ascendant) M est un sous-modèle de N si κ > |M|.

Idées des démonstrations[modifier | modifier le code]

Théorème de Löwenheim-Skolem ascendant[modifier | modifier le code]

Soit σ, κ, M comme dans l'hypothèse du théorème ascendant ː |σ| ≤ κ < |M|. Ajoutons une constante ca pour tout élément a du domaine de M. Soit M+ défini comme le modèle M mais où, on interprète également les constantes ca ː l'interprétation de ca est a. On considère un ensemble E de cardinal κ et des constante di pour tout i dans E. Soit T+ l'ensemble des formules vraies dans M' sur le langage de signature σ et les constantes ca. On considère alors la théorie T' contenant T+ et les formules di ≠ dj pour i ≠ j. Toute partie finie de T' est satisfiable dans un modèle M', qui est comme M sauf que l'on interprète aussi les constantes di. Par le théorème de compacité, T' admet un modèle dont le cardinal est au plus κ. Par définition de T', le cardinal est exactement κ. En s'aidant des constantes ca, on montre que ce modèle est extension de M[4].

Théorème de Löwenheim-Skolem descendant[modifier | modifier le code]

La partie descendante se montre en utilisant par exemple le théorème de complétude, ou au minimum la complétion du langage par des témoins de Henkin utilisée dans les versions modernes de la démonstration du théorème de complétude.

Corollaires[modifier | modifier le code]

  • Le théorème de Löwenheim-Skolem permet par exemple de montrer que la logique du premier ordre est strictement inférieure à celle du second ordre.
  • Considérons la signature de l'arithmétique 0, 1, +, ×, ≤ et le modèle des réels M = (R, 0, 1, +, ×, ≤). D'après le théorème de Löwenheim-Skolem, l'ensemble des formules vraies sur M admet un modèle dénombrable.
  • Si on applique le théorème descendant à la théorie des ensembles, par exemple ZFC, ou à une autre théorie axiomatique destinée à fonder les théorèmes de Cantor, on obtient un univers dénombrable de tous les ensembles définis dans ZFC. Mais le théorème de Cantor permet de prouver dans ZFC qu'il existe des ensembles non dénombrables : c'est le paradoxe de Skolem, qui n'est contradictoire qu'en apparence. Le terme « dénombrable » est utilisé dans deux sens différents, au sens de la métathéorie pour « univers dénombrable », au sens de la théorie pour « il existe des ensembles non dénombrables ».

Notes et références[modifier | modifier le code]

  1. a, b et c (en) Ben-Ari, Mordechai, Mathematical Logic for Computer Science, Springer,‎ (ISBN 978-1-4471-4129-7)
  2. C'est-à-dire M et N satisfont les même formules du premier ordre sur la signature σ
  3. C'est-à-dire que le domaine de N est inclus dans le domaine de M et que les interprétations des fonctions et prédicats dans M sont les restrictions des interprétations dans N.
  4. (en) Malitz, J., Introduction to mathematical logic, Springer-Verlag,‎

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • René Cori et Daniel Lascar, Logique mathématique II. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles [détail des éditions]
  • Jean Ladrière, Le théorème de Löwenheim-Skolem, Cahier pour l'analyse, vol. 10 : La formalisation, 1969. [lire en ligne]