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

Answer :

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$).

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.