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](https://mathoverflow.net/questions/390494/applications-of-zorn-s-lemma-that-aren-t-chain-complete-directed-complete/390519#comment995269_390519).



Does every countable set of Turing degrees have an upper bound, without AC?
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**](http://dx.doi.org/10.1017/jsl.2018.73), J. Symb. Log. 84, No. 1, 123-159 (2019). [ZBL1448.03038](https://zbmath.org/?q=an:1448.03038).
> 
> 
> 


