11
$\begingroup$

It is easy to see that every countable collection of sets $A_n\subseteq\mathbb{N}$ has an upper bound in the Turing degrees, since we can just take a copy of their disjoint sum $\oplus_n A_n=\{\langle n,m\rangle\mid m\in A_n\}$, using a computable pairing function $\langle\cdot,\cdot\rangle$. From this, we can easily compute each $A_n$.

My question is whether we can do that just in the Turing degrees, where we don't have the $A_n$ as sets, but only their degrees $[A_n]_T$.

Question. Without using AC, does every countable set of Turing degrees have an upper bound?

Of course, if we had countable choice, we could choose a representative from each degree and then apply the earlier disjoint sum operation.

It is consistent with ZF that the reals are a countable union of countable sets, but I couldn't see directly how to turn this into an answer to the question.

A similar question seems to arise in the Hausdorff order of almost-inclusion $\subseteq^*$, where $A\subseteq^* B$ if and only if all but finitely many elements of $A$ are in $B$. Let's mod out by the corresponding equivalence relation $A=^*B\iff A\subseteq^*B\subseteq^*A$, and let's remove the top element in the quotient. So we are looking at the almost-equal equivalence classes of co-ininfinite sets, under almost inclusion.

Hausdorff proved that every countable increasing chain of almost inclusion has a co-infinite upper bound. But without AC, it is not clear how to use this argument when you are initially given only the almost-equality equivalence classes of the sets, rather than the sets themselves.

Question. Without AC, is every countable increasing chain of almost-equality equivalence classes of co-infinite sets bounded by another such class?

You seem to need countable choice to pick the representatives.

This question arose in a comment on another question.

$\endgroup$
7
  • 4
    $\begingroup$ I suspect that no. Suppose that we add Cohen reals, $r_n$ for $n<\omega$, and we do not add the set $\{r_n\mid n<\omega\}$, but yet, "somehow" we do get the set $\{[r_n]_T\mid n<\omega\}$ (e.g., preserve $[r_n]_{\rm fin}$ from which you can define $[r_n]_T$). If there's an upper bound, then you should be able to uniformly compute all the reals, but there is no single real which computes all of them. $\endgroup$ – Asaf Karagila Apr 19 at 16:26
  • 2
    $\begingroup$ Yes, I had a similar idea, but I was stumped at the "somehow" part. $\endgroup$ – Joel David Hamkins Apr 19 at 16:53
  • $\begingroup$ I think preserving the sequence of $[r_n]_{\text{fin}}$ is a good idea. $\endgroup$ – Joel David Hamkins Apr 19 at 17:06
  • $\begingroup$ Yes, because $[r_n]_T = \bigcup\{[r]_T\mid r\sim_{\rm fin} r_n\}$. $\endgroup$ – Asaf Karagila Apr 19 at 17:17
  • 2
    $\begingroup$ Yes, of course. It is very straightforward. I'll write an answer. $\endgroup$ – Asaf Karagila Apr 19 at 17:31
12
$\begingroup$

No. It is quite possible to get a counterexample, even without having the reals as a countable union of countable sets. Indeed, we only need to add $\omega$ Cohen reals in order to find such a symmetric extension!

Let's first make a small observation:

Suppose that there is a sequence of equivalence classes mod-finite without a choice function, then there is a countable family of Turing degrees without an upper limit.

