ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

集合と写像の勉強まとめ

また祝日、天皇誕生日です。

前回記事「
シェルスクリプトとかExcelとか」は非祝日に書きましたが、あの記事はあってないようなクオリティなので、まともな記事はなんと三連続で祝日となります。

ちょうど書きたくなる時に祝日がやって来るのか、祝日に書きたくなるのか分かりませんが。


なんて言っていたら、記事を書いている間に日付が変わってしまいました。

クリスマスイブですよ。
私は一体、クリスマスに何をしているんでしょうか。


さて、このごろ論理学についてより学びたいなあと思っていたら、いま京都大学の教授をやっている方の、講義資料を載せているウェブサイトがあって、数理論理学のページを見つけました。

論理学はインターネットにほとんど日本の資料がない中で非常に貴重です。

このサイトを見て勉強していきたいと思っているのですが、内容はいくつかの章に分かれていて、最初の章は論理学というより集合論についてでした。

大学でやる数学の基本みたいな感じですね。

まあ、これを前提知識にしないと、論理学には太刀打ちできないということでしょう。


というわけで、最近はそのページで集合と写像の勉強をしました。
今回は、そのまとめをメモします。

しかし、文章量的にはめちゃくちゃ短いのですが、読むのに時間が掛かりますね…。
だいぶ難しいと私は思いましたが、そうでもないのでしょうか。




集合

まず、集合とは何かというところですが、サイトでは“モノの集まり”程度にしか言及していませんでした。

本当はこんな曖昧なものでは面倒くさいパラドックスが生まれるそうですが、とりあえず集合の定義については深く考えないで話が進みます。

そんなようなレベルの集合については、高校一年生が学ぶことなので、説明はまあいいですね。

一応、部分集合とは何か書いておきます。
集合Aの要素を全て集合Bも持っていたら、AはBの部分集合、A⊆Bです。

Bの持つ要素がAの持つ要素と全く同じかもしれませんが、それでもOKです。
プラスアルファとしてBがAにない要素を持っているなら、A⊂Bと書くことも出来ます。

和集合と積集合についても書いておきますが、
A = {a, b, c}, B = {b, c, d} だとしたら、

和集合はAとBの要素を全て集めた集合
A∪B = {a, b, c, d}

積集合はAとBの共通する要素を集めた集合
A∩B = {b, c}

となります。

ただ、積集合という名前が後述の直積集合と別物なんですが、紛らわしいので、本当はよろしくないと思います。


冪集合

そして新しい集合に対する操作として、冪集合なるものが登場します。

冪集合とは、ある集合Aに対して、Aの部分集合になり得る集合を全て集めた集合です。

集合を集めた集合というのは変な感じですが、部分集合になっているのではなく、集合を要素とする集合になっています。

では、たとえば A = {a, b, c} において、部分集合になり得る集合を列挙してみましょう。

{a, b, c} ⊆ A, {a, b} ⊆ A, {a, c} ⊆ A, {a} ⊆ A
{b, c} ⊆ A, {b} ⊆ A, {c} ⊆ A, φ ⊆ A

これらがAの部分集合になり得ますね。
最後のφに注意してください。

φは空集合を表しますが、どの集合においても空集合は部分集合となります。

上の集合たちを集めた集合がAの冪集合であり、2AとかP(A)とか書いて表します。

P(A) = { {a,b,c}, {a,b}, {a,c}, {a}, {b,c}, {b}, {c}, φ }

みたいになります。冪集合はあとで出てくる重要な概念です。

Pはなぜかよくわかりませんが、Powerの頭文字です。
冪集合はPower Setというようです。


直積集合

二つの集合X、Yがあったとして、Xからxという要素をひとつ、Yからyという要素をひとつとってきて、
(x,y)と書いてひとつのモノにできるようにします。

このモノを順序対いいます。
順番が大事で、(x,y)と(y,x)は別物です。

このときX×Yで表す、XとYの直積というものを定義します。
これは、Xからひとつ、Yからひとつ要素を持ってきて作ることができる順序対を全て集めた集合のことです。

この順序対は、X×Yと書いたなら1番目がXの要素で2番目がYの要素の順序対だけを作ります。

