I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus integers encoding a TM that halts in an even number of steps. I am hoping to come up with something much simpler to define in FOL. One idea I had was the set of positive integers whose Goodstein's sequence terminates in an odd number of steps versus those whose sequence terminates in an even number of steps. Can the length of Goodstein's sequence be made into a first order statement? Basically, I want to know how simple the definition of recursively inseparable sets can be.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ @Easterly: What do you mean here with the word "Complexity"? $\endgroup$– boumolCommented Feb 15, 2014 at 21:22
-
$\begingroup$ Because all Goodstein sequences terminate, and because we can compute the Goodstein sequence of every number, the set of numbers whose Goodstein sequence terminates in an even number of steps is decidable - so it trivially is a computable separating set for itself and its complement (which is also computable). Separately, yes, it is a routine exercise to show that Peano arithmetic defines the function mapping each number to its Goodstein sequence, and the function mapping each number to the length of that sequence. $\endgroup$– Carl MummertCommented Feb 16, 2014 at 0:59
-
$\begingroup$ So it doesn't matter that we can't put any bound on how long the sequence is? The set is decidable as long as it's members and its complement's members terminate? $\endgroup$– Russell EasterlyCommented Feb 16, 2014 at 5:52
-
$\begingroup$ A set of natural numbers is decidable if we can write an algorithm that halts on all numbers and tells correctly whether each number is in the set. Because there is an algorithm to compute the Goodstein sequence of each number, and every number has a finite sequence, we can decide whether the sequence of an arbitrary number has even length. Classical computability theory is about computation when there is no limit on how long a computation can take, as long as the computation halts eventually. @Russell Easterly $\endgroup$– Carl MummertCommented Feb 16, 2014 at 12:33
-
$\begingroup$ Can we assume every Goodstein sequence terminates even if this can't be proven in PA? Can two sets be recursively inseparable in a weak theory but recursive in a stronger theory? $\endgroup$– Russell EasterlyCommented Feb 19, 2014 at 23:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
On expressing the length of the Goodstein sequence ...
Let $g(n, k)$ be the $k$-th value in the Goodstein sequence starting at $n$. $g$ is evidently a primitive recursive function (its value can be computed without open-ended searches), so the two-place function can be represented by a three-place $\Sigma_1$ wff arithmetical wff $\mathsf{G(x, y, z)}$.
The length $l$ of the sequence starting from $n$ is the least $k$ such that $g(n, k) = 0$. Formally that gets expressed as $\mathsf{G(n, l, 0) \land \forall y(y < l \to \neg G(n, y, 0)}$.
Is that any help?
answered Feb 15, 2014 at 20:20
-
$\begingroup$ My Latex skills are lacking. I have been told decidable sets of natural numbers have complexity $\sum_3^0$. I am looking for a recursively inseparable set with this complexity or less. If Goodstein's sequence is primitive recursive does this mean the length of such sequences is recursive? $\endgroup$ Commented Feb 15, 2014 at 23:10
-
3$\begingroup$ Each individual decidable (i.e. computable) set of number is at level $\Delta^0_1$ of the arithmetical hierarchy of subsets of $\mathbb{N}$: both it and its complement are $\Sigma^0_1$. The class of decidable sets (as a subset of Cantor space $2^\mathbb{N}$) is $\Sigma^0_3$. The usual examples of recursively inseparable sets are examples of recursively separable r.e. sets, i.e. two sets each of which is $\Sigma^0_1$. $\endgroup$ Commented Feb 16, 2014 at 0:57
-
$\begingroup$ Are you sure you meant "primitive recursive". I don't know much about the Goodstein sequence, but if the value of $g$ "can be computed with open-ended searches", that seems to imply that it very well mightn't be primitive recursive. $\endgroup$ Commented Feb 16, 2014 at 15:15
-
$\begingroup$ It was a slip, sorry: it should have read, and now does read, "without open-ended searches". $\endgroup$ Commented Feb 16, 2014 at 15:22