« Section 2.2: Problem 28 Solution

# 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 $P$ . 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 $\sigma_{n}=\forall xPxx\wedge\exists v_{1}\ldots\exists v_{n}\wedge_{1\le i . Every model $\mathfrak{A}$ of $\sigma$ is such that a) for every $d\in|\mathfrak{A}|$ , $\in P^{\mathfrak{A}}$ , and b) there are $d_{1},\ldots,d_{n}\in|\mathfrak{A}|$ such that for $1\le i , $\notin P$ , implying $d_{i}\neq d_{j}$ . Then, $\sigma_{n}$ has no model of size $n-1$ 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 $\sigma$ in a language without the equality symbol of size $n$ , then there is a model of size $n+1$ . Indeed, having a model $\mathfrak{A}$ of $\sigma$ of size $n$ , we add a new element $a$ to its universe, and consider a function $h$ from $|\mathfrak{A}|;a$ onto $|\mathfrak{A}|$ which is the identity for all elements of $|\mathfrak{A}|$ and assigns any element $b$ to $a$ . Then, by choosing $P^{\mathfrak{B}}$ appropriately ($\in P^{\mathfrak{A};a}$ iff $\in P$ , and $\in P^{\mathfrak{A};a}$ iff $\in P$ ), $h$ is a homomorphism of $\mathfrak{A};a$ onto $\mathfrak{A}$ , implying, by the Homomorphism Theorem, part (d), that $\mathfrak{A}$ and $\mathfrak{A};a$ are elementarily equivalent, and $\sigma$ is true in $\mathfrak{A};a$ . Therefore, the answer is no, in (a) we cannot replace “or less” by “or more”.