Skip to main content
added 425 characters in body
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

A group $G$ that can't be isomorphic to Aut($\mathcal D$) is the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$, whereLet $p_i$ denotesdenote the $i$th prime number, and wherelet $B$ has$\oplus$ be the recursive join on $\omega$. Let $\mathcal O$ be Kleene's $\Pi^1_1$-complete set and $\mathcal O'$ its Turing degree not below a given presentation of Aut($\mathcal D$)jump. 

For Richterany $B$, in her famous paperlet $G_B$ be the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$. So $G_B$ is a countably infinite abelian group.

I claim that

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 Aut(1981$\mathcal D$). is not isomorphic to ZBL0512.03024$G_B$ with $B=\mathcal O'$.

showedI'll show this by showing that Aut($\mathcal D$) has a presentation which is recursive in $G=G_B$$\mathcal O$, hence not $\ge_T B$. This will suffice because Richter, in her famous paper,

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 (1981). ZBL0512.03024.

showed that for all $B$, $G_B$ has isomorphism type of degree $[B]_T$, i.e., all presentations of $G_B$ have degree $\ge_T B$.

So to answer your question it remains to find a $B$ such that Aut($\mathcal D$) has a presentation that's $\not\ge_T B$.

Note that if Aut($\mathcal D$) is finite then it is not isomorphic to $G_B$ for any $B$, since the latter is countably infinite. So assume Aut($\mathcal D$) is infinite.

Slaman and Woodin showed that each automorphism $\pi$ of $\mathcal D$ is represented by an arithmetic function in the sense that there is an $n_0$ such that for all $\pi$ and all $X$, $\pi([X]_T)= [P(X)]_T$ where $P(X)=\{e\}({X^{(n_0)}})$.

Now we consider the necessary questions about numbers $e$ in order to present Aut($\mathcal D$). We let $E=\{e_0<e_1<e_2<\dots\}$ be the set of those $e$ for which $P_e$ given by $X\mapsto \{e\}^{X^{(n_0)}}$ is an arithmetic representation of some automorphism.

TheWe claim that the set $E$ is $\Pi^1_2$$\Pi^1_1$: \begin{equation} \forall A(P_e(A)\text{ is total}) \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)), \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} \begin{equation} \forall A\exists B(P(B)\equiv_T A), \end{equation} (ActuallyFirst, I think this canlet $F$ be reduced tothe $\Pi^1_1$ or a coupleset of jumps thereof: we can check whether there is another injective $e_j$ such that both compositions $e_i*e_j$,all $e_j*e_i$ are the identity.)$e$ for which \begin{equation} \forall A(P_e(A)\text{ is total}), \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)),\text{ and } \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} Then $$E=\{e: e\in F\text{ and }(\exists d\in F) \forall A(P_d(P_e(A))\equiv_T A\text{ and }P_d(P_e(A))\equiv_T A)\}.$$

The multiplication is given by defining $*$ by $$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2}. $$$$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2} $$ which is equivalent to $$\forall A\forall B\forall C(B=P_{e_2}(A)\text{ and }C=P_{e_1}(B)\to C=P_{e_1*e_2}(A))$$ We also have to mod out by equality of the automorphisms induced by $e_1$ and $e_2$, which we check by: $$ e_1 \sim e_2 \iff \forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$$$\forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$ Overall, takingwe get a subset of $B$ to be$\omega$ recursive in the $C^{(\omega)}$ where$\Pi^1_1$-complete set Kleene's $C$$\mathcal O$, with an $\mathcal O$-recursive group operation. This is athen isomorphic to all of $\Pi^1_2$$\omega$ with an $\mathcal O$-complete set sufficesrecursive group operation, as desired.

A group $G$ that can't be isomorphic to Aut($\mathcal D$) is the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$, where $p_i$ denotes the $i$th prime number, and where $B$ has Turing degree not below a given presentation of Aut($\mathcal D$). For Richter, in her famous paper

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 (1981). ZBL0512.03024.

showed this $G=G_B$ has isomorphism type of degree $[B]_T$, i.e., all presentations of $G_B$ have degree $\ge_T B$.

So to answer your question it remains to find a $B$ such that Aut($\mathcal D$) has a presentation that's $\not\ge_T B$.

Note that if Aut($\mathcal D$) is finite then it is not isomorphic to $G_B$ for any $B$, since the latter is countably infinite. So assume Aut($\mathcal D$) is infinite.

