数学＞集合論
集合（set）とは、物の集まりであって、何か物を持ってきたときにそこに属すのか属さないのかどちらかに必ず定まるもののことである。例えば、「標高8500m以上の山」「都道府県であって、人口500万人未満のもの」「すべての二等辺三角形」「正の奇数すべて」などは集合である。ただし、「頭がいい人」のような、何が属して何が属さないのかが曖昧なものは集合とは呼ばないことにする。
集合に属している物のことを元 （element）と呼ぶ。先ほどの例から、「標高8500m以上の山」という集合では、「エベレスト、K2、カンチェンジュンガ、ローツェの4つの元がある」などと言う。「正の奇数すべて」の集合は、「1,3,5,...という無限個の元から成っている」と言える。元が集合に属していることを「\in」という記号で表す。例えば、自然数の全体という集合を\mathbb{N}とすると、1 \in \mathbb{N}と書ける。
なお、元が1つもない集合も集合とみなすことにする。そのような集合を空集合 （empty set、null set）と呼び、\varnothingで表す。
集合をあらわすには、その集合に属している元をすべて書き表すのが最も簡単だ。例えば「1桁の素数」という集合なら
 \{ 2,3,5,7\}
と書ける。このような書き方を外延的記法という。
しかし、集合の元の数が多くなってくると外延的記法は難しくなってくる。例えば、人口500万人未満の都道府県は38個もあるので全部列挙していたら大変だ。それどころか、正の奇数すべての集合の元は無限個あるので、全部書き表すことは不可能で、{1,3,5,7,...}と書くしかない。しかし、このような書き方は、どのような集合なのか誤解を招きやすい。ある人は、「奇数の素数と1」という集合{1,3,5,7,11,13,17,...}の意味でこのように書くかもしれない。
そこで、ある集合の元が満たすべき性質を書くことで集合をあらわすことを考える。そのような記法を内包的記法という。内包的記法では、集合の元を代表する文字と満たすべき条件を縦棒を挟んで並べて書く。例えば、正の奇数の集合は
 \{ x \mid x=2n-1 , n \in \mathbb{N}\}
