Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Most of the applications of Finite Model Theory I have seen are in graphs, using FMT one can prove that certain properties of finite graphs are not FO definable. I am interested in similar kind of applications of FMT in finite algebraic structures, namely in finite fields or finite groups? Are their properties of finite fields or groups which are not FO definable and can be proved using FMT? Reference to any book or research paper would be highly appreciated.

share|cite|improve this question
I am not sure what you are asking. Can you be more specific about the type of structure you are interested in for undefinability results? E.g. are you asking about undefinability in models of the theory of ordered fields with characteristic $p$? If so why not the usual model theory of finite fields answer your question? Can you give an example of the kind of result you are interested in (the result doesn't need to be true, I just want to know what kind of results you are looking for)? – Kaveh Feb 4 '13 at 7:39
Are you familiar with universal algebra? There are lots of results there about properties of algebras. Analogous to universal algebra providing an axiomatic view of algebraic structures, one can view finite-model theory as providing an axiomatic view on combinatorial structures. – Vijay D Feb 5 '13 at 14:36
@Kaveh: Using EF-game or Hanf locality we can prove connectivity of a graph is not FO definable. I was interested whether using similar ideas we can prove FO definability of certain properties of finite fields or groups; Eg:"Evenness of the characteristic of a finite field is not FO definable" or "Cyclicity of a finite group (i.e checking whether a finite group is cyclic or not) is not FO definable" etc. Also I should say that I dont know General Model Theory; I have taken a course on FMT this semester and I am a mathematics student. – pritam Feb 6 '13 at 11:10

Your Answer


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

Browse other questions tagged or ask your own question.