自然数の部分集合
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:32 UTC 版)
二つの集合 A , B ⊆ N {\displaystyle A,B\subseteq \mathbb {N} } があるとする。何らかの全体計算可能関数 f {\displaystyle f} が存在して A = f − 1 [ B ] {\displaystyle A=f^{-1}[B]} であるとき、 A {\displaystyle A} は B {\displaystyle B} に多対一還元可能であると言い、次のように書く。 A ≤ m B . {\displaystyle A\leq _{m}B.} これに加えて f {\displaystyle f} が単射である場合、 A {\displaystyle A} は B {\displaystyle B} に1-還元可能であると言い、次のように書く。 A ≤ 1 B . {\displaystyle A\leq _{1}B.}
※この「自然数の部分集合」の解説は、「多対一還元」の解説の一部です。
「自然数の部分集合」を含む「多対一還元」の記事については、「多対一還元」の概要を参照ください。
ウィキペディア小見出し辞書の「自然数の部分集合」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 自然数の部分集合のページへのリンク
