MathOverflow is a question and answer site for professional mathematicians. 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

(originally posted at MSE as Same same but different: Coextensive relations in model and set theory, slightly modified)

The official definition of a structure in model theory in its presumably most compact form is (for simplicity's sake without individual constants and functions):

Def. 1 A structure is a 3-tuple of sets $\langle \alpha, I, A\rangle$ such that:

  1. $\alpha$ and $I$ are functions
  2. $\text{dom}(\alpha) = \text{dom}(I)$
  3. $\alpha(R) \in \mathbb{N}$ for all $R \in \text{dom}(\alpha)$
  4. $I(R) \subseteq A^{\alpha(R)}$ for all $R \in \text{dom}(I)$

From the point of view of model theory the set $\sigma$ := dom($\alpha$) is most important as the set of symbols, and plays a dominant role as the signature of a language L which is then built on top of it.

If you are not so interested in model theory (and the relation between language and reality) but in structures per se you would define a structure maybe like this:

Def. 2 A structure is a 2-tuple of sets $\langle A, R\rangle$ such that

  1. $R$ is a function
  2. $(\exists \alpha \in \mathbb{N})\ R(i) \subseteq A^\alpha$ for all $i \in \text{dom}(R)$

You would choose this definition if you suspect that there might be coextensive but different relations. (If not so, this would be overly complicated, see below.)

It's obvious that Def. 1 and Def. 2 are equivalent, only that dom(R) in Def. 2 - which corresponds to the signature $\sigma$ = dom($\alpha$) in Def. 1 - isn't so important per se and maybe only considered a index set.

But if you take the position that two coextensive relations must be the same, you have no need anymore to index the relations because they are different by themselves. The definition then simplifies to:

Def. 3 A structure is a 2-tuple of sets $\langle A, \rho\rangle$ such that

  1. $(\exists \alpha \in \mathbb{N})\ R \subseteq A^\alpha$ for all $R \in \rho$

What puzzles me is that the (conceputally) same set dom($\alpha$) resp. dom(R) comes into play for two seemingly unrelated reasons: on the one side to be able to define a language on top of a signature (and doing model theory on top of that), and to simply be able to have coextensive but different relations on the other side. But I find it hard to make a real question out of this. Maybe like this?

Can an alternative model theory be imagined based on a definition of a structure equivalent to Def. 3 reflecting the assumption that coextensive relations are the same?

It's quite obvious that all of this has to do with the distinction between intension and extension, but I find it hard to argue that standard model theory is an intensional theory, opposed to an extensional one - or vice versa. (Argumentation aid needed!)

share|cite|improve this question

One often regards lattices as algebraic structures with two binary operations, $\land$ and $\lor$. There are, of course, equivalent definitions, for example in terms of a partial order relation. The dual of a lattice is obtained by reversing the partial order; from the algebraic point of view, this amounts to interchanging $\land$ with $\lor$. Using your proposed Definition 3, a lattice and its dual, qua algebraic structures, would be identical. (Since you want relational structures, replace the binary operations $\land$ and $\lor$ with ternary relations; what I wrote about the algebraic structures still applies to the relational ones.) An example like this explains why, though strictly speaking the answer to your question ("Can ... be imagined ...?") is yes, I wouldn't want to imagine it.

share|cite|improve this answer
@Andreas: Thanks, I kind of have foreseen this answer. But could you please explain in a few words why you wouldn't want to imagine such a thing (= alternative model theory)? (I believe to understand the first part of your answer, but it didn't explain the second part.) – Hans Stricker Jun 28 '11 at 22:11
@Hans: I think the difference between a lattice and its dual is important enough that I wouldn't want model theory to "lose" this difference. In particular, in such a model theory, I could no longer say that the algebraic notion of lattice is essentially the same as (formally: bi-interpretable with) the partial-order notion. I can't define the partial order in a lattice if I don't know which operation is $land$ and which is $\lor$. – Andreas Blass Jun 29 '11 at 0:35
$land$ needs a backslash to be come $\land$; apologies for the typo. – Andreas Blass Jun 29 '11 at 0:36
Isn't a lattice and its dual essentially the same (= bi-interpretable)? – Hans Stricker Jun 29 '11 at 10:40
@Hans: they are essentially the same with regards to general model-theoretic properties of the structure, but they are quite different structures from the mathematical point of view (they are different lattices). In other words, your interpretation changes the meaning, whereas Andreas’ interpretation only expresses the same information in a different language. (I don’t claim this to be a formal distinction.) – Emil Jeřábek Jun 29 '11 at 14:12

In parts of modern model theory, one abstracts away from structures with fixed signatures, and instead uses the set of all definable relations as the working definition of a structure. (Abstractly, a set of relations on a given set which contains the identity and is closed under finite intersections, complements, projections, and adding dummy variables. I hope I didn’t forget anything.) This, in particular, has the effect of killing the distinction between coextensive relations (and much more).

share|cite|improve this answer
@Emil: Thanks. Where can I learn more about this approach, do you have a reference? – Hans Stricker Jun 29 '11 at 14:23
This is common in literature on o-minimality, for example see “Tame topology and o-minimal structures” by van den Dries. – Emil Jeřábek Jun 29 '11 at 16:14
Thank you, I'll have a look at it. – Hans Stricker Jun 29 '11 at 16:17

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.