Team TripleFalcon. http://www.triplefalcon.com/

概要

 区別可能なものの集まりを集合(set) と呼びます。 集合のもつ要素が有限の場合は有限集合(finite set) と呼び、有限でない場合は無限集合(infinite set) と呼びます。集合論は、代数などの基礎的な定義も与えており、重要な概念です。(有限集合と無限集合の形式的定義はこちらを参照→濃度

 本ページは論理記号 ¬,∨,∧ を用います。(参照→記号論理)

 以下に集合上の演算を示します。

名称 記号 概要 (A,B は集合)
x∈A A に要素 x が含まれている
空集合 φ 中身が空っぽの集合
積集合 A∩B AにもBにも含まれる要素の集合
和集合 A∪B AまたはBに含まれる要素の集合
直和 A∪B (A∩B=φ) であるような和集合
部分集合 A⊂B 集合AはBに含まれている
直積集合 A×B (x,y) の集合 (x∈A,y∈B とする)
普遍集合 Ω その系の議論に含まれる全部の要素
差集合 A-B Aに含まれBに含まれない要素の集合
補集合 AC Aに含まれない要素の集合
冪集合 2A Aの部分集合全体の集合

 以下は概念図です。

 人間が使う名詞はたいていの場合、集合を表します。 例えば、「猫」という名詞はニャーニャー鳴く動物を連想させます。 「猫」はかなり具体的な「物」を示す言葉に感じられてしまうのですが、良く考えるとこれはかなり抽象的な言葉で、三毛猫もシャム猫もペルシャ猫も「猫」で示されます。「猫」というのは「猫以外」の動物と区別された「概念」に過ぎません。

 具体的に物を指し示す思われる名詞も大部分は、「概念」だけを差しています。

 集合は、日本語の”は”と感覚的につながりが深いようです。英語では"is"ですね。日本語で A は B であるというと、いろいろな意味を持ちますが、数学用語では3種類に分類すべきです。

 (1) AはBと等しい。

 (2) Aは集合Bに含まれる。

 (3) Aは集合Bの部分集合である。

 例えば太郎は日本人であるといえば(2)にあたりますし、日本人は人間であるといえば(3)に相当します。計算機上でいつでも集合が利用できるように実装すると便利です。(参照→集合の実装)

Team TripleFalcon. http://www.triplefalcon.com/

集合の表記

 要素 a,b,c が集まった集合を表現する場合は、 {a,b,c} と表記します。内容がある程度自明な場合は、 {1,2,3, ... , n } と書いて間を ”...” で略記してもいいことになっています。この場合、左から 3 つ目までは書くのが慣習のようです。

 また、述語 P を補って、 { x | P( x ) } と表す場合もあります。 例えば、{x|x は日本人} と書いたらこの集合は日本人の集合をあらわします。

 (1) {n | n は偶数}  この集合は偶数の集合です。

 (2) {2n | n は整数}  この集合も偶数の集合です。((1)と等しい。)

 内容が空の集合は空集合と呼び、空集合を φで表します。

 集合がもつ要素を、集合のと呼びます。a は集合{a,b,c}の元です。要素 a が集合 A の元であるとき、a∈A と表記します。

 集合は元の順番を問いません。従って、{a,b}{b,a} は同じ集合を表現します。

 集合は、元の重複をさせません。つまり、{a}{a,a} は区別されません。しかし、{a}a は区別されます。従って、{a}{{a}} は異なります。φ{φ} も異なります。重複を許容する概念に、多重集合があります。(参照→多重集合)

 (3)  {a}={a,a}  ,  {a,b,c}={c,b,a}

 (4)  {a}≠{{a}} , φ≠{φ} ,{a,b}≠{a,{b}}

Team TripleFalcon. http://www.triplefalcon.com/

対 , 組

 2要素をもつ集合を対(pair)といいます。集合は要素に順序が無いので {a,b}={b,a} となりますが、 どうしても順序を表現したい場合は、順序対(orderd pair) を定義して使います。 順序対は、(a,b)のように表現します。 {a,b} は非順序対(unordered pair) と呼ばれます。また、n だけ要素を並べて拡張した対を n-組(n-tuple) といいます。

 順序対では (a,b)≠(b,a) となり、それぞれ意味が異なります。反対に非順序対では {a,b}={b,a} であり、同じ集合を表現しています。以下では単にと述べた場合は順序対だけをさすことにします。

 (x1,x2,x3,...,xn) ,・・・(xi∈A) の様に、同じ集合の元で組を構成した場合、計算機では配列を利用して実装します。

 (a,b,c) ,・・・(a∈A , b∈B, c∈C) の様に、異なる集合の元で組を構成した場合、計算機では構造体を利用して実装します。

 対 (a,b) は形式的には {{a},{a,b}} で定義するようです。組(a1,a2,a3,a4,...,an) は対の概念を繰り返し適用して、 (...(((a1,a2),a3),a4),...,an) と定義します。

定義1) (a,b)
def
{{a},{a,b}}
定義2) (a1,a2,a3,a4,...,an)
def
(...(((a1,a2),a3),a4),...,an)

 はじめてみた時、定義1 を最初に考えた人はエライなと思いました。集合には順番の概念がないのですが、上記のように定義すると (a,b)(b,a) を区別できます。初歩の教科書だと、組の定義はさらっと流すだけで書いてないのもあります。定義2は、定義1を連鎖的に使って、より長い組を定義します。定義1や定義2は数学上の定義としてはきれいかもしれませんが、定義をそのまま実装するには不向きです。組や対は、配列や構造体を用いるのが良いと思われます。以下には、集合に対して行うことができる操作を列挙しています。

