Skip to main content
deleted 154 characters in body
Source Link
Dave Marker
  • 3.5k
  • 22
  • 22

The first example, dense linear orders without endpoints is model complete, indeed it has quantifier elimination and any theory with quantifier elimination is model complete. If we look at dense linear orders with top or bottom element then an argument like the one below shows it is not model complete.

For the second example, let $M$ be the natural numbers and let $N$ be the integers greater than or equal to -1. Then $M$ is a substructure of $N$ but $M\models$ ``0 is the least element", while this is false in $N$. Thus the theory is not model complete.

The first example is similar, let $M$ be $[0,1]$ and let $N$ be $[-1,1]$. Again $M\models$ ``0 is the least element" but the extension $N$ does not.

One equivalent of model completeness is that every formula is equivalent to an existential formula. So theories like true arithmetic, the theory of the natural numbers in the language {$+,\cdot,0,1$}, are far from model complete.

The first example, dense linear orders without endpoints is model complete, indeed it has quantifier elimination and any theory with quantifier elimination is model complete. If we look at dense linear orders with top or bottom element then an argument like the one below shows it is not model complete.

For the second example, let $M$ be the natural numbers and let $N$ be the integers greater than or equal to -1. Then $M$ is a substructure of $N$ but $M\models$ ``0 is the least element", while this is false in $N$. Thus the theory is not model complete.

One equivalent of model completeness is that every formula is equivalent to an existential formula. So theories like true arithmetic, the theory of the natural numbers in the language {$+,\cdot,0,1$}, are far from model complete.

For the second example, let $M$ be the natural numbers and let $N$ be the integers greater than or equal to -1. Then $M$ is a substructure of $N$ but $M\models$ ``0 is the least element", while this is false in $N$. Thus the theory is not model complete.

The first example is similar, let $M$ be $[0,1]$ and let $N$ be $[-1,1]$. Again $M\models$ ``0 is the least element" but the extension $N$ does not.

One equivalent of model completeness is that every formula is equivalent to an existential formula. So theories like true arithmetic, the theory of the natural numbers in the language {$+,\cdot,0,1$}, are far from model complete.

Source Link
Dave Marker
  • 3.5k
  • 22
  • 22

The first example, dense linear orders without endpoints is model complete, indeed it has quantifier elimination and any theory with quantifier elimination is model complete. If we look at dense linear orders with top or bottom element then an argument like the one below shows it is not model complete.

For the second example, let $M$ be the natural numbers and let $N$ be the integers greater than or equal to -1. Then $M$ is a substructure of $N$ but $M\models$ ``0 is the least element", while this is false in $N$. Thus the theory is not model complete.

One equivalent of model completeness is that every formula is equivalent to an existential formula. So theories like true arithmetic, the theory of the natural numbers in the language {$+,\cdot,0,1$}, are far from model complete.