計算機基礎論

Size: px

Start display at page:

Download "計算機基礎論"

りえつつの
5 years ago
Views:

1 集合論の基礎 (1) 集合演算デカルト積 ( 教科書 :1.1~1.3) 藤田聡 ( 広島大学 )

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

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

4 例要素を明示することによって集合を表記することができるたとえば N ={ 0,1,2, } 自然数全体の集合 Z ={, -2, -1, 0, 1, 2, } 整数集合 R ={ x x は実数 } 実数集合 N は natural number, R は real number からきており Z はドイツ語の Zahlen からきている定義から {1,3,5} ={5,3,1}

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

6 部分集合 A が B の部分集合 (subset) であるとは A の要素がつねに B の要素であるときであり A B と表示する A B = x(x A x B) 任意の集合 S に対して Φ S S S

7 真部分集合 A B かつ A B のとき A を B の真部分集合 (proper subset) と呼び A B と表記する

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

9 例定義から Φ は有限集合であり Φ =0 いっぽう N, R, Z は無限集合無限集合の濃度については後述する

10 べき集合集合 S を与えたとき S のべき集合 (power set) は S の部分集合の集合であり P(S) と表記する

11 例 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({Φ})={Φ, {Φ}}

12 直積 ( デカルト積 ) 順序対を (a 1, a 2,, a n ) と表記する A と B の直積 (Cartesian product) を A B であらわす : A B={(a,b) a A b B }

13 例 A={ 0,1,2 }, B={ a,b } とすると A B={ (0,a), (1,a), (2,a), (0,b), (1,b), (2,b) }

14 集合演算集合和 (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): A={ x x A}=U-A (U: universe)

15 例等式 A B=A B を証明しよう

16 例 x A B とせよ x A B すなわち x A 又は x B が成立これは x A B したがって A B A B

17 例逆に x A Bとせよ x A 又はx Bすなわちx A Bが成立これはx A B したがって A B A B 両方から A B=A B

18 集合論の基礎 (2) 関係 ( 教科書 :1.4~1.8)

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

20 関係の定義域と値域関係 R A B の定義域 (domain) は { a A (a,b) R } 関係 R A B の値域 (range) は { b B (a,b) R }

21 例 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 }

22 関係の性質 (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 は推移的であるという

23 関係の性質 (2) 反反射性任意の a A について (a,a) R のとき R は反反射的であるという反対称性任意の a,b A について (a,b) R かつ (b,a) R ならば a=b であるとき R は反対称的であるという

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

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

26 集合の分割 A が空でないとき { S 1, S 2,, S m } は以下の条件を満たすとき A の分割 (partition) という : 1. 各 S i が空でないこと 2. 任意の i,j について (i j) S i S j =φ であること 3. S 1 S 2 S m = A であること

27 商集合 A の同値関係 R に対してすべての同値類の集合 { [a] R a A } を A の R による商集合と呼び A/R とかく A の同値関係 R による商集合 A/R はひとつの分割である

28 順序関係 (ordered relation) 以下の 3 つの法則が成立するような関係を順序関係 (ordered relation) と呼ぶ 1) 反射法則 (reflexive law): x x 2) 反対称法則 (asymmetric law): x y かつ y x ならば x=y 3) 推移法則 (transitive law): x y かつ y z ならば x z

29 順序集合 (ordered set) 元の間に順序関係が定義された集合 X を順序集合と呼ぶ元 a X は任意の x X に対して x<a とならないとき極小 (minimal) であるという

30 ハッセ図

31 整列集合 (well ordered set) 順序集合 X が条件 x y X(x y y x) を満たすとき全順序 (total ordered) であるという全順序集合 X の空でない任意の部分集合が極小元 ( 実際には最小元 ) をもつとき X を整列集合という

32 例非負整数の集合は, 通常の順序のもとで整列集合である整数の集合は整列集合ではない X={a,b,c,d} とし 2 X を考える通常の集合間の包含関係で順序を定めると,2 X は全順序ではないので整列集合ではない非負実数の集合は通常の順序のもとで整列集合ではないたとえば部分集合 (1,2) は最小元をもたない

33 数学的帰納法 (Mathematical Induction) 非負整数 n に対する性質 P(n) を証明するとき, 1. 基底段階 (base step): P(0) が正しいことを示す 2. 帰納段階 (induction step): 任意の非負整数 n について P(n) P(n+1) が正しいことを示す (P(n) を帰納法仮定 (induction hypothesis) と呼ぶ )

34 要するに, 数学的帰納法 (Mathematical Induction) (P(0) n (P(n) P(n+1))) n P(n) n P(n) を仮定しているわけではないことに注意

