型理論

型理論（かたりろん、英: Type theory）は、集合論を数学基礎論の観点から代替する目的で提唱された理論である。階型理論（かいけいりろん、英: Theory of Types）とも呼ばれる。型理論は一般的に計算機科学およびコンピュータプログラミング分野で重視されている型システムの正当性を裏付ける学術研究として認知されている。バートランド・ラッセルが自身のパラドックスによって発見したフレーゲの素朴集合論が抱える問題点を説明するために構築したのが型理論の始まりであり、その詳細はホワイトヘッドとラッセルの 『プリンキピア・マテマティカ』に収録されている。現在の型理論の中でよく知られているものは、アロンゾ・チャーチによる型付きラムダ計算と、マルティン・レーフによる直感的型理論の二つである。型理論は数学基礎論または数理論理学で扱われる分野と見なされているが、取り分けコンピュータプログラミング分野の型システムと密接に関連して相互に発展してきたという背景を持つ。型理論の実用例と言える型システムは、計算式内の各タームに「型」を持たせてターム間の計算可能性を定義するための形式体系である。

単純階型理論（Simple Theory of Types）

ここでは、Mendelson (1997, 289-293）の体系 ST を解説する。量化の議論領域は型の階層に分けられ、個体要素（individuals）には型が割り当てられる。基盤となる論理は一階述語論理であり、量化変数の範囲は型によって限定される。ST は『数学原理』の型理論に比べて単純であり、任意の関係の議論領域は全て同じ型でなければならない。

階層中、最も低い型では、個体要素にはメンバーはなく、それらは2番目に低い型のメンバーとなる。最下層の型の個体要素は、ある集合論の原要素（Ur-elements）に対応する。それぞれの型にはより高位の型があり、ペアノの公理の後者関数（successor function）の記法にも似ている。ST では最高位の型があるかどうかは規定していない。超限数個の型があってもなんら不都合は生じない。このようにペアノの公理と似た性質であるため、各型に自然数を割り当てることが容易で、最下層の型に 0 を割り当てる。ただし、型理論そのものは自然数の定義を前提とはしていない。

ST に固有な記号として、プライム付きの変数と接中辞 ∈ がある。論理式において、プライムのない変数は全て同じ型に属し、プライム付き変数（x' )はその1つ上の型に属する。ST の原子論理式は、x=y （恒等式）か y∈x ’ という形式である。接中辞記号 ∈ は、集合の包含関係を示唆している。

以下にあげる公理に使われている変数は、全て2つの連続する型のいずれかに属する。プライムなしの変数は低位の型の変数であり、'∈' の左辺にのみ出現する（プライムつきは逆）。ST での一階述語論理では、型をまたいだ量化ができない。従って、ある型とそれに隣接する型ごとに外延性と内包性の公理を定義する必要が出てくるが、下記の外延性と内包性の公理を型をまたいで成り立つ公理型（axiom schema）とすればよい。

• 同一性: x=y ↔ ∀z’ [x∈z’ ↔ y∈z’]
• 外延性: ∀x[x∈y’ ↔ x∈z’] → y’=z’

ここで、自由変項 x を含む任意の一階述語論理式を Φ(x) で表すものとする。

• 内包性: ∃z’∀x[x∈z’ ↔ Φ(x)]

注意: 同じ型の要素を集めたものは次のレベルの型のオブジェクトを形成する。内包性は型に関する公理というだけでなく、Φ(x) の公理でもある。

• 無限性: 空でない二項関係 R が最下層の型の個体要素間に成り立つとき、それは非反射的で推移的であり、強連結である (∀x, y [xRy ∨ yRx])。

注意: 無限性 は純粋に数学的な ST 固有の公理である。これは R が全順序関係であることを意味している。最下層の型に 0 を割り当てたとき、R の型は 3 となる。無限性 が成り立つのは R の議論領域が無限のときだけであり、結果として無限集合の存在を前提としている。関係を順序対で定義する場合、この公理の前に順序対を定義する必要が生じる。これは ST に Kuratowski の定義を導入することで実現する。ZFCのような他の集合論の無限集合の公理が何故 ST で採用されなかったのかは書籍にも書かれていない。

ST は型理論が公理的集合論と似ていることを明らかにした。さらに、ZFC などの従来の集合論よりも単純な存在論に基づく "iterative conception of set" と呼ばれる ST のより精巧な存在論がもっと簡単な公理（公理型）を構成している。型理論の出発点は集合論だが、その公理、存在論、用語は異なる。型理論には他にも New Foundations や Scott-Potter set theory がある。

型理論の他分野への影響

コンピューター

型理論の最も顕著な応用は、プログラミング言語のコンパイラでの意味論解析部での型チェックアルゴリズムの構築である。

型理論は自然言語の意味論の理論構築にもよく使われる。以下ではモンタギュー文法の内包論理（型理論と様相論理を折衷したもの）での型を例として説明する。最も基本的な型として $e$（entity=もの）と $t$（truth-value=真理値）があり、以下の規則を帰納的に適用して型の集合を定義する。

1. $a$ と $b$ が型であるとき、$\langle a,b\rangle$ も型である。
2. $a$ が型であるとき、$\langle s,a\rangle$ も型である。ここで、$s$ は型ではなく、指標（可能世界と時点の組み合わせ）である。こちらの規則は様相論理（可能世界）や時相論理（時点）も関わってくる。

$\langle a,b\rangle$ という複合型は、ある型 $a$ の要素から $b$ の要素への関数型である。つまり、$\langle e,t\rangle$ は「もの」から真理値への関数であり、いわば集合の指示関数である。$\langle \langle e,t\rangle ,t\rangle$ は、指示関数の指す集合から真理値への関数であり、いわば集合の集合である。後者は自然言語で言えば、 every boy とか nobody といった表現に相当する（Montague 1973, Barwise and Cooper 1981）。

型システム

→詳細は「型システム」を参照

型システムの定義は様々だが、プログラミング言語理論の世界では Benjamin C. Pierce の定義が一般に受け入れられている。

（型システムは）プログラムが計算する値の種類に従って句（phrase）を分類することで、そのプログラムがある動作をしないことを証明する扱いやすい文法的手法である。 (Pierce 2002)

換言すれば、型システムはプログラムの値を「型」と呼ばれる集合に分類し（これを「型設定」あるいは「型割り当て」と呼ぶ）、特定のプログラムの動作が不正であることを示す。例えば、"hello" という値を文字列型、5 という値を整数型としたとき、プログラマに "hello" と 5 を加算できないといった制限を課すのである。このような型システムでは、次のプログラム

"hello" + 5

は不正である。もちろん、文字列と整数を加算することを許す型システムもありうる。

型システムの設計と実装は、プログラミング言語そのものと同じ程度に広がりを持った話題である。実際、プログラミング言語の最大の基盤は型システムであるとも言われ、「型システムを正しく設計すれば、言語は自分自身で設計される」と言われている。

参考文献

• Robert L. Constable (ed.). "Computational type theory". Scholarpedia.
• Per Martin-Löf (1980), Intuitionistic Type Theory, http://www.csie.ntu.edu.tw/~b94087/ITT.pdf 
• Bengt Nordström,Kent Petersson,Jan M. Smith (1990), Programming in Martin-Löf's Type Theory, http://www.cse.chalmers.se/research/group/logic/book/ 
• 日本数学会編 編『岩波数学辞典 第4版』岩波書店、2007年。ISBN 978-4-00-080309-0。 

関連項目

• ペール・マルティン＝レーフ
• 型システム
• データ型
• 領域理論
• 圏論
• 型付きラムダ計算
• バートランド・ラッセル