(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

- to a formula $\omega(x) \vee \phi(x)$ with $\phi(x) \not\rightarrow \omega(x)\ \ \ \ \ \ \ \ \ \ $
**or** - 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?

somesense 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). $\endgroup$ – Hans-Peter Stricker Feb 5 '10 at 8:40