MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Let $\mathcal{M}$ be an infinite model of a first-order language, and for each $n$, let $\mathcal{B}_n$ be the algebra of definable sets of $n$-tuples from $|\mathcal{M}|$.

  1. Given $\{\mathcal{B}_n\mid _{n\in\mathbb{N}}\}$ (and, obviously, $|\mathcal{M}|$, is it possible to describe explicitly some $\mathcal{M}'$ whose definable sets are $\{\mathcal{B}_n\}$? (I think the question makes the most sense assuming that the language itself is unknown, so I'm asking if there's a natural way to invent a language and a model which gives the chosen definable sets. Obviously there is such a model, namely the original one, but I'm open minded about what it would mean to construct $\mathcal{M}'$ "explicitly".)

  2. How well do the definable sets "pin down" the model? Need two models with the same definable sets in the same language be elementarily equivalent? Can anything be said about the relationship between two different models of different languages, but with the same definable sets?

  3. There are some obvious restrictions on the $\mathcal{B}_n$: $\mathcal{B}_n\times\mathcal{B}_m\subseteq\mathcal{B}_{n+ m}$, each $\mathcal{B}_n$ is a Boolean algebra, $\mathcal{B}_m$ contains all projections from $\mathcal{B}_{m+n}$. Are there any others?

share|cite|improve this question
up vote 5 down vote accepted

The answer to the first part of #2 is no. In a language with (just) one binary relation, let the two models be $\omega$ with the relation interpreted as $<$ in one model and as $>$ in the other.

For #1, the canonical choice would be to take all the relations from the $\mathcal{B}_n$'s as the interpretations of relation symbols. Presumably, you want a smaller language, but I don't see any good criterion for what would be small enough.

For #3, I think the restrictions you list are all you need (provided "Boolean algebra" means subalgebra of the power set of $|\mathcal{M}|^n$ for the appropriate $n$). They seem to be exactly what you need to do quantifier elimination for the language and interpretation I suggested for #1.

share|cite|improve this answer

I like this question very much.

For 1, you can add a relation symbol for every set in the family, and this will of course suffice to define every set in the family, while creating no additional definable sets, since giving a name to a definable set is clearly conservative.

For 2, two models giving rise to the same family of definable sets need not be elementarily equivalent. For example, you can turn an order upside-down or use the complement of a relation to get the same definable sets, but this can strongly affect the theory.

For 3, the properties you list do not suffice, since you need to be able to permute variables within any one dimension, since definable sets are closed under that operation. Also, you will need to close under composition of relations and substitution. For example, if you have the graph of a function that is definable, then you will need to have all substitution instances of this function into definable sets. Finally, you will need to add the diagonal $\Delta=\{(x,x)\mid x\in M\}$, which is always a definable binary relation (if one assumes as usual that $=$ is included in all first order languages). This last property does not follow from your properties, since one could double every point while preserving your properties. Perhaps these additional requirements suffice to carry out Andreas' elimination of quantifiers idea...

share|cite|improve this answer
Thanks for the corrections about #3. You also need to be able to add dummy variables, or did you intend "substitution" to include that? On the other hand, I think you can do without composition of relations, since it can be defined using existential quantification (i.e., projection, which was already included in the statement of #3) and intersection. – Andreas Blass Sep 28 '10 at 14:01
I think you are right about composition, and I guess dummy variables follow from the requirement that $B_n\times B_m\subset B_{n+m}$. So what is the best minimal list of properties? Is it what was listed plus the diagonal and permutations of variables? – Joel David Hamkins Sep 28 '10 at 14:07

Your Answer


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.