2
$\begingroup$

I am reading Enderton's book, A mathematical introduction to logic, beggining of the section $2.6$. I have two following question (page 147).

First question

He says that some sentences have only infinite models and the negation of such a sentence is true in every finite structure.

  • Is it there any proof of this statement? Or, what is the intuition behind this statement?

Second question

(Theorem 26A) If a set $\Sigma$ of sentences has arbitrarily large finite models, then it has an infinite model.

For a set $\Sigma$ of sentences, let $\text{Mod } \Sigma$ be the class of all models of $\Sigma$.

A class $K$ of structures for our language is an elementary class (EC) iff $K = \text{Mod } \tau$ for some sentence $\tau$.

A class $K$ of structures for our language is an elementary class in the wider sence ($EC_\Delta$) iff $K = \text{Mod } \Sigma$ for some set $\Sigma$ of sentences.

(Corollary 26B)

  1. The class of all finite structures (for a fixed language) is not $EC_\Delta$.
  2. The class of all infinite structures is not $EC$.

Proof: 1) follows immediately from theorem 26A. 2) [...]

We consider some fixed language and the class $K$ of all finite structure of the language (i.e., all structure of the language such that the domain of the structure is finite). By the definition we need to show that there is no set $\Sigma$ of sentences such that $K = \text{Mod }\Sigma$.

How can apply Theorem 26A to prove this part of the corollary?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

For the first question, the point is that there are basic algebraic/combinatorial phenomena which can only occur in infinite structures. The simplest example is an injective non-surjective function: in the language with a unary function symbol $f$, the sentence $$[\forall x, y(x\not=y\implies f(x)\not=f(y))]\wedge[\exists x\forall y(f(y)\not=x)]$$ does have models but does not have any finite models. Another easy example is linear orders without endpoints: in the language with a binary relation symbol $R$, the sentence asserting that $R$ is a linear order with no greatest (or least, if you prefer) element has only infinite models.

(There are also surprisingly deep examples, e.g. Wedderburn's little theorem says that the sentence saying "the universe is a non-commutative division ring" has only infinite models.)

For the second question, this is just a direct application of the theorem. Let $\mathbb{K}$ be the class of all finite structures (in some fixed language). If $\mathbb{K}$ were $EC_\Delta$, then there would be some set of sentences $\Gamma$ such that $\mathbb{K}$ is exactly the class of all models of $\Gamma$. But:

  • Do you see why such a $\Gamma$ must have arbitrarily large finite models? (HINT: how large can elements of $\mathbb{K}$ be?)

  • Do you see why such a $\Gamma$ cannot have infinite models? (HINT: how large can elements of $\mathbb{K}$ not be?)

This gives a contradiction, so our assumption that $\mathbb{K}$ was $EC_\Delta$ must have been wrong.

$\endgroup$
4
  • 1
    $\begingroup$ Thank You. 1) For the sake of the contradiction suppose that $\Gamma$ has no arbitrarily large finite models. So there is $k \in \mathbb{N}$ such that a model of $\Gamma$ has not size $k$, but then $\text{Mod } \Gamma \neq \mathbb{K}$, since $\mathbb{K}$ is the class of all finite models (including of size $k$). 2) For the sake of the contradiction suppose that $\Gamma$ has an infinite model. But, then $\text{Mod } \Gamma \neq \mathbb{K}$ since $\mathbb{K}$ is class of finite models, i.e., does no contain a model of infinite domain. $\endgroup$
    – Kapur
    Aug 29, 2019 at 18:54
  • $\begingroup$ After that, we can on the first one apply Theorem 26A that give a contradiction. It is okay? $\endgroup$
    – Kapur
    Aug 29, 2019 at 18:54
  • $\begingroup$ @Kapur Yes, that's right. Although I'd say "$\Gamma$ does not have arbitrarily large finite models" rather than "$\Gamma$ has no arbitrarily large finite models" - the latter suggests that "arbitrarily large" is a property of individual models, whereas what's actually going on is we're talking about sets of models. But you used the correct formal notion, so that's just a superficial comment. $\endgroup$
    – Noah Schweber
    Aug 29, 2019 at 18:56
  • $\begingroup$ I have one more question. Enderton gives a proof to the second part of Corollary 26B "The class of all infinite structures is not $EC$." Here is the proof: "If the class of all infinite structures 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 understand what he wrote, but I do not see how it implies that $\text{Mod }\tau$ is not $EC$. I just see that $\text{Mod }\neg\tau$ is not $EC$. $\endgroup$
    – Kapur
    Aug 30, 2019 at 9:49

You must log in to answer this question.

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