2008-08-20

集合位相入門読書会第三回

id:witchmakersと。全単射とか、合成写像、写像の集合などなど。結構ややこしい感じがしたので(主に僕にとって)、例を多めでやっていきました。

全射、単射、全単射

全射の前に終集合というのをしっかり考えておかないといけない。例えば $R \rightarrow R$ への写像 $f(x) = a^x (a > 0, a \neq 1)$ というものを考える。こういう場合だと、始集合はR、終集合もRということになる。しかし、値域 $V(f)$ は $(0,\infty)$ となって、 $f(R) \neq R$ となる。こういうのは全射とは言わない。fをAからBへの写像とした時に値域と終集合が一致するものを全射と言う。 $f(x)=x+1$ や $f(x)=x^3$ のようなものは全射だが、 $f(x)=x^2$ は全射ではない(値域とRが一致しないから)。

単射は一対一対応のことですね。これはまーよい。

で、定義4でこんなのが出てくる。

写像 $f:A \rightarrow B$ の逆対応 $f^{-1}:B \rightarrow A$ が写像になるための必要十分条件は、fがAからBへの全単射であることである。またそのとき、 $f^{-1}$ はBからAへの全単射となる。

写像の合成

$(g \circ f)(a) = g(f(a))$ のようなやつ。gとfの順序に注意しておかないとあとでごちゃごちゃしてくる。定理5にはこんなのがあった。

$f:A \rightarrow B$ 、 $g:B \rightarrow C$ とするとき、f、gがともに全射ならば、 $g \circ f : A \rightarrow C$ も全射である。また、f、gがともに単射ならば、 $g \circ f$ も単射。f、gがともに全単射ならば、 $g \circ f$ も全単射である。

本当かなーということで証明を見てもいくんだけど、例題を見たほうが納得する性格なので、例題を見ていくことに。 $f(x)=x+1$ 、 $g(x)=x^3$ とすると、fとgはそれぞれ全単射である。それらの合成は $(g \circ f) = g(f(x)) = (x+1)^3$ となる。これは値域と $V(g(f(x))) = R$ となっているので全射で、一対一対応しているので単射。これより全単射となっていて、上の性質を満たすことが分かる。ほー。

他に写像に関する性質として

交換律は一般には成立しない
- $(g \circ f) \neq (f \circ g)$ のような例が簡単に作れる
写像の合成に関して、結合律が成立する

例は、あとで書くかも。

集合の終集合に関する注意

終集合が異なるけど、ほとんど一緒のようなものを同一視するようなやり方。測度論の同値類とかとちょっと似てる?

写像に関する集合

結構やっかいだったところ。

A、Bを任意の集合とするとき、AからBへの写像全部の集合を $\mathfrak{F}(A,B)$ 、または $B^A$ で表わす。この集合は、しばしば、Aの上のBの配置集合と呼ばれる。

分けわかんなくなりそうなんだけど、配置集合の一つ一つの要素は写像になっている。写像をRuby風の関数と考えるならば

[lambda_1{|A|..},lambda_2{|A|..},lambda_3{|A|..},]

のようなイメージ。写像を要素として持つ集合。AからBへの写像全部を集めてくる。

例を考えた。 $A = \{1,2\}$ 、 $B = \{1,2,3\}$ を考えたときの配置集合がどんなものかを考えてみる。 $f:A \rightarrow B$ で、 $f(1)=1,f(2)=1$ を(1->1, 2->1)のように書くとすると、配置集合は{(1->1, 2->1), (1->1, 2->2), (1->1, 2->3), (1->2, 2->1), (1->2, 2->2), (1->2, 2->3), (1->3, 2->1), (1->3, 2->2), (1->3, 2->3)}のような感じになる。あー、確かに要素は写像になっているわー。これからも分かる通り、3^2=9個が配置集合の個数となる。

で、理論統計とかその辺でよく見かけるindicator functionというかそんなものが登場する。

2008-08-14

集合位相入門読書会第二回

