Logic Seminar
Siddharth Bhaskar
IU Bloomington
Finitary stability
Abstract: We introduce a novel measure of complexity of set systems called thicket
density which can be seen as an analogue to both VC density and Cantor-
Bendixson rank of topological spaces. The analogue to VC theory is quite
exact: we have "thicket" versions of dimension, shatter function, and density.
In this case, infinite dimensionality captures exactly those set systems which
satisfy the order property, as opposed to the independence property. These
quantities satisfy several identities (including the Sauer-Shelah dichotomy) that
hold verbatim in the VC case. Curiously, the proofs of these identities seem
quite different, and we cannot infer the "thicket" versions from the VC versions
and vice versa.
On the other hand, thicket density can be seen as a finitary version of Cantor-Bendixson rank; in particular, the polynomial/exponential growth dichotomy
from "thicket Sauer-Shelah" corresponds to the countable/continuum cardinality dichotomy in the perfect set theorem. (This justifies the name "Finitary
Stability.") We even believe there is a notion of "derivative of a set system"
that corresponds to the Cantor derivative and induces something like the actual
discrete deriative on shatter functions.
Finitary stability has at least one application in pure model theory, namely
a short proof of the Erdös-Hajnal property for stable graphs, which we might go
over, time permitting. Curiously enough, I discovered it not through model theory, but implicitly hidden in a 1989 paper---about something totally different---by
Polish computer scientist Jerzy Tiuryn.
This talk should be widely accessible, being relatively close to first principles.
It describes work that is very current, and I would like to present one proof (of
"thicket Sauer-Shelah").
Tuesday November 29, 2016 at 4:00 PM in SEO 427