4
$\begingroup$

Let $C$ be an axiomatisable class of structures for some given first-order signature, i.e. there is a set $T$ of sentences whose models are exactly the members of $C$.

Apparently it follows from the compactness theorem that: If $C$ contains arbitrarily large finite structures then it must contain an infinite structure.

Can someone explain this result? The compactness theorem tells me that $T$ has a model if each finite subset of $T$ has a model but I don't see how this relates to the size of structures in $C$.

$\endgroup$
2
  • $\begingroup$ @Taroccoesbrocco: In your edits, you need to put "the" before "compactness theorem". It is usual to say something follows "from compactness" (no "the"), but this means it follows from the compactness theorem $\endgroup$ May 15, 2018 at 0:53
  • $\begingroup$ @CarlMummert - Thank you! $\endgroup$ May 15, 2018 at 4:56

2 Answers 2

6
$\begingroup$

Hint: $\phi_3 \equiv \exists x\exists y\exists z(x \neq y) \land (x \neq z) \land (y \neq z)$ is a sentence that only holds in a structure with at least three elements. Using this pattern, you can design a sequence of sentences $\phi_3, \phi_4 \ldots$ such that $\phi_n$ only holds in a structure with at least $n$ elements. Then any finite subset of $T' = T \cup\{\phi_3, \phi_4, \ldots\}$ is consistent (because you are given that $C$ contains a model for $T$ that is also a model for $\phi_n$ for arbitrarily large $n$). Compactness gives you a model for $T'$ and that model is then an infinite model for $T$.

$\endgroup$
1
  • 1
    $\begingroup$ Nice, no expansion of the language. $\endgroup$
    – BrianO
    Feb 15, 2016 at 0:48
4
$\begingroup$

If you adjoin infinitely many constants $c_n$ to the language of $T$, and add sentences $c_i \ne c_j, i \ne j$ to $T$, obtaining a new theory $T'$, then every finite subset of $T'$ has a model: Given finite $T'_0\subseteq T'$, let $N$ be the number of distinct $c_n$ appearing in $T'_0$. There is $M\in C$ of size $\ge N$ which is a model of $T'_0\cap T$. Clearly we can assign the $c_n$ occurring in $T'_0$ to distinct elements of $M$, and expand the signature of $M$ to a model $M'$ that includes those elements as interpretations of the $c_n$.

By compactness, $T'$ has a model $M' = (U, ..., (a_n)_{n\in\Bbb N})$. Because $M'$ models all the sentences $c_i\ne c_j$, all the $a_n$ are distinct, so $U$ is infinite. But now the reduct $M = (U, ...)$ is an infinite model of $T$, so $M\in C$.

$\endgroup$

You must log in to answer this question.

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