MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 2010 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/…). – Hans Stricker Feb 5 2010 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 2010 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 2010 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.

A good place to get started with Descriptive Set Theory is Kechris's Classical Descriptive Set Theory. For your particular problem, you want to look at the "lightface theory," for which the standard reference is Moschovakis's Descriptive Set Theory. There are a few good surveys and books on Borel equivalence relations, but most require a fair amount of familiarity with the subject.

-
 This is an enlightening answer to a supposedly obscure question. Thank you. – Hans Stricker Feb 5 2010 at 9:04 What is the complexity of a set/system of sets? What is complexity in this context, anyway? Has it to do with the level in the arithmetical/analytical hierarchy? Is it then not the members of the set/system that are of high complexity? By contrast: Is "simple" in the "simple system of distinct representatives" you mention a precisely defined term? – Hans Stricker Feb 11 2010 at 8:45 Assuming that your set of distinct representatives is the set of "natural" sets I am looking for - which I am not quite sure yet - I accept this answer. (In any case it opened up my mind for descriptive set theory.) – Hans Stricker Feb 11 2010 at 9:31 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 2010 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 2010 at 12:43
show 7 more comments