Natural models of graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T23:55:15Z http://mathoverflow.net/feeds/question/11647 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11647/natural-models-of-graphs Natural models of graphs? Hans Stricker 2010-01-13T10:41:11Z 2010-01-13T16:10:36Z <h3>Motivation</h3> <p>I want to capture the notion of <em>natural models of finite graphs</em>: How can <em>natural predicates</em> and <em>natural relations</em> on a given <em>natural base class</em> $D$ be defined? If this succeeds the question arises if every (or which) finite graph has a <em>natural model</em> with respect to these "natural" ingredients.</p> <p>As natural base classes I have in mind $\mathbb{N}$ and sets (e.g. the finite subsets of $\mathbb{N}$).</p> <h3>Preliminaries</h3> <p>Let a complete description of an (unlabeled) graph be a formula</p> <p>$$(\exists x_1)...(\exists x_n)\ \bigwedge_{i \neq j} x_i \neq x_j \ \ \wedge \ \ (\forall x) \bigvee_i x = x_i \ \ \wedge \ \ \bigwedge_{i,j}[\neg]?Rx_ix_j$$</p> <p>The canonical model of such a description - seen as a categorical theory - consists of $[n]$ as the domain $A$ and some $R \subseteq [n]^2$ as the relation. It is trivially construed from the indexes of the variables (if choosen in the canonical way as it is done above).</p> <p>The canonical model is at least "natural" with respect to the domain: it's not <em>any</em> set but a subset of a natural base set, $\mathbb{N}$, singled out by a "natural" predicate/formula $\phi(x) : =x \leq n$.</p> <p>With respect to $R$, the canonical model isn't "natural": $R$ is just <em>any</em> subset of $A^2$, generally given by a formula </p> <p>$$\psi(x,y) := \bigvee_{n_i,n_j} x = n_i \wedge y = n_j$$ for appropriate $n_i, n_j$. </p> <p>It is this kind of ad-hoc-formula I want to rule out. Maybe this can be done straight forwardly? Let for instance $T$ be any theory of the natural numbers and $L(T)$ be its language.</p> <blockquote> <p>Definition: An $L(T)$-formula $\Psi(x_1,...,x_n)$ is <em>$T$-natural</em> iff it is $T$-equivalent to a formula $\Psi'(x_1,...,x_n)$ that doesn't contain literals of the form $x_i = n$ with $n$ the name of an $n \in \mathbb{N}$.</p> </blockquote> <p><em>(Note: I know that this definition is maybe not quite correct from the point of view of model theory, but I hope that it is sensible. If it is not: How to improve it? <strong>If it is not possible to improve it, you can stop reading here.</strong>)</em></p> <h3>Questions</h3> <p>The set of finite subsets of $\mathbb{N}$ that can be defined by a $T$-natural formula probably depends on $T$.</p> <blockquote> <p>Question 1: Is there a theory $T$ of arithmetic that allows to define <em>all</em> finite subsets of $\mathbb{N}$ by an $T$-natural formula.</p> </blockquote> <p>Furthermore: </p> <blockquote> <p>Question 2: Is there a theory $T$ of arithmetic that allows to define <em>all</em> finite subsets of $\mathbb{N}^2$ by an $T$-natural formula.</p> </blockquote> <p>Now to the natural models of graphs:</p> <blockquote> <p>Definition: A <em>natural $T$-model of a finite graph $G$</em> is given by a domain $A = \lbrace x \in \mathbb{N} | \phi(x) \rbrace$ and a relation $R = \lbrace (x,y) \in A^2 | \psi(x,y) \rbrace$ with $T$-natural formulas $\phi(x), \psi(x,y)$.</p> </blockquote> <p>Final question (maybe equivalent to Question 2):</p> <blockquote> <p>Question 3: Is there a theory $T$ of arithmetic that allows to find natural $T$-models for each finite graph?</p> </blockquote> <p>If not so: How can the finite graphs with no $T$-natural model for any $T$ be characterized?</p> <p>Can anything be gained by considering set theory instead of arithmetic?</p>