For example, if a sentence is satisfiable, is it possible that it has no models of size, say, 4 or greater? I'm thinking it's not possible, but I can't quite see why.
Asked
Active
Viewed 266 times
3
-
May be related: https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem – Mar 11 '17 at 14:34
2 Answers
7
Totally!
How about the sentence $$"\exists x\exists y\exists z\exists w\forall u(u=x\vee u=y\vee u=z\vee u=w)"?$$ This sentence is true in exactly the models of size at most $4$.
In general, any finite set of finite numbers can be the set of sizes of models of some sentence (exercise, using the example above). However, once we move to infinite models, the picture changes completely: putting together the compactness theorem and the downward Löwenheim-Skolem theorem gives us the full Löwenheim-Skolem theorem - that if $\varphi$ has an infinite model, it has models of every infinite cardinality.
(Actually the full Löwenheim-Skolem theorem is broader still - it applies to theories, not just sentences.)
In a comment, you also asked about languages without equality. In this case, the answer is negative. It's not hard to show that every model of a sentence without equality can be "blown up" - replacing each element with a set of indistinguishable elements. This isn't quite trivial, but it's not too hard and is a good exercise.
hmakholm left over Monica
- 286,031
Noah Schweber
- 245,398
-
@HughMungus: Without equality you can always pick an element and add however many new elements you want that behave exactly like your chosen one. First-order statements will then not be able to distinguish between them. – hmakholm left over Monica Mar 11 '17 at 14:41
4
If it has an infinite model, then it has models of all larger cardinalities (Löwenheim-Skolem). But we can specify bounded-size finite models using a clause of the following form: $$(\exists a, b)(\forall y)(y = a \vee y = b)$$
Patrick Stevens
- 36,135