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 M M , since M M M is alwaays a substructure of itself). And the problem can be solved vacuously by considering a structure M M 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 } \{P,f\} { P , f } , where P P P is a unary relation symbol and f f f is a unary function symbol. Let M = N M = \mathbb{N} M = N , where P M P^M P M holds only of 0 0 0 and f M f^M f M is the successor function f M ( n ) = n + 1 f^M(n) = n+1 f M ( n ) = n + 1 . The substructures of M M M are of the form { k , k + 1 , k + 2 , … } \{k,k+1,k+2,\dots\} { k , k + 1 , k + 2 , … } for any k k k . Consider the sent...