内包的記法

数学、より具体的には集合論において、内包的記法（ないほうてききほう、）とは、集合の元を特徴づける性質によってその集合を指定する記法である。外延記法は、集合の元を列挙することによって集合を指定する類似の記法である。

元の性質によって集合を指定することは、分出公理型によって認められている。これは集合内包または集合抽象としても知られる。

述語によって定義される集合 内包的記法は、述語によって定義される集合を記述するために用いることができる。ここで述語とは、その集合の元に対しては真、それ以外に対しては偽と評価される論理式のことであるMichael J Cullinan, 2012, A Transition to Mathematics with Proofs, Jones & Bartlett, pp. 44ff.。この形式では、内包的記法は変項、コロンまたは縦棒の区切り記号、述語の3つの部分から成る。したがって区切り記号の左側に変項があり、その右側に規則がある。これら3つの部分は波括弧の中に収められる。

または

縦棒（またはコロン）は区切り記号であり、「〜であるような」、「〜を満たす」、「〜という性質を持つ」のように読むことができる。式は規則あるいは述語と呼ばれる。述語が成り立つ（真である）すべてのの値は、定義される集合に属する。述語が成り立たないすべてのの値はその集合に属さない。したがっては、式を満たすのすべての値の集合である。のいかなる値も式を満たさない場合、それは空集合でありうる。

定義域の指定

その記法が部分集合を定義する対象となる集合である定義域は、縦棒の左側に現すことができる。

あるいは述語に付け加えることもできる。

（記号は集合の帰属を表し、記号は論理積演算子を表す。）この記法は、集合に属し、かつ述語が真であるようなすべてのの値の集合を表す。分出公理型は、が集合でありが述語であるとき、この記法が常にの部分集合である集合を定義することを保証する。がという形をしているとき、は記号の代わりにコンマを用いてと書かれることがある。

集合が文脈から明らかである場合、それは明示的に指定されないことがある。文献では、著者があらかじめ定義域を述べておき、その後内包的記法の中でそれを指定しないことがよくある。例えば著者は、「特に断らない限り、変項は自然数であるものとする」といったことを述べることがあるが、定義域が仮定できるようなより形式的でない文脈では、明記すること自体が不要であることも多い。

定義域が（暗黙にも明示的にも）定義されていない場合には、その記法が集合ではなく真クラスを定義してしまうことが起こりうるRichard S. Pierce (1968) Introduction to the Theory of Abstract Algebras, page 2。例えば、ラッセルのパラドックスは、式が内包的記法として一見整式であるように見えても、矛盾を生じさせることなしには集合を定義できないことを示している。

場合によっては、この記法は以前に定義された集合の部分集合ではない集合を定義することもある。これは集合の冪集合の場合であり、これは次のように定義される。

これが集合を定義するという事実は集合論の公理であり、冪集合公理と呼ばれる。

例 以下の例は、述語による内包的記法によって定義される特定の集合を示している。いずれの場合も、定義域は縦棒の左側に、規則は右側に指定されている。 は、厳密に正の実数すべての集合であり、区間表記ではと書くことができる。

は集合である。この集合はとしても定義できる（後述の同値な述語は等しい集合を生むを参照）。 各整数に対して、と定義できる。例えば、である。

は、ある関数が与えられたとき、yが0より大きくより小さいような実数の組の集合である。ここで直積は実数の順序対の集合を表す。

は、すべての偶自然数の集合である。の記号は「かつ」を表し、論理積として知られる。∃の記号は「存在する」を表し、存在量化として知られる。したがって例えばは「であるようなが存在する」と読まれる。

は同じ偶自然数の集合に対する記法上の変種である。が自然数であることを指定する必要はない。これは右側の式によって含意されているからである。

は有理数、すなわち2つの整数の比として書ける実数の集合である。

記法の左側におけるより複雑な式

内包的記法の拡張として、単一の変項を式に置き換えることができる。すなわち、の代わりにと書くことができ、これは次のように読むべきである。 .

例えば （はすべての自然数の集合）は、すべての偶自然数の集合である。 （はすべての整数の集合）は、すべての有理数の集合である。 は奇整数の集合である。 は、各整数を対応する奇整数と対にする組の集合を作る。

逆関数を明示的に述べることができる場合、左側の式は単純な代入によって消去できる。例として集合を考える。、すなわちと置き換え、内包的記法の中でtを置き換えると次のようになる。

同値な述語は等しい集合を生む

2つの集合は、それらが同じ元を持つとき、かつそのときに限り等しい。内包的記法によって定義される集合は、その内包規則が定義域指定子を含めて同値であるとき、かつそのときに限り等しい。すなわち

であるのは

のとき、かつそのときに限る。したがって、内包的記法によって定義される2つの集合の等しさを証明するには、定義域限定子を含めてそれらの述語の同値性を証明すれば十分である。

例えば

となる。なぜなら2つの規則述語は論理的に同値だからである。

この同値性が成り立つのは、任意の実数xについて、であるのはxがを満たす有理数であるとき、かつそのときに限るからである。特に、両方の集合はいずれも集合に等しい。

集合存在公理 ツェルメロ＝フレンケル集合論のような多くの形式的集合論では、内包的記法は理論の形式的構文の一部ではない。その代わりに集合存在公理型があり、が集合でありが集合論の言語における論理式であるとき、の元のうちを満たすものすべてを元とする集合が存在する、と述べる。

この公理から得られる集合は、まさに内包的記法でと記述される集合そのものである。

プログラミング言語における内包的記法

多くのプログラミング言語（特にPythonとHaskell）で利用できる類似の記法にリスト内包表記がある。これは1つまたは複数のリストに対するmap演算とfilter演算を組み合わせたものである。

Pythonでは、内包的記法の波括弧は角括弧、丸括弧、あるいは波括弧に置き換えられ、それぞれリスト、ジェネレータ、集合オブジェクトを与える。Pythonは英語に基づいた構文を用いる。Haskellは内包的記法の波括弧を角括弧に置き換え、標準的な内包的記法の縦棒を含む記号を用いる。

同様のことはScalaでもSequence Comprehensionsを用いて実現でき、そこでは"for"キーワードが"yield"キーワードを用いて生成された変項のリストを返す。

いくつかのプログラミング言語における内包的記法の例を見てみよう。 例1 例2 内包的記法 Python {l for l in L} {(k, x) for k in K for x in X if P(x)} Haskell [l | l <- ls] [(k, x) | k <- ks, x <- xs, p x] Scala for (l <- L) yield l for (k <- K; x <- X if P(x)) yield (k,x) C# from l in L select l from k in K from x in X where P(x) select (k,x) SQL SELECT l FROM L_set SELECT k, x FROM K_set, X_set WHERE P(x) Prolog setof(L,member(L,Ls),Result) setof((K,X),(member(K,Ks),member(X,Xs),call(P,X)),Result)Erlang[L || L <- Ls][{K,X} || K <- Ks, X <- Xs, p(X)]Julia[l for l ∈ L][(k, x) for k ∈ K for x ∈ X if P(x)]Mathematica(l |-> l) /@ LCases[Tuples[{K, X}], {k_, x_} /; P[x]]

Tuples[{K, Select[X, P]}]

内包的記法とリスト内包表記は、いずれもモナド内包表記として知られるより一般的な記法の実例である。これは、モナドに対するmap/filterに似た演算を、零元を持つ任意のモナドに対して許すものである。

関連項目 集合論の用語一覧

注