ブログ「サイバー少年」

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

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


当ブログは3月31日をもって更新終了します。

有限体の勉強まとめ (後編)

記事「有限体の勉強まとめ (前編)」の続きです。
これは長くなりますなあ…。
まあ、最後なので気合い入れて執筆していきましょう。

Yahoo!知恵袋でヒントをもらったりしていますが、細かなところは自分で考えた理論展開です。
全体的な理論展開の方針は、私が読んでいた本にならっています。


まず、有限体の話に入る前に、あとで使う定理として、環同型の話をします。
環Q, Rの間に同型写像φ:Q→Rが定義できるとします。

定理1: 単元c∈Qについてφ(c)∈Rは単元である。
証明
すべてのa∈Qについてa = ca'が成り立ちます。
両辺をφに入れてφ(a) = φ(c)*φ(a')が成り立ちます。
任意のx∈Rについてx = φ(a)となるaが存在し、x = φ(c)*φ(a')です。
よってφ(c)は任意のx∈Rを割り切るため、単元です。

定理2: 単元でないa∈Qについてφ(a)∈Rは単元でない。
証明
φの逆写像φ'を利用して、定理1のように
「単元c∈Rについてφ'(c)∈Qは単元である」と言えます。
対偶をとり「単元でないφ'(c)∈Qについてc∈Rは単元でない」と言えます。
これはφ'が全射なのでφ'(c) = aと置けますが、そのときc = φ(a)と表せます。

定理3: 素元p∈Qについてφ(p)∈Rは素元である。
証明
φ(p) = abとなる任意のa,bを置いたとき、φ'(φ(p)) = p = φ'(a)*φ'(b)が成り立ちます。
pは素元なのでφ'(a)とφ'(b)のどちらかは単元です。
定理1よりφ(φ'(a)) = aとφ(φ'(b)) = bのどちらかは必ず単元です。
pは単元でないので定理2よりφ(p)は単元でなく、0でもないのでφ(p)は素元です。


それでは、有限体の話を始めましょう。

続きを読む

tag: 数学 群環体 証明 論理学 多項式 有限 集合 同値 勉強 終活

有限体の勉強まとめ (前編)

できれば昨年中に書いておきたかった有限体の勉強まとめです。
内容が広いので文量はともかく、執筆時間が相当なものになるだろうということで、前編、後編でお送りします。

今のところ予定している配分では、特に後編がかなりヘビーになると思っています。
内容が広いって言っても、広くないんですけどね。
私が書くのが遅いという…。

前編は導入部分の話だけで証明といった証明も特になく、準備運動のようなものです。
いや、前編もかなり時間かけて書いたんですけど。


さて、まず体についてはご存知のものとします。
有限体とは、体を構成している集合が有限集合であるものです。

有限集合ですから要素数を自然数で表すことができます。
この要素数を体の位数と呼びます。

後述する体の要素についての位数というのもあって、両方とも位数という名前ですが別概念です。
同じ名前やめろよと言いたいですが、余談として、たぶん位数がnの体の要素が構成する乗法群が集合の要素数として位数nになるから、なんでしょうね。


なお、ここで体の位数が1、体の要素が1 = 0のひとつだけということは、ありえません。
(このような代数系である場合、零環という名前の環になります。)

この話題は記事「体の準同型写像に必要な定義」でもしましたが、どうやら体の公理系に零環は矛盾しないのだけれど、
零環でない体が充足してくれる魅力的な性質が零環だけ充足してくれないことがあって、テンションだだ下がりだから排除しておきたい、
しかし零環というたったひとつのケースを除外するための公理を設定するのもなんだかなぁって感覚で、暗黙的に体から除外しているみたいですね。

厳密にやるなら体の公理に零環を除外することを加えるべきだと思います。
ただ証明でいちいち「ここで1 = 0ではないので…」と言及するのも面倒ですからねぇ。

数学はフィーリングで考えている部分も大きいので、零環でない体に共通するイメージの論理的妥当性を主張するために零環ではないという条件を持ち出さなければならないのは邪魔です。

続きを読む

tag: 数学 群環体 集合 有限 同値 素数 ユークリッド 勉強 多項式 終活

多項式の商環による体の拡大

前回記事「イデアルと商環とユークリッド整域の商環」で紹介した知識をベースに、予告していたとおり続編にあたるものを今回は書きます。

有限体については完璧に読み解くことが出来ました!
というわけで、それはまた今度まとめたいと思います。
まずは今回の話をしないと、有限体も理解しづらいですからね。


多項式の変数Xに係数環(係数体)の要素を代入すると、多項式として全体の計算結果を得ることが出来ます。
ここで、係数環(係数体)に含まれない要素を代入できないかと考えてみます。
(以後、係数は体に限定して話を進めます。)

そのためには、その要素γと係数体Kの要素の間で加算と乗算が可能でなければなりませんので、要するにKを部分集合にしており尚且つγを含む大きな環が必要です。

別に複素数体を想定しているわけではないですが、その環をCと名付けることにします。
K⊆C、γ∈Cですが、ここでCの加法、乗法はKの中ではKの加法、乗法と一致していなければなりません。

となると単位元は一致しますし、KはCの部分体とでも言えるんですかね。
そこまで本に書いていないので、よく分かりませんが。
あくまでCはKを拡大したものです。
この条件は満たしてないと論理的に矛盾するわけではないのですが、今から行う体の拡大の趣旨に反します。

続きを読む

tag: 数学 群環体 証明 集合 素数 勉強 ユークリッド 同値 写像 複素数

イデアルと商環とユークリッド整域の商環

群・環・体の本を読んでいるのですが、有限体の解説を読むのに苦戦しておりまして、最近ようやく方針が見えてきたところであります。

ですから、もう少ししたら理解できるはずですので、それは当ブログでも記事にまとめたいと思っているのですが、
あまりにも最近は数学のネタを書いていないので、つなぎとして商環の話を。

今回は自分で考えたこととかじゃなくて、完全なる本の受け売りなのですが、今後、有限体についてまとめるときに使う知識ですので、閲覧者の皆様にもあらかじめ知っておいていただければ話が早いと思います。


まず、ある条件を満たす環の空集合でない部分集合をイデアルと呼びます。
条件というのは、環RとイデアルI⊆Rについて

1. a∈I かつ b∈I ならば a+b∈I
2. a∈Iな らば -a∈I
3. a∈I かつ b∈R ならば ab∈I

の3つです。
3.はIについて閉じていると言っているわけではなく、bはRの要素であればabはIの要素であるという、さらに強い条件を主張していることに注意してください。

3.によると0∈Rなので、a∈Iとなるaは必ず存在しますから、a0 = 0 ∈ Iです。
ですから、Rを群と見なすとすればIは加法について閉じており、逆元が存在し、単位元0が存在していますので、IはRの部分群となります。

さらに、ここで扱っている環は加法について交換法則が成り立つ可換環を想定しているのですが、そのためIがRの正規部分群であることは明らかです。


さて、任意のa∈Rの倍元全体の集合{ab | b∈R}を(a)と表記するのですが、これがRのイデアルであることは、条件と照らし合わせてみると分かると思います。
このようなイデアルをaによる単項イデアルと呼びます。

続きを読む

tag: 数学 勉強 同値 イデアル 群環体 ユークリッド 関係 集合 素数 証明

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

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

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

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


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


準同型写像φ: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: 数学 論理学 演算 論理式 命題 命題論理 集合 意味論

次のページ

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