(y,x)みたいな順序対は入ってきません。

逆にY×Xと書いたなら(y,x)みたいな順序対だけ集めます。

前述したとおり(x,y)と(y,x)は別物なので、X×YとY×Xは全く違う順序対を集めることになります。

さて、たとえば、A = {a, b}, B = {α, β} なら
A×B = { (a,α), (a,β), (b,α), (b,β) } となります。


順序対は2つの組ですが、これを発展させて順序を考慮するnつ組と、nつの直積を定義することもできますね。

順序を考慮するnつ組を順序組と呼んで、普通に(x,y,z...)みたいに書きます。

X×Y×Zは、(x,y,z)みたいな形になる順序組を集めます。

ちなみに、X×Y×Zという形でひとつの式(?)であって、(X×Y)×ZとかX×(Y×Z)とかは別の集合になってしまうと思います。

これは、たとえば(X×Y)×Zなら((x,y),z)みたいな順序対をネストした順序対を集めてしまって、3つ組の順序組とは別物です。


ようするに直積の記号は×ですが、交換法則や結合法則は無いということですね。

「あってるよな?」と思ってWikipediaを見たら、そこのところをもう少し詳しめに書いていました。

直積集合 - Wikipedia
https://ja.wikipedia.org/wiki/%E7%9B%B4%E7%A9%8D%E9%9B%86%E5%90%88

(x,y,z)と((x,y),z)と(x,(y,z))は別物だけど、等価に変換可能だよねみたいなことでしょうか。



写像

写像というのは、関数をより一般的にしたものであるといえます。

関数は数を入力すると数が出力されるイメージですが、写像は集合の要素を入力すると集合の要素が出力される感じです。


写像というものを作るときは、まず入力の集合と出力の集合を決めます。

写像fがXという集合からYという集合へのものならば、f:X→Yと書いてそれを表せます。

そして、Xの特定の要素xをとってきて、f(x)なんて書けばxに対応するYの要素を表します。

対応するYの要素をyとすれば、f(x) = yとなります。

ちなみに、括弧の中には要素ひとつだけでなく、集合(Xの部分集合)をぶちこむこともできます。

これは、特に新しい意味を持つものではなく、集合の要素それぞれをYの要素に対応させて、その結果の集合がまとめて返ってきます。

ようするに f({a,b}) = { f(a), f(b) } です。

写像fに集合Aをぶちこんで返ってきた集合を、“fによるAの像”と呼びます。


全射、単射、逆像、逆写像

また、fがあるならf-1という写像を作ることもできます。
f:X→Yなら、f-1:Y→Xという写像になって、逆関数みたいなものです。

集合Yから要素yをとってきて、f-1(y)と書けば、これはXの部分集合で、fにぶちこむとyになるような要素の集合が返ってきます。

なぜ集合が返ってくるのかというと、f(x) = yになるようなxが無いかもしれないし、2つ以上あるかもしれないからです。

また、f-1に要素ではなく集合(Yの部分集合)をぶちこむと、先ほどと同じ要領でXの部分集合が返ってきます。


というわけでf-1は集合が返ってくるということですから、今f-1:Y→Xという写像を作ることができるといったのは、嘘です。

写像というのは、ひとつの入力に対して、必ず0つでも2つでもなく、1つの出力を作らないといけませんが、f-1にそんな保証はありません。

確実に作れるのは、Yの要素に対応するXの部分集合を返す写像、記号で書くと、f-1:Y→P(X)です。

P(X)とはXの冪集合、つまりXの部分集合の集合でしたね。
冪集合はこういうふうに使います。


f-1:Y→Xを作ることは基本不可能ですが、写像fが全単射である場合は可能です。

写像が全単射であるとは、写像が全射であり、単射であるという意味です。


全射であるとは、f:X→Yにおいて、Yの全ての要素において、f(x)がそれになるようなxが存在するということです。

言い方を変えれば、f(X) = Yですが、このほうがわかりにくいですね。

まあ、参照なんて言葉は出てきてないですが、Yの要素が全て何かしらに参照されているというイメージです。

f:X→Yが全射であることは、f-1:Y→P(X)においてf-1(y)のyに何を入れても要素が1つ以上のXの部分集合が返ってくること、すなわち空集合が返ってくることがないことを保証します。


