プログラミングの基礎理論 第4回 自由に生成された集合と再帰的関数、暗黙に型付けられたラムダ計算

はじめに 帰納的閉包のさらなる理解のために、 自由に生成された集合 再帰的関数定義 について理解するのが良いので概要のみ紹介する。 自由に生成された集合 帰納的閉包 X = Ind(C, F)が以下の条件を満たすとき、「自由に生成された集合である」と言う。 任意の異なる関数fr(n),gr(m) ∈ Fに対して、fr(n)(X) ∩ gr(m)(X) = ∅ である。 1.1 つまり異なる関数を適用した結果の共通集合はなく、すなわち異なる関数を適用した結果はそれぞれ異なることを意味する 任意の関数fr(n) ∈ Fについて、fr(n)(X) ∩ C = ∅ である 2.1 つまり関数を適用した場合、定数Cを生成することはないことを意味する 任意の関数fr(n) ∈ Fについて、fr(n)|xn は単射関数である 3.1 fのXへの制限すなわち定義域をXに制限した集合{(a, b) | (a

[mitsuyoshi4]

かいた