集合構築記法

Use of braces for specifying sets

${\displaystyle \{n\mid \exists k\in \mathbb {Z} ,n=2k\}}$

集合構築記法で表現されたすべての偶数の集合。

数学、特に集合論において、集合構築記法は集合のメンバーを特徴付ける性質によって集合を指定する記法である。 ^[1]

集合をメンバープロパティで指定することは、仕様公理スキーマによって可能になります。これは集合内包や集合抽象とも呼ばれます。

述語によって定義された集合

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

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

または

${\displaystyle \{x\colon \Phi (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{ and }}\Phi (x)\}\quad {\text{or}}\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} \}.}$

同等の述語は同等の集合を生成する

二つの集合が等しいのは、それらが同じ要素を持つ場合のみです。集合構築記法で定義された集合は、定義域指定子を含む集合構築規則が等しい場合のみです。つまり、

${\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]

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

	例1	例2
セットビルダー	${\displaystyle \{l\ |\ l\in L\}}$	${\displaystyle \{(k,x)\ |\ k\in K\wedge x\in X\wedge P(x)\}}$
パイソン	{ L 内 のlの l }	{( k , x ) 、 kがKに含まれ、 xがXに含まれ、 P ( x )の場合}
ハスケル	[ l | l <- ls ]	[( k , x ) | k <- ks , x <- xs , p x ]
スカラ	( l <- L )の場合、lが得られる	( k <- K ; x <- X 、 P ( x )の場合) は( k 、x )となる。
C#	Lのlからlを選択	KのkからXのxからP ( x )で( k , x )を選択する
SQL	L_setからlを選択	K_set 、X_setからk 、xを選択します。WHERE P ( x )
プロローグ	setof ( L 、メンバー( L 、Ls )、結果)	setof (( K , X ),(メンバー( K , Ks ),メンバー( X , Xs ),呼び出し( P , X )),結果)
アーラン	[ L || L <- Ls ]	[{ K , X } || K <- Ks , X <- Xs , p ( X )]
ジュリア	[ l ∈ Lの場合のl ]	[( k , x ) 、k ∈ K 、x ∈ X 、 P ( x )の場合]
マセマティカ	( l |-> l ) /@ L	ケース[タプル[{ K , X }], { k_ , x_ } /; P [ x ]]

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

参照

• 集合論の用語集

注記

1. ローゼン、ケネス (2007). 離散数学とその応用（第6版）. ニューヨーク：マグロウヒル. pp.  111– 112. ISBN 978-0-07-288008-3。
2. Michael J Cullinan、2012年、「証明による数学への移行」、Jones＆Bartlett、44ページ以降。
3. Weisstein, Eric W. "Set". mathworld.wolfram.com . 2020年8月20日閲覧。
4. “Set-Builder Notation”. mathsisfun.com . 2020年8月20日閲覧。
5. アーヴァイン、アンドリュー・デイヴィッド；ドイチュ、ハリー（2016年10月9日）[1995]「ラッセルのパラドックス」スタンフォード哲学百科事典。 2017年8月6日閲覧。
6. “シーケンス内包表記”. Scala . 2017年8月6日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Set-builder_notation&oldid=1312232894"