2017-02-08

Atiyah-MacDonaldのProposition 1.11について(prime avoidance lemma, 2/13追記)

Atiyah-MacDonaldの「可換代数入門」のProposition 1.11では、

環Aとそのイデアル $\frak a$ と素イデアル $\frak p_1,\dots,\frak p_n$ について、
$\frak a \subset \bigcup_{i=1}^n \frak p_i$ となっているとする。
このとき、あるiに対して $\frak a \subset \frak p_i$ となる。

ということが書いてある。この素イデアルの条件を外すと不味いのかなと思って、
n=2で反例を探していたのだがずっと見つからなかった。
しかし、今日n=2だと素イデアルの条件なしでも同様のことが言えてしまうと気づいたので書いておく。

示すことは、

環Aとそのイデアル $\frak a,\frak b,\frak c$ について、 $\frak a\subset \frak b \cup \frak c$ が成り立っているとする。
このとき、 $\frak a\subset \frak b$ か $\frak a\subset \frak c$ かのどちらかが成り立つ。

である。背理法で示す。仮に、
(1) $\frak a\subset \frak b\cup \frak c$ 、(2) $\frak a \not\subset \frak b$ 、(3) $\frak a\not\subset \frak c$ のすべてが成立していたとする。
仮に、 $\frak b\subset \frak c$ だとすると、 $\frak b\cup \frak c = \frak c$ となって(1)に反するので、(4) $\frak b\not\subset \frak c$ である。
同様に、(5) $\frak c\not\subset \frak b$ も成り立つ。(2)、(3)、(4)、(5)より、 $x \in (\frak b\setminus \frak c)\cap \frak a$ と
$y\in (\frak c\setminus \frak b)\cap \frak a$ が成り立つようなxとyが存在する*1。 $x,y\in \frak a$ なので、(1)より $x+y\in \frak a\subset \frak b\cup \frak c$ となる。
よって、 $x+y\in \frak b$ か $x+y\in \frak c$ かのどちらかは成立する。
前者が成立するとする。 $y=(x+y)-x$ だが、 $x$ は定義から、 $x+y$ は仮定より $\frak b$ の元なので、 $y$ も $\frak b$ の元である。
これは $y$ の定義に反し、矛盾である。後者が成立すると仮定すると同様に $x\in \frak c$ が導かれ、矛盾する。
よって、どちらにしても矛盾する。証明おわり。

というわけで少なくともn≧3で探さないと意味がないっぽい。Alloyで探してみようと思う。

2/13追記

id:qnighyさんがn=3で例を見つけてくれました。

Prime Avoidance Lemma で素イデアルの仮定を外した場合2個までは成り立つが3個では成り立たないっぽいやつです pic.twitter.com/Vw1SKD5bUz
— Masaki⊣Hara (@qnighy) 2017年2月13日

2次の項全部で割ってるので有限の環になってます。これならAlloyでも見つけられそう(勉強中)。
加群ぽく考えるのが大事みたいです。

あと、タイトルのprime avoidanceの説明をしてなかったのですが、このAtiyah-MacDonaldのProposition 1.11には
prime avoidanceという名前がついているようで、こんな記事https://en.wikipedia.org/wiki/Prime_avoidance_lemmaがあります。

*1:2/13修正

2016-08-05

公式のPythonとAnacondaを共存させる(備忘録)

Dev

(2018年8月31日追記): pyenvでぐぐりましょう。以下はすごく変です。

2016-02-28

プログラミングコンテストチャレンジブックの分割数について

「分割数」でぐぐると同様の記事がいろいろ出てくるのだけれど、やっぱりよく分からなかったので考えたらようやっと納得がいった。なので、その記録をしておく。

まず、なんだか分からなかった原因は、「jのi分割数」というのは「jを1以上の自然数i個の和でかきあらわしたときの(順序を無視した)書き表しかたの個数」であるはずなのに、0の和も考えているようにも読めて何を考えているのだかよく分からなくなるところにあったと思う。そういうわけで、式と向き合っていたところ意図がわかった。

「jのi分割」は「jを1以上の自然数i個の和でかきあらわしたときの(順序を無視した)書き表しかた」で、これらのなす集合である「jのi分割のなす集合」を考える。
この集合を、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」と「jのi分割のなす集合のうち、1を(1個以上)使うもの」の2つに分ける。
すると、この2つの部分集合は交わりがなく、しかもこの2つの集合の結びは「jのi分割のなす集合」となるので、「jのi分割数」であるdp[i][j]を求めるには、この2つの部分集合それぞれの元の個数を数えればよい。

