一般に、演算が定義された集合でを満たす元eを単位元という。 例えば、整数では“乗法”という演算を考えたとき,通常の 1 が単位元である.また,“加法”では 0 が単位元である.
*リスト：リスト::数学関連
とあるテキスト（書籍）の代数（分野）に関する記述で、幾つかの種類の可換環が登場するのですが、分類の基準がよく分からない。なので、ちょっと伺ってみたり調べたりしてみました。分類された各クラスに所属する／所属しない可換環の実例や、クラスの相互関係などは考えが及んでません。聞きかじりや俄仕込みの浅知恵な記述が多いです。$`\newcommand{\mrm}[1]{ \mathrm{#1} } \newcommand{\hyp}{\text{－} } `$内容： 分類基準 単数群 イデアル 因子分解 方程式の解 分類されたクラス 分類基準イチを持つ可換環しか考えないので、単に「環」と言ったらイチを持つ…
全方位木 DP の練習問題！！ が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみたす場合の数を で割った余りを求めよ。 頂点 は黒色である 黒色の頂点は連結である 制約 解法：全方位木 DP この問題に対して、各頂点 を根とした木 DP をしてしまうと、 の計算量となってしまいます。このようなとき、全方位木 DP がしばしば有効です。 ここでは、通常の「根を 1 つ決めたときの木 DP」を全方位木 DP へと機械的に拡張す…
これを考えるために、整数では何が成り立っているのかをまず見ていく必要があります。 準備: 整数の性質 整数 $ \left( \mathbb{Z} \right)$ では、加法 ($+$) と乗法 ($\cdot$) が定義されており、以下の性質が成立しています。① 加法について A. 加法について閉じている。つまり、$\forall a, b \in \mathbb{Z}$ に対して $a + b \in \mathbb{Z}$ が成り立つ。 B. 結合法則。つまり、$\forall a, b, c \in \mathbb{Z}$ に対して $(a + b) + c = a + (b + c…
とする． 前回，が-準同型写像であることを確かめた．これはについて，-準同型写像の加法を定めたことに成る．いま，-準同型写像の集合 を考えると，演算に対して，これは加法群を成す． (証明) Ⅰ. 結合律 を選ぶ(パラメタの自在性)すなわち と置く．このとき，より が成立する． Ⅱ. 単位元(零元) と置く．より と成る．実際 (ア) i.e. が成り立つ． (イ) (ア)よりであるから，同様にしてである．したがってが成立する． Ⅲ. 逆元 と置く．このときより と表される．というのも (ア) について i.e. と書けるからである． (イ) について (ア)と同様にしてが成り立つ． 以上より，…
とする．このとき ① ② を考える．まず，①についてを加法群で考え と置く．このとき，は加法群であり，より i.e. である． 次に②について，いま，剰余類の集合を と置けばは群を成す． (証明) の演算に関してその和を で定める． (ア) 結合律 と置くとき，を示す． より と書ける． 一方，から である．ここで，は何れもパラメタであるから と成るように置けば(パラメタの自在性による) が成立する． したがって，であることが示された． (イ) 単位元(零元) と置く．このときより という性質(群の零元の公理をみたす)をもつ． それゆえ，剰余類の集合の零元はであることがわかる． (ウ) 逆元 …
Xで連載していた，著書の『いきものの「種」はどのように決まるんだろう』の内容の紹介を以下に示しておきます． https://www.amazon.co.jp/dp/B0CMQ5ZXJS ・表紙について 表紙の写真はブダイと，そのブダイに付着した寄生虫を食べるホンソメワケベラという魚です．これは2種が相利共生していることを示す生態展示になっています．京都大学白浜水族館で撮影しました． 魚類のうち結構な種類のものが，ホンソメワケベラを発見すると近寄って行きます．寄生虫を食べてもらう魚はその寄生虫を食べてもらいたい体の部分をホンソメワケベラに差し出したり，全身を硬直させてホンソメワケベラを受け入れま…
目標 ここでは「群論の計算」などで扱っている問題をChatGPTを使って書いていきます。まず、これは何のためにやっているのかを書きます。これはChatGPTではなかなかちゃんとした答えが返ってくるように書くのは難しいようなので、大まかなことは自分で書きます。以下のようなことをやろうとしています。 数学の問題を表す適切な用語がないものについて考える 帰納法を数式の変形またはビジュアルプログラミングで表す 多項式の計算でできることを考える プログラムの代数的構造を考える 細かい個別のテーマを書いておきます。これらについては何か答えが得られるかもしれません。 写像と同値関係の間の関係 単一化による帰…
半環について Prolog のプログラムは論理式と解釈できます。論理式の全体は分配束となります。分配束は(単位元の存在などを無視すると)半環となります。このブログでは Prolog のプログラムを半環を使って調べています。分配束を使って調べても良いのですが、半環は環と同様のことが成り立つことがあって考えやすいので半環を使っています。いくつかの入力とそれに対する答えです。 半環の定義を教えてください 半環（Semiring）は、代数構造の一種であり、加法と乗法を持ち、それぞれに対して加法単位元と乗法単位元を持つ非常に基本的な構造です。以下に、半環の定義を示します。半環は、以下の条件を満たす二項演…
とあるキッカケがあって、マッテーオ・カプチとディビッド・ジャズ・マイヤースの講演アブストラクトを眺めてみました。 [CM23] Title: Constructing triple categories of cybernetic processes Authors: Matteo Capucci, David Jaz Myers Date: 2023/11/11 Pages: 3p URL: https://act2023.github.io/papers/paper58.pdf Applied Category Theory 2023 でのカプチによる発表の録画もあるようですが、その動画は…
ここではこのブログで書いたことや検討中のことをChatGPTでやってみたらどうなるかを調べることにします。もし簡単にできるようならブログを書く意味がなくなるので、やってみた方が良いと考えました。とりあえずいろいろやってみたところ、簡単にはできませんでした。しかしこれは入力が良くないのかもしれず、今はできないだけなのかもしれません。最近は入力のやり方や、何ができるのかなどが書かれた本も出ているので、少し読んでみましたが、わかりませんでした。今はまだわからないのかもしれません。証明は簡単なものであればできました。プログラムの作成はもう少し複雑なものもできました。今はビジュアルプログラミングを使う方…
まえがき こんにちは、ARC173で水落ちした獅子座じゃない人です。 ARC173のE問題が単純な問題設定で一見単純な答えでありつつも、とても非自明な場合分けが必要であると感じました。 また、ARC-Eだけあって解説もとても行間が広く、行間を埋めたり別のアプローチをとって証明を試みたところ、さらに面白く感じたのでまとめます。 問題 atcoder.jp 元の問題文で理解できる問題設定だと思いますが、一応書いておきます。 長さの非負整数列が入力として与えられます。 非負整数の二項演算で、二進表記の各桁についてXORをとるものを、ビット単位XOR演算と定義しておきます。 を好きなように並び替えたも…
Scala with Cats を読んだので学習した内容のメモを残します。 2章のMonoids and Semigroupsです。 はじめに Monoidは二項演算と単位元を持つ代数的構造であり、Catsでは型クラスが提供されている。 Monoidの定義 CatsでのMonoidの定義を簡略化したものが以下。 trait Monoid[A] { def combine(x: A, y: A): A def empty: A } combine(二項演算): A型の2つの値を結合させて1つのA型の値を返す empty(単位元): A型の空要素を返す という2つの操作がMonoidには定義されて…
前にまとめたが、( → ノート：群・モノイド・半群・マグマ(亜群) - 滴了庵日録 ) モノイドとは、集合と二項演算について単位元が存在するやつだった。 (ただし、この二項演算はこの集合のなかで閉じていること、また結合法則をみたすこと)このようなモノイド (集合, 二項演算, 単位元) の例としてプログラミングの世界でおなじみのやつを挙げると、 (Int, +, 0) (Int, *, 1) (Bool, ||, False) (Bool, &&, True) (String, +, "") (Array, +, []) このうち、(Int, +, 0) 以外は任意の元に対する逆元が存在しない…
概要 通常のセグメント木では、管理対象の列の項数 を固定して完全二分木を構築するため、初期化に時間計算量および空間計算量 を要し、1 回のクエリあたり時間計算量 を要する。 したがって、 として利用できる値には計算機資源上の制限があり、列のインデックス (セグメント木の定義域) としてより大きな値を利用するには、オフライン クエリ (入力値がすべて予め与えられる) を前提として座標圧縮をする必要があった。 そこで本稿では、セグメント木の定義域を拡張し、例えば や のような範囲を利用できる方法について記述する。 これにより、座標圧縮をせずにセグメント木のオンライン クエリ (入力値が逐次的に与え…
現在２０２３年８月２日１２時２８分である。（この投稿は、ほぼ１８１１文字）麻友「もう、私の手を離れたのだから、自由にやって良いわよ」私「昨日、第Ⅰ章の は、ちょっとずつ書くと言った。今日、『解析入門Ⅰ・Ⅱのノート（１～１０）』を持って来て、眺めたが、全部写す必要は、ないなと、思った。結局躓きやすい場所は、大体決まっている。私が、もの凄く書き込んでいる場所を中心に、記して行こう。まず、述語論理が現れる部分(本文p.5-6)」 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 実数 本当は、よっぽどど素人でなければ、半分くらいは、理解できるものだと思う。２００６年１月１０日から、復習…
ja.wikipedia.org
