Natural models of graphs?

2010-01-13T10:41:11Z

Motivation

I want to capture the notion of natural models of finite graphs: How can natural predicates and natural relations on a given natural base class $D$ be defined? If this succeeds the question arises if every (or which) finite graph has a natural model with respect to these "natural" ingredients.

As natural base classes I have in mind $\mathbb{N}$ and sets (e.g. the finite subsets of $\mathbb{N}$).

Preliminaries

Let a complete description of an (unlabeled) graph be a formula

$$(\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$$

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).

The canonical model is at least "natural" with respect to the domain: it's not any set but a subset of a natural base set, $\mathbb{N}$, singled out by a "natural" predicate/formula $\phi(x) : =x \leq n$.

With respect to $R$, the canonical model isn't "natural": $R$ is just any subset of $A^2$, generally given by a formula

$$\psi(x,y) := \bigvee_{n_i,n_j} x = n_i \wedge y = n_j$$ for appropriate $n_i, n_j$.

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.

Definition: An $L(T)$-formula $\Psi(x_1,...,x_n)$ is $T$-natural 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}$.

(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? If it is not possible to improve it, you can stop reading here.)

Questions

The set of finite subsets of $\mathbb{N}$ that can be defined by a $T$-natural formula probably depends on $T$.

Question 1: Is there a theory $T$ of arithmetic that allows to define all finite subsets of $\mathbb{N}$ by an $T$-natural formula.

Furthermore:

Question 2: Is there a theory $T$ of arithmetic that allows to define all finite subsets of $\mathbb{N}^2$ by an $T$-natural formula.

Now to the natural models of graphs:

Definition: A natural $T$-model of a finite graph $G$ 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)$.

Final question (maybe equivalent to Question 2):

Question 3: Is there a theory $T$ of arithmetic that allows to find natural $T$-models for each finite graph?

If not so: How can the finite graphs with no $T$-natural model for any $T$ be characterized?

Can anything be gained by considering set theory instead of arithmetic?

Natural models of graphs? - MathOverflow

Natural models of graphs?

Motivation

Preliminaries

Questions