2001年度情報数学

Ver.2
1
再掲：講義資料の所在 (URL)

下のＵＲＬは「情報数学」シラバスの「履修上の
注意」に掲載されています。

後藤研のＷＥＢページ（日本語）の「後藤先生担
当の講義」から辿ることもできます。
http://www.goto.info.waseda.ac.jp/
~goto/infomath.html
ここに ~ が必要
2
参考書（金曜日・後藤担当分）


講義資料の多くの部分を作成した上田先生の参考文献
（１） J. マトウシェク, J. ネシェトリル著
根上生也, 中本敦浩訳「離散数学への招待上」
シュプリンガー・フェアラーク東京 ISBN 4-431-70896-0
（２）M.A.アービブ, A.J.クフォーリ, R.N.モル著
甘利俊一, 金谷健一, 嶋田晋訳
「計算機科学入門」 (Information & Computing 1）
サイエンス社 ISBN4-7819-0375-4
後藤が教材を追加した際に参照した文献
（３）守屋悦朗「コンピュータサイエンスのための離散数学」
(Information & Computing 61)
サイエンス社 ISBN 4-07819-0643-5
（４）小野寛晰「情報代数」情報数学講座第2巻
共立出版 ISBN 4-320-02652-7
3
演習問題の解答はスライドに掲載せず

例外として次を解説「ラッセルのパラドックス」
 集合Ｘを次のような「もの」の集まりとする
Ｘの要素は「自分自身を要素として含まない集
合」である X  {x | x  x}, x は集合
［説明］Ｘは集合である。ＸはＸ自身を含むか、含
まないか、いずれかである。もし X  X とすると
X  X  X となる。すなわちＸはＸを含むから定
義によりＸはＸの要素ではありえない。これは矛
盾。一方 X  X とすると、ＸがＸ自身を含まない
のであるから、定義によりＸはＸの要素となる筈
である。これは矛盾。
4
写像 (map) または関数 (function)


ＡとＢを集合とする
f
がＡからＢへの写像 (map) または関数 (function)
であるとは
 ｆがＡの各要素に対して、Ｂのただ一つの要素を対
応させる規則であること
［例題］実数ｘにｘの実数平方根を対応させる規則
x  0に対して　x は定義されない。
x  0に対して　二つの実数平方根 x と  xが対応する。
上の対応規則は関数（写像）ではない。
5
関数と関数空間
A の要素にB の一つの
要素を対応づける規則 f
A から B への
写像（関数）全体の集合
f : A B
定義域（始集合）
domain
終集合
codomain (値域と区別)
集合Ｂの要素の中でｆの像になっている要素の集合
f ( A)  { f (a) | a  A } をｆの値域 (range) という。


Aと書くことがある。説明は後述。
を
A B
B
6
関数のグラフ
2
関数の内包的定義： y  x  3x  5
 外延的定義： , 1,  7 , 0,  5 , 1, 1 , 2, 5 , 
これを関数のグラフという
f : A  B のグラフとは { a, f (a) ) | a  A }


グラフは直積ＡＸＢ
の部分集合である
A

B
グラフが同じ関数は等しい（外延的な等しさ）
単射と全射



論理記号ならば
implies
写像 (関数) f : X  Y が任意の x1, x 2  X に対し
て、 f ( x1)  f ( x2)  x1  x2 という性質を満たす
時に単射という。１対１写像ともいう。
上の性質は x1  x2  f ( x1)  f ( x2) とも書ける。
7
写像 (関数) f : X  Y が、任意の y  Y に対して
f ( x)  y なる x  X が存在する時に全射という。
上への写像ともいう
全射かつ単射である写像を全単射という。
［例］ f : R  R を f ( x)  x3 と定めると、全単射
となる
8
関数と部分関数


論理記号同値
f B 
①
f  A B
②  x  A y  B ( x, y  f )
③  x  A y  B y  B
 x, y  f  x, y  f  y  y 
A
条件②が成り立たない場合は部分関数(部分写像)
9
多変数の関数（多引数の関数）
2 引数関数 f ( x, y ) の考え方
 直積の上の1 引数関数 f ( x, y ) と同一視
 x だけ指定すると y に関する 1 引数関数になる．
つまり f ( x, y )  f ( x) ( y ) を満たすような関数
f  （＝ x を与えると「y に関する1引数関数」を
返す関数）を考えることができる (currying)
 A  B  C と A  ( B  C ) は対等
 2次元配列は1次元配列の配列 (プログラム)
 0 引数関数 f ( ) というのは定数のことである
 数学ではあまり見ないがプログラムで使う

10
配列と関数

プログラムでは区別がある。
数学的には同一視できる。
 n 要素の一次元配列： A

n
0, 1,, n 1 を定義域 (domain) とし、
A を終集合とする関数
上の二つは対等（同一視可能）．
 集合論では自然数を
 上の見方は
n  {0, 1, , n  1} と定義
n という表記と合致する
A
11
部分集合と特性関数


S ( A) （または S  2 A ）と S  A とは同じ意味
集合 A の部分集合を一つ与えることは A  0, 1
に属する関数を一つ決めることと同じ
A
 つまり 2 と A  0, 1 とは対等
 部分集合 S に対応する関数のことを
S の特性関数 (characteristic function) という
 1 if x  S
s( x)  
 0 if x  S
