Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If I'm giving a lecture on trivial definable closure (as a property of graphs), what is a good example of a graph that I can easily draw to depict the concept of trivial dcl?

share|cite|improve this question
Can you please tell me the definition of definable closure? I would be interested in knowing it, but I am not able to find it quickly. – Valerio Capraro Oct 31 '11 at 16:37
@ValerioCapraro: There is a thorough treatment in Wilfrid Hodges' books Model Theory and A Shorter Model Theory. Just like the (model-theoretic) algebraic closure of a set consists of all elements realising types (equivalently: formulas) over the set that have only finitely many solutions, the definable closure consists of all elements realising types (equivalently: formulas) over the set that have only one solution. E.g., in algebraically closed fields, the definably closed sets are the subfields, and the algebraically closed sets are the algebraically closed subfields. – Hans Adler Oct 18 at 14:27

1 Answer 1

The infinite edgeless graph has trivial definable closure, since for any finite tuple $\bar a$, there are automorphisms fixing $\bar a$ and swapping any two vertices outside of $\bar a$.

But of course, the infinite edgeless graph is so not interesting to have drawn on the chalkboard. (I suppose you could address this by drawing the complete graph on infinitely many vertices, which also has trivial definable closure for the same reason.) But I would recommend another example, the countable random graph. For any finite tuple $\bar a$ and any vertex $b$ outside $\bar a$, there is an automorphism fixing $\bar a$ and moving $b$, and so the definable closure of $\bar a$ is itself. This situation would be a good excuse to discuss the random graph, if you have not done so already.

share|cite|improve this answer
I really don't know the answer to this, but it seems that the Henson graphs, $H_n$ (Fraisse limits of the class of finite graphs with $K_n$, the complete graph on $n$ vertices banned) should have trivial dcl, but I don't know. On the other hand, in the case of the random graph, the complement is the random graph as well, but with these graphs, their complements are actually different, and they should also have the property, right? Can anyone think of any other examples (besides by doing things like taking disjoint unions of these graphs or finite empty or complete graphs)? – James Freitag Oct 31 '11 at 22:15

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.