4
$\begingroup$

I almost finish the section 2.6 in Enderton's A mathematical introduction to logic, but I still do not understand some thing.

(The first three question are closely related, so I hope that it does not a problem that I ask several questions in one topic.)

(1) Finitely valid

At the beginning of the subsection Finite Models, he says

Some sentences have only infinite models, for example, the sentence saying that $<$ is an ordering with no largest element. The negation of such a sentence is finitely valid, that is, it is true in every finite structure.

  • a sentence $\sigma$ is finitely valid iff $\sigma$ is true in every finite structure

If a sentence $\sigma$ has only infinite models (but not necessarily $\sigma$ is true in every infinite model, i.e., there can be some infinite structure such that the structure is not model of $\sigma$), then the negation of $\sigma$ is finitely valid. Am I right? Moreover, it is here some proof? (how can I be sure that there is no infinite models of $\sigma$)

Conversely, let $\sigma$ be a finitely valid sentence. Clearly the negation of $\sigma$ cannot be true in any finite structure (but necessarily $\sigma$ is true in every infinite structure). Am I right?

(2) The class of all infinite structure is not $EC$ (second part of Corrolary 26B)

  • a class of structures $K$ is in $EC$ iff there is some setence $\sigma$ such that $\text{Mod }\sigma = K$

Here is the proof given by Enderton:

If the class of all infinite structure is $\text{Mod }\tau$, then the class of all finite structures is $\text{Mod }\neg\tau$. But this class isn't even $EC_\Delta$, much less $EC$.

I accept that what he wrote, but I think that to finish the proof we must show that $\text{Mod }\tau \in EC$, but I do not see how it follows from that $\text{Mod }\neg\tau$ is not in $EC$. I think that something missing, but I am not able to finish the proof by myself.

(3) Corollary 26E

Assume the language is finite, and let $\Phi$ be the set of setences true in every finite structure. Then its complement, $\overline \Phi$, is effectively enumerable.

Proof. For a sentence $\sigma$, $$\sigma \in \overline \Phi \Leftrightarrow (\neg\sigma) \text{ has a finite model.}$$ [...]

In other words, $\Phi$ is a set of finitely valid sentences. Thus its complement, $\overline \Phi$, is the set of sentences $\sigma$ such that $\sigma$ is not true in some finite structure. It does not imply that $\sigma$ has only infinite models ($\sigma$ can be true in some finite structure, but not in all finite structures). So, we cannot use the facts from (1). How can I get the equivalence?

$\endgroup$
5
$\begingroup$
  1. I cannot understand what you are asking and saying. If a sentence is only true in infinite models then it is false in every finite model, so its negation is true in every finite model. That's it.
  2. For any sentence $\sigma$ whatsoever $\operatorname{Mod}(\sigma)\in EC$... this is the definition of $EC.$ So in particular $\operatorname{Mod}(\lnot \tau)\in EC.$ It doesn't follow from this that $\operatorname{Mod}(\lnot \tau)\notin EC$... that follows from the first part of the theorem where they show the class of finite structures is not in EC. This produces a contradiction that proves that a $\tau$ with the assumed properties can't exist.
  3. This is a corollary to a theorem immediately preceding that shows that the set of all sentences that have a finite model is effectively enumerable (as you have said, $\bar\Phi$ is just the set of all sentences whose negations have a finite model). This in turn follows from a couple paragraphs up where they show that for any $n$, it is decidable if a sentence has a model of size $n.$ (All of this assuming a finite language.)
$\endgroup$
  • $\begingroup$ Thank you, I accepted 2) and 3). I also accepted 1), but I have one more question: you said "If a sentence is only true in infinite models then it is false in every finite model, so its negation is true in every finite model", it does not exclude that its negation can be true in some infinite models, am I right? $\endgroup$ – Kapur Sep 8 '19 at 8:06
  • $\begingroup$ @Kapur Yes, if something is "only true in infinite models", then it could be true in all infinite models, false in all infinite models (in which case it isn't true in any model), or true in some infinite models and false in others. $\endgroup$ – spaceisdarkgreen Sep 8 '19 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.