単射であるというのは、f:X→Yにおいて、2つ以上の異なるXの要素(仮にx,x'とする)をとってきて、f(x) = f(x')になることが絶対にないということです。

しかし、これは直感からずれている表現でわかりにくいです。

全射の説明みたいにあえて参照という言葉を使えば、2つ以上のXの要素に参照されているYの要素はないという意味です。

参照されていないYの要素の存在はありえます。


f-1:Y→P(X)において、
全射は返ってくる集合の要素数で0がありえないことを保証して、
単射は返ってくる集合の要素数で2以上がありえないことを保証します。

よって、その両方を満たす、つまり全単射であるとは、返ってくる集合の要素数が必ず1つであるということです。

なので、わざわざ集合を返さなくても、Xの要素を直接返しても問題ありません。

よって、写像f:X→Yが全単射である場合のみ、逆写像f-1:Y→Xを作ることができます。

ちなみに、f-1:Y→P(X)は写像fがなんであれ作れるわけですが、これは逆像というみたいです。

名前とか表記が紛らわしいので、定義や名前をちゃんとチェックしないといけません。


合成写像、恒等写像

三つの集合X,Y,Zと、二つの写像f:X→Y, g:Y→Zがあったとします。

このとき、Xの要素xをひとつ決めると、f(x)が決まります。
f(x)はYの要素なので、写像gにぶちこめます。

よって、g(f(x))みたいな書き方ができます。
これは、Xの要素を入力するとZの要素が返ってくるひとつの写像と見なすこともできます。

そこでfとgの合成写像というものを作って、g∘fと書きます。
入力は右から左の写像へと流れていきます。

一番右の入力はXの要素で、一番左の出力はZの要素なので、g∘f:X→Zです。


また、入力と出力が同じ集合の写像で、入力された要素と同じ要素を出力するだけの写像を恒等写像と呼びます。

集合Aがあったら、idAと書くことで恒等写像を表します。
idA:A→Aであり、常にidA(x) = xです。

恒等写像の存在は透過的であり、写像の合成を行っても、合成していないのと同じことになりますね。

恒等写像を何に使うのか私は知りませんが、まあ使うんでしょう。


グラフ

写像f:X→Yを作るということは、Xの全ての要素に対してf(x)を決めることができるということです。

そこで、順序対(x,f(x))のxをXの全ての要素でそれぞれ当てはめたような順序対の集合を考えることができます。

このような順序対の集合をグラフと呼びます。

いや、なにがグラフだよって言いそうですが、一次関数のグラフとか二次関数のグラフとか、いわゆるあのグラフを形式化したものが今言っているグラフということなんでしょうね。

一次関数のグラフとかも点の集合であって、点を(x,y)の順序対と見なすことができますからね。

ここで直積集合のX×Yを思い出してみると、これは(x,y)という形の順序対全ての集合です。

それに対して、グラフという集合は、条件でフィルタをかけた(x,y)の順序対の集合であり、X×Yの部分集合です。

その条件というのが、(x,f(x))となるような順序対だけ、という条件です。

これはグラフの要素には、ひとつのxに対して、対応する順序対(x,f(x))がひとつだけ存在するということを意味します。

よって、Xの要素xを決めればグラフの中から順序対をひとつ決められます。

一次関数とかのグラフでいうなら、X軸の値を決めれば絶対に点の座標は決まりますね。

言わば、xの値から順序対(x,y)を引く辞書みたいなものです。
その辞書がグラフという集合です。


xが決まれば(x,y)が決まるということでしたが、これは暗黙的にYの要素yも決めているということですね。

Xの要素をひとつ決めてYの要素がひとつ決まるというのは、よく考えてみたら写像のことでした。

写像を決めればそこからグラフも決定しますし、
逆に二つの集合X,Yに対してグラフとなるような順序対の集合をひとつ決めるということは、それに基づいた写像をひとつ決めることに等しいわけです。


ところで、集合Xの要素数がn、集合Yの要素数がmだとして、可能性として考えうる、xからyへの対応表は何通りあるでしょうか。

