0

I was reading about amorphous sets recently and I thought the idea was quite intriguing, but couldn't come up with any natural example of one (perhaps because the existence of one implies the falsehood of Choice).

Setting my sights lower to include only computable sets, I came to suspect that a "computably amorphous" set of natural numbers may exist. So far I haven't been able to come up with an example, but I feel like there might be one.

A starting point is that if the set is written in ascending order as a sequence of natural numbers, every number in the sequence after the nth (or n^2th, or whatever) may be required to be a multiple of n, thereby guaranteeing that any partition of the set into residue classes modulo n contains only one infinite class, namely zero.

But I have no idea how to go further to having all computable partitions of the set contain only one infinite member. Does anyone else know whether this is possible and if so how to achieve it?

Andrés E. Caicedo
  • 79,201
Seth Schmidt-O'Hainle
  • 151
  • 5
    If $\langle n_i : i \in \omega \rangle$ is the increasing enumeration of a computable set, isn't $\langle n_{2i} : i \in \omega \rangle$ trivially also computable? – Jonathan Schilhan Feb 27 '20 at 14:15
  • I'm not sure I understand the Question as you mean it. Certainly the subsets of any finite computable set are finite, so as the final paragraph seems to allude, you are really interested in the case where this involves an infinite computable set. So perhaps your cofinite qualification is meant with respect to the specified infinite set (rather than with respect to the natural numbers at large). That said, we could split such an infinite set into two infinite subsets by alternating between the order in which they occur (first entry in one bucket, next one into the other bucket, etc.). – hardmath Feb 27 '20 at 14:17
  • I meant an infinite set, and indeed by cofinite I meant with reference to the set itself. As always I forgot obvious and important details... but yeah, I considered the "every other entry" idea but I wasn't sure it was applicable because there's nothing in the numbers themselves which immediately tells you which entry of the sequence they are. If that's the case though then I guess the answer is just a flat "no"? – Seth Schmidt-O'Hainle Feb 27 '20 at 14:44

1 Answers1

0

This was answered in the comments; I'm answering here to move this off the "unanswered" queue. I've made this CW so I don't get reputation for others' work.

No such set exists.

The key point here is that if $X$ (WLOG, infinite) is computable then $X$ can be computably listed in order as $X=\{x_0<x_1<x_2<x_3<...\}$. More precisely: if the characteristic function of $X$ ($n\mapsto 1$ iff $n\in X$, $n\mapsto 0$ otherwise) is computable, then the principle function of $X$ ($n\mapsto$ $n$th smallest element of $X$) is computable. This is a good exercise, and the converse holds too.

With this in hand, we can argue as follows. If $X$ is computable, let $\pi_X$ be its principle function. Then we can consider the set $$E_X:=\{\pi_X(2k):k\in\mathbb{N}\}.$$ We have that both $E_X$ and $X\setminus E_X$ are infinite, and $E_X$ is computable: to check if $n\in E_X$, just compute $\pi_X(0),\pi_X(2),\pi_X(4),...,\pi_X(2\cdot \lfloor {n\over 2}\rfloor)$ and check if $n$ is one of these values (note that if $n=\pi_X(2k)$ then $2k\le n$).

Noah Schweber
  • 245,398