Naturally definable sets of natural numbers

Question

(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?)

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

Answer 1

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?

Answer 2

I have a few observations which settle your questions.

• First, you will never prove in Peano's Axioms PA that any particular formula is natural.

The reason is that in order to prove a particular formula is natural, we must prove that particular subformulas are not "equivalent" to other expressions. You have suggested in the comments that you mean "equivalent" in the sense of provably-equivalent-in-PA. Thus, in order to prove a formula is natural, we must prove that PA does not prove that its subformulas are equivalent to some other expressions. But this fact by itself implies, of course, that not very statement is provable in PA. And this implies that PA is consistent. In summary, the assertion that any particular formula is natural implies Con(PA). Since PA, if consistent, does not prove Con(PA) by the Incompleteness theorem, it follows that we cannot prove in PA that any particular formula is natural.

• Second, it is consistent with Peano's Axioms that there are no natural formulas.

By the Incompleteness Theorem, there is a model of PA + ¬Con(PA). In such a model, all of the PA axioms are true, but the model believes that any statement at all is provably equivalent to x=1. Thus, this model believes that there are no natural formulas.

• Third, if PA is consistent, then EVERY formula is natural.

The assumption that Con(PA) removes the obstacles of the previous two observations. For this argument, I take your definition of "natural" in the most literal interpretation. You say that an expression phi(x) is natural if it is equivalent to a formula having no subformulas equivalent to x=n. Suppose phi(x) is any formula. The formula phi(x) is provably equivalent to the formula "exists y ( y=x and phi(y))". This latter formula has only one occurrence of the variable x, which is in the clause x=y, which has another free variable y. Thus, there simply are no subformulas psi(x) as you mention in the definition of naturality. So this formula is vacuously natural according to your definition. QED

To summarize, the observations taken together show that the assertion that a formula is natural, is exactly equivalent to Con(PA). So either every formula is natural or none are, depending on whether Con(PA) holds.

I think these observations suggest that your proposed definition of natural may be unnatural, or at least that it is probably not expressing what you intend.

Answer 3

In general, I consider this question interesting. But on the other hand - well, you don't specify what literals you accept in your formal System.

If you have $\le$ for example, it is likely that you define $a < b$ by $a \le b \wedge a\neq b$, so you implicitly get an $=$ into your formula, and hence, you also cant allow $x < n$ for fixed $n$. Same for $\le$. So actually, I would consider it more reasonable to disallow explicit numbers in general. In fact, anything that depends on an explicitly given (and therefore exchangable) number doesnt seem "natural" to me.

(Also, being even doesnt really seem natural to me - it is divisibility by 2, why not divisibility by 3? But as soon as you have a $+$-Function, you cannot suppress this being natural.)

Lets assume we are in a classical setting. Then it is sufficient to have $\wedge$, $\vee$, $\lnot$, $\forall$ to express anything we want, and the relation symbols $=$, <, and the function symbols $S$, $+$, $\cdot$ (normally, we could spare $S$ and add $0$ and $1$ if we have $+$, but since we dont want explicit numbers anyway, lets just add the successor-function and disallow $0$ and $1$ - so the "naturality" is a consequence rather than an enforcement).

Of course, we can express $\mathbb{N}$ and $\emptyset$ by $x=x$ and $x < x$, and conjunctions and disjunctions of it. We can express the set of even numbers by $\lnot\forall y \lnot x=y+y$, and the set of all primes by $\forall a,b,c,d . x=a\cdot d \rightarrow x=b\cdot d \rightarrow x \neq c \cdot d$, and we can express finite intersections and unions.

And - we still can define predicates depending on explicit numbers, since $\forall y (x < y \vee x=y) \leftrightarrow x=0$. So lets - additionally - disallow <. Then the atoms we have left are $=$-expressions between terms consisting of variables, $S$, $+$ and $\cdot$. Trivially, every of these terms is equal to some polynomial with natural coefficients. On the other hand, we can express every polynomial with natural coefficients of at least degree 1 in every variable by these natural numbers. And thus, our atomic relationships between variables are equivalent to the relationships between polynomials with natural coefficients of at least degree 1, which can always be expressed as sets of roots of a polynomial with integer coefficients of at least degree 1. So what we get as atoms are relations describing sets of natural roots of polynomials with integer coefficients.

Anyway, enough of this, well, we can still get $0$ by saying $x+x=x$ and $1$ by saying $x*x=x \wedge x+x \neq x$.

Disallowing $+$ and $\cdot$ would seem strange to me, as then you would only have the successor-function, which would only allow atomic relations equivalent to $x=y+n$ for fixed $n$ - and still, here you would be able to get $0$ by saying $\forall y.x \neq S(y)$.

Maybe you could also disallow negations instead, then you would get something similar to algebraic varieties. Or maybe you should take a look at Presburger Arithmetic.

I myself would just define a set of natural numbers as "natural" if it is decidable.