集合しゅうごうと写像しゃぞうの基本きほん

1導入どうにゅう

この講義こうぎでは、集合しゅうごうの基本演算きほんえんざんと写像しゃぞうの性質せいしつを定義ていぎし、アルゴリズムの入出力にゅうしゅつりょくやグラフの頂点集合ちょうてんしゅうごうを記述きじゅつするための基礎きそを構成こうせいする。

2集合しゅうごうと包含ほうがん

集合しゅうごうとは、対象たいしょうを要素ようそとしてまとめたものである。$$x$$x が集合しゅうごう $$A$$A の要素ようそであることを $$x\in A$$x\in A、要素ようそでないことを $$x\notin A$$x\notin A と記しるす。要素ようそを一ひとつも持もたない集合しゅうごうを空集合くうしゅうごうといい、$$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing と記しるす。

任意にんいの $$x$$x について $$x\in A$$x\in A ならば $$x\in B$$x\in B であるとき、$$A$$A は $$B$$B の部分集合ぶぶんしゅうごうであるといい、$$A\subseteq B$$A\subseteq B と記しるす。$$A\subseteq B$$A\subseteq B かつ $$B\subseteq A$$B\subseteq A であることと $$A=B$$A=B であることは同値どうちである。

3集合演算しゅうごうえんざん

集合しゅうごう $$A,B$$A,B に対たいして、和集合わしゅうごう、共通部分きょうつうぶぶん、差集合さしゅうごうを

と定義ていぎする。補集合ほしゅうごうには、考察対象こうさつたいしょうを含ふくむ全体集合ぜんたいしゅうごう $$U$$U の指定していが必要ひつようである。$$A\subseteq U$$A\subseteq U の補集合ほしゅうごうは

である。したがって、全体集合ぜんたいしゅうごうを変更へんこうすれば補集合ほしゅうごうも変化へんかする。

集合しゅうごう $$A,B$$A,B の直積ちょくせきは、順序対じゅんじょついの集合しゅうごう

である。一般いっぱんには $$(a,b)\ne (b,a)$$(a,b)\ne(b,a) であり、順序じゅんじょを区別くべつする。

4関係かんけい

集合しゅうごう $$A,B$$A,B の二項関係にこうかんけい $$R$$R とは、直積ちょくせきの部分集合ぶぶんしゅうごう $$R\subseteq A\times B$$R\subseteq A\times B である。$$(a,b)\in R$$(a,b)\in R のとき、$$a$$a と $$b$$b の間あいだに関係かんけい $$R$$R が成立せいりつするといい、$$aRb$$aRb とも記しるす。$$A=B$$A=B の場合ばあいは、$$A$$A 上じょうの関係かんけいという。

有向ゆうこうグラフの辺集合へんしゅうごう $$E\subseteq V\times V$$E\subseteq V\times V は、頂点集合ちょうてんしゅうごう $$V$$V 上じょうの二項関係にこうかんけいである。無向むこうグラフでは端点たんてんの順序じゅんじょを区別くべつせず、二要素部分集合にようそぶぶんしゅうごう $$\{u,v\}$${\{u,v\}} を辺へんとして使用しようする。この相違そういは、後続こうぞくするグラフの講義こうぎで厳密げんみつに定義ていぎする。

5写像しゃぞう

集合しゅうごう $$A,B$$A,B に対たいして、写像しゃぞう $$f:A\to B$$f:A\to B とは、$$A$$A の各要素かくようそ $$a$$a に $$B$$B の要素ようそをただ一ひとつ対応たいおうさせる規則きそくである。$$A$$A を定義域ていぎいき、$$B$$B を終域しゅういきといい、$$a$$a に対応たいおうする要素ようそを $$f\left(a\right)$$f(a) と記しるす。定義域ていぎいきの全要素ぜんようそに値あたいが指定していされ、しかも各要素かくようその値あたいが一意いちいであることが必要ひつようである。

部分集合ぶぶんしゅうごう $$S\subseteq A$$S\subseteq A の像ぞうと、$$T\subseteq B$$T\subseteq B の逆像ぎゃくぞうを