まず、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の個数を考える。実は、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」と「(j-i)のi分割のなす集合」との間には同型対応が作れる(つまり、余りもダブりもなく、2つの集合から1つずつ選んできたペアを作ることができる)。具体的にどうするかというと、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の元「2を $a_2$ 個、3を $a_3$ 個、…」に対して*1「1を $a_2$ 個、2を $a_3$ 個、…」と割り当てる。いま、i分割を考えていることから、 $a_2+a_3+\dots = i$ が成り立っており、この対応は確かにi分割をi分割に写している。さらに、jの分割を考えていることから $\sum_{i\ge 2} i a_i = j$ となっており、よって $\sum_{i\ge 2} (i-1)a_{i}= \sum_{i\ge 2} i a_i - \sum_{i\ge 2} a_i = j - i$ となる。よって、確かにjの分割を(j-i)の分割に写している。以上のことより、この対応は確かに「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」から「(j-i)のi分割のなす集合」への写像になっている。逆の対応は明らかなので省略し、それが全単射になっていることも省略する*2。よって、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の個数はdp[i][j-i]である。

次に、「jのi分割のなす集合のうち、1を(1個以上)使うもの」の個数を考える。「jのi分割のなす集合のうち、1を(1個以上)使うもの」は、その使っている1を取り除いて考えれば「jの(i-1)分割」になり、逆の対応もつけることができて同型であることがわかる。よって、「jのi分割のなす集合のうち、1を(1個以上)使うもの」の個数は「jの(i-1)分割」の個数であり、これはdp[i-1][j]である。

以上で、dp[i][j] = dp[i][j-i] + dp[i-1][j]である。

集合の分け方が一番のミソでした。

*1:「2以上のみを～」という定義から、「1を0個」使っているということに注意。つまり、「1を $a_1$ 個～」と書く必要はない。

*2:だんだん飽きてきた

2015-11-30

米田の補題のしょうもない使用例

マクレーンを読んでて米田の補題を示したはいいが何やってるか全然わからないし、議論する階層も深すぎて何を扱ってるのかもよくわからなかったのでしょうもない
例を作った。式は
$y\colon \bf{Nat}(D(r,-),K) \simeq Kr$ だが、右の $Kr$ から何か元をとってきてそこからどんな自然変換ができるかを見てみることにした。

それぞれの登場人物は、以下のようにする。

圏 $D$ : モノイドの圏。 $D=\bf{Mon}$
関手 $K$ : $\bf{Mon}$ から $\bf{Set}$ への忘却関手
$r$ : 「 $\{a,b,A,B\}$ という4文字のアルファベットを並べた文字列」というモノイド

そして、 $Kr$ の元として文字列「 $AabB$ 」をとり、これが $y^{-1}$ でどんな自然変換を生むかを見る。

「AabB」を使って、モノイド $d$ を固定したときに自然変換 $\alpha_d$ を作りたい、つまり
モノイド準同型 $f\in D(r,d)$ が $\alpha_d$ で $Kd$ のどこに写るかを定めたい。
そのためには以下の図式を使うのだった。

f:id:sle:20151130011539p:plain

ここで、この図式の左側はモノイドの圏の図式で、右側が集合の圏の図式なことに注意する。
ここで、右の四角の左上に恒等写像 $1_r$ を流せば、図式の可換性より
$\alpha_d(f) = (\alpha_d \circ (f\circ ?) )(1_d) = ( (Kf)\circ (\alpha_r) )(1_d) = (Kf)(\alpha_r 1_d)$
となるが、この $\alpha_r 1_d \in Kr$ を今は文字列「 $AabB$ 」と定めるというのが $y^{-1}$
の定義だった。つまり、
$(Kf)(\alpha_r 1_d) = (Kf)("AabB")$ であり、
$\alpha_d(f) = (Kf)("AabB")$ ということになる。

具体的にこの自然性を使ってみる。
いま、「 $\{a,b\}$ という2文字のアルファベットを並べた文字列」というモノイド $(\{a,b\}, \cdot)$ を考える。
また、先のモノイド $r$ は $(\{a,b,A,B\}, \cdot)$ と書くことにする。
さらに、モノイド準同型 ${\bf{count}} \colon (\{a,b\}, \cdot) \to (N, +)$ を文字数を数えるモノイド準同型とする。
ただし、 $N$ は0以上の自然数。このとき、自然性より次の図式が得られる。

