ブログ「サイバー少年」

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

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

群の準同型定理のイメージをやっと掴めた

群の準同型定理ですが、今まで本を読んで論理的に定理として成り立つことは分かっていたのですが、正直なところ言っている意味、イメージが分かりませんでした。

命題のイメージを掴むということは、わりと大事であると思います。

命題が、証明を読んで論理的に推論可能であることだけを知っていても、
結局なにを言ってるんだ??という状態では、どのように命題を利用していけばいいのか見当もつかないですからね。


イメージを掴むことを心がけてはいるのですが、今まで準同型定理はイメージできなかったんですよね。
体論に入っているというのに、最近ようやく理解できました。


準同型写像φ:G→G'について、φによるGの核(これはGの正規部分群)でGを類別した商群と、φによるGの像は同型であるという定理ですが、

残念ながら有限集合でしか通用しないイメージですが、ようするにGの像⊆G'はφが単射でない限りGより小さいので、まずGの核でGを類別してGより小さい商群を作ります。

このとき商群の中身がどうなってるかが肝心です。
これはφでG'に写したときに同じ元になるGの元をまとめた同値類系となっています。
(これを示すために証明が必要ですが、証明は本で読んでそこからイメージしました。)

ですからφが単射なら同値類は、それぞれひとつしか元を持ちません。
そうでなければどこかに2つ以上の元を持つ同値類があります。


そして、この商群とGの像が一対一に対応しているという話ですが、当たり前といえば当たり前であります。

Gの像と対応している商群の同値類は、Gの像と対応していることを考えれば必ず存在しますし、Gの像の中の同じ元へと写されるGの元は同じ同値類に属するはずですから、これは一対一となります。

この一対一の対応に則した写像を定めれば、その写像は全単射となりますね。
あとは、その写像が準同型写像の定義を満たすことが必要ですが、実はこのメカニズムはイメージできていません。

ただ要点は一対一対応があるということだと思うので、まあ大丈夫じゃないかなと思いますね。


ちなみにGの核は商群の元、同値類のひとつですが、φ(e)=e'より、Gの核には必ずGの単位元eが入っているので、
Gの核の元はすべてφ(e)と同じ値になるということでしたので、つまりすべてe'に写しますし、Gの核に入っていないようなφ(a)=e'となるaは存在しません。


以上です。
まだイメージを掴めていない人が、これを読んでも説明がヘタクソすぎてよく分からないと思いますが、私自身はだいぶイメージを掴めて満足しています。

自己満足の記事です。

わりと当たり前のことを言っているだけの定理だったのですが、イメージできたときは少し面白かったですね。

ただ、すごく大事な定理らしいのですが、どのように活用するのかよく分かりません。
どうなんでしょうか。

tag: 数学 証明 群環体 勉強 命題 同値 写像 同型 集合

数理論理学の些細な気づきごと

数理論理学の勉強はもう終わらせてやめましたが、最近ふと気づいてしまったメチャメチャどうでもいい発見があったので、たいしたことではないですから短くまとめます。

すごく小さな発見を、今回は2点ほど用意しております。

(追記ですが、ちっとも短く書けませんでした…)


まず1つ目ですが、xor演算についてです。
数学というより、プログラミングで論理演算をするときに知っとくとためになるかもしれませんね。

xorは、a xor bだったら、どういう意味かといえば、

aとbが両方ともfalseなら結果もfalse、aかbのどちらかだけがtrueなら結果はtrue、aとbが両方ともtrueなら結果はfalse、ですよね。


じゃあ、これがa xor b xor cと3つになったらどうなるでしょうか。
ちなみに左結合、つまり(a xor b) xor cです。

これは、感覚的には2項バージョンの拡張として、a,b,c全てがfalseなら結果はfalse、a,b,cのどれか1つだけがtrueなら結果はtrue、a,b,cのうち2つ以上がtrueなら結果はfalseになる演算だとみなしたいわけですが、そうはならないようなんですね。

反例としては、a,b,cが全てtrueだとしたら結果はfalseになってもらいたいわけですが、a xor bの時点で一回falseになってしまうので、そのfalseとcつまりtrueをxorして、結果はtrueになってしまうと。

