3 edited body

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

2 unbroken -> broken

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

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

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

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