Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is 2.3.8(b) in Hodges' A Shorter Model Theory, p.43. (It's also in his original Model Theory on p. 47). I'll cite the problem, follow it by definitions of key terms, and then explain why the statement to prove feels false to me.

L is a first order language, with finitely many symbols. Show that there is a quantifier-free type such that a structure $A$ is locally finite iff it omits the type.

[Definitions: a locally finite structure is a structure where every finite subset generates a finite substructure. An $n$-type is a set of formulas in variables $x_1,\dots,x_n$. A type is an $n$-type for some positive integer $n$. A type is omitted by a structure if there's no way of plugging in the variables with elements of the structure so that all the formulas are simultaneously true.]

The reason it feels false is that I can construct, for any $n$, a structure of a language with a single binary function symbol such that every $n$ elements generates a finite substructure but where $n+1$ elements can generate an infinite substructure. It seems to me that an $n$-type shouldn't be able to distinguish between such a structure and a locally finite one. I've checked the errata and found nothing, so maybe my intuition is just off.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

This is a mistake in Hodges. As you say, for any $n>0$, it's possible to construct a structure $B_n=<U,f>$, where $f$ is a binary function symbol, such that every $n$ elements of $B_n$ generate a finite substructure but there are $n+1$ elements of $B_n$ which generate an infinite substructure. For example, you can take $U={\mathbb Z_{\ge 0}}$ and $$f(a,b)=a+1,\ \ \ \ \ \hbox{if $b \equiv a+1 \ \ ({\rm mod}\ n+1)$},$$ $$f(a,b)=a, \ \ \ \ \hbox{otherwise.}$$ $f$ has been defined so that it can generate no more elements than the unary successor function ($S(x)=x+1$), but it may generate fewer, as in order to generate an element which equals $S(a)$, the residue class of $S(a)$ modulo $n+1$ must already be occupied. Now, the elements $\{0,1,2,\ldots,n\}$ generate all of $U$ under $S$ and occupy all residue classes modulo $n+1$, so they generate all of $U$ under $f$. However, any $n$-element set $V$ must omit some residue class modulo $n+1$. Then, starting with some $a\in V$ as the first argument of $f$, we can only generate some proper subset of $$T_a:=\{a, S(a), S^2(a), \ldots, S^n(a)\},$$ since before we can generate all of $T_a$, we will come to the unfilled residue class, which cannot be filled using $f$. Therefore, any $n$-element set $V$ can generate only a finite substructure of $B_n$.

Now, taking the language $L$ to be $\{f\}$, if there were a quantifier-free type $T({\bf x})$ such that an $L$-structure $A$ was locally finite iff it omitted $T({\bf x})$, $T({\bf x})$ would have to be an $m$-type for some $m$. Then since $B_m$ is not locally finite, it must realize $T({\bf x})$, i.e., there are elements $a_1$, $\ldots$, $a_m$ in $B_m$ such that $B_m \vDash T(a_1,\ldots,a_m)$. But since $T({\bf x})$ is quantifier-free, then we also have $C \vDash T(a_1,\ldots,a_m)$, where $C$ is the finite substructure of $B_m$ generated by $\{a_1,\ldots,a_m\}$. Therefore, $C$ realizes $T({\bf x})$. Since $C$ is finite, it is locally finite, so this is a contradiction. Therefore, the statement cannot be proved.

In A shorter model theory, the exercise reads:

Let $L$ be a first-order language. An $L$-structure $A$ is said to be locally finite if every finitely generated substructure of $A$ is finite. (a) Show that there is a set $\Omega$ of quantifier-free types (i.e. types consisting of quantifier-free formulas) such that for every $L$-structure $A$, $A$ is locally finite if and only if $A$ omits every type in $\Omega$. (b) Show that if $L$ has finite signature, then we can choose the set $\Omega$ in (a) to consist of a single type.

To fix it, change the last sentence to:

(b) Show that if $L$ has finite signature, then we can choose the set $\Omega$ in (a) to consist of a single $n$-type for each $n$.

The exercise should then be doable.

share|improve this answer
    
Thank you. That is precisely the way to make my intuition on that issue rigorous. –  user25327 Feb 23 '12 at 4:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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