ナンバリングの比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/30 14:17 UTC 版)
「ナンバリング (計算可能性理論)」の記事における「ナンバリングの比較」の解説
全てのナンバリングからなる集合には半順序付けが存在する。 いま ν 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}} と書く。
※この「ナンバリングの比較」の解説は、「ナンバリング (計算可能性理論)」の解説の一部です。
「ナンバリングの比較」を含む「ナンバリング (計算可能性理論)」の記事については、「ナンバリング (計算可能性理論)」の概要を参照ください。
- ナンバリングの比較のページへのリンク