c
S   red, blue, yellow 
black
red
cyan
green
0
1
0
0
magenta
blue
yellow
white
0
1
1
0
12
集合族 (family of sets)
プログラミングでは配列が便利である。
集合に添字をつけることがある。
 A0 , A1, A2 , A3 , 
 添字の種類は有限でも無限でもよい。自然数でな
くてもよい。添字の集合を I とする集合族を


 A ii I
と書く。
 集合族は，実は添字 i を集合 A i に写像する関数に
他ならない。
集合の 

13
関数
A   A i  iI
B   A i   A i i  I 
和集合
iI
とするとき、
A  f B

i
I

i  I  f (i )  A i 
i I
 引数の値に応じて，返す値の型が決まる関数

例： n を与えると配列 0, 0,, 0 が返る

n個
集合の

直和の個数を一般化したもの
 A   i, x


14
i I
i
i  I  x  Ai 
例：Ａがアルファベットの集合
有限長の文字列全体の集合は
A0  A1  A2   
直和

n
A

n Ν
演習：I  {0,1} , A0 { 2, 3, 4 }, A1={ 3, 5 } の場合に
上の定義による  Ai の要素を具体的に記せ。
iI
15
無限集合

無限集合の例：
Ν  0, 1, 2,,
2n
Z  ,2,  1, 0, 1, 2,
n  Ν,
cardinal number,
cardinality
potency,
power
 集合Ａの要素の数 |Ａ| を基数、濃度という。
 上の例では、要素の数は無限。
ただし、すべての要素にもれなく通し番号をつ
けることができる。
 ここで、無限の要素に必ず通し番号がつけ
られるかどうかは自明でない。（後述）
16
有限集合と無限集合の要素の数に注目

有限集合





{2, {4, 6, 8}, 10, 12, {}}
0
{0 } すなわち {{}}
{x, y}
無限集合
 {0, 1,
2, 3, ...} and {1, 2, 3, 4, ...}
 {0, 1, 2, 3, ...} and {1, 10, 100, 1000, ...}
 Z とR
17
可算無限集合
「集合 S の全要素に通し番号がつけられる」
⇔ 「S と自然数の集合N とが対等」（S  N ）
 N と対等な集合のことを可算無限集合または可算集
合 (enumerable set, denumerable set, countable set)
という。


2n
n  Ν や Z  ,2,  1, 0, 1, 2, は
可算無限集合である
 例題：自然数の集合Nから0を除いた集合 Nー{0}
とNとの間には f 1  x  1 という全単射が存在する。
よって | N  {0} || N | である。
18
集合の濃度
A や B が有限集合のとき， A と B とが対等である
ための必要十分条件は A  B である。
f : A  B が全射ならば A  B , 単射ならば A  B .
 無限集合のときも， A  B のとき，そしてそのと
きに限って A  B と書く。 A ，つまり一般化さ
れた個数のことを A の濃度 (cardinarity) という。

N のことをしばしば 0 と書く
例： Z  0
アレフ・ゼロ
 数学者は


無限集合では、自分自身の真部分集合と対等にな
る場合がある。例： | N  {0} || N |
19
可算（無限）集合の例

素数全体の集合
 2, 3, 5, 7, 11,
 一般に可算集合の無限部分集合は可算集合

自然数格子点の集合
NN

有理数全体の集合
Q

有限長の数列全体の集合
N0  N1  N2   
n
N

n Ν

整数Z
k if m  2k
f 2 : N  Z, f 2(m) 
 k if m  2k  1
20
自然数 N と整数 Z

全単射
k if m  2k
f 2 : N  Z, f 2(m) 
 k if m  2k  1
０
１
２
３
４
５
６
７
８
９
－７－６－５－４－３－２－１０
１
２
３
４
５
６
７
８
９
21
可算でない無限集合
対角線論法
実数全体の集合 R は可算集合ではない
［証明の概略］R’ を 0 および正の実数の集合とする。
N⊂R’⊂Rである。|N| ≦ |R’| ≦ |R| である。
NからR’への全単射 f が存在すると仮定する。
f (m)  km dm0dm1dmn  有限小数は 0 を付ける
.
f (0)  k .d d d 
f (1)  k .d d d 
f (2)  k .d d d 
~ ~
~
r  0.d d  d 
0
1
00
10
2
20
00
01
02
11 12
21
11
22
nn
~ 1 if d  0
d 
0 if d  0
ｆは全射であるからｒ＝ｆ（ｓ）
となる自然数ｓが存在する
筈。そのｄｓｓに注目する。
22
可算でない無限集合
［続］r=f(s)となるsが存在する。ところでf(s)の小数点
以下第(s+1)桁目は定義によりdssである。一方で、r
～
の小数点以下第(s+1)桁目は定義によりdssであり、こ
の二つは一致しない。 ~
d ss  dss
Nの部分集合全体の集合 2 N は可算集合でない
A
任意の集合Aに対して | A |  | 2 |
N
 自然数上の関数全体の集合 N は可算集合でない

0
0
0
2 
0
 
再履修の諸君に重要な連絡
23
 再履修の諸君に大切な連絡があります
 できるだけ迅速に上田和紀先生にメールで連
絡をすること
 メールアドレスが不明の場合には、学科事務
所で尋ねるか、クラス担任の先生に質問する

Download Report