An example of an exists-sentence such that the sentence is true on an infinite model M, yet on every submodel, the sentence is false

Question

This problem and its solution were given at class. I don't understand why the solution is the solution. Could someone please explain in detail?

I am sorry for not using MathJax: it isn't working for me, this didn't help.

Problem: find an example of an exists-sentence (a formula where every variable is under the existence quantifier) such that the sentence is true on an infinite model $M$ (i.e. a model with an infinite carrier), yet on every submodel of $M$, the sentence is false.

The signature to use was told to be an equivalence relation ~, and two different unary operators $f$ and $g$. The answer to the problem is $\exists x\exists y \neg(x\sim y)$.

Now, suppose $N<M$, $a$ and $b$ are in $N$, and $a\sim b$. The smallest submodel = $\{a, b, f(a), f(f(a)),\dots, f(b), f(f(b)), \dots, g(a), g(g(a)), \dots, g(b), g(g(b)), \dots\}$. I don't see how two non-equivalent elements could not exist in $N$.

Is my reasoning wrong? Could I have missed something obvious in class?

Thank you.

Answer 1

As Noah and Eric pointed out, the statement of the proplem is missing the word "proper" (the sentence should be false only on the proper substructures of $M$, since $M$ is alwaays a substructure of itself). And the problem can be solved vacuously by considering a structure $M$ with no proper substructures.

The solution as you described it makes no sense. Here's an example which does have proper substructures and which I believe is similar in spirit to the intention of the proposed solution (but simpler).

Consider the language $\{P,f\}$, where $P$ is a unary relation symbol and $f$ is a unary function symbol. Let $M = \mathbb{N}$, where $P^M$ holds only of $0$ and $f^M$ is the successor function $f^M(n) = n+1$.

The substructures of $M$ are of the form $\{k,k+1,k+2,\dots\}$ for any $k$.

Consider the sentence $\exists x\, P(x)$. This sentence is true in $M$ (witnessed by $0$), but false in every proper substructure of $M$ (since no proper substructure of $M$ contains $0$).

Answer 2

If I understand correctly, you're looking for an infinite structure $M$ and some $\exists$-sentence true in $M$ but false in all of $M$'s proper substructures. The given solution appears a bit garbled and incomplete, and is also excessively complicated.

The simplest way to whip this up is to build an $M$ with no proper substructures whatsoever. In this case it's vacuously true that all sentences are false in all proper substructures of $M$. As Eric Wofsey commented this can trivially be done in an infinite language. For a finite language example, consider $\mathbb{N}$ with $0$ and successor.