(This is a follow-up question from over there: [Natural models of graphs](https://mathoverflow.net/questions/11647/natural-models-of-graphs).)


(And it *has* a follow-up question over there: [Naturally definable sets of natural numbers (2): Can the circle be broken?](https://mathoverflow.net/questions/14211/naturally-definable-sets-of-natural-numbers-2-can-the-circle-be-broken))


### Motivation


I am looking for a way to syntactically characterize formulas in the first order language of Peano arithmetics that specify a natural or "truely shared" property of a set of natural numbers.


The term *natural* (formula or set) is chosen in contrast to *contingent*, alternatively *ad hoc, mereological* or even *random* (→ Kolmogorov complexity).


The canonical counter-examples are formulas of the form $x = n\_0 \vee x = n\_1 \vee ... \vee x = n\_k$ which prima facie merely list some arbitrary numbers. But of course such formulas are often enough equivalent to "natural" ones, e.g. $x = 2 \vee x = 4 $ is equivalent to $x \geq 1 \wedge x \leq 4 \wedge (\exists y)\ x = 2 \cdot y$ which specifies the natural property of "being even and greater than 0 and less than 5".


Which syntactic conditions on a formula $\Phi(x)$ would do it? Let's try to prohibit literals of the form $x = n\_0$ for some fixed natural number $n\_0$ and everything equivalent to such literals: conjunctions like $x > n\_0-1 \wedge x < n\_0+1$, literals with general terms $t(x) = t\_0$ (with $n\_0$ the unique solution) and so on.



> 
> Definition: A formula $\Phi(x)$ is *natural* if there is
> a formula equivalent to it that does not contain subformulas $\phi(x)$ (with $x$ the only free variable) - or (maybe spread) conjunctions of such subformulas - that are equivalent to $x = n\_0$ for some fixed $n\_0$.
> 
> 
> 


A consequence of this definition is that singleton sets can never be defined naturally because every formula that defines a singleton set $\lbrace n\_0 \rbrace$ is equivalent to the formula $x = n\_0$. But that's OK since I want to capture the notion of a "shared" property.



> 
> Question #1a: Can anyone show by a simple (!) argument, that every formula with at least two "truth-makers" is natural as defined above (if this is the case)?
> 
> 
> 


This would make my definition useless, since it would not capture what I tried to capture. A tricky argument would be OK (see Question #4).



> 
> Question #1b: How could one try to demonstrate that a given formula is **not** natural?
> 
> 
> 




---



> 
> Question #2: Is there already
> research or relevant statements about natural
> formulas as defined above? How can the set of natural formulas be characterized otherwise?
> 
> 
> 


Anyway, the following questions arise:



> 
> Question #3: Can every finite set of natural
> numbers be defined by a natural formula?
> 
> 
> 




---



> 
> Question #4: Can every definable set
> of natural numbers be defined by a
> natural formula?
> 
> 
> 


I.e.: Is every formula natural?



> 
> Question #5: What's the classification
> of a definable set in the arithmetical
> hierarchy if only natural formulas are
> allowed?
> 
> 
> 


I guess it might be better to "form(ul)alize" a **degree** of naturality (resp. randomness) like this: "How many literals of the form $m = m\_0$ are minimally needed to define set $M$?" But that's another question...



Naturally definable sets of natural numbers

> 
> Question 3: Can every finite set of natural numbers be defined by a natural formula?
> 
> 
> 


If I understand correctly, the answer is yes: We can always rewrite $x = n\_0 \vee x = n\_1 \vee ... \vee x = n\_k$ in the form $p(x) = q(x)$ for some polynomials $p$ and $q$ with natural number coefficients, which seems to meet your criteria. Is this really the question you want to ask?