f:id:sle:20151130013459p:plain

ここで、この図式の左側はモノイドの圏の図式で、右側が集合の圏の図式なことに注意する。
ここで、図式の左上に、大文字を小文字に、小文字をそのままにするモノイド準同型
${\bf {lower}} \in {\bf {Mon}}( (\{a,b,A,B\}, \cdot),(\{a,b\}, \cdot) )$ を入れてみる。すると、
↓→というたどりかたでは、
$\begin{align} (\alpha_{(N,+)}\circ ({\bf count} \circ ?) )({\bf lower}) &= \alpha_{(N,+)}( {\bf count} \circ {\bf lower}) \\ &= ({\bf count} \circ {\bf lower})("AabB")\\ &= {\bf count}("aabb")\\ &= 4. \end{align}$
一方、→↓というたどりかたでは、
$\begin{align} ( (K{\bf count}) \circ \alpha_{(\{a,b\},\cdot)} )({\bf lower}) &= K{\bf count}({\bf lower}("AabB") )\\ &= K{\bf count}("aabb")\\ &= 4. \end{align}$

となり、確かに一致する。↓→での $"aabb"$ はモノイド $(\{a,b\}, \cdot)$ の元であり、
→↓での $"aabb"$ は集合 $\{a,bからなる文字列\}$ の元であることに注意する。

つまるところ、「準同型を忘却させて関数を作り、そこに『AabB』をわたす」という操作は自然である」ということになった。

忘却関手を使うとこのへんがごちゃごちゃになるしもうちょっと込み入った関手を使えばよかったのかなあ。

2015-10-22

tikzcdが動かなかったけど直った話

TeX

前も似たようなことをやったのに忘れて同じ轍を踏んだので大したことではないが書いておく。

breqnと衝突しているらしく、あれを外したら動いた。黒魔術系パッケージには気をつけましょう。

2015-06-28

右可逆写像・左可逆写像・単射・全射

math

2ヶ月に1回ぐらい「あっ！右逆写像と左逆写像と単射と全射の関係の覚えかたを思い付いたぞ！」となってその後忘れるというのをくりかえしているのでこの際きちんと書いておく。

f:id:sle:20150628013937p:plain

写像を分解すると、結局単射は $B \subset A$ のときの、そのままの元に写す写像 $B \to A$ が典型的なので、そのときだけを考えることにする。そうすると上の図の上段のように $A$ の $B$ の部分はそのまま写し、残りは出鱈目に送れば左逆写像が作れる。よって、単射ならそれに対して左逆写像が作れる。

写像を分解すると、結局全射は $B\subset A$ のときの、 $A$ の $B$ のところをそのままの元に写し、残りは出鱈目に送る写像が典型的なので、そのときだけを考えることにする。そうすると上の図の下段のように $B$ をそのまま写せば右逆写像が作れる。よって、全射ならそれに対して右逆写像が作れる。

2015-05-21

ゲームを作りたい人は割とすぐ作りはじめられるのではないか

人生の混沌: システム工学に関するメモ(講演資料作成にご協力お願いします)という記事をサークルの同期が書いたのだが、そもそもゲームを作りたい人があまり情報に恵まれていないというところに賛同できないので、何をすればいいかを書いてみる。

本を読めばいいのではないか

一般論として、はじめての人はできるだけ新しい本を買ったほうがいいのではないかと思う。
なぜなら、古い本だと使っているOSが古かったりプログラミング環境が古かったりする
ために、スクリーンショットが微妙に食い違ったり、メニューを辿るときに
「ファイル→プロジェクト→…」といった辿りかたがずれたりして、
そのために混乱するかもしれないから*1。
ある程度なれれば自分で修正できるのだが、いまはとりあえずゲームが作りたいのだから
そういう力を鍛えようなどとは思わないほうがいい。

また、一般論その2として、よく分からなかったら2冊目を買ったほうがいいと思う。
文体や扱う題材には向き不向きがあるので、2冊目だったら案外すいすい行けたり
することもあるし、根本的に本に書いてあることが間違っていたということは十分ありえるから。

あと、これからいろいろ挙げていくが読んだり読んでなかったりすることはご了承いたあきたい。

HSP