Slaman and Woodin showed that each automorphism $\pi$ of $\mathcal D$ is represented by an arithmetic function in the sense that there is an $n_0$ such that for all $\pi$ and all $X$, $\pi([X]_T)= [P(X)]_T$ where $P(X)=\{e\}({X^{(n_0)}})$.

Now we consider the necessary questions about numbers $e$ in order to present Aut($\mathcal D$). We let $E=\{e_0<e_1<e_2<\dots\}$ be the set of those $e$ for which $P_e$ given by $X\mapsto \{e\}^{X^{(n_0)}}$ is an arithmetic representation of some automorphism.

The set $E$ is $\Pi^1_2$: \begin{equation} \forall A(P_e(A)\text{ is total}) \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)), \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} \begin{equation} \forall A\exists B(P(B)\equiv_T A), \end{equation} (Actually, I think this can be reduced to $\Pi^1_1$ or a couple of jumps thereof: we can check whether there is another injective $e_j$ such that both compositions $e_i*e_j$, $e_j*e_i$ are the identity.)

The multiplication is given by defining $*$ by $$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2}. $$ We also have to mod out by equality, which we check by: $$ e_1 \sim e_2 \iff \forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$ Overall, taking $B$ to be $C^{(\omega)}$ where $C$ is a $\Pi^1_2$-complete set suffices.

Let $p_i$ denote the $i$th prime number, and let $\oplus$ be the recursive join on $\omega$. Let $\mathcal O$ be Kleene's $\Pi^1_1$-complete set and $\mathcal O'$ its Turing jump. 

For any $B$, let $G_B$ be the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$. So $G_B$ is a countably infinite abelian group.

I claim that

Aut($\mathcal D$) is not isomorphic to $G_B$ with $B=\mathcal O'$.

I'll show this by showing that Aut($\mathcal D$) has a presentation which is recursive in $\mathcal O$, hence not $\ge_T B$. This will suffice because Richter, in her famous paper,

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 (1981). ZBL0512.03024.

showed that for all $B$, $G_B$ has isomorphism type of degree $[B]_T$, i.e., all presentations of $G_B$ have degree $\ge_T B$.

Note that if Aut($\mathcal D$) is finite then it is not isomorphic to $G_B$ for any $B$, since the latter is countably infinite. So assume Aut($\mathcal D$) is infinite.

Slaman and Woodin showed that each automorphism $\pi$ of $\mathcal D$ is represented by an arithmetic function in the sense that there is an $n_0$ such that for all $\pi$ and all $X$, $\pi([X]_T)= [P(X)]_T$ where $P(X)=\{e\}({X^{(n_0)}})$.

Now we consider the necessary questions about numbers $e$ in order to present Aut($\mathcal D$). We let $E=\{e_0<e_1<e_2<\dots\}$ be the set of those $e$ for which $P_e$ given by $X\mapsto \{e\}^{X^{(n_0)}}$ is an arithmetic representation of some automorphism.

We claim that the set $E$ is $\Pi^1_1$: First, let $F$ be the $\Pi^1_1$ set of all $e$ for which \begin{equation} \forall A(P_e(A)\text{ is total}), \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)),\text{ and } \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} Then $$E=\{e: e\in F\text{ and }(\exists d\in F) \forall A(P_d(P_e(A))\equiv_T A\text{ and }P_d(P_e(A))\equiv_T A)\}.$$

The multiplication is given by defining $*$ by $$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2} $$ which is equivalent to $$\forall A\forall B\forall C(B=P_{e_2}(A)\text{ and }C=P_{e_1}(B)\to C=P_{e_1*e_2}(A))$$ We also have to mod out by equality of the automorphisms induced by $e_1$ and $e_2$, which we check by: $$\forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$ Overall, we get a subset of $\omega$ recursive in the $\Pi^1_1$-complete set Kleene's $\mathcal O$, with an $\mathcal O$-recursive group operation. This is then isomorphic to all of $\omega$ with an $\mathcal O$-recursive group operation, as desired.

deleted 5 characters in body
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

A group $G$ that can't be isomorphic to Aut($\mathcal D$) is the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$, where $p_i$ denotes the $i$th prime number, and where $B$ has Turing degree not below a given presentation of Aut($\mathcal D$). For Richter, in her famous paper

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 (1981). ZBL0512.03024.

