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.

This is (a slight paraphrase) of question 1.3.14 in Chang and Keisler's Model Theory book.

"Show that for each natural number $n$, there is a language $L_n$ and finite model $M_n$ of $L$ such that $M_n$ has precisely $n$ undefinable elements."

Here, an element $x\in M$ is definable if there is a (first order) formula in $L$, called $\phi$, such that $x$ is the unique element of $M$ satisfying $\phi$. Of course, "undefinable" means "not definable".

It is starred, indicating that it is more difficult than a standard problem in that book.

Chang and Keisler remark that $n=1$ is the only difficult case. In that spirit, here is the proof for all $n\neq 1$.

Let $L_n$ have a single 2 place predicate symbol (I'm thinking of $L_n = \{ < \}$). Let $M_n$ be the partial order with minimum a and with elements $b_1,...,b_{n}$ with $a < b_i$ for all $i$ and the $b_i$ pairwise incomparable.

First note that a is definable: it uniquely satisfies $\phi(x) =$ for all y, $x\leq y$.

Now, if $n =0$, there are no $b_i$, and hence in this model, we have 0 undefinable elements.

If $n > 1$, then I claim that all the $b_i$ are undefinable. The short answer is that any permutation of the $b_i$ can be extended to a unique isomorphism of $M_n$. Hence, for any formula $\phi$, we have $\phi(b_i)$ iff $\phi(b_j)$ for all $b_j$. Thus, no $\phi$ can single out any particular $b_i$, so each $b_i$ is undefinable.

This proof fails completely for $n=1$, for then $b_1$ is the unique element that satisfies "b_1 is not a". Or more in the spirit of first order logic, $b_1$ is the unique element satisfying $\phi(x) =$ there is a $y$ such that for all $z$, $y< z$ and $x$ is not equal to $y$." Incidentally, this proves that any such model that works for $n=1$ must have at least 3 elements.

So, my question is:

What is an example of a language with finite model having precisely one undefinable element? Is the smallest cardinality of such a model known?

Thanks in advance!

share|improve this question

2 Answers 2

up vote 12 down vote accepted

If your languages necessarily have the = relation, which is a common assumption, then the case n=1 is impossible in a finite model. The reason is that if a model $M$ has $k$ elements $x_1$, $x_2$, ... $x_k$ for finite $k\gt 1$ and each $x_i$ is defined by $\varphi_i(x)$ for $i\lt k$, then the remaining element $x_k$ is defined by the formula $\neg\varphi_1(x)\wedge\cdots\wedge \neg\varphi_{k-1}(x)$. If $M$ has only one element, then it is defined by the formula $x=x$.

But if we do not insist that $=$ is in the language, then let $L$ be the empty language, having no relations at all. In this case, there are no atomic formulas and hence no well-formed formulas to define elements, so a one-point model has exactly one undefinable element.

If we allow infinite models, then we can easily arrange to have exactly one undefinable element, even in a language with $=$. For example, consider the lanuage with infinitely many constant symbols, and have a model where all these constants are interpreted by different elements, and there is one extra un-named object. That extra object will be the only non-definable element, even when $=$ is in the language.

share|improve this answer
    
Thank you for your answer as well! –  Jason DeVito Sep 29 '10 at 17:07

You can't have equality as a relation in the language that is interpreted as equality in the model, otherwise you can define the undefinable element as that (one) which is not equal to any of the definable ones. Most languages in common use have equality so it is hard to think of a natural example that describes, e.g., algebraic structures or combinatorial objects.

share|improve this answer
    
Thank you for your answer! –  Jason DeVito Sep 29 '10 at 17:06

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.