35 数学的帰納法が正しいことの証明 (1) (P(0) n(p(n) P(n+1))) が T であるにも関わらず np(n) が F であると仮定するしたがってある n が存在して P(n)=F S={ n: P(n)=F } とすると S Φ であるから最小元 k が存在する ( 整列集合だから )

36 数学的帰納法が正しいことの証明 (2) P(0)=T であるから k 0 である k-1 は非負整数であり,k-1<k であるから k-1 は S には属さないすなわち P(k-1)=T ところが P(k-1) P(k) は T だからこれは矛盾証明終わり

37 集合論の基礎 (3) 関数, 濃度 ( 教科書 : 1.9, 1.10) 藤田聡 ( 広島大学 )

38 関数 (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) とよぶ

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

40 関数の種類 (1) 単射 (injective) 又は一対一 (one-to-one) f(x)=f(y) x=y を満たすとき a 1 b 2 c 3 こんなことが起こらない

41 関数の種類 (2) 全射 (surjective) 又は上への関数 (onto) B=f(A) であるとき a 1 b 2 c 3 こんなものがないとき

42 関数の種類 (3) 全単射 (bijection) 又は一対一対応 (oneto-one correspondence) a 1 b 2 c 3

43 関数の合成 (composition) g: A B, f: B C とする f g を (f g)(x)=f(g(x)) で定義する A B C g f

44 例 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

45 逆関数 f: A Bを全単射とする f -1 : B Aを f(a)=b のときf -1 (B)=A によって定義する

46 例 f(x)=x+1 のとき f -1 (y)=y-1

47 濃度 (cardinality) 集合 A と B の間に一対一対応があるとき A と B の濃度は等しいという自然数と同じ濃度をもつ集合を可算集合 (countable set) とよぶ

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

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

50 例実数集合は非可算 (uncountable) であるなぜか ( 対角線論法という方法で証明できる )

51 例 3 実数区間 (0,1) ですら可算でないことを示す ( 可算であるとして矛盾を導く ) 可算であるから N( 自然数の集合 ) と (0,1) の間の一対一対応が存在する 0.d 00 d 01 r 0 r 1 r 2 0.d 10 d 11 0.d 20 d 21

52 例 3 r 0.d 1 d 2 を以下のように定める : もし d nn 4 ならば d n =4 もし d nn =4 ならば d n =5 するとあきらかに r r n (n=0, 1, 2, ) よって矛盾実数集合は非可算である

53 列 (sequence) とは? 非負整数 ( あるいは自然数 ) の集合からある集合への関数を列という数 n に対する像を A n とかきその列の項 (term) とよぶ geometric progression, arithmetic progression, etc.

54 級数 (summation) n j m a j a m a m 1 a n n のことを上限 (upper limit) m のことを下限 (lower limit) j のことを和の添字 (index of summation) とよぶ

55 例幾何数列 ( 等比数列 ) S n ar j j 0 幾何級数のことを geometric series 等差級数のことを arithmetic series という

56 例幾何数列 ( 等比数列 ) 1 1) ( 1 r r a S n 1) ( n n n j j n j j r a S ar a ar ar rs

57 関数の増加速度ビッグ O 記法 (Big-O notation) f(x)=o(g(x)) であるのはある定数 c>0 と k>0 が存在して任意の x>k に対してを満たすことである f(x) c g(x)

58 例 f(x)=6x 2 +2x+3とすると f(x) = O(x 2 ) f(x) = O(x 3 ) だけれども f(x) O(x)

59 例 n! を考える n! = 1 2 n n n したがって log(n!) n log n =O(n log n) = O(n 2 )

60 関数の増加速度 (2) ビッグ Ω 記法 (Big-Ω notation) f(x)=ω(g(x)) であるのはある定数 c>0 と k>0 が存在して任意の x>k に対してを満たすことである f(x) c g(x)

61 例 6 f(x)=6x 2 +2x+1とすると f(x) = Ω(x 2 ) f(x) = Ω(x) だけれど f(x) Ω(x 3 )

Basic Math. 1 0 [ N Z Q Q c R C] 1, 2, 3,... natural numbers, N Def.(Definition) N (1) 1 N, (2) n N = n +1 N, (3) N (1), (2), n N n N (element). n/ N.

Basic Math. 1 0 [ N Z Q Q c R C] 1, 2, 3,... natural numbers, N Def.(Definition) N (1) 1 N, (2) n N = n +1 N, (3) N (1), (2), n N n N (element). n/ N. Basic Mathematics 16 4 16 3-4 (10:40-12:10) 0 1 1 2 2 2 3 (mapping) 5 4 ε-δ (ε-δ Logic) 6 5 (Potency) 9 6 (Equivalence Relation and Order) 13 7 Zorn (Axiom of Choice, Zorn s Lemma) 14 8 (Set and Topology)