計算機基礎論

集合論の基礎（１）

集合演算、デカルト積

（

教科書：1.1～1.3） 藤田 聡

集合と要素

対象(object)の集まりを集合(set)という 集合を構成する対象を、集合の要素 (element)、または元という 例: Vを英語の母音の集合とすると、 V ＝｛ a,e,i,o,u ｝であり、 たとえばaはVの要素

集合はその要素を含む(contain)あるいは 要素は集合に属す(belong to)という 要素aが集合Sに属すとき、a∈Sとかく ２つの集合A,Bが条件a∈A ↔ a∈B を満た すとき、AとBは等しい(equal)といい、A=B と記す

例

要素を明示することによって集合を表記す ることができる。たとえば • N ＝{ 0,1,2,… ｝ 自然数全体の集合 • Z ＝{ …, -2, -1, 0, 1, 2, … } 整数集合 • R ＝{ x | xは実数 } 実数集合

– Nはnatural number, Rはreal numberからきてお り、Zはドイツ語のZahlenからきている

空集合

要素をひとつも含まない集合を空集合 (empty set)と呼びΦであらわす

部分集合

AがBの部分集合(subset)であるとは、Aの 要素がつねにBの要素であるときであり、 A⊆Bと表示する A⊆B ＝ ∀x（x∈A→x∈B） 任意の集合Sに対して Φ⊆S ∧ S⊆S

真部分集合

A⊆BかつA≠Bのとき、AをBの真部分集合

集合の濃度

集合Sがちょうどn個の要素をもつとき、Sを 有限集合(finite set)と呼ばれる。またこの ときnをSの濃度(cardinality)と呼び、|S|な どであらわす 有限集合でない集合は無限集合である

例

定義からΦは有限集合であり、|Φ|＝0 いっぽうN, R, Zは無限集合

べき集合

• 集合Sを与えたときSのべき集合(power

set)はＳの部分集合の集合であり、P(S)と 表記する

例

• S ＝ { 0,1,2 }ならば、 • P(S) ＝ { Φ, {0}, {1}, {2}, {0,1}, {1,2}, {2,0}, {0,1,2} } • S ＝ Φならば P(S) ＝ {Φ} • S ＝{Φ}ならばP(S)＝P({Φ})＝{Φ, {Φ}}

直積（デカルト積）

• 順序対を(a₁, a₂, …, a_n)と表記する

• AとBの直積(Cartesian product)をA×Bで

例

• A＝{ 0,1,2 }, B＝{ a,b }とすると、

• A×B＝{ (0,a), (1,a), (2,a), (0,b), (1,b), (2,b) }

集合演算

集合和(union): A∪B＝{ x｜x∈A∨x∈B ｝ 集合積(intersection):

A∩B＝{ x｜x∈A∧x∈B } 集合差(difference):

A－B＝{ x｜x∈A∧x∉B } 補集合(complement):

例

例

• x∈ A∩Bとせよ

• x ∉A∩Bすなわちx∉A又はx∉Bが成立 • これはx∈A∪B、したがって

例

• 逆に、x∈ A∪Bとせよ • x∉A又はx∉Bすなわちx∉A∩Bが成立 • これはx∈A∩B、したがって A∩B⊇A∪B 両方から A∩B＝A∪B

集合論の基礎（２）

関係

二項関係

• 集合Aと集合Bの直積A×Bの部分集合Rを二項 関係と呼ぶ • A=Bのとき、RをA上の関係という • (a,b)∈Rのとき、aとbはRの関係にあるといい、 aRbまたはR(a,b)などとかく • 項の数をnとしたn項関係も自然に定義できる

関係の定義域と値域

• 関係R⊆A×Bの定義域(domain)は、 { a∈A | (a,b) ∈ R }

• 関係R⊆A×Bの値域(range)は、 { b∈B | (a,b) ∈ R }

例

• A = { 1, 2, 3, 4 }

• A上の大小関係Rは以下のように定義される： • R = { (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) } • Rの定義域は{ 1,2,3 }、Rの値域は{ 2,3,4 }

関係の性質

(1)

• 反射性 – 任意のa∈Aについて(a,a)∈Rのとき、Rは反射的 であるという • 対称性 – 任意のa,b∈Aについて(a,b)∈Rならば(b,a)∈R のとき、Rは対称的であるという • 推移性 – 任意のa,b,c∈Aについて(a,b)∈Rかつ(b,c)∈R ならば(a,c)∈Rのとき、Rは推移的であるという

関係の性質

(2)

• 反反射性 – 任意のa∈Aについて(a,a)∉Rのとき、Rは反反射 的であるという • 反対称性 – 任意のa,b∈Aについて(a,b)∈Rかつ(b,a)∈Rな らばa=bであるとき、Rは反対称的であるという

同値関係

• 集合A上の関係Rが反射的、対称的、推移的 であるとき、Rは同値関係であるという • 「通常の意味での」同値をイメージすればOK – 数字に対する等号 – 集合の意味での等号 – リストの意味での等号、etc.. – 「３で割った余りが等しい」というのも同値関係

同値類と代表元

• A上の同値関係Rを考える。任意のa∈Aに大し て集合[a]_R = { x | (a,x)∈R }をaのRによる同 値類といい、aを同値類[a]_Rの代表元と呼ぶ

集合の分割

• Aが空でないとき、{ S₁, S₂, …, S_m }は以下の 条件を満たすときAの分割(partition)という： 1. 各S_i が空でないこと 2. 任意のi,jについて(i≠j)、S_i∩S_j =φであること 3. S₁∪S₂∪ … ∪S_m= Aであること

商集合

• Aの同値関係Rに対して、すべての同値類の集 合{ [a]_R | a∈A }をAのRによる商集合と呼び 、A/Rとかく

• Aの同値関係Rによる商集合A/Rはひとつの分 割である

順序関係

(ordered relation)

• 以下の３つの法則が成立するような関係 ≦を順序関係(ordered relation)と呼ぶ １） 反射法則(reflexive law)： ｘ≦ｘ ２） 反対称法則(asymmetric law)： ｘ≦ｙ かつ ｙ≦ｘ ならば ｘ＝ｙ ３） 推移法則(transitive law)： ｘ≦ｙ かつ ｙ≦ｚ ならば ｘ≦ｚ

順序集合

(ordered set)

• 元の間に順序関係が定義された集合Xを

順序集合と呼ぶ

• 元a∈Xは、任意のｘ∈Xに対してｘ＜aとな らないとき極小(minimal)であるという

ハッセ図

111 011 101 110 001 010 100 000

整列集合

(well ordered set)

• 順序集合Xが、条件

∀ｘ、ｙ∈

X（ｘ≦ｙ∨

ｙ≦ｘ）を満たすとき、

全順序

(total

ordered)

であるという

• 全順序集合Xの空でない任意の部分集合 が極小元(実際には最小元）をもつとき、X を整列集合という

例

• 非負整数の集合は，通常の順序のもとで整列集 合である • 整数の集合は整列集合ではない • X={a,b,c,d}とし、２X_{を考える。通常の集合間の} 包含関係で順序を定めると，２Xは全順序ではな いので整列集合ではない • 非負実数の集合は通常の順序のもとで整列集 合ではない。たとえば部分集合（１，２）は最小元 をもたない

数学的帰納法

(Mathematical Induction)

• 非負整数ｎに対する性質P(n)を証明すると き， １．基底段階(base step)： P(0)が正しいことを示す ２．帰納段階(induction step)：任意の非負 整数ｎについて、P(n)→ P(n+1)が正しいこ とを示す（P(n)を帰納法仮定(induction hypothesis)と呼ぶ）

数学的帰納法

(Mathematical Induction)

• 要するに， （P(0)∧∀n （P(n)→P(n+1))）→∀n P(n) ※∀n P(n)を仮定しているわけではないこと に注意

数学的帰納法が正しいことの証明（１）

• （P(0)∧∀n（P(n)→P(n+1))）がTであるにも関わ らず∀nP(n)がFであると仮定する • したがってあるｎが存在してP(n)=F • S=｛ n： P(n)=F ｝とすると、S≠Φであるから、 最小元ｋが存在する(整列集合だから）

数学的帰納法が正しいことの証明（２）

• P(0）＝Tであるからk≠０である • k-1は非負整数であり，k-1<kであるから、k-1 はSには属さない。すなわちP(k-1)=T • ところがP(k-1)→P(k)はTだからこれは矛盾。 証明終わり

集合論の基礎（３）

関数，濃度

(

教科書： 1.9, 1.10)

藤田 聡 （広島大学）

関数

(function)とは？

• AとBを集合とする • AからBへの関数とは、Aの各要素に対するB の要素の割当てである • b∈Bをa∈Aに対して割当てられた要素とす ると、b＝f(a)とあらわす

• Aを領域(domain)、Bを終集合(co-domain)、 b＝f(a)をaの像、f(A)＝｛f(a)｜a∈A｝を値域 (range)とよぶ

例

• A＝{ 春, 夏, 秋, 冬 }, • B＝{ コーヒー, 紅茶, ミルク }とする f 春 コーヒー 夏 紅茶 秋 ミルク 冬

関数の種類（１）

• 単射(injective)又は一対一(one-to-one) ※ f(x)＝f(y) ⇒ x＝y を満たすとき a １ b ２ c ３ こんなことが起こらない

関数の種類（２）

• 全射(surjective)又は上への関数(onto) ※ B＝f(A)であるとき a １ b ２ c ３ こんなものがないとき

関数の種類（３）

• 全単射(bijection)又は一対一対応 (one-to-one correspondence) a １ b ２ c ３

関数の合成

(composition)

• g: A→B, f: B→Cとする

• f○gを(f○g)(x)＝f(g(x))で定義する

A B _C

例

• f(x)=2x+3, g(x)=3x+2とする (f○g)(x)=f(g(x))=f(3x+2) =2(3x+2)+3 = 6x+7 (g○f)(x)=g(f(x))=g(2x+3) =3(2x+3)+2=6x+11

逆関数

• f: A→Bを全単射とする • f－１: B→Aを、

f(A)=B のときf-1_(B)=A

例

• f(x)=x+1のとき、 f-1_(y)=y-1

濃度

(cardinality)

• 集合AとBの間に一対一対応があるとき、A とBの濃度は等しいという

• 自然数と同じ濃度をもつ集合を可算集合 (countable set)とよぶ

例

• 奇数の自然数のみならなる集合は可算で ある f(n)=2n-1 とすれば、f(n)は奇数の集合と自然数の集 合との間の一対一対応を与える なぜか？

例

１） f(n)は単射である f(n)=f(m) とすると、2n-1=2m-1よりn=m が結論される ２） f(n)は全射である あきらか

例

• 実数集合は非可算(uncountable)である なぜか

例３

• 実数区間(0,1)ですら可算でないことを示す （可算であるとして矛盾を導く） • 可算であるから、N(自然数の集合）と(0,1) の間の一対一対応が存在する r₀ 0.d₀₀d₀₁… r₁ 0.d₁₀d₁₁… r₂ 0.d₂₀d₂₁… …

例３

r 0.d₁d₂… を以下のように定める： もしd_nn≠4ならばd_n=4 もしd_nn=4ならばd_n=5 するとあきらかにr≠r_n(n=0, 1, 2, …) よって矛盾 →実数集合は非可算である

列

(sequence)とは？

• 非負整数（あるいは自然数）の集合からあ る集合への関数を列という

• 数ｎに対する像をA_nとかき、その列の項 (term)とよぶ

• geometric progression, arithmetic progression, etc.

級数

(summation)

• nのことを上限(upper limit)、ｍのことを下限 (lower limit)、ｊのことを和の添字(index of summation)とよぶ n m n m j m j

a

a

a

a





_









₁



例 幾何数列

(等比数列)

※幾何級数のことをgeometric series、 等差級数のことをarithmetic seriesという







n j j

ar

S

0

例 幾何数列

(等比数列)

1

)

1

(

1









r

r

a

S

n ) 1 ( 1 1 0 0 1            





n n n j j n j j r a S ar a ar ar rS

関数の増加速度

• ビッグO記法（Big-O notation) f(x)＝O(g(x))であるのは、ある定数c>0と k>0が存在して、任意のx>kに対して |f(x)| ≦ c|g(x)| を満たすことである

例

• f(x)＝6x2_{＋2x＋3とすると、}

f(x) = O(x2₎

f(x) = O(x3_{） だけれども}

例

• n!を考える

n! = 1・2・…・n ≦ nn

したがって

関数の増加速度（２）

• ビッグΩ記法（Big-Ω notation) f(x)=Ω(g(x))であるのは、ある定数c>0と k>0が存在して、任意のx>kに対して |f(x)| ≧ c|g(x)| を満たすことである

例６

• f(x)=6x2_{＋2x＋1とすると、}

f(x) = Ω(x2₎

f(x) = Ω(x) だけれど f(x) ≠ Ω(x3₎