The Arithmetic Hierarchy
Some loose
notes
A
formula
is called:
Δ
0
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Delta_0
Δ
0
,
Σ
0
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_0
Σ
0
, or
Π
0
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Pi_0
Π
0
if it contains only
bounded
quantifiers
Σ
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_n
Σ
n
if it contains a string of existentials followed by a
Π
n
−
1
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Pi_{n{-1}}
Π
n
−
1
formula
Π
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Pi_n
Π
n
if it contains a string of universals followed by a
Σ
n
−
1
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_{n{-1}}
Σ
n
−
1
formula
Δ
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Delta_n
Δ
n
if it is in
Σ
n
∩
Π
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_n \cap \Pi_n
Σ
n
∩
Π
n
A
set
A
⊆
N
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A \subseteq \bb N
A
⊆
N
is called:
Σ
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_n
Σ
n
if there is a
computable
relation
R
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} R
R
over which
A
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A
A
is
Σ
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_n
Σ
n
-
definable
; ie,
x
∈
A
⟺
∃
v
1
∀
v
2
⋯
R
(
v
1
,
v
2
,
…
)
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} x \in A \iff \exists v_1 \forall v_2 \cdots\ R(v_1, v_2, \dots)
x
∈
A
⟺
∃
v
1
∀
v
2
⋯
R
(
v
1
,
v
2
,
…
)
Likewise for
Π
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Pi_n
Π
n
And
Δ
n
=
Σ
n
∩
Π
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Delta_n = \Sigma_n \cap \Pi_n
Δ
n
=
Σ
n
∩
Π
n
Say
A
≤
T
B
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A \leq_T B
A
≤
T
B
if the
characteristic function
1
A
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} 1_A
1
A
can be computed
relative to
an oracle for
B
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} B
B
If
A
⊆
N
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A \subseteq \bb N
A
⊆
N
, its
turing jump
A
′
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A'
A
′
is
defined
to be
A
′
=
{
n
:
φ
n
A
(
n
)
↓
}
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A' = \{ n : \varphi^A_n(n)\downarrow \}
A
′
=
{
n
:
φ
n
A
(
n
)
↓
}
where
φ
(
−
)
A
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \varphi^A_{(-)}
φ
(
−
)
A
enumerates the programs
definable
relative to
an oracle for
A
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A
A
Always
X
<
T
X
′
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} X <_T X'
X
<
T
X
′
Say a
set
A
⊆
N
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A \subseteq \bb N
A
⊆
N
is
Σ
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_n
Σ
n
-
complete
if for every
Σ
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_n
Σ
n
set
B
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} B
B
we have
B
≤
m
A
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} B \leq_m A
B
≤
m
A
A
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A
A
is
Σ
n
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \Sigma_n
Σ
n
-
complete
iff
A
≡
T
∅
(
n
)
% shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } % category names \newcommand{\cat}[1]{{ \sf{#1} }} % more shorthands \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} A \equiv_T \varnothing^{(n)}
A
≡
T
∅
(
n
)