ブログ「サイバー少年」

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

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

ユークリッド整域の定義を見直す

またユークリッド整域の話かよ!!!!
もうすでにイデアルの勉強に移っているんですが、ちょっと前にユークリッド整域で判明した事実があったので、今回は軽くですが記しておきます。

記事「ユークリッド整域の素元分解可能性について自分なりに補足」で、x = 0ならH(x) = 0およびH(x) = 0ならx = 0は定義せずとも定理として成り立つだろうかと疑問を書いていました。

結論からいうと定義しなければ定理としては成り立ちません。
ただ、そもそもユークリッド整域において、これが成り立つ必要はありません。

必要なのは「H(a)がすべてのxにおけるH(x)の最小値ならa = 0」です。
これがあればユークリッドの互除法が使える整域になるわけです。

なぜなら、ユークリッド関数のその他の定義により、元a,b(b != 0)について
a = b×q + rかつH(r) < H(b)となる元q,rが存在しますが、これを互除法で繰り返していくと、どんどんH(r)が小さくなっていって、最小値になったときにr = 0となって、もうbをrで割れないということになります。

H(r)が最小値になったときにr = 0でなければ、さらに割れることになってしまうので、それは困るからr = 0を要請しているということです。

しかし、「それは困る」という事態を詳しく見てみると、
もしH(r)が最小値なのにも関わらずr = 0でないとしたら、さらにbをrで割ることができて、新しい余りをr'とするとH(r') < H(r)でありH(r)が最小であることに反するから、r = 0であるしかありえなくて、実はこの定義すら必要なかったわけです。


また、「H(a)がすべてのxにおけるH(x)の最小値ならa = 0」が成り立つなら逆も成り立ちます。
その説明をするには写像の仕組みを論理的に説明できるスキルが必要ですが私には残念ながら能がないので、イメージになってしまいますが、
すべてのxにおいて最小となるH(a)は必ず存在するので、そのときa = 0なわけですから、aとH(a)が対応している、写像なのでaが他のところにも対応していることはない、つまりH(a)はすべてのxにおけるH(x)の最小値です。

そしてa = 0ですからH(0)はすべてのxにおけるH(x)の最小値です。

これがもし「H(a) = 0ならa = 0」とかだと、逆は一般に成り立ちません。
H(x) = 0となるxが存在しているとは限らないので、0とaの対応が保証できないからです。
すべてのxにおけるH(x)の最小値は必ず、なんらかのxと対応しているので保証できます。
論理的に説明するにはどうしたらいいんだろうか…。


ちなみに、

ユークリッド環 - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E7%92%B0

を見てみると、整域に元a,b(b != 0)についてa = b×q + rかつG(r) < G(b)を満たす写像Gが導入できるならば、
さらにそれと加えてH(a×b) >= H(a)を満たす写像Hを導入できることがいえるそうです。

H(a×b) = H(a)ならbは単元というのはどこにいったのか分かりませんが、まあ多分、これも定義せずともいえるんでしょう。(適当)

つまり、元a,b(b != 0)についてa = b×q + rかつH(r) < H(b)を満たす写像Hが導入できる整域であれば“ユークリッド整域”と呼んでいいわけですね。


論理というのは不思議ですね。
一を聞いて十を知るという言葉がまさにふさわしい。
ひとつ公理として定めたらめちゃめちゃ色々な定理が湧き出てきます。

恐らく、これでユークリッド整域についての記事は最後になります。
冒頭でも述べたとおり、イデアルの勉強をやっているので、引き続き頑張ります。

tag: 勉強 数学 群環体 ユークリッド 公理 写像 関数

ユークリッド整域における元と高さの関係

先日に書いた記事「ユークリッド整域の素元分解可能性について自分なりに補足」で


つまりH(x) = 0のところにx = 0が、H(x) = 1のところに単元のxが、H(x) = 2のところに単元と素元のxが、H(x) > 2のところに単元、素元、いくつかの素元の積がすべて分布してる感じですね。


と記述しました。

「単元と素元~」みたいな言い方をANDと解釈するなら間違いですが、まあORと解釈するなら間違った主張ではないんですけどね。

ただ、たとえばH(x) = 2のところに単元または素元のxが分布しているという主張ですが、これは正しくはH(x) = 2となるxについて、それは単元または素元である、という主張にするべきでした。

前回の言い方だとH(x) = 2となるxが必ず存在するかのような主張となっています。


そして、その他の点でも非常にナンセンスな表現であるということに気が付きました。
後述しますが、まず単元はそんな色んなところに分布してなくて、すべて同じ高さのところにあります。

あと、前述のようにORで解釈するなら間違いではないのですが、この主張を読んだときにイメージするのはH(x) = 2のところに素元となるxがあって、H(x) > 2以降において素元の積のxも含まれてくるという感じだと思います。

そのイメージは間違いですが、主張自体は間違いではないので、たしかに読み手が悪いと言えばそうですが、私の書き方にも問題があると思いました。


それは、1という数、2という数を定数として決定してしまっているところです。
実際は定数は決定せずに、色々な元に対する高さの大小関係だけをイメージしてもらえるような書き方にするほうが自然でした。

事の発端はYahoo!知恵袋で、整数に関数Hを導入したときに、H(x) = |x|ではなくH(x) = 2×|x|とすることも可能である、という指摘を受けたことでした。

このときH(x) = 2のところに単元があって、H(x) >= 4以降に素元などがあり、あとH(x)が奇数であることはありえません。

こんなように、定数はまったく変わってくるわけですが、大小関係は変わりません。
そこで今回は、元による高さの大小関係に着目して判明することを書いていきたいと思います。

続きを読む

tag: 数学 群環体 ユークリッド 考察 勉強 関係 素数 証明 写像 帰納法

ユークリッド整域の素元分解可能性について自分なりに補足

私が群・環・体の勉強に使っている本を読んでいたら、以前の記事「[環論] ユークリッド整域で陥った詭弁」にも登場しているユークリッド整域において、

0(零元)でも単元でもない任意の元は素元の積に分解できて、それぞれの素元における単元倍の差を除いて一意である

ということが解説されていたのですが、一意性についてはいいとして、分解可能性の証明に足りない部分があると思ったので、自分なりに考えて補足してみます。

そんな、この本の著者様に意見できるほど優れた人間ではないのですが…(汗)


まず、本では元xの高さH(x)の値に注目して、H(x)がどんな値であってもxが0でも単元でもないなら素元分解可能であることから、任意のxについて0でも単元でもないなら素元分解可能であるということを述べようとしています。

ここがまずちょっと難しいですが、すべてのxは必ずなにかしらの自然数H(x)に対応しているわけですから、すべての自然数において対応するxが性質を満たすことがいえれば、すべてのxにおいて性質を満たすことがいえるわけですよ。

厳密に証明しろと言われると、能力がなくて私にはできないですが…。

逆に、すべてのxについて対応する自然数がある性質を満たすとき、すべての自然数がその性質を満たすという論法は一般には正しくありません。
ただし、xから自然数へ対応させる写像が全射であるなら、上の場合と同じ状況になるので、正しいと思います。

続きを読む

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: 数学 勉強 問題 証明 代数学 ワーキングメモリ 集合 写像

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

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

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

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

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

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

集合と写像の勉強まとめ

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

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

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


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

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


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

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

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

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

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


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

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

続きを読む

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

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