dp-rank and forbidden configurations (Q1934949): Difference between revisions

Recall that Shelah defined an \textit{ICT pattern of depth \(\kappa\)} in variables \(\bar x\) as a sequence of formulas \((\varphi_i(\bar x,\bar y_i):i<\kappa)\) together with an array \((\bar b_n^i:i<\kappa,\,n<\omega)\) such that for all \(\eta\in\omega^\kappa\) the set of formulas \[ \{\varphi_i(\bar x,\bar b^i_{\eta(i)}):i<\kappa\}\cup\{\neg\varphi_i(\bar x,\bar b^i_n):i<\kappa,\,n\not=\eta(i)\} \] is consistent. On the other hand, if \(\psi(\bar x,\bar y)\) is a formula, \(M\) some structure and \(A\subseteq M^{|\bar x|}\) a finite subset, then \(\psi\) \textit{shatters} \(A\) if every subset of \(A\) is of the form \(\{a\in A:M\models\psi(a,\bar b)\}\) for some \(\bar b\in M\). The maximal \(d\) such that \(\psi\) shatters a set of cardinality \(d\) is the \textit{VC-dimension} of \(\psi\) in \(M\). We say that \(\psi\) is \textit{\(d\)-maximal} if \(\psi\) has VC-dimension \(d\), and for any subset \(X\subseteq M\) not of the form \(\psi(M,\bar b)\), there is a subset \(A\) such that \(\psi\) shatters \(A\) except for \(A\cap X\). We call \(|\bar y|\) the parameter length. The author shows that for any complete theory \(T\), there is a model with an ICT pattern of depth at least \(d\) in \(n\) variables if and only if \(T\) has a \(d\)-maximal formula in \(n\) parameters. The arguments include a lengthy discussion about characterizing VC-families by forbidden patterns.