5分でわかる集合論-基礎編

必要な気がしたので、集合論の記号・言葉、定理などのカンペをつくりました。忘れたりするものがかなりあるので。タイトルは大げさか。さーせん。

集合論以前

• カンマ ( , ) は 'かつ' (and) とおなじ意味
• $\forall x(p)$・・・すべてのxに対してpが成り立つ
• $\exists x(p)$・・・pが成り立つようなxが(少なくとも一つ)存在する

基礎

• 集合・・・範囲のはっきりした集まり
• 元、要素・・・集合の中にはいっているもの
• $a \in A$・・・aは集合Aに属する、含まれる
• 有限集合・・・有限個の元のみもつ集合
• 無限集合・・・無限個の元をもつ集合
• よく使われる記号
  • $\mathbb{N}$・・・自然数全体の集合
  • $\mathbb{Z}$・・・整数全体の集合
  • $\mathbb{Q}$・・・有理数全体の集合
  • $\mathbb{R}$・・・実数全体の集合
• 外延的記法・・・$\left{a,b,c,\cdots \right}$のような記法
• 内包的記法・・・$\left{ x|C\left(x\right)\right}$のような記法(ただし、Cは条件)
• 空集合・・・元をまったく含まない集合、記号$\phi$
• 相等・・・集合A,Bが、まったく同じ元からなるとき、AとBは'等しい'

部分集合

• 任意のものxについて、$x \in A \Rightarrow x \in B$が正しいならば、AはBの部分集合である(記号$A \subset B$)
  • 否定は$A \not \subset B$
• th. $A = B \Leftrightarrow A \subset B, A \supset B$
• th. 部分集合は推移性が成り立つ: $A \subset B, B \subset C \Rightarrow A \subset C$
• $(\forall A) \phi \subset A$

(2021/5/20 追記)

• $A \subset B \text{かつ} A \neq B$ のとき、 $A$ は $B$ の 真部分集合 である、という
• ※ 本記事では採用していないが、記号として、$A \subseteq B$ を部分集合とし、$A \subset B$ を真部分集合とするケースもある。
  • どちらが正しいということもない。
  • 「真部分集合」や記号 $\subseteq$ について調べてみたが、どうも真部分集合という概念自体が現代ではあまり使われない概念っぽい。
  • (とはいえ情報ソースが怪しいものしか無くて詳細不明)

集合演算

• 和集合(結び)・・・$A \cup B = { x | x \in A \text{ or } x \in B }$
  • $A \subset A \cup B, B \subset A \cup B$・・・和集合は、足されたものを含む
  • $A \subset C, B \subset C \Rightarrow A \cup B \subset C$
  • $A \cup A = A$・・・冪等律
  • $A \cup B = B \cup A$・・・交換律
  • $(A \cup B) \cup C = A \cup (B \cup C)$・・・結合律
  • 省略記法・・・$A_1, \cup A_2 \cup \cdots \cup A$n、あるいは$\bigcup{i=1}^n A_i$
  • $A \subset B \Leftrightarrow A \cup B = B$・・・ある集合に、その部分集合を足しても変わらない
  • $A \subset B \Rightarrow A \cup C \subset B \cup C$
  • $\phi \cup A = A$
• 共通部分(交わり)・・・$A \cap B = \left{ x | x \in A, x \in B \right}$
  • $A \cap B \ne \phi$のとき、A,Bは'交わる'という
  • $A \cap B = \phi$のとき、A,Bは'交わらない'あるいは'互いに素である'という
  • $A \supset A \cap B, B \supset A \cap B$
  • $A \supset C, B \supset C \Rightarrow A \cap B \supset C$
  • $A \cap A = A$・・・冪等律
  • $A \cap B = B \cap A$・・・交換律
  • $(A \cap B) \cap C = A \cap (B \cap C)$・・・結合律
  • 省略記法・・・$A_1, \cap A_2 \cap \cdots \cap A$n、$\bigcap{i=1}^n A_i$
  • $A \subset B \Leftrightarrow A \cap B = A$
  • $A \subset B \Rightarrow A \cap C \subset B \cap C$
  • $\phi \cap A = \phi$
• 分配律
  • $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$
  • $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$
