Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.