XR 勉強会集合論集合位相入門

id:witchmakersと。今回はP20くらいからP32まで進んだ。"対応"と"写像"がキーポイント。

対応の概念

P23の定義より。

A、Bを2つの集合とし、ある規則 $\Gamma$ によって、Aの各元aに対してそれぞれ1つずつBの部分集合 $\Gamma(a)$ が定められているとする。そのとき、その規則 $\Gamma$ のことをAからBへの対応といい、Aの元aに対して定まるBの部分集合 $\Gamma(a)$ を $\Gamma$ によるaの像という。

解析で言うところの関数と結構ややこしい。解析で言うところの関数はあとで出てくる写像なんだけど、対応は微妙に違う。プログラミングで言うところの戻り値が元ではなく、部分集合であることに注意をしなければならない。

例

id:witchmakersが考えてくれた例。有権者={1,2,3,4,5} 、候補者={a,b,c}とする。すると対応として $\Gamma(1)=\{a\}$ 、 $\Gamma(2)=\{b\}$ 、 $\Gamma(3)=\{a,c\}$ 、 $\Gamma(4)=\{\phi\}$ 、 $\Gamma(5)=\{a,b,c\}$ のようなものを考えることができる。部分集合が返ってきていることに注意。

P24にはこんな図がある。図は超適当なんだけど、ある元aに対して、部分集合が返ってきている様子を図で表わしたもの。

一方、(後述する)写像を図に表わすとこういう感じ(P29)。Aのある元aに対して、Bのある元bを返している。 $\Gamma(a)$ はBのただ一つの元からなる集合である(つまり一点みたいなもん)となることが上の場合と対象的であることに注意しよう。

グラフについて

$G(\Gamma) = \{(a,b). | a \in A, b \in \Gamma(a)\}$ みたいなのがグラフで、対応とそのグラフは一意に決められるとあった。なんか複雑なもので、「一意に決まるんなら対応だけあれば、グラフとかいらなくね?」と思ったんだけど、さっきの有権者とかの例だとグラフを使えば $G(\Gamma) = \{(1,a), (2,b), (3,a), (3,c), (5,a), (5,b), (5,c)\}$ という感じで非常に簡潔に書ける。 $G(\Gamma)$ とあって、 $\Gamma$ 出てこなくね?と思ったんだけど、分かった。 $\Gamma$ は規則を与えるというところだけ残して、Gの中では無名関数になってしまっているのだ。そういうことだったのか。

写像

P27の定義より。AからBへの対応 $\Gamma$ は次の性質を持つ時、特にAからBへの写像と呼ばれる。

Aの任意の元aに対して、 $\Gamma(a)$ はBのただ一つの元からなる集合である。

何回も言ってるけど、引数に元で戻り値も元なのが写像。この辺のところが次の付近にきいてくる。

写像に関する諸概念(写像による像および原像)

この辺で結構ややこしい操作とかが出てくる。

AからBへの一つの写像fが与えられたとする。PをAの任意の部分集合とするとき、Pを元aのfによる像f(a)を全部あつめてできる集合、より正確に言えば、f(a)=bとなるPの元aが(少なくとも一つ)存在するようなBの元b全体からなる集合を、fによるPの像といい、f(P)で表わす。すなわち $f(P) = \{b | \exists a \in P (f(a) = b)\}$ 。

何がややこしくなってきたかと言うと、「あれ、写像って(プログラム的な意味での)引数に元を持ってくるやつで、部分集合とかよかったっけ?」という疑問。それまでは対応に制限をかけたものが写像、すなわち「写像 $\subset$ 対応」だと思っていたのに、逆?みたいなことになっていたのだった。

例を考えるとAを実数の集合Rとしておいて、その部分集合 $P=[0,1]$ のようなものを考える(閉区間)。それに対して、写像 $f(x)=x^2$ というものを考えた場合、 $f(P)=[0,1]$ ということで、戻り値も集合?みたいなことになっていた。