• 吸収律
  • $(A \cup B) \cap A = A$
  • $(A \cap B) \cup A = A$
• A,Bが互いに素であるとき、和集合$A \cup B$はAとBの直和という
• 差集合
  • 集合Aの元であって、集合Bの元でないものの全体をつくる集合をA,Bの差といい、A-Bで表す
  • $A-B = { x | x \in A, x \not \in B }$
  • $A \supset B$である場合、A-BをAに対するBの補集合という
• 考えている全体の集合・・・普遍集合、全体集合
• Xが普遍集合のとき
  • X-Aを単に「Aの補集合」といい、$A^c$で表す
  • xをXの元としたとき、$A^c = \left{ x | x \in A \right}$あるいは$x \in A^c \Leftrightarrow x \not \in A$
  • $A \cup A^c = X, A \cap A^c = \phi$
  • $A^{cc} = A$
  • ${\phi}^c = X, X^c = \phi$
  • $A \subset B \Leftrightarrow A^c \supset B^c$
• de Morganの法則
  • ${(A \cup B)}^c = A^c \cap B^c$
  • ${(A \cap B)}^c = A^c \cup B^c$
• 集合系・・・集合の集合(その元が、すべてそれ自身集合であるような集合)
  • 集合Xのすべての部分集合全体がつくる集合系を巾集合という(ここでは$\mathfrak{P}(X)$と表現する)
  • $\mathfrak{P}(\phi) = {\phi}$
  • Xがn個の元からなる集合のとき、$\mathfrak{P}(X)$の要素は$2^n$個の要素を持つ
  • 集合系の和集合(記号:$\bigcup \mathfrak{P}$)・・・$\mathfrak{P}$に属するすべての集合の和集合、すなわち$\bigcup \mathfrak{P}={x|\exists A \in \mathfrak{P}}$
  • 集合系の共通部分(記号:$\bigcap \mathfrak{P}$)・・・$\mathfrak{P}$に属するすべての集合の共通部分、すなわち$\bigcap \mathfrak{P}={x|\forall A \in \mathfrak{P}}$
  • $\forall A \in \mathfrak{P}(A \subset \bigcup \mathfrak{P})$
  • $[\forall A \in \mathfrak{P}(A \subset C)] \Rightarrow \bigcup \mathfrak{P} \subset C$
  • $\forall A \in \mathfrak{P}(A \supset \bigcap \mathfrak{P})$
  • $[\forall A \in \mathfrak{P}(A \supset C)] \Rightarrow \bigcap \mathfrak{P} \supset C$

対応

• 直積($A \times B$)・・・集合Aの元aと集合Bの元bの組(a,b)全体のつくる集合
• 対応・・・ある集合Aの各元aに、集合Bの部分集合を割り当てるルール$\Gamma$を、AからBへの対応という。
  • $\Gamma: A \rightarrow B$と書く
  • Bの部分集合$\Gamma(a)$→$\Gamma$よるaの像
  • A→始集合
  • B→終集合
  • $\Gamma, \Gamma': A \rightarrow B, \forall a \in A(\Gamma(a) = \Gamma'(a))$が成り立つとき、$\Gamma, \Gamma'$は等しい
• 対応のグラフ
  • $G(\Gamma) = \left{ (a,b) | a \in A, b \in \Gamma(a) \right}$を$\Gamma$のグラフという
  • $\Gamma(a) = \left{ b | (a,b) \in G(\Gamma) \right}$
• $\Gamma$の定義域($D(\Gamma)$)・・・$\Gamma$のグラフをGとしたとき、$(a,b) \in G$となるようなbが存在するようなa全体のつくるAの部分集合
  • $D(\Gamma) = { a | \exists b ( (a,b) \in G) }$
• $\Gamma$の値域($V(\Gamma)$)・・・$\Gamma$のグラフをGとしたとき、$(a,b) \in G$となるようなaが存在するようなa全体のつくるAの部分集合
  • $V(\Gamma) = { b | \exists a ( (a,b) \in G) }$
• 逆対応(${\Gamma}^{-1}$)
  • $b \in \Gamma(a) \Leftrightarrow a \in {\Gamma}^{-1}(b)$
  • $D({\Gamma}^{-1})=V(\Gamma), V({\Gamma}^{-1}) = D(\Gamma)$
  • $({\Gamma}^{-1})^{-1} = \Gamma$

