Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Elementary equivalence
Summary
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 '
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.