0

Let $L$ be any language for predicate logic and $S$ be any set of sentences in $L$. Prove that $S$ is satisfiable iff it has an infinite model.

So I know that a set of sentences is only satisfiable if every finite subset is also satisfiable. I don't know where to go from there though, because I don't think I can apply Skolem-L$\ddot{o}$wenheim Theorem, since the set isn't necessarily countable?

Tim
  • 67
  • 3
    Well this isnt true. – Rene Schipperus Jan 07 '18 at 22:31
  • 1
    What do you call "language for predicate logic? Is it the same as a first order language (refer to https://en.m.wikipedia.org/wiki/First-order_logic). If yes, does it (as commonly we take) contain equality? If yes, then the claim does not hold (e.g. $(\exists x)(\forall y)(y=x)$ cannot be satisfied by an infinite model). –  Jan 07 '18 at 22:34
  • I think it is the same as a first-order language. My professor did specifically mention that it wouldn't hold under equality. But that it could hold otherwise. – Tim Jan 07 '18 at 23:45

1 Answers1

0

Requiring equality makes the claim trivially false, but it should be true in FOL without equality.

Then, from any $M\models T$ we can obtain $N\models T$ with the domain equal to M plus one fresh element n, by choosing any $m\in M$ and defining all relations in N with n as they are in M with m, i.e., for each relation symbol $R: R^N(...n...) \iff R^M(...m...)$, ("..." contain unchanged elements of M, if any; we replace each number of occurrences of m by n, e.g., from $R^M(m,m)$ we would obtain $R^N(n,n)$, $R^N(m,n)$ and $R^N(n,m)$, etc.) N is then elementary extension of M, so $N\models T$.

If M is finite, we repeat this $\omega$ times, obtaining in the limit an infinite elementary extension L of M, i.e., $L\models T$. Does this argument work?

Michal
  • 36