http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html Ver.2 再掲:講義資料の所在 (URL) 後にレポートを回収した時に、提出者の学籍番号を、ここに掲載する予定です。 後藤研のWEBページ(日本語)の「後藤先生担当の講義」から辿ることもできます。 http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html ここに ~ が必要
数学は、その場で考えれば解るのか? 解りません 基本的な記号の意味を覚える必要がある 数学は記号の羅列 記号の辞典がある 使うことにより、学習できる 普通に考えると解らないような箇所を出題 基本的な考え方を身に付けておく
参考書(金曜日・後藤担当分) 講義資料の多くの部分を作成した上田先生の参考文献 (1) J. マトウシェク, J. ネシェトリル著 根上生也, 中本敦浩訳「離散数学への招待 上」 シュプリンガー・フェアラーク東京 ISBN 4-431-70896-0 (2)M.A.アービブ, A.J.クフォーリ, R.N.モル 著 甘利俊一, 金谷健一, 嶋田晋 訳 「計算機科学入門」 (Information & Computing 1) サイエンス社 ISBN4-7819-0375-4 後藤が教材を追加した際に参照した文献 (3)守屋悦朗「コンピュータサイエンスのための離散数学」 (Information & Computing 61) サイエンス社 ISBN 4-07819-0643-5 (4)小野 寛晰「情報代数」情報数学講座 第2巻 共立出版 ISBN 4-320-02652-7
演習問題の解答はスライドに掲載せず 例外として次を解説「ラッセルのパラドックス」 集合Xを次のような「もの」の集まりとする Xの要素は「自分自身を要素として含まない集合」である [説明]Xは集合である。XはX自身を含むか、含まないか、いずれかである。もし とすると となる。すなわちXはXを含むから定義によりXはXの要素ではありえない。これは矛盾。一方 とすると、XがX自身を含まないのであるから、定義によりXはXの要素となる筈である。これは矛盾。
写像 (map) または関数 (function) AとBを集合とする f がAからBへの写像 (map) または関数 (function) であるとは fがAの各要素に対して、Bのただ一つの要素を対応させる規則であること [例題]実数xにxの実数平方根を対応させる規則 上の対応規則は関数(写像)ではない。
関数と関数空間 集合Bの要素の中でfの像になっている要素の集合 をfの値域 (range) という。 を と書くことがある。説明は後述。 A の要素にB の一つの 要素を対応づける規則 f A から B への 写像(関数)全体の集合 集合Bの要素の中でfの像になっている要素の集合 をfの値域 (range) という。 を と書くことがある。説明は後述。 定義域(始集合) domain 終集合 codomain (値域と区別)
関数のグラフ A B 関数の内包的定義: 外延的定義: これを関数のグラフという グラフは直積AXB の部分集合である のグラフとは グラフは直積AXB の部分集合である グラフが同じ関数は等しい(外延的な等しさ) A B
単射と全射 写像 (関数) が任意の に対して、 という性質を満たす時に単射という。1対1写像ともいう。 上の性質は とも書ける。 論理記号 ならば implies 写像 (関数) が任意の に対して、 という性質を満たす時に単射という。1対1写像ともいう。 上の性質は とも書ける。 写像 (関数) が、任意の に対して なる が存在する時に全射という。上への写像ともいう 全射かつ単射である写像を全単射という。 [例] を と定めると、全単射となる
関数と部分関数 論理記号 同値 条件②が成り立たない場合は部分関数(部分写像)
多変数の関数(多引数の関数) 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 を与えると配列 が返る 和集合
集合の 直和の個数を一般化したもの 例:Aがアルファベットの集合 有限長の文字列全体の集合は 例:Aがアルファベットの集合 有限長の文字列全体の集合は 演習:I {0,1} , A0 { 2, 3, 4 }, A1={ 3, 5 } の場合に 上の定義による の要素を具体的に記せ。 直和
cardinal number, cardinality 無限集合 無限集合の例: 集合Aの要素の数 |A| を基数、濃度という。 上の例では、要素の数は無限。 ただし、すべての要素にもれなく通し番号をつけることができる。 ここで、無限の要素に必ず通し番号がつけられるかどうかは自明でない。(後述) 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 全単射 0 1 2 3 4 5 6 7 8 9 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
可算でない無限集合 対角線論法 実数全体の集合 R は可算集合ではない [証明の概略]R’ を 0 および正の実数の集合とする。N⊂R’⊂Rである。|N| ≦ |R’| ≦ |R| である。 NからR’への全単射 f が存在すると仮定する。 有限小数は 0 を付ける fは全射であるからr=f(s)となる自然数sが存在する筈。そのdssに注目する。
可算でない無限集合 [続]r=f(s)となるsが存在する。ところでf(s)の小数点以下第(s+1)桁目は定義によりdssである。一方で、rの小数点以下第(s+1)桁目は定義によりdssであり、この二つは一致しない。 Nの部分集合全体の集合 は可算集合でない 任意の集合Aに対して 自然数上の関数全体の集合 は可算集合でない ~
再履修の諸君に重要な連絡 再履修の諸君に大切な連絡があります できるだけ迅速に上田和紀先生にメールで連絡をすること メールアドレスが不明の場合には、学科事務所で尋ねるか、クラス担任の先生に質問する