1
$\begingroup$

I'm not sure about this problem. I should determine if this if true or false:

If L is languege $L-$sentence $\phi$ is satisfiable in every finite $L-$structure, is it satisfible also in every infinite $L-$structure?

I would say that's true. In my opinion, from the Compactness theorem it holds that if $\phi$ is satisfiable in every finite $L-$structure, it has to be satisfiable in any infinite $L-$structure. However, I'm not sure why it has to be satisfiable in every.

I've tried to prove it like that: Let ve have $\neg \phi$ and let suppose it has some infinite model (that means there exist some $L-$structure in which $\neg \phi$ is satisfiable). Then, according to the Compactness theorem, there has to exist some finite subset of our $L-$structure in which $\neg \phi$ is satisfiable, which is a contradiction.

Is it possible to do it like that or am I wrong in some point? Because I'm not really sure about it, so I'm afraid I'm doing some mistake without knowing it...

$\endgroup$
3
  • $\begingroup$ I do not know what is meant by satisfiable in every (finite) $L$-structure. In any specific $L$-structure, $\phi$ is either true or false. $\endgroup$
    – André Nicolas
    Jun 11, 2015 at 6:32
  • $\begingroup$ Yes, that's how I've understood the question. It was really formulated like this, however, I supposed that $\phi$ is satisfiable in some $L-$structure if it's true in it. $\endgroup$
    – kilpikonna
    Jun 11, 2015 at 6:36
  • $\begingroup$ Compactness tells us that, if $\phi$ is true in finite models of arbitrarily large cardinality, then $\{\phi\}\cup\{\text{there are at least } $n$\text{ distinct elements} \mid n\in\mathbb{N}\}$ is consistent, so there exists an infinite model in which $\phi$ is true. You are using a (false) partial converse, that if $\psi = \neg\phi$ is true in some infinite model, then it is true in some finite model. Lots of theories have infinite models but no finite models—algebraically closed fields, for example. $\endgroup$
    – Andrew Dudzik
    Jun 11, 2015 at 7:14

1 Answer 1

Reset to default
1
$\begingroup$

There are sentences $\phi$ that are true in every finite $L$-structure but such that there are infinite $L$-structures in which $\phi$ is not true.

Here is one example. Let $L$ have a single binary predicate symbol $\lt$. Let $\alpha$ be the conjunction of all the sentences that together say that $\lt$ is a total order. Let $\beta$ be the sentence that says there is a smallest element under $\lt$, and let $\phi$ be the sentence $(\alpha\to\beta)$.

Then $\phi$ is true in every finite $L$-structure. However, there are infinite totally ordered sets that do not have a least element, so there are infinite $L$-structures in which $\phi$ is false.

Remark: I am puzzled by the phrase "satisfiable in every (finite) $L$-structure. Given any $L$-structure $\mathbb{M}$, any sentence is either true of false in $\mathbb{M}$.

$\endgroup$
4
  • $\begingroup$ Yes, that makes a sense... thank you. However, I still don't know why my orgumentation was wrong, but I'll think about it. Thank you so much! $\endgroup$
    – kilpikonna
    Jun 11, 2015 at 7:03
  • $\begingroup$ You are welcome. Compactness tells us in particular that if $\phi$ has models of every finite cardinality, or even just of arbitrarily large finite cardinality, then $\phi$ has an infinite model. But there may well be infinite structures in which $\phi$ is false. $\endgroup$
    – André Nicolas
    Jun 11, 2015 at 7:09
  • $\begingroup$ That's the reason I wasn't sure about it. I thought that there is an equivalence, that if $\phi$ has an infinite model, then there must exists any finite subset of this model for $\phi$. So this implication doesn't hold? $\endgroup$
    – kilpikonna
    Jun 11, 2015 at 7:13
  • $\begingroup$ It is not true that if $\mathbb{M}$ is an infinite model, then some finite substructure of $\mathbb{M}$ is a model. There may not even be a finite substructure, $\endgroup$
    – André Nicolas
    Jun 11, 2015 at 7:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .