http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html Ver.2 再掲：講義資料の所在 (URL) 下のＵＲＬは「情報数学」シラバスの「履修上の注意」に掲載されています。 後藤研のＷＥＢページ（日本語）の「後藤先生担当の講義」から辿ることもできます。 http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html ここに ~ が必要

参考書（金曜日・後藤担当分） 講義資料の多くの部分を作成した上田先生の参考文献 （１） 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 

演習問題の解答はスライドに掲載せず 例外として次を解説「ラッセルのパラドックス」 集合Ｘを次のような「もの」の集まりとする Ｘの要素は「自分自身を要素として含まない集合」である ［説明］Ｘは集合である。ＸはＸ自身を含むか、含まないか、いずれかである。もし　　　とすると 　　　　　 となる。すなわちＸはＸを含むから定義によりＸはＸの要素ではありえない。これは矛盾。一方　　　とすると、ＸがＸ自身を含まないのであるから、定義によりＸはＸの要素となる筈である。これは矛盾。

写像 (map) または関数 (function) ＡとＢを集合とする f がＡからＢへの写像 (map) または関数 (function) であるとは ｆがＡの各要素に対して、Ｂのただ一つの要素を対応させる規則であること ［例題］実数ｘにｘの実数平方根を対応させる規則 上の対応規則は関数（写像）ではない。

関数と関数空間 集合Ｂの要素の中でｆの像になっている要素の集合 をｆの値域 (range) という。 を と書くことがある。説明は後述。 A の要素にB の一つの 要素を対応づける規則 f A から B への 写像（関数）全体の集合 集合Ｂの要素の中でｆの像になっている要素の集合 　　　　　　　　　をｆの値域 (range) という。 　　　　を　　と書くことがある。説明は後述。 定義域（始集合） domain 終集合 codomain (値域と区別)

関数のグラフ A B 関数の内包的定義： 外延的定義： これを関数のグラフという グラフは直積ＡＸＢ の部分集合である 　　　　　　のグラフとは グラフは直積ＡＸＢ の部分集合である グラフが同じ関数は等しい（外延的な等しさ） A B

単射と全射 写像 (関数) が任意の に対して、 という性質を満たす時に単射という。１対１写像ともいう。 上の性質は とも書ける。 論理記号　ならば implies 写像 (関数) 　　　　　が任意の　　　　　に対して、　　　　　　　　　　　という性質を満たす時に単射という。１対１写像ともいう。 上の性質は　　　　　　　　　　　とも書ける。 写像 (関数) 　　　　　が、任意の　　　に対して 　　　　なる　　　　が存在する時に全射という。上への写像ともいう 全射かつ単射である写像を全単射という。 ［例］　　　　　を　　　　　と定めると、全単射となる

関数と部分関数 論理記号　同値 条件②が成り立たない場合は部分関数(部分写像)

多変数の関数（多引数の関数） 2 引数関数 の考え方 直積の上の1 引数関数 と同一視 2 引数関数 の考え方 直積の上の1 引数関数 と同一視 x だけ指定すると y に関する 1 引数関数になる．つまり を満たすような関数 （＝ x を与えると「y に関する1引数関数」を返す関数）を考えることができる (currying) と 　は対等 2次元配列 は1次元配列の配列 (プログラム) 0 引数関数 というのは定数のことである 数学ではあまり見ないがプログラムで使う

配列と関数 プログラムでは区別がある。 数学的には同一視できる。 n 要素の一次元配列： を 定義域 (domain) とし、 　　を終集合とする関数 上の二つは対等（同一視可能）． 集合論では自然数を　　　　　　　　　と定義 上の見方は　　という表記と合致する

部分集合と特性関数 （または ）と とは同じ意味 集合 A の部分集合を一つ与えることは に属する関数を一つ決めることと同じ （または ）と とは同じ意味 集合 A の部分集合を一つ与えることは に属する関数を一つ決めることと同じ つまり と とは対等 部分集合 S に対応する関数のことを S の特性関数 (characteristic function) という black magenta red 1 blue 1 cyan yellow 1 green white

集合族 (family of sets) プログラミングでは配列が便利である。 集合に添字をつけることがある。 と書く。 集合族は，実は添字 i を集合 　に写像する関数に他ならない。

集合の 関数 とするとき、 引数の値に応じて，返す値の型が決まる関数 例： n を与えると配列　　　　　 が返る 和集合

集合の 直和の個数を一般化したもの 例：Ａがアルファベットの集合 有限長の文字列全体の集合は 例：Ａがアルファベットの集合 　有限長の文字列全体の集合は 演習：I  {0,1} , A0 { 2, 3, 4 }, A1={ 3, 5 } の場合に 上の定義による　　　の要素を具体的に記せ。 直和

cardinal number, cardinality 無限集合 無限集合の例： 集合Ａの要素の数 |Ａ| を基数、濃度という。 上の例では、要素の数は無限。 ただし、すべての要素にもれなく通し番号をつけることができる。 ここで、無限の要素に必ず通し番号がつけられるかどうかは自明でない。（後述） cardinal number, cardinality potency, power

有限集合と無限集合の要素の数に注目 有限集合 無限集合 Z と R

可算無限集合 「集合 S の全要素に通し番号がつけられる」 ⇔ 「S と 自然数の集合N とが対等」（ ） N と対等な集合のことを可算無限集合または可算集合 (enumerable set, denumerable set, countable set) という。 や 　は 可算無限集合である 例題：自然数の集合Nから0を除いた集合 Nー{0} とNとの間には　　　　という全単射が存在する。よって　　　　　　　である。

集合の濃度 A や B が有限集合のとき， A と B とが対等であるための必要十分条件は である。 が全射ならば 単射ならば 　　　　が全射ならば　　　　単射ならば 無限集合のときも，　　　のとき，そしてそのときに限って　　　　と書く。　 ，つまり一般化された個数のことを A の濃度 (cardinarity) という。 数学者は　　のことをしばしば　　と書く 例：　　　　　　　　　　アレフ・ゼロ 無限集合では、自分自身の真部分集合と対等になる場合がある。例：

可算（無限）集合の例 素数全体の集合 一般に可算集合の無限部分集合は可算集合 自然数格子点の集合 有理数全体の集合 有限長の数列全体の集合 整数Z

自然数 N と整数 Z 全単射 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ －７ －６ －５ －４ －３ －２ －１ ０ １ ２ ３ ４ ５ ６ ７ ８ ９

可算でない無限集合 対角線論法 実数全体の集合 R は可算集合ではない ［証明の概略］R’ を 0 および正の実数の集合とする。N⊂R’⊂Rである。|N| ≦ |R’| ≦ |R| である。 NからR’への全単射 f が存在すると仮定する。 有限小数は 0 を付ける ｆは全射であるからｒ＝ｆ（ｓ）となる自然数ｓが存在する筈。そのｄｓｓに注目する。

可算でない無限集合 ［続］r=f(s)となるsが存在する。ところでf(s)の小数点以下第(s+1)桁目は定義によりdssである。一方で、rの小数点以下第(s+1)桁目は定義によりdssであり、この二つは一致しない。 Nの部分集合全体の集合　　は可算集合でない 任意の集合Aに対して 自然数上の関数全体の集合　　は可算集合でない ～

再履修の諸君に重要な連絡 再履修の諸君に大切な連絡があります できるだけ迅速に上田和紀先生にメールで連絡をすること メールアドレスが不明の場合には、学科事務所で尋ねるか、クラス担任の先生に質問する