snge.me

5分でわかる集合論-基礎編公開・2009年04月26日

2021/5/20 真部分集合について追記

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

集合論以前

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

基礎

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

部分集合

任意のものxについて、x∈A⇒x∈Bx \in A \Rightarrow x \in Bx∈A⇒x∈Bが正しいならば、AはBの部分集合である(記号A⊂B A \subset BA⊂B)
- 否定はA⊄BA \not \subset BA⊂B
th. A=B⇔A⊂B,A⊃BA = B \Leftrightarrow A \subset B, A \supset BA=B⇔A⊂B,A⊃B
th. 部分集合は推移性が成り立つ: A⊂B,B⊂C⇒A⊂CA \subset B, B \subset C \Rightarrow A \subset CA⊂B,B⊂C⇒A⊂C
(∀A)ϕ⊂A(\forall A) \phi \subset A(∀A)ϕ⊂A

(2021/5/20 追記)

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

集合演算

和集合(結び)・・・A∪B={x∣x∈A or x∈B}A \cup B = { x | x \in A \text{ or } x \in B }A∪B={x∣x∈A or x∈B}
- A⊂A∪B,B⊂A∪BA \subset A \cup B, B \subset A \cup BA⊂A∪B,B⊂A∪B・・・和集合は、足されたものを含む
- A⊂C,B⊂C⇒A∪B⊂CA \subset C, B \subset C \Rightarrow A \cup B \subset CA⊂C,B⊂C⇒A∪B⊂C
- A∪A=AA \cup A = AA∪A=A・・・冪等律
- A∪B=B∪AA \cup B = B \cup AA∪B=B∪A・・・交換律
- (A∪B)∪C=A∪(B∪C)(A \cup B) \cup C = A \cup (B \cup C)(A∪B)∪C=A∪(B∪C)・・・結合律
- 省略記法・・・A1,∪A2∪⋯∪AnA_1, \cup A_2 \cup \cdots \cup AnA1,∪A2∪⋯∪An、あるいは⋃i=1nAi\bigcup{i=1}^n A_i⋃i=1nAi
- A⊂B⇔A∪B=BA \subset B \Leftrightarrow A \cup B = BA⊂B⇔A∪B=B・・・ある集合に、その部分集合を足しても変わらない
- A⊂B⇒A∪C⊂B∪CA \subset B \Rightarrow A \cup C \subset B \cup CA⊂B⇒A∪C⊂B∪C
- ϕ∪A=A\phi \cup A = Aϕ∪A=A
共通部分(交わり)・・・A∩B={x∣x∈A,x∈B}A \cap B = \left{ x | x \in A, x \in B \right}A∩B={x∣x∈A,x∈B}
- A∩B≠ϕA \cap B \ne \phiA∩B=ϕのとき、A,Bは'交わる'という
- A∩B=ϕA \cap B = \phiA∩B=ϕのとき、A,Bは'交わらない'あるいは'互いに素である'という
- A⊃A∩B,B⊃A∩BA \supset A \cap B, B \supset A \cap BA⊃A∩B,B⊃A∩B
- A⊃C,B⊃C⇒A∩B⊃CA \supset C, B \supset C \Rightarrow A \cap B \supset CA⊃C,B⊃C⇒A∩B⊃C
- A∩A=AA \cap A = AA∩A=A・・・冪等律
- A∩B=B∩AA \cap B = B \cap AA∩B=B∩A・・・交換律
- (A∩B)∩C=A∩(B∩C)(A \cap B) \cap C = A \cap (B \cap C)(A∩B)∩C=A∩(B∩C)・・・結合律
- 省略記法・・・A1,∩A2∩⋯∩AnA_1, \cap A_2 \cap \cdots \cap AnA1,∩A2∩⋯∩An、⋂i=1nAi\bigcap{i=1}^n A_i⋂i=1nAi
- A⊂B⇔A∩B=AA \subset B \Leftrightarrow A \cap B = AA⊂B⇔A∩B=A
- A⊂B⇒A∩C⊂B∩C A \subset B \Rightarrow A \cap C \subset B \cap CA⊂B⇒A∩C⊂B∩C
- ϕ∩A=ϕ\phi \cap A = \phiϕ∩A=ϕ
分配律
- (A∪B)∩C=(A∩C)∪(B∩C)(A \cup B) \cap C = (A \cap C) \cup (B \cap C)(A∪B)∩C=(A∩C)∪(B∩C)
- (A∩B)∪C=(A∪C)∩(B∪C)(A \cap B) \cup C = (A \cup C) \cap (B \cup C)(A∩B)∪C=(A∪C)∩(B∪C)
吸収律
- (A∪B)∩A=A(A \cup B) \cap A = A(A∪B)∩A=A
- (A∩B)∪A=A(A \cap B) \cup A = A(A∩B)∪A=A
A,Bが互いに素であるとき、和集合A∪BA \cup BA∪BはAとBの直和という
差集合
- 集合Aの元であって、集合Bの元でないものの全体をつくる集合をA,Bの差といい、A-Bで表す
- A−B={x∣x∈A,x∉B}A-B = { x | x \in A, x \not \in B }A−B={x∣x∈A,x∈B}
- A⊃BA \supset BA⊃Bである場合、A-BをAに対するBの補集合という
考えている全体の集合・・・普遍集合、全体集合
Xが普遍集合のとき
- X-Aを単に「Aの補集合」といい、AcA^cAcで表す
- xをXの元としたとき、Ac={x∣x∈A}A^c = \left{ x | x \in A \right}Ac={x∣x∈A}あるいはx∈Ac⇔x∉Ax \in A^c \Leftrightarrow x \not \in Ax∈Ac⇔x∈A
- A∪Ac=X,A∩Ac=ϕA \cup A^c = X, A \cap A^c = \phiA∪Ac=X,A∩Ac=ϕ
- Acc=AA^{cc} = AAcc=A
- ϕc=X,Xc=ϕ{\phi}^c = X, X^c = \phiϕc=X,Xc=ϕ
- A⊂B⇔Ac⊃BcA \subset B \Leftrightarrow A^c \supset B^cA⊂B⇔Ac⊃Bc
de Morganの法則
- (A∪B)c=Ac∩Bc{(A \cup B)}^c = A^c \cap B^c(A∪B)c=Ac∩Bc
- (A∩B)c=Ac∪Bc{(A \cap B)}^c = A^c \cup B^c(A∩B)c=Ac∪Bc
集合系・・・集合の集合(その元が、すべてそれ自身集合であるような集合)
- 集合Xのすべての部分集合全体がつくる集合系を巾集合という(ここではP(X)\mathfrak{P}(X)P(X)と表現する)
- P(ϕ)=ϕ\mathfrak{P}(\phi) = {\phi}P(ϕ)=ϕ
- Xがn個の元からなる集合のとき、P(X)\mathfrak{P}(X)P(X)の要素は2n2^n2n個の要素を持つ
- 集合系の和集合(記号:⋃P\bigcup \mathfrak{P}⋃P)・・・P\mathfrak{P}Pに属するすべての集合の和集合、すなわち⋃P=x∣∃A∈P\bigcup \mathfrak{P}={x|\exists A \in \mathfrak{P}}⋃P=x∣∃A∈P
- 集合系の共通部分(記号:⋂P\bigcap \mathfrak{P}⋂P)・・・P\mathfrak{P}Pに属するすべての集合の共通部分、すなわち⋂P=x∣∀A∈P\bigcap \mathfrak{P}={x|\forall A \in \mathfrak{P}}⋂P=x∣∀A∈P
- ∀A∈P(A⊂⋃P)\forall A \in \mathfrak{P}(A \subset \bigcup \mathfrak{P})∀A∈P(A⊂⋃P)
- [∀A∈P(A⊂C)]⇒⋃P⊂C[\forall A \in \mathfrak{P}(A \subset C)] \Rightarrow \bigcup \mathfrak{P} \subset C[∀A∈P(A⊂C)]⇒⋃P⊂C
- ∀A∈P(A⊃⋂P)\forall A \in \mathfrak{P}(A \supset \bigcap \mathfrak{P})∀A∈P(A⊃⋂P)
- [∀A∈P(A⊃C)]⇒⋂P⊃C[\forall A \in \mathfrak{P}(A \supset C)] \Rightarrow \bigcap \mathfrak{P} \supset C[∀A∈P(A⊃C)]⇒⋂P⊃C

