集合構築記法

集合論と論理学、数学、コンピュータサイエンスへの応用において、集合構築記法は、集合のメンバーが満たさなければならない特性を記述することによって集合を記述するための数学的記法である。 ^[1]

プロパティによってセットを定義することは、セットの理解、セットの抽象化、またはセットの意図の定義とも呼ばれます。

セットビルダー記法は、述語、つまりセットの要素に対して真と評価され、そうでない場合は偽と評価される論理式によって定義されるセットを記述するために使用できます。^[2]この形式では、セットビルダー記法は、変数、コロンまたは縦棒の区切り、および述語の3つの部分で構成されます。したがって、区切りの左側には変数があり、右側にはルールがあります。これらの3つの部分は中括弧で囲まれています。

${\displaystyle \{x\mid \Phi (x)\}}$

または

${\displaystyle \{x:\ファイ (x)\}.}$

縦棒（またはコロン）は区切り文字で、「となるような」、「 となるような 」、または「 となる性質を持つ 」と読むことができます。式Φ( x )は規則または述語と呼ばれます。述語が成り立つ（真である） xのすべての値は、定義されている集合に属します。述語が成り立たないxのすべての値は、集合に属しません。したがって、 は式Φ を満たすxのすべての値の集合です。^{[3]式を満たす}xの値がない場合、空集合になることがあります。 ${\displaystyle \{x\mid \Phi (x)\}}$

ドメインEは縦棒の左側に現れることがある: ^[4]

${\displaystyle \{x\in E\mid \Phi (x)\},}$

または述語に付加して次のようにします。

${\displaystyle \{x\mid x\in E{\text{ および }}\Phi (x)\}\quad {\text{または}}\quad \{x\mid x\in E\land \Phi (x)\}。}$

ここで、∈ 記号は集合のメンバーシップを表し、記号は論理積 と呼ばれる論理演算子を表します。この表記は、述語が真である特定の集合Eに属するxのすべての値の集合を表します(以下の「集合の存在公理」を参照)。 が連言 である場合、 は、記号 の代わりにコンマを使用して と記述されることがあります。 ${\displaystyle \land}$${\displaystyle \Phi (x)}$${\displaystyle \Phi _{1}(x)\land \Phi _{2}(x)}$${\displaystyle \{x\in E\mid \Phi (x)\}}$${\displaystyle \{x\in E\mid \Phi _{1}(x),\Phi _{2}(x)\}}$${\displaystyle \land}$

一般的に、談話領域を定義せずに集合を考えるのは得策ではない。なぜなら、これは述語が真となる可能性のあるすべてのもののサブセットを表すことになるからである。これは簡単に矛盾やパラドックスにつながる可能性がある。例えば、ラッセルのパラドックスは、式が集合構築式としては適切に形成されているように見えても、矛盾を生じさせずに集合を定義することはできないことを示している。^[5]${\displaystyle \{x~|~x\not \in x\},}$

集合E が文脈から明らかな場合、明示的に指定されないことがあります。文献では、著者が事前にドメインを述べ、その後、集合構築記法でそれを指定しないのが一般的です。たとえば、著者は「特に明記しない限り、変数は自然数とみなされます」などと言うことがありますが、ドメインが想定できるあまり形式的でない文脈では、書面での言及は多くの場合不要です。

次の例は、述語を介してセットビルダー表記法で定義された特定のセットを示しています。いずれの場合も、ドメインは縦棒の左側に指定され、ルールは右側に指定されます。

• ${\displaystyle \{x\in \mathbb {R} \mid x>0\}}$は、すべての正の実数 からなる集合であり、区間表記ではと表すことができます。${\displaystyle (0,\infty )}$
• ${\displaystyle \{x\in \mathbb {R} \mid |x|=1\}}$は集合 です。この集合は と定義することもできます。同等の述語が等しい集合を生成することを以下で参照してください。${\displaystyle \{-1,1\}}$${\displaystyle \{x\in \mathbb {R} \mid x^{2}=1\}}$
• 各整数mに対して、 を定義できます。例として、および とします。${\displaystyle G_{m}=\{x\in \mathbb {Z} \mid x\geq m\}=\{m,m+1,m+2,\ldots \}}$${\displaystyle G_{3}=\{x\in \mathbb {Z} \mid x\geq 3\}=\{3,4,5,\ldots \}}$${\displaystyle G_{-2}=\{-2,-1,0,\ldots \}}$
• ${\displaystyle \{(x,y)\in \mathbb {R} \times \mathbb {R} \mid 0<y<f(x)\}}$は、与えられた関数fに対して、 yが 0 より大きくf ( x )より小さい 実数のペアの集合です。ここで、直積は実数の順序付きペアの集合を表します。 ${\displaystyle \mathbb {R} \times \mathbb {R} }$
• ${\displaystyle \{n\in \mathbb {N} \mid (\exists k)[k\in \mathbb {N} \land n=2k]\}}$は、すべての偶数の 自然数の集合です。記号は「and」を表し、論理積として知られています。 記号∃は「存在する」を表し、存在量化として知られています。したがって、たとえば、 は「 P ( x )となるx が存在する」と読みます。${\displaystyle \land}$${\displaystyle (\exists x)P(x)}$
• ${\displaystyle \{n\mid (\exists k\in \mathbb {N} )[n=2k]\}}$は、同じ偶数の自然数の表記法の変形です。右の式からわかるように、nが自然数であることを明記する必要はありません。
• ${\displaystyle \{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\}}$は有理数の集合、つまり 2 つの整数の比として表される実数です。

