日記 (2025 年 12 月 24 日)
今回は、 関数ではなく関係に焦点を当てる。
ここで、 数学における (特に自然数の間の) 関係について思い出しておこう。
自然数上の k 項関係とは、 素朴には k 個の自然数の組に対して真偽が定まっている式のことだが、 これは直積の部分集合 P⊆k として定式化できるのであった。
この見方では、 ある x が P を満たすとは x∈P が成り立つことである。
そこで以降は、 x が P を満たすことを x∈P と書いたり P(x) と書いたりする。
さて、 関係からは 「特性関数」 と呼ばれる関数を作ることができ、 両者は同一視できるのであった。
定義を確認しておこう。
定義 3.1.
関係 P⊆k に対して、 全域関数 chP:k→ を
chP(x):={ 1 (x∈P) 0 (x∉P)
で定義する。
これを P の 「特性関数 (characteristic function)」 という。
そこで今後は、 関係とその特性関数を同一視して、 関数に対する用語をそのまま関係にも適用することにする。
例えば、 関係が原始再帰的であるとは、 その特性関数が原始再帰的であることを意味する。
では、 原始再帰的な関係の例をいくつか挙げていこう。
まずは、 与えられた自然数が 0 であるかもしくは正であるかを判定する関係を見る。
命題 3.2.
関係 Zero,Pos⊆ を
x∈Zero :⟺ x=0 x∈Pos :⟺ x>0
で定めると、 これは原始再帰的である。
証明.
chZero と chPos が原始再帰的であることを示せば良い。
chZero については、
chZero(x):={ 1 (x=0) 0 (x>0)
と書けるが、 これは
chZero(0) = 1 chZero(x+1) = 0
という原始再帰の形で表せる。
したがって、 chZero は原始再帰的である。
chPos については、
chPos(x)={ 0 (x=0) 1 (x>0)
であるから、 ほぼ上記と同様に、
chPos(0) = 0 chPos(x+1) = 1
という原始再帰の形で表せる。
したがって、 chPos も原始再帰的である。
ところで、 この証明に出てきた chPos は、 1 以上の引数を 1 に潰して返す関数と見なせる。
これは特性関数を扱う上で便利なので、 sgn という名前を与えておくことにする。
すなわち、
sgn(x)={ 0 (x=0) 1 (x>0)
である。
次に、 関係の原始再帰性が基本的な集合演算で閉じていることを示す。
まずは、 補集合, 共通集合, 和集合をとるという操作について考える。
なお、 ここでは補集合を ∁ で表す。
命題 3.3.
関係 P⊆k をとる。
P が原始再帰的ならば、 ∁P も原始再帰的である。
証明.
chZero が引数の 0 と 1 を反転することに注目すれば、 ch∁P は、
ch∁P(x)=chZero(chP(x))
と書けることが分かる。
命題 3.2 より chZero は原始再帰的であるから、 chP が原始再帰的ならば ch∁P も原始再帰的である。
命題 3.4.
関係 P,Q⊆k をとる。
P と Q がともに原始再帰的ならば、 P∩Q と P∪Q も原始再帰的である。
証明.
chP∩Q は、
chP∩Q(x)=chP(x)×chQ(x)
と書ける。
命題 2.9 より × は原始再帰的であるから、 chP と chQ が原始再帰的ならば chP∩Q も原始再帰的である。
chP∪Q については、 前に述べた sgn を用いることで、
chP∪Q(x)=sgn(chP(x)+chQ(x))
と書けることが分かる。
すなわち、 chP∪Q は chP, chQ, +, sgn の合成である。
命題 2.8 と命題 3.2 により + と sgn がそれぞれ原始再帰的であることが分かっているので、 chP と chQ が原始再帰的ならば chP∪Q も原始再帰的である。
次に、 量化子をとる操作について考えるが、 一般の量化に対しては原始再帰性は保たれない。
ただし、 量化の上界を制限すれば原始再帰性は保たれる。
命題 3.5.
関係 P⊆k+1 に対し、 関係 ∀P,∃P⊆k+1 を
(x,y)∈∀P :⟺ ∀t<yP(x,t) (x,y)∈∃P :⟺ ∃t<yP(x,t)
で定める。
P が原始再帰的ならば、 ∀P と ∃P も原始再帰的である。
証明.
ch∀P と ch∃P は、
ch∀P(x,y) = t<ychP(x,t) ch∃P(x,y) = sgn(t<ychP(x,t)(
と書ける。
命題 2.12 と命題 3.2 により、 chP が原始再帰的ならば ch∀P と ch∃P も原始再帰的である。
このくらい準備をしておくと、 自然数に関する様々な性質が原始再帰的であることが分かる。
まず、 与えられた 2 つの自然数の比較は原始再帰的である。
命題 3.6.
各種の比較関係 ≤,<,≥,>⊆2 は原始再帰的である。
証明.
まず ch≤ と ch≥ については、 それぞれ
ch≤(x,y) = chZero(x∸y) ch≥(x,y) = chZero(y∸x)
と書けるから、 命題 2.11 と命題 3.2 によって原始再帰的である。
また、 < と > はそれぞれ ≥ と ≤ の補集合であるから、 命題 3.3 によって原始再帰的である。
命題 3.7.
等号関係 =⊆2 は原始再帰的である。
これらを応用すれば、 例えば整除関係が原始再帰的であることも分かる。
命題 3.8.
関係 ∣⊆2 を
x∣y:⟺x は y をわり切る
で定めると、 これは原始再帰的である。
証明.
まず、 わり切ることの定義から、
x∣y⟺∃q(y=q·x)
である。
しかし、 このような q が存在するなら y 以下であるから、 q を y+1 未満に制限しても良い。
すなわち、
x∣y⟺∃q<y+1(y=q·x)
が成り立つ。
この右辺にある式は積, 等号, 和, (上限付き) 量化の組み合わせだが、 これらの操作は命題 2.9, 命題 3.7, 命題 2.8, 命題 3.5 によって全て原始再帰的だから、 上記の関係全体も原始再帰的であることが分かる。
前回と今回で見てきたように、 原始再帰的な範囲内でかなり様々な関数や性質を表現することができる。
次回は、 さらに多くのことが可能なことを見ていこう。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press