(a), (b) Consider the sentence $\sigma_{n}=\forall xPxx\wedge\exists v_{1}\ldots\exists v_{n}\wedge_{1\le i<j\le n}\neg Pv_{i}v_{j}$ . Every model $\mathfrak{A}$ of $\sigma$ is such that a) for every $d\in|\mathfrak{A}|$ , $<d,d>\in P^{\mathfrak{A}}$ , and b) there are $d_{1},\ldots,d_{n}\in|\mathfrak{A}|$ such that for $1\le i<j\le n$ , $<d_{i},d_{j}>\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 ($<a,d>\in P^{\mathfrak{A};a}$ iff $<b,d>\in P$ , and $<d,a>\in P^{\mathfrak{A};a}$ iff $<d,b>\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”.