Proof. Note that if $\{a_n\mid n<\omega\}$ is the family of equivalence classes mod finite, then for every $a\in a_n$, $[a]_T=\bigcup\{[a']_T\mid a'\in a_n\}$. This is because $\sim_{\rm fin}$ is a refinement of $\sim_T$.

If we had an upper bound to these Turing degrees, let $t$ be a representative, then we can now use $t$ to compute a representative from each $a_n$ by simply finding the smallest program that produces a representative with $t$ as an oracle. $\square$

Therefore, it is enough to find a model where there is a countable sequence of such equivalence classes. For example, if we add $\omega$ Cohen reals, $r_n$, and forget $\langle r_n\mid n<\omega\rangle$, while preserving $\langle [r_n]_{\rm fin}\rangle$. So let's construct a symmetric extension in which this happens.

The idea is as follows: find out how to change each Cohen real on a finite set in an arbitrary fashion, then consider permutations that do exactly that on each of them, separately, and without changing the indices of your newly found Cohen reals; and take a good notion of finite support to generate your filter of subgroups.


We force with $\operatorname{Add}(\omega,\omega)$, so a condition is a finite partial function $p\colon\omega\times\omega\to2$. We denote by $\dot r_n$ the name of the $n$th real, $\{\langle p,\check m\rangle\mid p(n,m)=1\}$.

Now we consider the group of automorphisms of $\operatorname{Add}(\omega,\omega)$ given by $\prod B_{\rm fin}$ or $\bigoplus B_{\rm fin}$, where $B_{\rm fin}$ is the group of "finite bit flips" on each coordinates. That is, if $\sigma\in B_{\rm fin}$, then there is some finite set $X\subseteq\omega$ such that: $$\sigma p(m)=\begin{cases}1-p(m) & m\in X\\ p(m) & m\notin X\end{cases}$$ so we can write $\sigma=\sigma_X$ in this case.

Now, $\pi$ is in our group, let's denote it by $\scr G$, if $\pi\colon\omega\to B_{\rm fin}$, and $$\pi p(n,m) = \pi(n) p(n,m).$$ That is, $\pi$ acts on each coordinate separately with an automorphism from $B_{\rm fin}$. So we can write $\pi_n$ instead of $\pi(n)$, and if we write $\pi_n=\sigma_X$ then it is clear now what we mean by that.

For this construction it doesn't matter if we use $\prod$ or $\bigoplus$, the latter is countable and absolute so it has some nicer properties overall.

Finally, the filter of subgroups is given by finite supports: for $E\subseteq\omega$ we denote by $\operatorname{fix}(E)=\{\pi\in\mathscr G\mid\forall n\in E,\pi_n=\operatorname{id}\}$; now define $\scr F$ as the filter of subgroups generated by $\{\operatorname{fix}(E)\mid E\in[\omega]^{<\omega}\}$.

If $\dot x$ is a hereditarily symmetric name, then we say that $E$ is a support for $\dot x$ when every $\pi\in\operatorname{fix}(E)$ satisfies $\pi\dot x=\dot x$.

Claim. For each $n$, $\dot r_n$ is hereditarily symmetric.

Proof. $\{n\}$ is a support for $\dot r_n$. $\square$

Claim. For each $n$, $[\dot r_n]_{\rm fin}$ is hereditarily symmetric.

Proof. Note that every real in $[\dot r_n]_{\rm fin}$ has a name of the form $\pi\dot r_n$ for some $\pi\in\scr G$, and indeed, if $\pi\in\scr G$, then $1\Vdash\pi\dot r_n\sim_{\rm fin}\dot r_n$. Therefore $[\dot r_n]_{\rm fin}$ has a canonical name: $\{\pi\dot r_n\mid n<\omega\}^\bullet$.

Therefore for every $\pi\in\scr G$ and every $n<\omega$, $\pi[\dot r_n]_{\rm fin}=[\dot r_n]_{\rm fin}$. $\square$

Corollary. The sequence $\langle[\dot r_n]_{\rm fin}\mid n<\omega\rangle^\bullet$ is also hereditarily symmetric. $\square$

Finally, we show that there is no choice function.

Proposition. $1\Vdash^{\rm HS}\{[\dot r_n]_{\rm fin}\mid n<\omega\}^\bullet$ does not have a choice function.

Proof. Suppose that $\dot f$ is a hereditarily symmetric name and $p$ forces that its domain is the above family. Let $E$ be a support for $\dot f$, and let $n\notin E$.

Suppose that $q\leq p$ was a condition such that $q\Vdash\dot f([\dot r_n])=\dot x$, by extending $q$ if necessary, we may assume that $\dot x$ is actually $\tau\dot r_n$ for some $\tau\in\scr G$: all we need to do is find out what is that finite difference. Moreover, we can assume that $\tau_k=\operatorname{id}$ for all $k\neq n$, since the only coordinate that can change anything about $\dot r_n$ is $n$ itself.

But now take some very large $m$ such that $\langle n,m\rangle\notin\operatorname{dom}q$, and simply consider $\pi$ for which: $\pi_n=\sigma_\{m\}$ and for all other $k$, $\pi_k=\operatorname{id}$. We now have that:

  1. $\pi q=q$, since no information inside the condition was changed.
  2. $\pi\in\operatorname{fix}(E)$, since $n\notin E$.

By combining with the information from the claims we have that $$q\Vdash\dot f([\dot r]_{\rm fin})=\tau\dot r_n\iff\pi q\Vdash\pi\dot f(\pi[\dot r_n]_{\rm fin})=\pi\tau\dot r_n\iff q\Vdash\dot f([\dot r_n]_{\rm fin})=\tau\pi\dot r_n.$$

But we also know that $1\Vdash\tau\pi\dot r_n\neq\dot r_n$, since the two must disagree on whether $m$ is inside or outside!

Therefore, if no extension of $p$ can force that $\dot f$ is a choice function, so $p$ must force that $\dot f$ is not a choice function. But that means that no condition can force that any name is choice function, and therefore we proved the statement of the proposition. $\square$


Let me also add that this can be simplified even further when considering iterations of symmetric extensions and improper filters of groups, since we can now just consider the whole thing an iteration of length $\omega$, with finite support of course, where at each step we have some finitary permutation, but as long as finite steps are taken, we are allowed to use the trivial subgroup in our filter.

The limit step does all the work for us in this case! In fact, this exact example appears as a toy example for iterating symmetric extensions in my first paper on the topic:

Karagila, Asaf, Iterating symmetric extensions, J. Symb. Log. 84, No. 1, 123-159 (2019). ZBL1448.03038.

$\endgroup$
4
  • $\begingroup$ In the proof of the small observation, I feel more should be said. The point is that if you had an upper bound for the mod-finite classes, then you could fix a representative, and use that to choose least-programs producing a suitable set in the nth Turing degree from that oracle. So the point isn't just that mod-finite refines T, but also that we have a uniform manner of enumerating any Turing degree from any upper bound. $\endgroup$ – Joel David Hamkins Apr 19 at 18:36
  • $\begingroup$ That's a good point. $\endgroup$ – Asaf Karagila Apr 19 at 18:36
  • $\begingroup$ Would it help if instead of the finitary bit flips we take computable functions so that instead of going through the finite equivalence classes, we'll go directly to the Turing degrees? This only works if the Turing degree of $x$ is exactly the result of computable almost-permutations on $x$. But that seems like that should be true. $\endgroup$ – Asaf Karagila Apr 19 at 18:40
  • $\begingroup$ I think it is good to concentrate the issue on mod-finite. $\endgroup$ – Joel David Hamkins Apr 19 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.