{
  "id": "1106.5153",
  "version": "v2",
  "published": "2011-06-25T18:04:24.000Z",
  "updated": "2011-06-28T17:33:41.000Z",
  "title": "Characterization of NIP theories by ordered graph-indiscernibles",
  "authors": [
    "Lynn Scow"
  ],
  "comment": "(to appear in APAL)",
  "journal": "Annals of Pure and Applied Logic 163 (2012), no. 11, 1624-1641",
  "categories": [
    "math.LO"
  ],
  "abstract": "We generalize the Unstable Formula Theorem characterization of stable theories from \\citep{sh78}: that a theory $T$ is stable just in case any infinite indiscernible sequence in a model of $T$ is an indiscernible set. We use a generalized form of indiscernibles from \\citep{sh78}: in our notation, a sequence of parameters from an $L$-structure $M$, $(b_i : i \\in I)$, indexed by an $L'$-structure $I$ is \\emph{$L'$-generalized indiscernible in $M$} if qftp$^{L'}(\\ov{i};I)$=qftp$^{L'}(\\ov{j};I)$ implies tp$^L(\\ov{b}_{\\ov{i}}; M)$ = tp$^L(\\ov{b}_{\\ov{j}};M)$ for all same-length, finite $\\ov{i}, \\ov{j}$ from $I$. Let $T_g$ be the theory of linearly ordered graphs (symmetric, with no loops) in the language with signature $L_g=\\{<, R\\}$. Let $\\K_g$ be the class of all finite models of $T_g$. We show that a theory $T$ has NIP if and only if any $L_g$-generalized indiscernible in a model of $T$ indexed by an $L_g$-structure with age equal to $\\K_g$ is an indiscernible sequence.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-06-28T17:33:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03C45",
      "03C68",
      "05C55"
    ],
    "keywords": [
      "nip theories",
      "ordered graph-indiscernibles",
      "unstable formula theorem characterization",
      "generalize",
      "age equal"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1106.5153S"
    }
  }
}