Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Théorème de Löwenheim-Skolem
Résumé
En théorie des modèles, le théorème de Löwenheim-Skolem, énoncé par Leopold Löwenheim en 1915 et démontré entièrement en 1920 par Thoralf Skolem, établit que si un ensemble de formules closes de la logique du premier ordre admet un modèle infini, alors il admet un modèle de n'importe quelle cardinalité infinie supérieure ou égale au cardinal du langage et de l'ensemble de formules. 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.
Considérons que 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). Le théorème de Löwenheim-Skolem peut alors s'énoncer par : si une formule est satisfaisable alors elle admet un modèle au plus dénombrable. Ou plus généralement : si un ensemble T (dénombrable) de formules closes est satisfaisable alors T admet un modèle au plus dénombrable.
vignette|upright=2|À 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 infini tel que |σ| ≤ κ. Soit M un modèle infini sur la signature σ. Alors il existe un modèle N de cardinal κ tel que :
(théorème de Löwenheim-Skolem descendant) N est une sous-structure de M si κ < |M| ;
(théorème de Löwenheim-Skolem ascendant) M est une sous-structure élémentaire de N si κ > |M|.
En particulier, M et N sont alors élémentairement équivalents.
Soit σ, κ, M comme dans l'hypothèse du théorème ascendant : |σ| ≤ κ et |M| < κ . Ajoutons une constante ca pour tout élément a du domaine de M et appelons σ+ la signature σ augmentée de ces constantes ca. Soit M+ défini comme le modèle M mais où l'on interprète chaque constante ca par l'élément a du domaine de M.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.