Section 2.2: Problem 29-A Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
(Addiotional) Assume the only parameters in the language are the quantifier symbol and a two-place predicate symbol . And assume the language does not have the equality symbol.
(a) Find a sentence that is satisfiable, but has no models of size 3 or less.
(b) Does part (a) generalize to numbers other than 3?
(c) In part (a), can we replace "or less" by "or more" and still find a sentence?
(a), (b) Consider the sentence . Every model of is such that a) for every , , and b) there are such that for , , implying . Then, has no model of size or less.
(c) This part is related to the remark of Exercise 22 (upward Löwenheim–Skolem theorem without equality), which implies that if there is a model of a sentence in a language without the equality symbol of size , then there is a model of size . Indeed, having a model of of size , we add a new element to its universe, and consider a function from onto which is the identity for all elements of and assigns any element to . Then, by choosing appropriately ( iff , and iff ), is a homomorphism of onto , implying, by the Homomorphism Theorem, part (d), that and are elementarily equivalent, and is true in . Therefore, the answer is no, in (a) we cannot replace “or less” by “or more”.