型付きラムダ記法と、関連する問題 - (保存用) 檜山正幸のキマイラ飼育記メモ編

某N君に出した問題を掲載する。

「関数」と「写像」は（ここでは）完全に同義語、特に区別はしない。

ラムダ記法

写像 f:X→Y を、

λx∈X.( … :Y)

の形に書く。「…」の部分に、写像の働きを表す式が入る。

集合の直積〈direct product〉は、普通の掛け算記号'×'で表す。

A×B := {(a, b) | a∈A かつ b∈B}

複数の引数（変数）を持つ写像は、直積からの写像と考える。

λ(x, y)∈X×Y.( … :Z)
λ(x, y, z)∈X×Y×Z.( … :W)

写像の直列結合〈sequential composition | 順次結合〉は';'または' $\circ$ '、並列結合〈parallel composition〉は' $\otimes$ 'で表す。f:X→Y のとき、Xをfの域〈domain | 始域〉、Yをfの余域〈codomain | 終域〉と呼ぶ。次の書き方をする。

dom(f) = X
cod(f) = Y

id_Xは、集合X上の恒等写像〈identity map〉を表す。

id_X := λx∈X.(x :X)

逆写像

f:X→Y, g:Y→X に関して、g $\circ$ f = id_X かつ f $\circ$ g = id_Y が成立するとき、次のように言う。

fはgの逆写像〈inverse map〉である。
gはfの逆写像である。
fとgは互いに逆である。
fは可逆〈invertible〉である。
gは可逆である。

写像（関数）の定義が曖昧だと次の事実もちゃんとは言えない。

写像fに対して、fの逆写像が存在するとは限らない。
写像fに対して、fの逆写像が存在するなら、ただ1つだけ存在する。

練習問題1：上記の2番めの命題を証明せよ。

練習問題2：次のなかで可逆な写像はどれか？

λx∈R.(x² :R)
λt∈R.(-2t² + 5 :R)
λx∈R.(2x :R)
λx∈Z.(2x :Z)
λu∈R.(u³ :R)
λu∈N.(u³ :Z)
λθ∈R.(cos(θ) :R)
λφ∈R.(tan(φ) :R)
λx∈{t∈R | t≠0}.(1/x :R)
λs∈R(e^s :R) （eはネイピア数）

域と余域の制限

f:X→Y で、A⊆X とする。このとき、次のような写像を定義できる。

λx∈A.(f(x) :Y)

この写像を f|_A と書く。f|_Aは、fの域をAに制限したものである。Aは何でもかまわない。

B⊆Y のとき、

λx∈X.(f(x) :B)

は、定義できないときもある。

練習問題3：λx∈X.(f(x) :B) がうまく定義できないようなfとBの例を挙げよ。

λx∈X.(f(x) :B) がうまく定義できるときは、それをf|^Bと書く。f|^Bは、fの余域を制限したものである。

f|_A^Bは、fの域・余域ともに制限したものである。いつでも定義できるとは限らない。

練習問題4：練習問題2の可逆でない関数に対して、域・余域を適当に制限して可逆な関数を作れ。

制限のための部分集合は「適当に」選ぶので、できる可逆な関数は色々変わる。もともと可逆ではないので、人為的に可逆にする方法はいくらでもあり、優劣はない。

集合の集合

Xが集合のとき、Xのすべての部分集合からなる集合を、Xのベキ集合〈porwer set〉と呼び、Pow(X)と書く。

A∈Pow(X) ⇔ A⊆X

練習問題5： Pow({1, 2, 3}), Pow({1}), Pow({}) を求めよ（完全に書き出せ）。
練習問題6： Xが有限集合で、n個の要素を持つとき、Pow(X)は何個の要素を持つか？

Pow(X)から空集合を取り除いた集合をPow₊(X)と書くことにする（ここだけの記法）。0でない自然数をN₊と書くことにする（ここだけの記法）。

Pow₊(X) := {A∈Pow(X) | Aは空ではない}
N₊ := {k∈N | kは0ではない}

写像minを次のように定義する。

min := λA∈Pow₊(N).(Aのなかで最小の自然数 :N)

練習問題7： min({10, 20, 30]), min(偶数), min(奇数) を求めよ。
練習問題8： minは可逆か？

Mul（multiplesのつもり）を次のように定義する。

Mul := λn∈N₊.(nの倍数の集合、ただし0は除く :Pow(N))

練習問題9： Mulは可逆か？
練習問題10： Mulの余域を制限することにより、可逆な写像を作りなさい。