と定義ていぎする。特とくに $$f\left(A\right)$$f(A) を $$f$$f の像ぞうという。$$f\left(A\right)\subseteq B$$f(A)\subseteq B であり、像ぞうと終域しゅういきは必かならずしも一致いっちしない。また、$$f^{-1}\left(T\right)$$f^{-1}(T) という記法きほうは、$$f$$f が逆写像ぎゃくしゃぞうを持もたない場合ばあいにも使用しようできる。

6単射たんしゃ・全射ぜんしゃ・全単射ぜんたんしゃ

写像しゃぞう $$f:A\to B$$f:A\to B が単射たんしゃであるとは、

がすべての $$a_1,a_2\in A$$a_1,a_2\in A について成立せいりつすることである。すなわち、異ことなる入力にゅうりょくは異ことなる出力しゅつりょくを持もつ。

$$f$$f が全射ぜんしゃであるとは、すべての $$b\in B$$b\in B に対たいして $$f\left(a\right)=b$$f(a)=b となる $$a\in A$$a\in A が存在そんざいすることである。これは $$f\left(A\right)=B$$f(A)=B と同値どうちである。単射たんしゃかつ全射ぜんしゃである写像しゃぞうを全単射ぜんたんしゃという。全単射ぜんたんしゃに限かぎり、各かく $$b\in B$$b\in B をその唯一ゆいいつの原像げんぞうへ対応たいおうさせる逆写像ぎゃくしゃぞう $$f^{-1}:B\to A$$f^{-1}:B\to A が存在そんざいする。

7例れい

$$A=\{1,2,3\}$$A=\{1,2,3\}、$$B=\{a,b,c,d\}$$B=\{a,b,c,d\} とし、

とする。このとき $$f\left(A\right)=\{a,b\}$$f(A)=\{a,b\} であり、$$f^{-1}\left(\right\{b,c\left\}\right)=\{2,3\}$$f^{-1}(\{b,c\})=\{2,3\} である。$$f\left(2\right)=f\left(3\right)$$f(2)=f(3) なので $$f$$f は単射たんしゃでなく、$$c,d$$c,d が像ぞうに含ふくまれないので全射ぜんしゃでもない。

8情報科学じょうほうかがくへの接続せつぞく

長ながさ $$n$$n の配列はいれつは、添字集合そえじしゅうごう $$\{0,1,\dots ,n-1\}$$\{0,1,\ldots,n-1\} から値あたいの終域しゅういきへの写像しゃぞうとして表現ひょうげんできる。各入力かくにゅうりょくに出力しゅつりょくが一意いちいに定さだまる決定的けっていてきなアルゴリズムは、許容入力集合きょようにゅうりょくしゅうごうから出力集合しゅつりょくしゅうごうへの写像しゃぞうとして仕様化しようかできる。複数ふくすうの正解せいかいを許容きょようする問題もんだいの出力仕様しゅつりょくしようは、入力にゅうりょくと許容出力きょようしゅつりょくの関係かんけいとして表現ひょうげんできる。一方いっぽう、グラフ $$G=(V,E)$$G=(V,E) は、頂点集合ちょうてんしゅうごう $$V$$V と、直積ちょくせきまたは $$V$$V の二要素部分集合にようそぶぶんしゅうごうからなる辺集合へんしゅうごう $$E$$E によって記述きじゅつされる。

9まとめ

• 集合しゅうごうは要素ようその所属しょぞくによって定さだまり、$$A\subseteq B$$A\subseteq B は任意にんいの $$x$$x について $$x\in A\Rightarrow x\in B$$x\in A\Rightarrow x\in B が成立せいりつすることを意味いみする。
• 補集合ほしゅうごうの定義ていぎには全体集合ぜんたいしゅうごうが必要ひつようであり、直積ちょくせきでは順序じゅんじょを区別くべつする。
• 写像しゃぞうは定義域ていぎいきの各要素かくようそに終域しゅういきの要素ようそを一意いちいに対応たいおうさせる。
• 単射たんしゃでは異ことなる入力にゅうりょくが異ことなる出力しゅつりょくに対応たいおうし、全射ぜんしゃでは終域しゅういきの全要素ぜんようそが像ぞうに含ふくまれ、全単射ぜんたんしゃでは一対一対応いちたいいちたいおうが成立せいりつする。