ちなみに情報工学ではメジャーな話ですが、x xor trueをかけるとxの反転が得られますから、a xor b xor c xor dのa,b,c,dが全てtrueならa xor b xor c = trueの反転でfalseですね。

偶数個の項なら反例になりませんが奇数個のとき反例になることになります。


また、補足しておくと、ブール代数での話ですが、2項バージョンのときa,bの片方がtrueならtrueというのは、この“片方がtrue”というのが、
「1つだけtrueで残りはfalse」ということなのか、「1つ以上trueがあるが1つ以上falseがある(確実にすべてfalseではないが確実に1つはfalseがある)」ということなのか、という二つの捉え方があって、

これらは2項バージョンにおいては同値ですから違いが曖昧なのですが、3項以上になると違う命題になるので、後者のほうの捉え方も3項以上バージョンでは、また別個に考えられます。

つまり後者の捉え方で、a xor b xor cを、
a,b,c全てがfalseなら結果はfalse、a,b,cのうち1つ以上trueがあって1つ以上falseがあれば結果はtrue、a,b,c全てがtrueなら結果はfalseになる演算だとみなすこともできるわけですね。


さらに、trueでなくfalseの個数に着目した場合、つまりtrueとfalseが出てくる箇所をひっくり返した場合に後者では同値となりますが、前者では違う命題になるので、前者の捉え方のtrueとfalseをひっくり返した捉え方も論理的にはありますが、
まあa xor b xor cを感覚的に捉えるならばfalseの個数で考えるという発想はないと思いますので、この場合は無視しましょう。

だとすれば、上の話での後者の捉え方はどうなのかというのは考えなければなりませんが、このときも前者のときと同様にa,b,cが全てtrueという反例があって、感覚的なものとは違う真理値になります。


感覚的に捉えたものと同じ真理値にしたい場合はどういう論理式を書けばいいのかというと、後者の捉え方の場合は単純に、
(a or b or c) and not (a and b and c)みたいに全ての項をorでつなげたものと、andでつなげたものの否定の論理積をとるだけです。

むしろ、2項の場合はa xor bは(a or b) and not (a and b)と同値なのに、3項以上の場合は同値でなかったことに驚きますね。


前者の捉え方では、2つ以上の項がtrueにならないことを表現するために、あらゆる2つの項の組み合わせについて論理積がtrueにならないことを言わなければならないわけで、

a,b,cなら(a or b or c) and not (a and b) and not (a and c) and not (b and c)みたいに、長いですね。

全ての項をorでつなげたもののあとに、n項ならばnC2個の2つの項の組み合わせの論理積の否定を付けて、論理積でつなげなければなりません。
nandを使えば(a or b or c) and (a nand b) and (a nand c) and (b nand c)みたいに若干、短くなるか…。


というわけで、イメージ通りにやりたい場合はxorでつなげるのでは駄目で、地味に大変な論理式を書かなければならない、という話でした。

そうそう、上記の論理式を書く以外にも、真理値表をもとに論理式の標準形を書くという手段も、一応ありますね。

続きを読む

tag: 数学 論理学 論理式 論理演算 写像 集合 同値 組み合わせ 考察 クソ記事

数学が難しい

前回記事「論理学の勉強コンプリート!!!」で書いたとおり数理論理学の勉強が終わったので、
今は「群・環・体」を図書館で借りた本を読んで勉強してるんですが、なんとも心が折れそうです。

まだ本題には入っておらず、集合と写像についてやったり自然数や整数の性質を学んだりしているページを読んでます。

集合と写像は、去年の十二月にも数理論理学関連で勉強しましたけどね。
まあ置換とか、ちょっぴり新たな概念もありましたけども。


自然数とか整数が難しい!!!

今までやってきた論理学に比べて、こいつらは、かなりワーキングメモリがないと理解できないですね。

集合と写像においてもそうですが、こういう系統のやつは具体的にイメージする対象があって、自分でそれをイメージしないと駄目なものですから。

数理論理学は、なんか上手いこと表現できないですが、とにかく何かをイメージするということはあんまりなかったんですよね。