写像

• 写像・・・対応のうち、始集合の任意の元aに対して、$\Gamma(a)$は終集合のただ一つの元から成る集合であるもの
• 定値写像・・・$f(x)=1$のように、値が固定の写像
• 恒等写像($I_A$)・・・aにa自身を対応させる写像、$I_A(a) = a$
• Pの元aのfによる像f(a)をすべて集めてできる集合をfによるPの像といい、f(P)と表す
• $P_1 \subset P_2 \Rightarrow f(P_1) \subset f(P_2)$
• $f(P_1 \cup P_2) = f(P_1) \cup f(P_2)$
• $f(P_1 \cap P_2) \subset f(P_1) \cap f(P_2)$
• $f(A-P) \supset f(A) - f(P)$
• $Q_1 \subset Q_2 \Rightarrow f^{-1}(Q_1) \subset f^{-1}(Q_2)$
• $f^{-1}(Q_1 \cup Q_2) = f^{-1}(Q_1) \cup f^{-1}(Q_2)$
• $f^{-1}(Q_1 \cap Q_2) = f^{-1}(Q_1) \cap f^{-1}(Q_2)$
• $f^{-1}(B-Q) = A - f^{^1}(Q)$
• $f^{-1}(f(P)) \supset P$
• $f(f^{-1}(Q)) \subset Q$
• 全射・・・$f(A) = B$のとき、つまり終集合のすべての要素が指されている場合、fは全射
• 単射・・・$a \ne a' \Rightarrow f(a) \ne f(a')$の場合、fは単射
• 全単射・・・全射かつ単射
• AからBへの写像全部の集合を$\mathfrak{F}(A,B)$または$B^A$で表し、Aの上のBの配置集合という
• 特徴関数(定義関数)・・・Xを普遍集合としたとき、Xから{0,1}への写像$\chi_A$
  • $\chi_A(X) =\begin{cases} 1 & (\text{if } x \in A) \ 0 & (\text{if } x \in A^c=X-A) \end{cases}$

添数づけられた族

• $\mathbb{N}$から1つの集合Aへの写像aをAの元の列という
• a(n)を$a_n$とかき、元の列の第n項という
• 集合${a,b,\cdots,n}$から集合Aへの写像aをaの元の有限列という
• 一般に、ある集合$\Lambda$から集合Aへの写像を$\Lambda$によって添字付けられたAの元の族という
• $\Lambda$を添数集合といい、その元を添数という
• 集合族・・・族${(A$\lambda)}{\lambda \in \Lambda}で、$\Lambda$の各元$\lambda$においてとる値$A_\lambda$がそれぞれ一つの集合であるもの
• 部分集合族・・・上の集合族の、すべての$\lambda$にたいして$A_{\lambda} \subset X$となるもの
• 直積・・・$\Lambda$のすべての元$\lambda$に対しても$a(\Lambda) = a${\lambda} \in A{\lambda}を満足するような、族$(a${\lambda}){\lambda \in \Lambda}全体の集合
• 選出公理(axiom of choice)・・・$\forall \lambda \in \Lambda(A${\lambda} \ne \phi) \Rightarrow \prod{\lambda \in \Lambda} A_\lambda \ne \phi
• 射影(projection)・・・集合族の直積Aの元aに対して、aの$\lambda$においてとる値$a$\lambdaを対応させたとき、その写像を射影(記号: ${pr}\lambda \text{or} {proj}_\lambda$)という。
  • ${pr}$\lambda(a) = a\lambda

定理

• fをAからBへの写像とする
• fが全射であるとき、またそのときに限り、$f \circ s = I_B$となるs: B→Aが存在する
• fが単射であるとき、またそのときに限り、$r \circ f = I_A$となるr:B→Aが存在する

関係

• 関係・・・記号: R(x,y)、xRy
  • 同値関係の条件(同値律)
  • $\forall a \in A (aRa)$・・・反射律
  • $\forall a,b \in A (aRb \Rightarrow bRa)$・・・対称律
  • $\forall a,b,c \in A(aRb, bRc \Rightarrow aRc)$・・・推移律

以上。