1
$\begingroup$

Let $\mathcal{L}$ be a first order language and $M$ be a finite $\mathcal{L}$-structure. I want to know which relations $R\subseteq M^n$ are definable in $\mathcal{L}$? If I apply the well-known Svenonius's theorem, I can conclude that $R$ is definable iff it is preserved by every $L$-automorphism of $M$. Now, I want to know can I use Svenonius's theorem for finite structures or it concerns just the infinite case (I have only two references for Svenonius theorem, the book of Piozat and this note in ArXiv. The first does not require any condition on $M$, but the second assumes that $M$ is countable. I have a minimum knowledge of model theory and I am not able to analyze the proofs. I just want to apply this theorem in group theory. So I need to be sure if I can apply it for finite groups or not).

$\endgroup$
6
  • $\begingroup$ Svenonius theorem in the form you stated it does hold for finite structures (and in fact does not hold for infinite structures, one has to consider elementary extensions). However, the finite case amounts to a trivial exercise, so it looks kind of funny to call it the Svenonius theorem (and may also be part of the reason why the actual theorem may be stated in some sources only for infinite models). $\endgroup$ Jul 16, 2014 at 14:56
  • $\begingroup$ Anyway, finite structures are countable, so I don't see what the problem is in the first place. $\endgroup$ Jul 16, 2014 at 14:59
  • $\begingroup$ @EmilJeřábek: thank you, I supposed "countable" in that reference means "infinite countable". Now, how can I prove it directly for finite structures without using Svenonius theorem? $\endgroup$
    – Sh.M1972
    Jul 16, 2014 at 15:01
  • $\begingroup$ For example, let $a_1,\dots,a_n$ be an enumeration of the universe of the model, and take formula A(x_1,...,x_k) (where k is the arity of your relation R) saying "there exist $u_1,\dots,u_n$ that satisfy the diagram of the model when u_i stands for a_i, and such that $\vec x$ equals one of the tuples of the u_i's corresponding to a tuple of a_i's in R". (Sorry, writing this properly in TeX is a royal PITA on the Android keyboard.) The invariance of R easily implies that it is defined by this formula. $\endgroup$ Jul 16, 2014 at 15:18
  • $\begingroup$ @EmilJeřábek: I will try to understand and complete it. Thank you again. I need first to learn the meaning of some phrases like "diagram of the model". After that, I will be able to write a compact proof. Finally I must try to translate every thing to group theory in order that I have a "model-theory"-free argument. $\endgroup$
    – Sh.M1972
    Jul 16, 2014 at 15:25

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.