ナンバリング (計算可能性理論)
全てのナンバリングからなる集合には半順序付けが存在する。 いま
ν 1 :⊆ N → S 1 {\displaystyle \nu _{1}:\subseteq \mathbb {N} \to S_{1}}
と
ν 2 :⊆ N → S 2 {\displaystyle \nu _{2}:\subseteq \mathbb {N} \to S_{2}}
を2つのナンバリングとする。このとき ν 1 {\displaystyle \nu _{1}} が ν 2 {\displaystyle \nu _{2}} に還元可能 ν 1 ≤ ν 2 {\displaystyle \nu _{1}\leq \nu _{2}} とは、
∃ f ∈ P ( 1 ) ∀ i ∈ D o m a i n ( ν 1 ) : ν 1 ( i ) = ν 2 ∘ f ( i ) {\displaystyle \exists f\in \mathbf {P} ^{(1)}\,\forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i)}
が成り立つときをいう。
もし ν 1 ≤ ν 2 {\displaystyle \nu _{1}\leq \nu _{2}} かつ ν 1 ≥ ν 2 {\displaystyle \nu _{1}\geq \nu _{2}} ならば ν 1 {\displaystyle \nu _{1}} は ν 2 {\displaystyle \nu _{2}} と同値といい、これを ν 1 ≡ ν 2 {\displaystyle \nu _{1}\equiv \nu _{2}} と書く。
ナンバリングが全域的とはそれが全域関数であることをいう。もしナンバリングの定義域が帰納的可算ならば、同値な全域的ナンバリングが存在する(ナンバリングの同値性は後で定義される)。
ナンバリング η が決定可能とは集合 { ( x , y ) : η ( x ) = η ( y ) } {\displaystyle \{(x,y):\eta (x)=\eta (y)\}} が決定可能であることをいう。
ナンバリング η が一価とは η(x) = η(y) と x=y が同値であるときにいう。換言すれば η が単射であるときにいう。部分計算可能関数の一価ナンバリングはフリードバーグ・ナンバリングと呼ばれる。