Tag Archives: random graph

Some counterexamples for forking, dividing, invariance

At the end of my paper with Itay Kaplan “Forking and dividing in NTP2 theories” we had asked several questions, admittedly without giving them much thought. Since 2008 when the paper went in circulation, some people had actually shown interest in those questions. By now two of them are known to have negative answers, one due to Gabriel Conant and one by myself, with very easy examples. I’d like to have them written down for a reference somewhere, so I’ve thought this might be an appropriate place.

good forking

Question 1. (rephrased as more elaborate latex is not available here): Is it true that in a simple theory, every type has a global Lascar-invariant extension.

I recall that a complete global type {p\left(x\right)\in S\left(\mathbb{M}\right)} is Lascar-invariant over a small set {A} if whenever {\phi\left(x,a\right)\in p} and {b} has the same Lascar strong type over {A} as {a}, then {\phi\left(x,b\right)\in p}. Having the same Lascar strong type means that {a} is equivalent to {b} with respect to every equivalence relation with boundedly many classes which is {\mbox{Aut}\left(\mathbb{M}/A\right)}-invariant.

This property is true in the random graph, for example – any type can be extended to a global one without adding any new edges. This is also true in any extensible NIP theory, say in any stalbe theory, any {o}-minimal theory (e.g. real closed fields) or any {C}-minimal theory (e.g. algebraically closed valued fields), as well as in any theory with definable Skolem functions (e.g. {p}-adics). A theory is extensible if every type does not fork over its domain. However, the crucial point is that this property need not be preserved in reducts of the theory, which immediately gives an easy simple counterexample.

Example. Let {T} be the reduct of the random graph given by the ternary relation {R(x,y,z)} which holds if and only if {x\neq y\neq z} and the number of edges between vertices in the set {\left\{ x,y,z\right\} } is odd.

Claim.

  1. {T} is supersimple of {SU}-rank {1}. Thus, Lascar strong type is determined by the strong type.
  2. For any set {A}, {\mbox{acl}(A)=A}.
  3. All pairs of different elements have the same type over {\emptyset}.
  4. Let {M\models T} and {p\in S(M)}. Then {p} is not Lascar-invariant over {\emptyset}.

Proof: (1) is because {T} is definable on the set of singletons in the random graph, which is supersimple of {SU}-rank 1. Now it is a well-known fact that Lascar strong type is determined by the strong type in supersimple theories.

(2) is easy to see, and (3) is by back-and-forth.

(4) Assume {p} is Lascar-invariant over {\emptyset}, thus invariant over it by (1) and (2). Let {a\models p}, then by (3) either {\models R(a,b,c)} for all {b\neq c\in M} or {\models\neg R(a,b,c)} for all {b\ne c\in M}. In the first case, let {b\neq c\neq d\in M} satisfy {\neg R(b,c,d)}. Then it is easy to see that {\not\models R(a,b,c)\land R(a,c,d)\land R(a,b,d)} — a contradiction. In the other case, take {b,c,d} satisfying {R(b,c,d)} and check that {\not\models\neg R(a,b,c)\land\neg R(a,c,d)\land\neg R(a,b,d)} — a contradiction again. \Box

Thus, by (4) the unique type over the empty set has no global Lascar-invariant extension.

There are various modifications of the question which still make sense, and also one can ask if this property holds in particular algebraic structures of interest. I have some things to say about it, but not this time.

Question 2. “Can similar results be proved for NSOP theories?”

Here “similar results” refers to the main result of the paper, that is that in an NTP2 theory a formula divides over an extension base if and only if it forks over it. Now, Gabe shows in “Forking and dividing in Henson graphs” that it is not the case for the triangle-free random graph. From my own experience, triangle-free random graph seems to demonstrate the failure of all the phenomena which holds for NTP2 theories.

Example. Let {T} be the theory of the triangle-free random graph, and let {b_{0}\neq b_{1}\neq b_{2}\neq b_{3}}. Let {\phi\left(x,b_{0}b_{1}b_{2}b_{3}\right)=\bigvee_{i<j<4}\left(xRb_{i}\land xRb_{j}\right)}.

Claim.

  1. {xRb_{i}\land xRb_{j}} divides over {\emptyset} for any {i<j}.
  2. {\phi\left(x,b_{0}b_{1}b_{2}b_{3}\right)} does not divide over {\emptyset}.
  3. {\emptyset} is an extension base.
  4. {T} is {\mbox{SOP}_{3}} but {\mbox{NSOP}_{4}}.
  5. However, forking and dividing are the same for complete types.

See Gabe’s article for details and for the general case of Henson graphs.

Still the following part of the question remains open:

Problem.

  1. Is forking=dividing for complete types?
  2. Is forking equal to dividing for formulas in NTP1 over models?
Advertisements