I need to learn about Razborov's "flag algebras" (see http://bit.ly/1u1a1NB) to solve a problem about graphs. Flag algebras are a very general new algebraic tool for studying combinatorial structures. The theory of flag algebras uses some elementary model theory in its definition which is something I have not encountered before (in fact I have not taken any classes in formal logic beyond the first-year undergrad stuff). I've read through the first few sections of Marker's "Model Theory: An Introduction" (http://amzn.to/1zGuyKq) and I have easily understood the definitions and general approach; in particular, I think I only really need to understand the general concepts of languages $\mathcal{L}$, $\mathcal{L}$-structures, embeddings of $\mathcal{L}$-structures and some general facts about $\mathcal{L}$-theories and models, all of which seems fine.

Reading the beginning of Razborov's paper [p4], though, I found some terms that I have not seen defined which I'd like to clear up. In particular, he writes

"Let $T$ be a universal first-order theory with equality in a language $\mathcal{L}$ containing only predicate symbols; we assume that $T$ has infinite models. Our assumptions imply that every set of elements of a model of $T$ induces a model of $T$, and that $T$ has at least one finite model of every given size."

I have two essential questions:

  • what does "universal" mean in this context?
  • why do the assumptions imply that any subset of a model of $T$ induces a model of $T$?

An universal theory is a theory axiomatised by a set of universal sentences, i.e. of the form $\forall x_1\forall x_2\ldots\forall x_n \varphi(x_1,\ldots,x_n)$ (where $\varphi$ is quantifier-free).

That, in addition to absence of function symbols or constants trivially implies that for every model of $T$, any nonempty subset (with inherited structure) is also a model of $T$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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