# 集合 ## 定義 集合(set)は、要素(element)と呼ばれる対象の集まりであり、要素の重複や出現順序を区別しない点が列(sequence)と異なる(同じ要素を2度書いても {x, x} = {x} のように1つの要素として扱う)。ある対象eが集合Sの要素であることは e ∈ S と書く。よく使う集合には専用記号があり、空集合 ∅、非負整数の集合 N、整数の集合 Z、有理数の集合 Q、実数の集合 R、複素数の集合 C がある。集合SがTの部分集合(subset)であることを S ⊆ T、真部分集合(strict subset)であることを S ⊂ T と書く。基本演算として、和集合 A ∪ B(x ∈ A ∪ B iff x ∈ A or x ∈ B)、積集合 A ∩ B(x ∈ A ∩ B iff x ∈ A and x ∈ B)、差集合 A − B(A に属しB に属さない要素)、ある論議領域Dのもとでの補集合 A̅ := D − A が定義される。ある集合Aのすべての部分集合からなる集合はべき集合(power set)pow(A)と呼ばれ、|A| = n ならば |pow(A)| = 2ⁿ である(定理4.5.5、[[濃度]]参照)。列挙しにくい集合は、述語を満たす値の全体として定義する集合構築子記法(set builder notation)、例えば {n ∈ N | n is a prime and n = 4k+1 for some integer k} で表す。2つの集合が等しいとは、すべての要素についての所属が一致すること(z ∈ X iff z ∈ Y, for all z)であり、これがZFC集合論の外延性公理の起点になる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]]) ## 横断的知見 - 集合演算(∪, ∩, 補集合)と命題論理の論理演算(OR, AND, NOT)は定義のうえで直接対応する(x ∈ A ∪ B は x ∈ A OR x ∈ B と同値、というように)。実際、集合の分配律(定理4.1.2: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C))や集合の De Morgan の法則(A ∩ B の補集合 = A の補集合 ∪ B の補集合)は、[[命題論理]]の対応する等式(分配律 定理3.4.1、De Morgan の法則 3.11)へ要素の所属関係を翻訳し、iffの連鎖で証明することで得られる。一方で両者は型としては別物であり、集合に対して AND・OR・NOT を直接書くこと(あるいは命題に対して ∪・∩・補集合を書くこと)は型エラーとして明確に禁止される。命題論理という「真偽値の体系」と集合論という「要素の所属の体系」が、同型な代数構造を共有しながらも独立した体系として扱われている点が、両章を並べて初めて見える構造である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 3 Logical Formulas]]) ## 未解決の問い - 定理4.1.2のような2集合・3集合の分配律を、n個の集合の分配律(問題4.9)へ一般化するには[[整列原理]](Well Ordering Principle、第2章)が使われると示唆されている。この一般化の具体的な証明の形はどのようなものか。 - 本章の脚注は、2つの集合が等しいことの定義(z ∈ X iff z ∈ Y)がZFCの最初の公理であり、第7章§7.3.2でさらに議論されると予告している。ZFCの他の公理(特に無限公理・選択公理)は、有限集合しか扱わない本章の範囲をどのように越えて必要になるのか。 ## 関連 - 概念: [[命題論理]] / [[濃度]] / [[関数]] / [[二項関係]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 4.