showed this $G=G_B$ has isomorphism type of degree $[B]_T$, i.e., all presentations of $G_B$ have degree $\ge_T B$.

So to answer your question it remains to find a $B$ such that Aut($\mathcal D$) has a presentation that's $\not\ge_T B$.

Note that if Aut($\mathcal D$) is finite then it is not isomorphic to $G_B$ for any $B$, since the latter is countably infinite. So assume Aut($\mathcal D$) is infinite.

Slaman and Woodin showed that each automorphism $\pi$ automorphism of $\mathcal D$ is represented by an arithmetic function in the sense that there is an $n_0$ such that for all $\pi$ and all $X$, $\pi([X]_T)= [P(X)]_T$ where $P(X)=\{e\}({X^{(n_0)}})$.

Now we consider the necessary questions about numbers $e$ in order to present Aut($\mathcal D$). We let $E=\{e_0<e_1<e_2<\dots\}$ be the set of those $e$ for which $P_e$ given by $X\mapsto \{e\}^{X^{(n_0)}}$ is an arithmetic representation of some automorphism.

The set $e\in E$$E$ is $\Pi^1_2$: \begin{equation} \forall A(P_e(A)\text{ is total}) \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)), \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} \begin{equation} \forall A\exists B(P(B)\equiv_T A), \end{equation} (Actually, I think this can be reduced to $\Pi^1_1$ or a couple of jumps thereof: we can check whether there is another injective $e_j$ such that both compositions $e_i*e_j$, $e_j*e_i$ are the identity.)

The multiplication is given by defining $*$ by $$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2}. $$ We also have to mod out by equality, which we check by: $$ e_1 \sim e_2 \iff \forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$ Overall, taking $B$ to be $C^{(\omega)}$ where $C$ is a $\Pi^1_2$-complete set suffices.

A group $G$ that can't be isomorphic to Aut($\mathcal D$) is the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$, where $p_i$ denotes the $i$th prime number, and where $B$ has Turing degree not below a given presentation of Aut($\mathcal D$). For Richter, in her famous paper

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 (1981). ZBL0512.03024.

showed this $G=G_B$ has isomorphism type of degree $[B]_T$, i.e., all presentations of $G_B$ have degree $\ge_T B$.

So to answer your question it remains to find a $B$ such that Aut($\mathcal D$) has a presentation that's $\not\ge_T B$.

Note that if Aut($\mathcal D$) is finite then it is not isomorphic to $G_B$ for any $B$, since the latter is countably infinite. So assume Aut($\mathcal D$) is infinite.

Slaman and Woodin showed that each $\pi$ automorphism of $\mathcal D$ is represented by an arithmetic function in the sense that there is an $n_0$ such that for all $\pi$ and all $X$, $\pi([X]_T)= [P(X)]_T$ where $P(X)=\{e\}({X^{(n_0)}})$.

Now we consider the necessary questions about numbers $e$ in order to present Aut($\mathcal D$). We let $E=\{e_0<e_1<e_2<\dots\}$ be the set of those $e$ for which $P_e$ given by $X\mapsto \{e\}^{X^{(n_0)}}$ is an arithmetic representation of some automorphism.

The set $e\in E$ is $\Pi^1_2$: \begin{equation} \forall A(P_e(A)\text{ is total}) \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)), \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} \begin{equation} \forall A\exists B(P(B)\equiv_T A), \end{equation} (Actually, I think this can be reduced to $\Pi^1_1$ or a couple of jumps thereof: we can check whether there is another injective $e_j$ such that both compositions $e_i*e_j$, $e_j*e_i$ are the identity.)

The multiplication is given by defining $*$ by $$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2}. $$ We also have to mod out by equality, which we check by: $$ e_1 \sim e_2 \iff \forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$ Overall, taking $B$ to be $C^{(\omega)}$ where $C$ is a $\Pi^1_2$-complete set suffices.

A group $G$ that can't be isomorphic to Aut($\mathcal D$) is the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$, where $p_i$ denotes the $i$th prime number, and where $B$ has Turing degree not below a given presentation of Aut($\mathcal D$). For Richter, in her famous paper

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 (1981). ZBL0512.03024.

showed this $G=G_B$ has isomorphism type of degree $[B]_T$, i.e., all presentations of $G_B$ have degree $\ge_T B$.