伝統あるかんたんプログラミング言語という感じがする。
プログラミングコンテスト HSPプログラムコンテスト2014が定期的に実施されていて、
昔から小学生や中学生の投稿が目立つことからも取っ付きやすいなどと思う。
本も無数に出ていて、関連書籍の紹介本屋さんで
自分の作りたい感じの画面が載っているものを選べばよいと思う。

3Dプログラミングやネット対戦対応もできたと思うので、
込めた愛情でそこらの同人ソフトを凌駕することは十分可能だと思う。

なでしこ

日本語プログラミング言語。英語がどうしてもいやだという人がやると良い。
使っているうち英語がわからないままでも、「ああ、『もし』を単に『if』で置き換えればいいだけなんだな」ということで、英語ベースの言語にも馴染んでいけると思う。
本はほとんどないが、公式のマニュアルが絵がたくさんついていて楽しく読める。
基礎編プログラミング基礎編で文法を学んで、
ゲーム編ゲーム製作編まで用意してある。
ただ、描画機能がそんなに優れているわけではないので
あまり長居はしたくない気がする。

ゲームプログラマになる前に覚えておきたい技術

一昔に話題になった名著。セガの研修で使われている(いた)らしい。
C++の知識は仮定するが、そんなにヘビーではなかったと思うので
「ゲーム作るにはC++だと聞いてC++の本を読んでいたが飽きて半分で投げた」
というぐらいでもそのC++の本を傍らに置けば読めると思う。
あと、高校数学がすこし必要になるので、自信がなければ手頃なサイトを見つけておくか、
「大人のための高校数学を復習～」という類の本を手元に置いておいたほうがよい。

ただ、大問題として確かVisual Stuido 2008 + DirectX9で進んでいくので、
いま読むには結構古い感じがある。

作るものは本当に本格的だし、作っていく過程の話も文中に織り交ぜてきたので楽しく読めるのではないか。

[普及版]ジェネラティブ・アート―Processingによる実践ガイド

最近の私の一押し。
使う言語はProcessingで、デザイナに人気があると言われている。
綺麗な模様を出しながら短い行数でifやforの基本構造を学べるので、
飽きずにどんどん進めるはずである。

全然そういうテーマではないのだが、ジェネラティブということで
短いルールで複雑な模様を出すということを扱っているので、
絵が描けない人がアブストラクトで意味深な画面を作れるようになるという意味でも
ゲーム作りには良いのではないか。

言い忘れたが、ゲームそのものを作る本ではない。

「14歳からはじめる～」シリーズ

Amazon.co.jp： 14歳からはじめるC言語わくわくゲームプログラミング教室 Visual Studio 2013編: 大槻有一郎: 本が例えばある。
全然読んでないが伝統あるシリーズなのできっと楽しく読めると思う。
「なか見！検索」したが、絵がかわいい。

ぐぐろう

プログラミングをする人でも、そのプログラミング言語のことが全て頭に入っている
人というのは多くなくて、大体わからなくなる度に調べているものだと思う。

例えば、「セーブデータを作りたい」と思ったときは
「C# ファイル書き込み」などと調べることになる。ここで、
「C# セーブデータを作る」と書くのはあまりいい手ではないという意味で
ぐぐるというのも難しいのだが、その辺のキーワードの選び方は
入門書を一冊読んで、なんとなくぐぐることをくりかえすうちに身に付くのではないか。

Unityについて

いま流行りのゲームエンジンで、なんだかコードを書かずにゲームが作れるような
謳い文句だが、流石にコードは書かないとまずい。

Unityは画面のなかにどんどん物を置いていくのだが、
例えばその制御を何にまかせるのかや、物理エンジンを手書きしたほうがよいのか、
Unity内蔵のもの使ったほうがいいのかなど、使い方の幅が広く、はじめての人だと
かえって途方に暮れることが多いのではないかなあと思っている。
実際Twitterで流れてくるツイートを見ても、Unityの使い方はユーザーの数だけあるという
感じだし、Unityが真価を発揮するのはエディタ拡張でどんどん環境を変化させていってから
という感じがする。

はじめてやるのが悪いというわけではないが、決して簡単ではないので、
「Unityで駄目なら俺には駄目なんだ」と悲観するのは不味くて、
是非上に挙げたような古典的な方法を試してみていただきたい。

おわりに

文章が雑だなあ。

*1:特に環境変数の設定なんかWindowsがアップグレードする度にやり方が変わってしまって困りますね。