と書ける。
集合Sのすべての元が集合Tに属しているとき、SはTの部分集合 （subset）であるといい、S \subset Tと表す。空集合は任意の集合の部分集合である。また、S自身もSの部分集合である。S自身以外の部分集合をSの真部分集合といい、TがSの真部分集合であることをT \subsetneq Sとあらわす。
元が集合に属しているという関係と、元がひとつだけの集合が別の集合の部分集合であるという関係とは似て非なるものである。すなわち、x \in Xと\{ x \} \subset Xとは、同値ではあるが表していることは異なる。この違いにはよく注意すべきである。
X \subset YかつY \subset Xを満たすときX=Yと書き、この2つの集合は等しいという。何をくだらないことを定義するのか、と思ってはいけない。数学ではしばしばまったく別の方法で定義した2つの集合X,Yが実は同じ集合であることを証明すべきときがある。そのようなときには、X \subset YかつY \subset Xを示せばよいのである。
冪集合
集合があるとき、その集合の部分集合の集合というものを考えることができる。これをその集合の冪（べき）集合という。きちんと集合の記法で書けば、
のことを、Xの冪集合という。
例
\mathcal{P}(\{ 1,2,3 \} ) = \{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}
この例を見てもわかるように、有限個の元から成る集合（厳密な定義は後の節を参照）Xの冪集合\mathcal{P}(X)の元の個数は、Xの元の個数の2の冪である（この例でいえば、23=8個）ので、\mathcal{P}(X)のことを2^Xと書くこともある。また\mathfrak{P}(X)とも書かれる。
集合Sと集合Tの元をあわせた集合\{ x | x \in S \lor x \in T \}を和集合（sum）ないしは合併（union）といい、S \cup Tと表す。例えば、\{1,2,3\} \cup \{3,4,5\} = \{1,2,3,4,5\}である。
集合Sから集合Tの元を除いた集合\{ x | x \in S \land x \notin T \}を差集合（difference set）といい、S - TまたはS \setminus Tと表す。例えば、\{1,2,3\} \setminus \{3,4,5\} = \{1,2\}である。
集合Sと集合Tの共通する元の集合\{ x | x\in S \land x \in T \}を積集合（intersection）ないしは共通部分（meet）といい、S \cap Tと表す。例えば、\{1,2,3\} \cap \{3,4,5\} = \{3\}である。
これらに関しては、次の性質（ド・モルガンの法則）が成り立つ。SとTをXの部分集合とすると、
また、次の性質（吸収法則）もよく知られている。
集合Sと集合Tの元の組の集合\{ (x,y) | x \in S \land y \in T \}を直積（direct product）といい、S \times Tと表す。例えば、\{ 1,2 \} \times \{ 3,4 \} = \{ (1,3),(1,4),(2,3),(2,4) \}である。
我々は、関数という概念を既に知っている。fが関数（function）であるとは、xという数に対して別の数f(x)がただひとつ定まることであった。ここでは、関数の概念を一般化した写像という概念を考える。すなわち、集合XとYについて、任意のx \in Xに対してf(x) \in Yがただひとつ定まるとき、この対応fはXからYへの写像 （mapping）であるといい、
と書くことにする。2つの写像f_1,f_2:X \to Yについて、
と定める。
2つの写像f:X \to Yとg:Y \to Zがあるとき、写像h:X \to Z , x \mapsto g(f(x))が定まる。これをfとgの合成 （composite）といい、g \circ fと書く。
写像f:X \to YとXの部分集合Sがあるとき、Yの部分集合\{ f(x)|x \in S \}をfによるSの像 （image）といい、f(S)と書く。
写像f:X \to YとYの部分集合Tがあるとき、Xの部分集合\{ x|f(x) \in T \}をfによるTの逆像 （inverse image）といい、f^{-1}(T)と書く。
特にT= \{ y \}のときにはf^{-1}( \{ y \} )を単にf^{-1} (y)と書くこともしばしばある。しかし、この記号は少し紛らわしいので注意すべきである。f(S)とf^{-1}(T)はどちらも集合であるのに対して、f(x)は集合の元だがf^{-1}(y)は集合である。
写像f:X \to Yがf(x)=f(x') \Rightarrow x=x'(対偶を取れば、x \neq x' \Rightarrow f(x) \neq f(x'))を満たすとき、fは単射 （injection）であるという。また、f(X)=Yを満たすとき、fは全射 （surjection）であるという。全射かつ単射であることを全単射 （bijection）であるという。
file:Surjection.svg|全射であり単射でない
file:Injection.svg|単射であり全射でない
file:Bijection.svg|全単射
file:Total function.svg|全射でも単射でもない
例集合Xと部分集合Sが与えられているとする。このとき、i:S \to Xをi(x)=xで定めると、これは単射である。このiを包含写像という。特にS=Xのとき、iは全単射である。このとき恒等写像 （identity mapping）と呼び、特にid_Xと書く。
特に空集合は任意の集合の部分集合なので、空集合からは任意の集合へ包含写像を考えることができる（実質的には何も定めていない写像だが、集合論的に考えることはできる、ということである）。これを特に空写像という。
写像f:X \to Yとg:Y \to Xがあって、g \circ f =id_Xかつf \circ g =id_Yを満たすとき、gはfの逆写像 （inverse mapping）であるといい、f^{-1}と書く。
命題写像f:X \to Yに逆写像が存在することと、写像''f''が全単射であることは同値である。
この命題があるため、写像が全単射であることを証明するために、全射かつ単射であることを示すより、具体的に逆写像を構成してしまったほうが簡単な場合がしばしばある。
より細かくみると、次が成り立つ。
命題*''X''が空集合でないとき、写像f:X \to Yが単射であることは、r \circ f=id_Xを満たす写像r:Y \to X（''f''の左逆写像、またはレトラクトという）が存在することと同値である。また、写像f:X \to Yが全射であることは、f \circ s=id_Yを満たす写像s:Y \to X（''f''の右逆写像、またはセクションという）が存在することと同値である。
（単射性）''f''が単射のとき、y \in Yに対してy=f(x)を満たす''x''が存在すれば（ただ一つなので）その''x''をr(y)とし、y=f(x)を満たす''x''が存在しなければ適当な''X''の元x_0をr(y)とすることで写像''r''が定まり、この''r''はr \circ f=id_Xを満たす。
逆に、''f''に左逆写像''r''が存在するとき、f(x)=f(x')ならばr(f(x))=r(f(x'))であり、すなわちx=x'なので、''f''は単射であることがわかる。
（全射性）''f''が全射のとき、y \in Yを任意にとるとy=f(x)を満たす''x''が存在するのでその中から適当に一つを選び（ここで選択公理を用いる）それをs(y)とすることで写像''s''が定まり、この''s''はf \circ s=id_Yを満たす。
単射・全射については以下の命題も成り立つ。
命題
写像g:Y \to Zが単射で、f_1,f_2:X \to Yがg \circ f_1=g \circ f_2を満たすとき、f_1=f_2
（証明）x \in Xを任意にとると、g(f_1(x))=g(f_2(x))であり、''g''が単射なので、f_1(x)=f_2(x)である。よってf_1=f_2である。
命題
写像f:X \to Yが全射で、g_1,g_2:Y \to Zがg_1 \circ f=g_2 \circ fを満たすとき、g_1=g_2
（証明）y \in Yを任意にとると、''f''が全射なので、f(x)=yなるx \in Xがある。g_1(f(x))=g_2(f(x))なので、g_1(y)=g_2(y)である。よって、g_1=g_2である。
これらの命題は、単射や全射という概念を、集合の元という概念を用いずに特徴づけているという点で重要な命題である。
写像f:X \to Yと集合S \subset Xがあるとき、x \in Sに対してx \mapsto f(x)と定めることで、写像S \to Yが自然に定まる。このようにして定めた写像を''f''の''S''への制限といい、f|_Sであらわす。
はじめは''f''とf|_Sはほとんど同じもののように感じるかもしれないが、区別したほうが便利である。たとえば、f:\mathbb{R} \to \mathbb{R},x \mapsto x^2とS=\{ x \in \mathbb{R}| x \ge 0 \} \subset \mathbb{R}を考えると、''f''は全射でも単射でもないが、f|_Sは単射である。
写像の制限は、包含写像を使って表すことができる。i:S \to Xを包含写像とすると、
である。
「～」が集合A上の二項関係であるとは、任意のa,b \in Aについて、a～bであるかまたはそうでないかが必ず定まることである。例えば、実数の集合における「＝」「≦」などは二項関係である。さらに、二項関係であって次の3つを満たすもののことを同値関係 （equivalent relation）と呼ぶ。
先ほど挙げた「＝」は同値関係であるが、「≦」は対称律を満たさないので同値関係ではない。他に同値関係の例として、自然数の集合上の、ある自然数nで割った余りが等しいという関係「≡(mod n)」などを挙げておく。
さて、同値関係が与えられたときに、各a \in Aについて次の集合を考える。
C(a)= \{ x \in A | x \sim a \}
すなわちC(a)とは、同値関係～によってaと同値な元全体の集合である。これを～に関するaの同値類 （equivalent class）と呼ぶ。このように定めると、次の性質が成り立つことが容易にわかる。
証明
この2番目の性質は、同値関係が与えられると、元の集合Aは、互いに交わらない部分集合族によって分割（直和分解）されることを表している。この、Aを分割する部分集合族のことを、Aを同値関係～で割った商集合 （quotient set）といい、A/～と書く。集合の言葉できちんと書くと下のようになる。
 A/ \sim = \{ C(a) | a \in A \} 
