集合構成記法

数学、特に集合論において、集合構成記法は、集合の要素を特徴付ける性質によって集合を指定する記法である。 ^{[ 1 ]}列挙記法は、集合の要素を列挙することによって集合を指定するために使用される同様の記法である。

要素のプロパティによって集合を指定することは、仕様の公理スキーマによって許可されています。これは集合内包表記および集合抽象化とも呼ばれます。

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

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

または

${\displaystyle \{x\colon \Phi (x)\}.}$

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

集合構成記法の拡張では、単一の変数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} \}}$ 各ペアは、整数と奇数の対応関係を表すペアのセットを作成します。

逆関数が明示的に表せる場合、左辺の式は簡単な代入によって消去できます。例題を考えてみましょう。${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$置換を行う${\displaystyle u=2t+1}$つまり${\displaystyle t=(u-1)/2}$次に、セットビルダー表記のt を置き換えて、

${\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に対して、次の式が成り立つため成り立つ。${\displaystyle x^{2}=1}$xが有理数である場合に限る${\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」キーワードを使用してyieldされた変数のリストを返します。^{[ 7 ]}

いくつかのプログラミング言語における集合構成記法の例を以下に示します。

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

• 集合論の用語集