Reconstructing a model from its definable sets

Question

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?

Answer 1

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.

Answer 2

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...