Team TripleFalcon. http://www.triplefalcon.com/

直積集合

 集合 A の要素と集合 B の要素 による対の全体からなる集合を A と B の直積集合(Cartesian product) と呼びます。A と B の直積集合を A×B と表記します。

定義3) A×B
def
{(a,b) | a∈A , b∈B}

 例えば、集合 {北,南}×{東,西} は集合 {(北,東),(北,西),(南,東),(南,西)} を表します。また、R(=実数の集合) を用いて R×R として2次元の平面を表すことも出来ます。

Team TripleFalcon. http://www.triplefalcon.com/

共通部分

 集合 A にも 集合 B にも含まれる要素の集合をAとBの 積集合(product) とか共通部分(intersection) といいます。AとBの共通部分を、A∩B と表記します。

定義4) A∩B
def
{x | x∈A ∧ x∈B}

 例えば、素数の集合 P と偶数の集合 E の共通部分 P∩E{2} です。空集合φとの共通部分はφです。どんな集合 A を選んでも φ=A∩φ が成り立ちます。

 交換則と結合則が成立します。

 (1) A∩B=B∩A  ・・・交換則

 (2) A∩(B∩C)=(A∩B)∩C ・・・結合則

Team TripleFalcon. http://www.triplefalcon.com/

合併

 集合 A または集合 B に含まれる要素の集合をAとBの 和集合(sum) とか合併(union) といいます。AとBの合併を、A∪Bと表記します。

定義5) A∪B
def
{x | x∈A ∨ x∈B}

 空集合φと集合 A の合併は集合 A 自身です。どんな集合 A を選んでも A=A∪φ が成り立ちます。A,B が共通部分を持たない場合、AとBの合併を直和(disjoint union) といいます。

 交換則と結合則が成立します。

 (1) A∪B=B∪A  ・・・交換則

 (2) A∪(B∪C)=(A∪B)∪C ・・・結合則

Team TripleFalcon. http://www.triplefalcon.com/

部分集合

 集合 A の要素が必ず 集合 B にも含まれる場合は, AをB の部分集合(subset) と呼び、 A⊂B と表記します。

定義6) A⊂B
def
∀x (x∈A ならば x∈B)

 野球選手の集合は、スポーツ選手の集合の部分集合です。空集合φはすべての集合の部分集合です。また集合Aは必ず集合A自身の部分集合です。どんな集合A を選んでも、A⊂A が成立します。

 また、集合 A,B が A⊂B かつ A≠B のとき、AをBの真部分集合(proper subset) といいます。

Team TripleFalcon. http://www.triplefalcon.com/

差集合

 集合 A に属するけれど集合 B には属さないものの集合を A と B の差集合(difference set) といい、A-B とか A\B と表します。Bの(Aに対する)補集合(complement set)ということもあります。

定義7) A−B
def
{x | x∈A ∧ xÏB }

Team TripleFalcon. http://www.triplefalcon.com/

普遍集合と補集合

 ある議論の議題に沿って、ある集合についてしか議論しない場合はその集合全体を Ω のように表して、普遍集合(universal set) と呼びます。普遍集合 Ω と集合 A(⊂Ω) の差集合 Ω-A を Aの補集合(complement set)といいます。Aの補集合を AC と表記します。

定義8) AC
def
Ω−A

Team TripleFalcon. http://www.triplefalcon.com/

空集合

 要素を持たない集合です。記号では φ と表現します。

Team TripleFalcon. http://www.triplefalcon.com/

分割

  U の部分集合A,B⊂U が、 A∩B=φ かつ A∪B=U のとき集合 {A,B} を Uの分割(partition) といいます。 このとき、A,B をそれぞれブロック(block) と呼びます。

 3個以上の部分集合への分割も自明に拡張できます。 Uの部分集合、U1,U2,U3,...,Un( ⊂U) の集合 P={U1,U2,U3,...,Un}(i,j∈{1..n}),i≠j ならば Ui ∩Uj=φ) かつ (U1∪U2∪...∪Un=U) を満たすときP は U の分割になります。

Team TripleFalcon. http://www.triplefalcon.com/

冪集合

 U の部分集合全体の集合を U の冪集合(power set) といいます。 2U と表記します。

定義9) 2U
def
{u|u⊂U}

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

集合(set)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール