(This is a follow-up question from over there: 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?)
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...