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

2010-02-05T01:51:26Z

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

Answer by François G. Dorais for Naturally definable sets of natural numbers (2): Can the circle be broken?

2010-02-05T02:59:33Z

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.

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

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

Answer by François G. Dorais for Naturally definable sets of natural numbers (2): Can the circle be broken?