商集合は同値関係にある元を同じものとして同一視した集合であると言える。
例
A を三次元ユークリッド空間内の有向線分全体の集合とする。この集合 A に同値関係\sim をv \sim w \iff v, w の方向が同じでかつ長さが等しい で定める。
このとき、商集合A/\simは空間ベクトル全体の集合である。
集合Aと部分集合Sを考えると、SからAへは包含写像という自然な単射を考えることができた。商集合でも、次のような自然な写像を考えることができる。
\pi : A \to A/\sim , x \mapsto C(x)
この写像は明らかに全射である。この写像のことを、標準的全射とか、自然な全射という。
以下の命題が成り立つ。
命題集合A上の同値関係\simと写像f:A \to Bについて、次の3条件は同値である。
f=g \circ \piを満たす写像g:A/\sim \to Bがただひとつ存在する。
a,a' \in Aとするとき、a \sim a'ならばf(a)=f(a')である。
a \in Aとするとき、写像fの集合C(a) \subset Aへの制限f|_{C(a)}:C(a) \to Bは定数写像である。
（1.\Rightarrow 2.）a \sim a'のとき、\pi(a)=\pi(a')なので、f(a)=g(\pi(a))=g(\pi(a'))=f(a')である。
（2.\Rightarrow 3.）a' \in C(a)に対して、a \sim a'であるから、f(a')=f(a)である。
\forall \lambda \in \Lambdaに対して集合A_{\lambda}が対応するとき、集合A_{\lambda}たちすべてを元とする集合を考えることができる。これを\{ A_{\lambda} \}_{\lambda \in \Lambda}と表し、\Lambdaを添え字とする集合族という。このとき、\Lambdaを添字集合といい、\lambdaをA_{\lambda}の添字という。
\forall \lambda \in \Lambdaに対しA_{\lambda} \subset Xであるとき、集合族\{ A_{\lambda} \}_{\lambda \in \Lambda}はXの部分集合族であるという。
集合族\{ A_{\lambda} \}_{\lambda \in \Lambda}を構成するすべての集合A_{\lambda}の合併をとった集合\{ x | \exists \lambda \in \Lambda , x \in A_{\lambda} \}を和集合といい、\bigcup_{\lambda \in \Lambda} A_{\lambda}と表す。特にi,j \in \Lambda, i \ne j \Rightarrow A_i \cap A_j = \varnothingのとき、集合族\{ A_{\lambda} \}_{\lambda \in \Lambda}の和集合を\coprod_{\lambda \in \Lambda} A_{\lambda}と表し、直和という。
集合族\{ A_{\lambda} \}_{\lambda \in \Lambda}を構成するすべての集合に含まれている元の集合\{ x | \forall \lambda \in \Lambda , x \in A_{\lambda} \}を共通部分といい、\bigcap_{\lambda \in \Lambda} A_{\lambda}と表す。
集合族\{ A_{\lambda} \}_{\lambda \in \Lambda}を構成するすべての集合の直積をとった集合\{ \{ a_{\lambda} \}_{\lambda \in \Lambda} | \forall \lambda \in \Lambda , a_{\lambda} \in A_{\lambda} \}を直積といい、\prod_{\lambda \in \Lambda} A_{\lambda}と表す。直積\prod_{\lambda \in \Lambda} A_{\lambda}を定義域とする写像\pi_\mu : \prod_{\lambda \in \Lambda} A_{\lambda} \to A_\mu ; \{ a_{\lambda} \}_{\lambda \in \Lambda} \mapsto a_\muを第\mu-成分への射影という。
この節では、集合の元の個数について考える。いま、素朴に「個数」と書いたが、この概念は自明な概念ではない。確かに、 \{ 1,2,3 \}という集合の元の個数は3個である、といったことは、素朴に考えてもすぐに言うことができる。しかし、では元が「無限個」ある場合はどうしたらよいのだろうか？これは案外難しい。
そこで、個数という概念を直接定義するのではなく、2つの集合の元の個数がひとしいとはどういうことなのか、ということをまず定義することにしたい。これはそれほど難しくない。以下のようにすればよい。
定義2つの集合AとBの間に全単射があるとき、AとBは対等であるという。
元が有限個の場合に、これまでの素朴な「個数がひとしい」という概念と一致していることは容易にわかる。
さて、この集合と集合が対等であるという関係は、同値関係である。そこで、この同値関係によるAの同値類を\operatorname{Card}(A) と書き、これをAの濃度 （cardinality）という。2つの集合が対等であるということを、2つの集合の濃度がひとしいという言葉で言い換えただけである。これによって、任意の集合に適用できる「個数」にあたる概念を手に入れることができた。もちろん（くどいかもしれないが）この濃度の概念は有限集合の場合は素朴な「個数」の概念と一致する。
2つの集合があったとき、その2つの集合の濃度がひとしいか否かというのはしばしば気になることである。しかし、2つの集合の濃度がひとしいということを示すには、今のところは全単射を具体的に構成するしかなく、これはしばしば大変なこともある。例えば、閉区間[0,1]と\mathbb{R}とは濃度がひとしいのだが、全単射を具体的に作るのは容易ではない。
そこで役に立つのが、次に挙げる定理である。
定理(Bernstein)集合AとBがあり、AからBへの単射と、BからAへの単射があるとき、
card A=card B
AからBへの単射があることと、BからAへの全射があることは同値であるから、定理のステートメントの「単射」をすべて「全射」と書き換えても構わない。
この定理を用いて、自然数の集合\mathbb{N}と、有理数の集合\mathbb{Q}が対等であることを示してみよう。\mathbb{N}から\mathbb{Q}へは自明な単射が存在するから、逆向きの単射を作ればよい。\mathbb{Q}から\mathbb{N} \times \mathbb{N}への単射は容易に作れるので、結局\mathbb{N} \times \mathbb{N}から\mathbb{N}への単射を作ればよい。(a,b) \in \mathbb{N} \times \mathbb{N}に対してf((a,b))=2^{a-1}(2b-1)と定めると、これは\mathbb{N}への単射である。したがって、これらを合成すると\mathbb{Q}から\mathbb{N}への単射が構成でき、Bernsteinの定理より\mathbb{N}と\mathbb{Q}は対等である。
問Bernsteinの定理を用いて、閉区間[0,1]と\mathbb{R}は濃度が等しいことを証明せよ。
これまで「有限」という言葉をナイーブに未定義のままで使ってきたが、ここできちんと定義しておく。
定義[n]=\{1,2,...,n\}とする。特に[0]=\varnothingとする。集合Aが有限集合（finite set）であるとは、ある自然数nに対してAと[n]が対等であることである。
これまでナイーブに想像していた概念と一致することを確認してほしい。有限集合でない集合のことを無限集合（infinite set）という。
有限集合であるための同値な条件はこのほかにもあるが、ここではひとつ挙げておく。
命題*「*」を付した命題は、選択公理のもとで成り立つ命題である。このページでは公理的集合論には深く立ち入らないが、気になる読者のために軽く述べておくと、現代的な集合論は集合を「ものの集まり」といった漠然とした形で定義せず、いくつかの公理を満たすものとして定義している。これを公理的集合論という。この公理は当然直感的に「成り立ちそう」な公理を集めているのだが、その中にある選択公理という公理は「怪しい」結果を招くことから歴史的に他の公理群と区別されてきた。そのため、選択公理を含まない公理系でも成り立つ命題なのか、選択公理を含む公理系でしか成り立たない命題なのかは、このように区別することがしばしばある。集合Aが有限集合であることは、Aと対等なAの真部分集合が存在しないことと同値。
たとえば、偶数の集合は整数の集合の真部分集合だが、これらは対等である。有限集合ではこのようなことは起きない。
無限集合の中でも、特に\mathbb{N}と対等な集合は特別視して、可算集合（countable set）という（可算無限集合ということもあるが、重言である）。先ほどの議論から、\mathbb{Q}は可算集合である。有限集合と可算集合を合わせて高々可算な集合といい、高々可算でない集合のことを非可算集合という。
なぜ無限集合の中で可算集合を特別視するかというと、可算集合は「最も小さい」無限集合だからである。すなわち、
命題*任意の無限集合Aは、可算な部分集合を持つ。
つまり、非可算集合とは、自然数の集合よりも大きい集合のことである。
次の命題とその証明は非常によく知られている。
命題\mathbb{R}は非可算集合である。
（証明）
全射p:\mathbb{N} \to \mathbb{R}が存在したとすると、n \mapsto (p(n)の小数部分)と定めることで、全射f:\mathbb{N} \to (0,1)を作ることができる。したがって、任意の写像f:\mathbb{N} \to (0,1)が全射でないことを示せば十分である。
f(n)の小数第n桁目をa_nと定める。（ただし、小数による実数の表示は一意ではないので、ここでは同じ実数について無限に9が続く表示と無限に0が続く表示がある場合は後者を採用することにする。）このとき、数列b_nを
と定め、cを、整数部分が0で、小数第n桁目がb_nであるような実数とする。すると、明らかにcはfの値域に入っていない。よって、fは全射ではない。//
この有名な議論を、Cantorの対角線論法という。