まあ対象をイメージできないなら、もしくは式を変形するだとか論理的にひとつずつ推論していくことで、形式的に理解するという手立てもあると思いますが、
前回記事で書いたように私には論理を積み重ねる力もたいしてないので、なかなか難しいものがありますね。


このまえ前回記事で

しかし私だってそりゃ書かれてあることを読んで一瞬で理解できるなんてことはほとんどないですが、時間かけたら大抵のものは理解できますよ。

だのなんだのと言っていましたが、なんかもう撤回したい気分ですね。
数学をナメていた…。


整数の性質で、ユークリッドの互除法とか出てきたんですけど、わけわかめって感じでした。
さすがに完全にわからないわけではないですが。

ユークリッドの互除法は、学校でもやらされた気がするんですけどね。
覚えてねえ!


そういえば、集合と写像のページを読んでいて思ったんですが、かなり初歩的な問題だと思いますけど、ちょっと閲覧者の方に数学できる方がいらっしゃればお聞きしたいのですが、

要素数が同じの2つの有限集合A, Bと写像f:A→Bで、fが全射であることとfが単射であることって同値ですよね。

頭のなかで図をイメージすれば、これは正しいような気がするんですが、証明しようと思ったら論理力がなくてできない…。


インターネットで検索すればいくらか似たような問題の証明が出てくるんですけどね。
たとえば、こんなブログ記事が。

よしいずの雑記帳 対等な有限集合における全射と単射の同値性
http://yoshiiz.blog129.fc2.com/blog-entry-694.html


2つの集合が対等であるとは、2つの集合に全単射が存在するという意味だそうですから、有限集合において対等とは、つまり要素数が同じであることと同値だと思うので、これはまさに私が考えている問題の証明だと思うんですが、

読んでもよくわからない…。
イマジネーションが足りないですね。


この他にもQ&Aサイトに写像fの定義域と値域が同じ有限集合の場合において、fが全射であることとfが単射であることの同値性の証明が載ってたりしまして、
その証明を応用するだけでも要素数が同じという条件にまで拡張できると思うんですが、やはりよくわからない…。


数学難しいですね。
まあ分からないことが分かるようになるという喜びが数学の醍醐味なわけですが。

でも分からなさすぎなんだよチクショオオオオオオ!

tag: 数学 勉強 問題 証明 代数学 ワーキングメモリ 集合 写像

順序集合を並べるアルゴリズム

たいした内容ではないのですが、また数学のネタです。

今日は脳みそのコンディションが悪いので、読むに耐えないクソ記事になっているかもしれないですが…。

半順序関係が与えられた集合に対して、その半順序関係の情報に基づいて一列に並べるアルゴリズムについて考えていました。

その集合は“有限”の集合であると但し書きしないといけませんね。
なんか全部、有限であることが前提みたいに考えてしまうのは、情報系の人間の悪い癖だと思います。


さてしかし、普通、全順序関係じゃないと一列に並べられないんじゃないかということなのですが、

ここでは任意の元x,yについて、x <= yという順序関係があるとき、yは必ずxの右(上でもいいからとにかく大きい側の方向を定める)に来るという条件を充足するように、半順序集合の全ての元を一列に並べることを、一列に並べることとします。


つまり、大小比較できない二つの元については、どんな順番でもいいから無理やり一列に並べて、
大小比較できる二つの元については確実に、大きい元が大きい側になるように並べるということです。


このような一列を生成するアルゴリズムを、考えたわけなのですが、アルゴリズム自体はクソ簡単なものです。

そもそも私は難しいアルゴリズムを考案できるほどの脳みそがないので…。

続きを読む

tag: 数学 集合 順序 関係 アルゴリズム 計算 帰納法 証明 地図

数学の勉強について雑記…

今回の記事は本当に雑記です。
話を体系的に書くという意識がまったく感じられないものであります。

つまりはクソ記事であるということをご承知ください。


私は最近、数学が好きなので、数学の特に数学基礎論という部分について勉強したり考え事していたりするのですが、

…もしかして自分には数学の才能がないのではないかと思ってしまいますね。


まず数学において重要な、発想力が私は大きく欠如していますね。
だから証明しろとか言われても、どのようにすればいいのかわからない。

