Ê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 Graph Search.
Concept
Équivalence élémentaire
Résumé
In model theory, a branch of mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences.
If N is a substructure of M, one often needs a stronger condition. In this case N is called an elementary substructure of M if every first-order σ-formula φ(a1, ..., an) with parameters a1, ..., an from N is true in N if and only if it is true in M.
If N is an elementary substructure of M, then M is called an elementary extension of N. An embedding h: N → M is called an elementary embedding of N into M if h(N) is an elementary substructure of M.
A substructure N of M is elementary if and only if it passes the Tarski–Vaught test: every first-order formula φ(x, b1, ..., bn) with parameters in N that has a solution in M also has a solution in N when evaluated in M. One can prove that two structures are elementarily equivalent with the Ehrenfeucht–Fraïssé games.
Elementary embeddings are used in the study of large cardinals, including rank-into-rank.
Two structures M and N of the same signature σ are elementarily equivalent if every first-order sentence (formula without free variables) over σ is true in M if and only if it is true in N, i.e. if M and N have the same complete first-order theory.
If M and N are elementarily equivalent, one writes M ≡ N.
A first-order theory is complete if and only if any two of its models are elementarily equivalent.
For example, consider the language with one binary relation symbol '
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.