集合構築記法の拡張により、単一の変数x が式に置き換えられます。したがって、 の代わりに 、次のように読み替えること ができます。${\displaystyle \{x\mid \Phi (x)\}}$${\displaystyle \{f(x)\mid \Phi (x)\},}$

${\displaystyle \{f(x)\mid \Phi (x)\}=\{y\mid \exists x(y=f(x)\wedge \Phi (x))\}}$。

例えば：

• ${\displaystyle \{2n\mid n\in \mathbb {N} \}}$はすべての自然数の集合であり、はすべての偶数の自然数の集合です。${\displaystyle \mathbb {N} }$
• ${\displaystyle \{p/q\mid p,q\in \mathbb {Z} ,q\not =0\}}$は整数全体の集合であり、は有理数全体の集合です。${\displaystyle \mathbb {Z} }$${\displaystyle \mathbb {Q} ,}$
• ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$奇数の整数の集合です。
• ${\displaystyle \{(t,2t+1)\mid t\in \mathbb {Z} \}}$ ペアのセットを作成し、各ペアで整数を奇数の整数に対応させます。

逆関数を明示的に記述できる場合、左側の式は単純な置換によって削除できます。例の集合 を考えてみましょう。置換、つまり を行い、集合構築記法で t を置き換えて、${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$${\displaystyle u=2t+1}$${\displaystyle t=(u-1)/2}$

${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}=\{u\mid (u-1)/2\in \mathbb {Z} \}.}$

2つの集合は、同じ要素を持つ場合にのみ等しい。集合ビルダー記法で定義された集合は、ドメイン指定子を含む集合ビルダー規則が等しい場合にのみ等しい。つまり、

${\displaystyle \{x\in A\mid P(x)\}=\{x\in B\mid Q(x)\}}$

もし、もし、

${\displaystyle (\forall t)[(t\in A\land P(t))\Leftrightarrow (t\in B\land Q(t))]}$。

したがって、セット ビルダー表記法によって定義された 2 つのセットの等価性を証明するには、ドメイン修飾子を含む述語の等価性を証明すれば十分です。

例えば、

${\displaystyle \{x\in \mathbb {R} \mid x^{2}=1\}=\{x\in \mathbb {Q} \mid |x|=1\}}$

2 つのルール述語は論理的に同等であるためです。

${\displaystyle (x\in \mathbb {R} \land x^{2}=1)\Leftrightarrow (x\in \mathbb {Q} \land |x|=1).}$

この同値性は、任意の実数xに対して、 が成り立つのは、 x がを満たす有理数である場合に限ります。特に、両方の集合は集合 に等しいです。 ${\displaystyle x^{2}=1}$${\displaystyle |x|=1}$${\displaystyle \{-1,1\}}$

ツェルメロ-フランケル集合論などの多くの形式集合論では、集合構築記法は理論の形式構文の一部ではありません。代わりに、集合存在公理スキームがあり、これは、Eが集合であり、Φ( x ) が集合論の言語の式である場合、Φ を満たすEの要素をメンバーとする集合Yが存在することを述べています。

${\displaystyle (\forall E)(\exists Y)(\forall x)[x\in Y\Leftrightarrow x\in E\land \Phi (x)].}$

この公理から得られる集合Y は、集合作成記法で と記述される集合とまったく同じです。 ${\displaystyle \{x\in E\mid \Phi (x)\}}$

多くのプログラミング言語(特にPythonとHaskell )で使用できる同様の表記法は、1 つ以上のリストに対するマップ操作とフィルター操作を組み合わせたリスト内包表記です。

Python では、セットビルダーの中括弧は、角括弧、丸括弧、または中括弧に置き換えられ、それぞれリスト、ジェネレーター、およびセット オブジェクトになります。Python は英語ベースの構文を使用します。Haskell は、セットビルダーの中括弧を角括弧に置き換え、標準のセットビルダーの垂直バーなどのシンボルを使用します。

同じことはScalaでもシーケンス内包表記を使って実現できます。シーケンス内包表記では、「for」キーワードは「yield」キーワードを使用して生成された変数のリストを返します。^[6]

いくつかのプログラミング言語における次のセットビルダー表記の例を考えてみましょう。

セット ビルダー表記法とリスト内包表記法はどちらも、モナド内包表記法と呼ばれるより一般的な表記法のインスタンスであり、ゼロ要素を持つ任意のモナドに対してマップ/フィルターのような操作を許可します。

• 集合論の用語集