Elementary Equivalence

Elementary Equivalence

In model theory, a field within 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 φ(a₁, …, a_n) with parameters a₁, …, a_n from N is true in N if and only if it is true in M. If N is an elementary substructure of M, 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, b₁, …, b_n) 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 elementary equivalent with the Ehrenfeucht–Fraïssé games.