対応

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

写像

写像・・・対応のうち、始集合の任意の元aに対して、Γ(a)\Gamma(a)Γ(a)は終集合のただ一つの元から成る集合であるもの
定値写像・・・f(x)=1f(x)=1f(x)=1のように、値が固定の写像
恒等写像(IAI_AIA)・・・aにa自身を対応させる写像、IA(a)=aI_A(a) = aIA(a)=a
Pの元aのfによる像f(a)をすべて集めてできる集合をfによるPの像といい、f(P)と表す
P1⊂P2⇒f(P1)⊂f(P2)P_1 \subset P_2 \Rightarrow f(P_1) \subset f(P_2)P1⊂P2⇒f(P1)⊂f(P2)
f(P1∪P2)=f(P1)∪f(P2)f(P_1 \cup P_2) = f(P_1) \cup f(P_2)f(P1∪P2)=f(P1)∪f(P2)
f(P1∩P2)⊂f(P1)∩f(P2)f(P_1 \cap P_2) \subset f(P_1) \cap f(P_2)f(P1∩P2)⊂f(P1)∩f(P2)
f(A−P)⊃f(A)−f(P)f(A-P) \supset f(A) - f(P)f(A−P)⊃f(A)−f(P)
Q1⊂Q2⇒f−1(Q1)⊂f−1(Q2)Q_1 \subset Q_2 \Rightarrow f^{-1}(Q_1) \subset f^{-1}(Q_2)Q1⊂Q2⇒f−1(Q1)⊂f−1(Q2)
f−1(Q1∪Q2)=f−1(Q1)∪f−1(Q2)f^{-1}(Q_1 \cup Q_2) = f^{-1}(Q_1) \cup f^{-1}(Q_2)f−1(Q1∪Q2)=f−1(Q1)∪f−1(Q2)
f−1(Q1∩Q2)=f−1(Q1)∩f−1(Q2)f^{-1}(Q_1 \cap Q_2) = f^{-1}(Q_1) \cap f^{-1}(Q_2)f−1(Q1∩Q2)=f−1(Q1)∩f−1(Q2)
f−1(B−Q)=A−f1(Q)f^{-1}(B-Q) = A - f^{^1}(Q)f−1(B−Q)=A−f1(Q)
f−1(f(P))⊃Pf^{-1}(f(P)) \supset Pf−1(f(P))⊃P
f(f−1(Q))⊂Qf(f^{-1}(Q)) \subset Qf(f−1(Q))⊂Q
全射・・・f(A)=Bf(A) = Bf(A)=Bのとき、つまり終集合のすべての要素が指されている場合、fは全射
単射・・・a≠a′⇒f(a)≠f(a′)a \ne a' \Rightarrow f(a) \ne f(a')a=a′⇒f(a)=f(a′)の場合、fは単射
全単射・・・全射かつ単射
AからBへの写像全部の集合をF(A,B)\mathfrak{F}(A,B)F(A,B)またはBAB^ABAで表し、Aの上のBの配置集合という
特徴関数(定義関数)・・・Xを普遍集合としたとき、Xから{0,1}への写像χA\chi_AχA
- χA(X)={1(if x∈A)0(if x∈Ac=X−A)\chi_A(X) =\begin{cases} 1 & (\text{if } x \in A) \ 0 & (\text{if } x \in A^c=X-A) \end{cases} χA(X)={10(if x∈A)(if x∈Ac=X−A)

添数づけられた族

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

定理

fをAからBへの写像とする
fが全射であるとき、またそのときに限り、f∘s=IBf \circ s = I_Bf∘s=IBとなるs: B→Aが存在する
fが単射であるとき、またそのときに限り、r∘f=IAr \circ f = I_Ar∘f=IAとなるr:B→Aが存在する

関係

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

以上。

📎📎📎📎📎📎📎📎📎📎