Xの1番目の要素においてYの対応がm通り、
Xの2番目の要素においてもm通りなのでここまでm×m通り、
3番目以降も×m通り…というふうにXのn番目の要素まで掛け算を繰り返すわけで、

ようするに、mn通りです。

対応表を決めるというのはグラフを決めるということそのものであって、
グラフを決めることと写像を決めることは同じです。

つまりn個の要素を持つ集合Xから、m個の要素を持つ集合Yへの写像は、mn種類考えうるわけです。

その考えうる全ての写像を集めた集合をYXと書いて表せるようにします。

写像を集めた集合です。写像をモノとして扱っています。
なんでYXと書くのかは大体わかりますね。

まあ、Map(X,Y)と書くこともあるようですが。


指示関数

集合Xと、Xの部分集合Aがあるとします。
このときXAと書いてXにおけるAの指示関数を表します。

なんで急に写像じゃなくて関数になったのかというと指示関数の出力は数値だからです。

数値といっても、0と1のどちらかを出力するだけで、単に二値を区別するために数値を使っているだけみたいですが。

XAにはXの要素を与えることができ、その要素が部分集合Aに含まれていたら1、さもなければ0を返します。

XA:X→{0,1} となります。

この指示関数にXの全ての要素xをぶちこんで、それぞれが0と1のどちらになるのかというのは、部分集合Aを決定することで決まってきますね。

逆に、それぞれが0と1のどちらになるのかという対応表、すなわちグラフを決定させることで、そこから部分集合Aを決定させることも可能です。

ただ、考えるグラフの集合というのは表しづらいところがあります。
しかし、前述のとおり、考えうるグラフの集合と写像の集合は等価なので、これを使って

{0,1}X→P(X)という写像を作ることはできますね。

{0,1}Xというのは、Xにおいて考えうる指示関数の集合、P(X)というのはXの部分集合の集合ですね。

結局、Xの部分集合を決めれば相当する指示関数が決まるし、Xの指示関数を決めればXの部分集合がひとつ決まるということで、等価だということです。



本当は“関係”というのも勉強したので、そこも書きたかったのですが、指示関数でキリ良いし疲れたので、今日はここまでとします。

だいぶ執筆に時間をかけています。

次回があるなら、関係と、あとブール代数が同じ章に含まれていたので、その二つをまとめて記事にしたいですね。

どうせ書くネタないので。

集合の話題って地味ですが、なかなか面白いと思いました。

tag: 数学 論理学 集合 写像 順序組 グラフ

コメント

すげぇ

これまたすごいことを学んでいますね。
集合やら写像やら私には難しすぎるようで
私の頭ではほとんど理解できませんでしたw

それにしても、プログラミングやっている人は大抵
数学関連のことが好きみたいですね。

私の友人にも「アルゴリズム・数学マニア」みたいな人がいるんですけど
「自分から頭を使うことをやりたがる精神」や
その「学習意欲」を私にも分けてほしいと思いますねw

私は数学があまり好きじゃないというか
苦手意識があるものですからね。
やはり興味が無いと自分からやろうという気にならないもんですね。

いずれ私も数学について
自分で何か勉強してみましょうか。
興味が湧いたらですけどね。

  • 2015/12/25(金) 17:28:00 |
  • URL |
  • aridai #-
  • [ 編集 ]

Re: すげぇ

コメントありがとうございます。
私も難しいです。

最初は意味不明ですが、少しずつ時間をかけて、きっちり理解するように心がければ、分かってくると思います。
記事中で

> しかし、文章量的にはめちゃくちゃ短いのですが、読むのに時間が掛かりますね…。
> だいぶ難しいと私は思いましたが、そうでもないのでしょうか。

と書きましたが、これはこの記事について言ってるんじゃなく(分かりづらかったですが)、勉強したサイトのことを言っています。
日本語の一文を読むのに10分とか掛けていました(笑)

私も相当時間を掛けたので、aridaiさんも勉強することがあれば、ゆっくりやっていけばいいと思いますね。

コンピュータ含め、サイエンスが好きな人は数学好きですね~。
山があったら登るみたいなもので、わからないことがあったら知ろうとする精神でしょうか。

いや、私も最近は、そういう精神がちっとも無いんですが…。

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/435-ad70dba4
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。