# Naturally definable sets of natural numbers (2): Can the circle be broken?

(follow-up to: Naturally definable sets of natural numbers)

Every formula $\Psi(x)$ in the first-order language of Peano arithmetic defines a set of natural numbers. Some of these sets are finite, others are infinite. Every finite set $\lbrace n_0, n_1, ..., n_k \rbrace$ can be defined by an equation $p(x) = q(x)$ with $p(x), q(x)$ finite polynomials in $x$ with natural coefficients. Let in the following $\phi(x)$ be such an equation [read "phi" for "finite"]. Infinite sets cannot be described by any $\phi(x)$.

Given a formula $\Omega(x)$ which defines an infinite set [read "omega" for "infinite"]. Then every formula of the form $\Omega(x) \vee \phi(x)$ or $\Omega(x)\wedge \neg\phi(x)$ defines an infinite set, too.

The motivation of the following definition is this: A formula defining an infinite set shall be called arbitrary if it is derived from a natural (= non-arbitrary) formula by adding or removing finitely many arbitrary elements.

Definition (wannabe): A formula $\Omega(x)$ is arbitrary iff it defines an infinite set and is equivalent

1. to a formula $\omega(x) \vee \phi(x)$ with $\phi(x) \not\rightarrow \omega(x)\ \ \ \ \ \ \ \ \ \$ or
2. to a formula $\omega(x) \wedge \neg \phi(x)$ with $\omega(x) \not\rightarrow \neg\phi(x)$

where $\omega(x)$ is not arbitrary. (Of course, $\omega(x)$ defines an infinite set.)

On first sight, this definition seems circular:

Let $\Omega(x) \equiv \omega(x) \vee \phi(x)$ with $\phi(x) \not\rightarrow \omega(x)$.

Then $\omega(x) \equiv \Omega(x) \wedge \neg\phi'(x)$ with $\Omega(x) \not\rightarrow \neg\phi'(x)$.

Then $\Omega(x)$ is arbitrary iff $\omega(x)$ is not arbitrary.

Might this seemingly vicious circle not be in fact a (hidden) recursive definition (by something like "(abstract) length of formulas")?

Cannot this circle be broken? What about the intuition, that $(\exists y) x = 2 \cdot y$ is a non-arbitrary formula, but that $(\exists y) x = 2 \cdot y \vee x = 17$ is an arbitrary one?

-
-1. This question is terribly vague. Since I don't believe that there actually is a useful and coherent notion of "natural" along these lines, I find it impossible to help you give precise substance to an intuition that I don't share. But I would be happy to consider again, however, if you make a precise proposal. So I would encourage you to ask a focused, precise question. – Joel David Hamkins Feb 5 '10 at 2:41
I appreciate your comment, but what I cannot understand is, why nobody seems to share or even is willing to try to share my intuition/feeling expressed in the last sentence of my question? (Francois at least seemed to be able to make some sense of it.) Maybe I should have mentioned that my question has to do with the philosophical questions for "natural kinds" and "induction" (see e.g. en.wikipedia.org/wiki/Nelson_Goodman#Induction_and_.22grue.22). – Hans Stricker Feb 5 '10 at 8:40
Well, I think I did try, because I answered your two previous questions on this topic, with fairly complete answers each time (you deleted the first question shortly after I posted my answer). And Francois has also given you excellent answers. The substance of his answer below is that you may be looking for naturality in the wrong place, in the syntax, rather than in the sets themselves. – Joel David Hamkins Feb 5 '10 at 13:49
Indeed, the answers were excellent (see my comment on Francois' answer), and I am really thankful that you took the time. My comment only concerned your claim that you don't share my intuition. – Hans Stricker Feb 5 '10 at 14:13

From what I gather from your question, your "natural formulas" would form a complete set of distinct representatives for definable subsets of N under the equivalence relation $X \mathrel{E}_0 Y$ defined by $|(X \setminus Y) \cup (Y \setminus X)| < \aleph_0$. Unfortunately, there is no simple way to do this; such a system of distinct representatives necessarily has very high complexity. In fact, finding a system of distinct representative for $E_0$ over all subsets of N is precisely the same complexity as Vitali's construction of a non-measurable set!
In your question, you talk about formulas rather than the sets they define, but this is not much different (the difference is known as "lightface vs boldface" in the literature). Problems of this type are extensively studied in Descriptive Set Theory, under the heading of Borel Equivalence Relations. The relation $E_0$ is in a very precise sense the simplest Borel equivalence for which has no simple system of distinct representatives, it thus plays a very important role in this theory.
By "complexity," I meant the first level of the projective hierarchy that contains a solution of the given problem. This is independent of ZFC, but the minimum consistent with ZFC is $\Delta^1_2$. There are several similar options for "simplicity" and most make sense; I don't think I had a specific one in mind. – François G. Dorais Feb 11 '10 at 12:41
Your "wannabe definition" is very close to saying "the set is arbitrary if it is not equivalent to the representative of its $E_0$ equivalence class." (Technically, your definition should have a third case for when the set is neither contained in nor contains the representative of its $E_0$ class, but I assumed that this was an omission since $E_0$ equivalence was within the same spirit as what you were describing.) – François G. Dorais Feb 11 '10 at 12:43