で、分けが分からなくなっていたんだけど、@Misho先生に助けてもらってたら分かってきた。集合の集合を考えたような時なら閉区間も元のようなものとして扱えるじゃないかということに気がついた。

そういうわけで、「写像 $\subset$ 対応」というのはくずれずにすみそうであった。

で、P31の定義3の(4.5)付近が結構直感的じゃなかったので、簡単な例で遊んでみることにした。以後、 $f(x)=x^2$ としておく。

$P=[0,1]$ とすると、 $f(P)=[0,1]$ で、 $f^{-1}(f(P))=[-1,1]$ となってしまう。

$Q=[0,1]$ とすると、 $f^{-1}(Q)=[-1,1]$ で、 $f(f^{-1}(Q))=[0,1]$ となる。結果が対照的じゃないのも結構面白いなー。

2008-08-06

集合位相入門読書会第一回

XR 勉強会集合論集合位相入門

id:witchmakersと読むなどした。第一章の最初から、P20の(2.17)付近まで。来週は(2.17)の解読くらいからやるなどしたい。

空集合は任意の集合の部分集合

$\phi \subset A$ であるということ。

なんだか不思議な感じがするよねー
集合だけじゃなくて、集合系(P18)についても成立するのかな

という付近について議論した。不思議な感じがするところは論理命題のところに秘密がかくされていたりした。p、qを命題として、pを偽とする。するとp'は真ということになって、qの真偽によらず $q' \Rightarrow p'$ は真である(P10の(b)を(a)により導いた)。これを利用して、任意の集合Aに対して $\phi \subset A$ であることを示していた。

で、「集合だけじゃなくて、集合系(P18)についても成立するのかな」というところ(P18の最終段落)。空集合 $\phi$ は任意の集合系の部分集合であるか否か、という問題。集合系も集合であることを考えると成り立ちそうなんだけど、本当に? $X=\{a,b,c\}$ とした時、 $\mathfrak{P}(X)=\{\phi,\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{a,c\},\{a,b,c\}\}$ というのが考えられるが(べき集合(power set))、これの部分集合を考えたものが「部分集合系」ということになる。例えば $\{\phi,\{a\},\{a,b\}\} \subset \mathfrak{P}(X)$ である。この時、 $\{\{a\},\{a,b\}\} \subset \mathfrak{P}(X)$ のようなものも部分集合系となるんだろうか?というような疑問。 $\phi \in \{\{a\},\{a,b\}\}$ ってならなくないか?とおいらが勝手に思ってしまっていた。が、差しているものが違うのだった。部分集合であるとを言っているだけで、要素であるとは言っていない。そういうわけで、 $\phi \subset \{\{a\},\{a,b\}\}$ というのは成立して、空集合は任意の集合の部分集合というのは集合系についても成立しそうだということが分かった。

集合系の和集合、共通部分

ちょい苦手っぽい部分だな、ここは。 $\cup^n_{i=1}A_i$ みたいなの*1は測度論の時に山のように出てきたんだけど、これではない。 $\cup \mathfrak{A} = \cup_{A \in \mathfrak{A}} A$ というような感じのもの。集合系 $\mathfrak{A}$ の和集合とか言うらしい。が、これだけじゃ意味分からねー。と言ってたところにid:witchmakersが例を出してくれた。
$\mathfrak{A} = \{\{2\}, \{2,3\}, \{2,4\}\}$ にたいして $\cup \mathfrak{A} = \{2,3,4\}$ というようなのが集合系の和集合。なるほどー。共通部分は $\cap \mathfrak{A} = \{2\}$ ですね。

で、これを厳密にやろうということで論理記号を持って集合系の和集合とかを定義してあったりした。 $\mathfrak{A} = \{x | \exist A \in \mathfrak{A}(x \in A)\}$ という感じ。共通集合については、分かりやすいからいいんだけど、和集合についてがちょっと分かりづらい。あと(2.17)から(2.18)'くらいまでが分かってない。なんだけど、眠くなってきたので後日復習。

*1:P13とかの