Forking | fff

Tag Archives: Forking

MALOA “final” conference in Luminy

Posted on 09/05/2013 by Artem Chernikov | 2 comments

I had just attended the final MALOA conference “Logic and interactions“. MALOA was a European network, which is now essentially finished (though the “final” meeting was not the last one, there will be a workshop in Manchester soon). The meeting took place at CIRM in Luminy, a wonderful place not only for mathematical reasons:

(you can see some more photos here).

As MALOA was about logic, rather than model theory, the topics of the talks were quite diverse, ranging from purely algebraic model theory (definable valuations and height bound in arithmetic nullstellensatz) to proof theory and even “logical description for behaviour analysis in aerospace systems”. Not sure how productive this diversity is, but at least it is entertaining.

Some talks that I found of particular interest are:

Talks by Deirdre Haskell and Chris Laskowski on NIP, VC-density and connections to probability and combinatorics (in general one could safely add to this list some more subjects including set theory). These all are quite fascinating topics which deserve some postings in the future. There are already some examples of importing ideas from combinatorics (e.g. the beautiful (p,q)-theorem of Alon, Kleitman and Matousek) to prove model-theoretic results (e.g. UDTFS for NIP theories), but I believe that many more connections remain to be discovered.
Todor Tsankov spoke about generalizations of de Finetti’s theorem. Classical de Finetti’s theorem from probability theory says that a sequence of random variables is exchangeable if and only if it is independent and identically distributed over its tail sigma-algebra. Various multi-dimensional generalizations of this characterization form the so-called exchangeability theory. This theorem can viewed as providing a classification of all probability measures on $2^{\mathbb{N}}$ invariant under the action of $S_{\infty}$ . Now, in a general situation, given a permutation group $G$ acting on a countable set $M$ , one can’t really hope to give any kind of “classification” of $G$ -invariant measures on $2^{\mathbb{N}}$ as we are in the context of the general ergodic theory. However, it appears that if the group $G$ is sufficiently large compared to the index set, one can arrive at stronger results. Todor’s approach is to consider oligomorphic groups, i.e. such that the action of $G$ on $M^n$ has only finitely many orbits for each $n$ . These groups are familiar to model theorists as automorphism groups of $\omega$ -categorical structures. Todor provides a classification in the case when the underlying structure has trivial algebraic closure, and gives some promising partial results in the general case. In fact, this subject appears to have a lot to do with model theory. I am involved in a project together with Itai Ben Yaacov, of an abstract model theoretic approach to de Finetti’s theory in terms of the forking calculus, canonical bases and Morley sequences in the context of an arbitrary stable first-order theory, in the sense of continuous logic (which specializes to the classical case considering the theory of $[0, 1]$ -valued random variables equipped with the $L^1$ metric).

Also I gave what was probably my last talk as a “student”. I spoke about some new results with Pierre Simon and Anand Pillay concerning definable topological dynamics in NIP theories. The slides are available here. We show that notions like definable (extreme) amenability of a definable group, as well as various model theoretic components, are not affected by adding externally definable sets to the picture (that is, passing to a Shelah’s expansion of a model). These facts appear to have some applications to the questions of Newelski on describing $G/G^{00}$ in terms of the so-called Ellis group.

2 Comments

Posted in Conferences, General, Model Theory

Tagged Artem Chernikov, conference, connected component, de Finetti, Forking, Luminy, MALOA, NIP, stability, VC density

Some counterexamples for forking, dividing, invariance

Posted on 15/04/2013 by Artem Chernikov | Leave a comment

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.

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.

${T}$ is supersimple of ${SU}$ -rank ${1}$ . Thus, Lascar strong type is determined by the strong type.
For any set ${A}$ , ${\mbox{acl}(A)=A}$ .
All pairs of different elements have the same type over ${\emptyset}$ .
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.

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