So to answer your question it remains to find a $B$ such that Aut($\mathcal D$) has a presentation that's $\not\ge_T B$.

Note that if Aut($\mathcal D$) is finite then it is not isomorphic to $G_B$ for any $B$, since the latter is countably infinite. So assume Aut($\mathcal D$) is infinite.

Slaman and Woodin showed that each automorphism $\pi$ of $\mathcal D$ is represented by an arithmetic function in the sense that there is an $n_0$ such that for all $\pi$ and all $X$, $\pi([X]_T)= [P(X)]_T$ where $P(X)=\{e\}({X^{(n_0)}})$.

Now we consider the necessary questions about numbers $e$ in order to present Aut($\mathcal D$). We let $E=\{e_0<e_1<e_2<\dots\}$ be the set of those $e$ for which $P_e$ given by $X\mapsto \{e\}^{X^{(n_0)}}$ is an arithmetic representation of some automorphism.

The set $E$ is $\Pi^1_2$: \begin{equation} \forall A(P_e(A)\text{ is total}) \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)), \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} \begin{equation} \forall A\exists B(P(B)\equiv_T A), \end{equation} (Actually, I think this can be reduced to $\Pi^1_1$ or a couple of jumps thereof: we can check whether there is another injective $e_j$ such that both compositions $e_i*e_j$, $e_j*e_i$ are the identity.)

The multiplication is given by defining $*$ by $$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2}. $$ We also have to mod out by equality, which we check by: $$ e_1 \sim e_2 \iff \forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$ Overall, taking $B$ to be $C^{(\omega)}$ where $C$ is a $\Pi^1_2$-complete set suffices.

Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

A group $G$ that can't be isomorphic to Aut($\mathcal D$) is the direct sum of $\mathbb Z/p_i\mathbb Z$ over all $i\in B\oplus\overline B$, where $p_i$ denotes the $i$th prime number, and where $B$ has Turing degree not below a given presentation of Aut($\mathcal D$). For Richter, in her famous paper

Richter, Linda Jean, Degrees of structures, J. Symb. Log. 46, 723-731 (1981). ZBL0512.03024.

showed this $G=G_B$ has isomorphism type of degree $[B]_T$, i.e., all presentations of $G_B$ have degree $\ge_T B$.

So to answer your question it remains to find a $B$ such that Aut($\mathcal D$) has a presentation that's $\not\ge_T B$.

Note that if Aut($\mathcal D$) is finite then it is not isomorphic to $G_B$ for any $B$, since the latter is countably infinite. So assume Aut($\mathcal D$) is infinite.

Slaman and Woodin showed that each $\pi$ automorphism of $\mathcal D$ is represented by an arithmetic function in the sense that there is an $n_0$ such that for all $\pi$ and all $X$, $\pi([X]_T)= [P(X)]_T$ where $P(X)=\{e\}({X^{(n_0)}})$.

Now we consider the necessary questions about numbers $e$ in order to present Aut($\mathcal D$). We let $E=\{e_0<e_1<e_2<\dots\}$ be the set of those $e$ for which $P_e$ given by $X\mapsto \{e\}^{X^{(n_0)}}$ is an arithmetic representation of some automorphism.

The set $e\in E$ is $\Pi^1_2$: \begin{equation} \forall A(P_e(A)\text{ is total}) \end{equation} \begin{equation} \forall A\forall B(A\le _T B\to P_e(A)\le_T P_e(B)), \end{equation} \begin{equation} \forall A\forall B(P(A)\equiv_T P(B)\to A\equiv_T B). \end{equation} \begin{equation} \forall A\exists B(P(B)\equiv_T A), \end{equation} (Actually, I think this can be reduced to $\Pi^1_1$ or a couple of jumps thereof: we can check whether there is another injective $e_j$ such that both compositions $e_i*e_j$, $e_j*e_i$ are the identity.)

The multiplication is given by defining $*$ by $$ P_{e_1* e_2} = P_{e_1}\circ P_{e_2}. $$ We also have to mod out by equality, which we check by: $$ e_1 \sim e_2 \iff \forall A (P_{e_1}(A)\equiv_T P_{e_2}(A))$$ Overall, taking $B$ to be $C^{(\omega)}$ where $C$ is a $\Pi^1_2$-complete set suffices.