答えを見ずに自分の力でなんらかの知見を生み出すことができないのは、数学をやる人間としてどうかという感じですね。

無から何かを探すというのは、すごく考えのフィールドが広すぎて、探索しきれないということですね。

まあ、このフィールドの広さの中で知見を生み出すためには、問題を小さく分割してちょっとずつ考えて、
小さな結論をひとつずつ出していって、最後に大きな結論を出すというのが必要になると思うんですが、

なんか私の場合、大雑把になってしまうということですね…。
たぶん、脳のワーキングメモリが足りないので、細分化しても忘れちゃうんですね。

全体を一気に考えないと頭の中のイメージが崩れてしまうというか。
でも、全体を一気に考えるなんて、大きすぎて出来ないということです。

さらに、有限のものに対してはイメージできるとしても、無限のものはイメージ出来ないので、苦手ですね。

たとえば数学的帰納法とかも、苦手です。


さて一方で、すでに答えが書かれてあるときに、答えを読んで理解する力というのは、まあまあかなと思うのですが、

それでも理解力も足りないと、思ってしまいますね…。

いや、なんというか書かれてあるイメージが、日本語に書き下せる場合と、日本語にできない場合があると思うんです。

日本語で考えられるものであればわりと理解できるんですが、日本語にできないものは苦手ですね。
イメージをイメージのままにして考える力がないんですかねぇ…。

続きを読む

tag: 数学 集合 順序 関係 論理学 述語論理 公理 勉強 偉人 ワーキングメモリ

命題論理の意味論まとめ (前編)

記事「集合と写像の勉強まとめ」なんかも書きましたが、
昨年末から論理学の勉強を継続的にしていて、京都大学の教授の方のサイトをずっと見ています。

そういえばこの前、このサイトが書籍化されたらしい本を見かけました。


今回、命題論理、とくに意味論について書かれてある部分を、ようやく読破しましたので、そのまとめとしてお書きしようと思います。


そういえば昔も論理学について放送大学で学んで、記事「記号論理学という学問を知ってみたが」を書いたことがありました。

あのときは今回の命題論理よりハイグレードな述語論理だったんですが、数学的で厳密な定義はおいといて実用的な論理学をやるみたいなものでしたので、

今回は厳密な部分をとばさずに再挑戦しているみたいな感じですね。

記事の書き方も、あの記事ではトップダウン的な説明でしたが、今回はボトムアップ的であると思います。


ところで、意味論とか構文論ってどういうことなのかイマイチ入ってこないのですが、“命題論理の意味論”なのか“意味論の命題論理”なのか、どっちなんでしょうか。

一応、“命題論理の意味論”と書いてあったので、そういうことにしておきますが…。


あと、記事「集合と写像の勉強まとめ」と続編記事「続・集合と写像の勉強まとめ ~ブール代数も~」、
で書いた数学の知識は正直ほとんど使わなかったと思うのですが、最初の根源的な定義をするところで少しその知識がいりますね。


少なくとも演算というのが何なのか理解する必要がありますし、演算というのがなんのか理解するには写像についての理解、ひいては集合とは何か…

数学は少しずつ積み上げる学問なので、学校で嫌われるんですね。


今回、ひとつの記事に収めるつもりだったのですが、すごく基本的な話をしただけで無駄に長くしてしまったので、これを前編として次回、後編を書こうと思います。

お楽しみにしていてください。

続きを読む

tag: 数学 論理学 演算 論理式 命題 命題論理 集合 意味論

続・集合と写像の勉強まとめ ~ブール代数も~

前回記事「集合と写像の勉強まとめ」で、“関係”というものについてまで書きたかったのですが、
疲れて打ちきってしまったので、今回さっさと書いてしまいます。

また、あのあと“ブール代数”とは何かについても勉強したので、それも書きます。

と言っても、ブール代数の定義を見ただけで、使い方とかはまだなので、何なのかよくわからないままなんですけどね。

さて、この記事は前回記事を読んでいることを前提に書きますので、ご注意ください。
続きを読む

tag: 数学 論理学 集合 写像 関係 グラフ 述語 演算 ブール代数

集合と写像の勉強まとめ

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

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

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


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

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


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

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

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

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

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


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

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

続きを読む

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

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