…像 $`i`$ ： 不動点なし対合 対合以外はまったく不適切な呼称です。$`E`$ の要素は辺ではなくて半辺〈フラグ〉です。$`H`$ の要素が境界点〈端点〉を持つのに対して、$`E`$ には境界点を持たない半辺も含まれます。ソース写像 $`s`$ とは、単なる埋め込みです。$`H \subseteq E`$ とみなすと、$`E\setminus H`$ が境界点を持たない半辺（辺じゃありません）です。ターゲット写像 $`t`$ は、ソース写像 $`s`$（単なる埋め込み）と…

…`\iota`$ は不動点を持ちません。この点はジョイアル／コック〈André Joyal, Joachim Kock〉方式と同じです。幾何半グラフを組み合わせ半グラフにエンコードするために、補助的情報を書き込むと次のようになります。すべての辺は2つのフラグ〈半辺〉に分けられます。言い換えると、異なる2つのフラグのペアが辺を形成します。外部辺〈開放辺〉と例外辺は、無限遠点に接続しているとみなします。例外ループは、レンガ色のバッテンで描かれたダミー頂点の自己ループ辺とみなします…

…般的な用法とは違い「不動点が無い〈fixed-point free〉」のことです。群作用 $`\alpha`$ が自由〈free〉なら、単位元以外の群元（群 $`G`$ の要素）の作用は不動点を持ちません。自由であることは次のように書けます*1。$`\quad \forall g\in G.(\, g \ne I \Imp \forall x\in X.\, \alpha(g, x) \ne x \,) `$$`\alpha`$ が自由な群作用のとき、$`\mrm{motio…

…t \hyp`$ に不動点があるか？」を調べれば $`g = e`$ かどうかを判断できると言っています。ニ番目だと、$`g`$ ごとに適当な点 $`a\in X`$ があって、「その点 $`a`$ が $`g\cdot \hyp`$ の不動点かどうか？」を調べれば $`g = e`$ かどうかを判断できる、と。二番目じゃないだろうから、一番目だとして内側の待遇をとると：$`\quad \forall g\in G.(\, g \ne e \Imp \lnot (\exist…

…す。ペアリング対合は不動点を許すので、“一人だけのペア”も存在します。半グラフ $`\alpha`$ は、上記の構成素を並べて次のように書きます。$`\quad \alpha = (V(\alpha), F(\alpha), \bdry_\alpha, \iota_\alpha)`$半グラフ $`\alpha`$ のフラグの集合 $`F(\alpha)`$ 上にペアリング対合 $`\iota_\alpha`$ が働きますが、$`\iota_\alpha`$ （が誘導する同値関…

…／ドーラン・ツリー 不動点なし対合のオペラッド結合 ワイヤリング図とケリー／マックレーン・グラフ コステロの半グラフ圏によるシステム記述 コステロの半グラフ圏から二重関手意味論へ 開放ツリー： 半グラフ・ベースのツリー 半グラフの二重圏と半グラフ変形 半グラフ変形とDead-Or-Alive構造 半グラフのあいだのエタール射 半グラフに関わる諸概念 幾何半グラフの組み合わせ的表現（新方式） 強化ファインマン・グラフとバタニン／バーガー半グラフ プッシュアウトによる半グラフ接合…

…\sigma`$ は不動点を持ってもよい。 半辺の幾何的実現は片一方が開いた区間 $`\{x\in {\bf R}\mid 0\le x\lt 1\}`$ です。$`\sigma`$ によるパートナーとくっ付くと、両端の境界点を含む閉区間の形状になりますが、パートナーがいない（正確には自分自身がパートナーである）半辺もあります。このような状況を表すために次の定義をします。 $`T := \mathrm{Fixpoint}(\sigma) \subseteq H`$ ： $`\…

… が無い」の意味で「不動点が無い」こと。群作用の "free" は "fixed-point free" のことだと考えましょう、コジツケとしてですが*2。群作用が不動点無しだとすれば、次が成立します。$`\quad \forall g\in G.(\, g \ne I \Imp (\lnot \exists x\in X.\, g\cdot x = x ) \,)`$単位元の作用が不動点有り（つうか、不動点ばっかり）なのは致し方ないので、「単位元じゃなければ」という条件を付…

…T), -)`$ は不動点を持たない対合付き集合となります。半グラフとの関係性が匂ってきます（例えば、「テンソルの可視化のための半グラフ」参照）。ワイヤーには始点〈ソース点〉と終点〈ターゲット点〉があるので、ワイヤーに始点／終点を対応させる写像もあります。$`\quad \mrm{src} : \mrm{Wire}(T) \to \mrm{Port}(T)\\ \quad \mrm{trg} : \mrm{Wire}(T) \to \mrm{Port}(T) `$有限集合のあ…

… を満たす写像です。不動点があってもかまいません。$`a \sim b :\Iff b = \alpha(a)`$ と定義すると、$`\sim`$ は同値関係になります。$`C/\!\sim`$ はこの同値関係による商集合です。写像 $`\mrm{nn}`$ は次の条件を満たす（i.e. セクションである）とします。$`\quad \mrm{nn}; \pi = \id_{C/\!\sim} \In {\bf Set}`$ ここで $`\pi`$ は、商集合への標準射影です。…

… headache〉だからだそうです。これも「そうそう、そうだよね」。「不動点なし対合のオペラッド結合」において、ワイヤリング図のオペラッド結合の純組み合わせ的定義を示しましたが、これは無頂点ループを無視しています。無頂点ループが入ると、頭痛がひどくなりそうです。とはいえ、コンピュータで実行可能なアルゴリズムとしてオペラッド結合を書きたいなら、頭痛を我慢して頑張るしかありません。 *1:別などこかで「閉サイクル〈closed cycle〉」を見ましたが、これも混乱を招きそう。

… 。 $`w`$ は不動点を持たない。つまり、$`\forall x\in X.\, w(x) \ne x`$ 。 この条件は、「テンソルの可視化のための半グラフ」で出したパートナー指定対合〈partner designation involution〉＝ワイヤリング対合〈wiring involution〉の条件です。$`{\bf SC}`$ の（$`{\bf F}`$ の）ワイヤリング射の全体を次のように置きます。$`\quad W = W^{\bf SC} \subse…

…図しています。2つの不動点なし対合に対して、ある種の結合（オペラッド結合と呼ぶのですが）を定義して、それが再び不動点なし対合になることを示します。$`\newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\cat}[1]{\mathcal{#1}} %\newcommand{\twoto}{\Rightarrow } \newcommand{\In}{\text{ in } } %\newcommand{\Imp}{ \Rightarro…

…は： $`w`$ は不動点を持たない対合〈involution〉である。 $`w; t = t`$ である i.e. 型付けはワイヤリングに対して不変である。 型なし半グラフは、$`T = {\bf 1}`$ の場合と考えられるので、次が言えます。 型なし半グラフは特別な型付き半グラフである。 単に「半グラフ」と言ったときでも、常に型が付いている（自明な型かも知れないが）と思ってください。入れ子の型付き半グラフの一例を挙げましょう。2つの型付き半グラフ $`A, B`$ を考…

…対合 $`p`$ は不動点を持ちません。$`\quad \forall h \in H.\, p(h) \ne h`$以上の構成素達で、半グラフの組み合わせ的構造を記述できます。もう一度構成素を列挙すると： 半辺の集合 $`H`$ 頂点の集合 $`V`$ 境界写像 $`\B :H \to V + \{\bot\}`$ パートナー指定対合 $`p: H \to H`$ 構成素をひとつの図式で描けば：$`\quad\xymatrix{ % @(inDir, outDir) H \…

…ランチ〉の集合上に、不動点のない対合を考えるジョイアル／コック方式と、不動点があってもいいとするボリソフ／マニン方式のアイディアを組み合わせると、サークル〈無頂点ループ〉を持つ半グラフも表現できます。その方法が良いかどうかは疑問だけど（最後の段落参照）。次の例を考えます。図の左側はサークルを持つ半グラフで、5本の辺〈広義の無向辺〉を持ちます。それぞれの辺の種類は次のようになります。 名前 種類 a 自己ループ辺 b 二頂点辺 c 単頂点辺 d 無頂点辺 e サークル〈無頂点ル…

…の定義： 埋め込みと不動点無し対合 ボリソフ／マニンの定義： 無頂点辺が不要な場合 半グラフの各部の呼び名 おわりに 参考文献まず、半グラフに関する参考文献を列挙します。半グラフを主題的に扱っているとは限りませんが、半グラフの定義を含むものです。印象的な部分の画像コピーも貼っておきます。 nLab項目 冒頭に書いたとおり、比較的分かりやすいです。この記事では、nLab項目の定義と説明を基準に考えます。 Title: semi-graph URL: https://ncatla…

…素と閉包作用素のプレ不動点 順序集合の上でモナドなど $`(A, \le)`$ が順序集合（反対称律を満たす）のときは、三番目の条件をイコールで書いてもかまいません。 $`f(f(a)) = f(a)`$ （ベキ等〈idempotent〉） $`(A, \le)`$ を、べき集合に包含順序を入れた順序集合 $`(\mrm{Pow}(X), \subseteq)`$ に限定することもあります。Wikipedia項目 Closure operator の定義はそうなっています。つ…

…と再開モナド構成子 不動点方程式とFreeT 関数／関手のアフィン化フリーモナドもフリー・モナド変換子も、不動点理論の圏論バージョンに依拠しています。頻繁に現れる不動点方程式はアフィン型不動点方程式〈affine-type fixed point equation〉です（「不動点方程式／不動点不等式と不動点オペレーター // アフィン型不動点方程式」参照）。ここでの「アフィン」は、アフィン線形写像にちなんだものです。アフィン線形写像は、線形写像に定数項を足した形のものです。一…

…あります。トレースや不動点オペレータは、関手・自然変換ではないけど重要な圏論的構成素です。非関手的対応、非自然な変換も積極的に使いましょう。ここで僕が言いたいことは、我々に必要な操作・構成がすべて関手・自然変換であるとは限らないことです。また、最終的には関手・自然変換だと判明するにしても、最初からその姿で現れないかも知れません。そのような操作・構成の定式化に圏論的コンストラクタ／圏論的オペレータが有効です。 「非全域関手と非自然変換」より： 非全域関手や非自然変換のような変な…

ここ何回か不動点の話を書きました。 不動点方程式／不動点不等式と不動点オペレーター (2022-09-22) タルスキーの最小プレ不動点定理（訂正） (2022-09-23) 証明のツリー構造も描いてみる (2022-09-23) タルスキーの定理の実例と応用 (2022-09-24) 解析学や幾何学でも不動点定理を使いますが、我々の興味は別なところにあります。再帰や帰納と呼ばれる手法や現象を不動点により説明したいのです。よく知られた例（人によっては「またそれか」）ですが、階…

…タルスキーの定理は、不動点に関するタルスキーの定理です。不動点関連でも次のような「タルスキーの定理」があります。 最小プレ不動点と最小不動点の関係を述べた定理 最小不動点の存在定理 不動点集合の性質に関する定理 「最小プレ不動点ならば最小不動点」であることは「タルスキーの最小プレ不動点定理（訂正）」で詳しく述べました。この最小プレ不動点定理を使って、適当な条件のもとでの最小不動点の存在定理を示してみます。$`\newcommand{\mrm}[1]{\mathrm{#1}} …

…タルスキーの最小プレ不動点定理（訂正）」において： 証明の流れを完全に追えるように、中間の命題にいちいち名前（ブラケットで囲った文言）を付けて参照することにします。 と、やってはみたのですが、“証明の流れ”がテキストで直列に（シリアライズされて）書かれているので、やっぱり“証明の流れを完全に追う”のは辛いかも知れません。テキストで直列に書く方式だと、証明のツリー構造がつぶれてしまうので、それを再現する労力で消耗します。以下に、証明のツリー構造を Graphviz で描いた絵を…

「不動点方程式／不動点不等式と不動点オペレーター」において、タルスキーの最小プレ不動点定理を出しましたが、記述が間違っていたので訂正し、省いていた証明を記します。$`\newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\cat}[1]{\mathcal{#1}} \newcommand{\In}{\text{ in } } \newcommand{\Iff}{\Leftrightarrow } \newcommand{\Imp}{\Ri…

…しました。 圏論的な不動点方程式と、不動点方程式によるフリーモナドの構成については「2」で述べます。 しかし、不動点の話はフリーモナドとは独立に語れるので、「フリーモナド」の続きではない形にします。不動点の一般論を特にフリーモナドに対して適用する話が「フリーモナド 2」になるでしょう。不動点の話だけでもけっこうなボリュームになるので、この記事は“関数の不動点”を扱います。“関手の不動点”は続く記事にします（予定）。$`\newcommand{\mrm}[1]{\mathrm{…

…」とします。圏論的な不動点方程式と、不動点方程式によるフリーモナドの構成については「2」で述べます。どこの誰？この記事では、何人か（擬人法）の登場人物が出てきます。それらの登場人物（概念）が“どこの誰”かが分からないと、理解が不明瞭になりがちです。「どこ」とは、概念的事物達の棲息地ですが、集合や関数なら集合圏 $`{\bf Set}`$ に棲んでいます。$`F:{\bf Set} \to {\bf Set}`$ が関手だとすると、この関手は（サイズの制限から）集合圏には居られ…

…点〈要素〉を のプレ不動点〈pre-fixed point〉と呼びます。 自己関手 ： 代数 ＝ 単調作用素 ： プレ不動点 不等式が逆向き だとポスト不動点〈post-fixed point〉を定義します。僕は、プレとポストの区別が憶えられないので、 の縮小点／増大点とかのほうがいいのですが … まっ、憶えましょ。自己関手〈単調作用素〉がモナド〈閉包作用素〉のとき、代数に対する法則（結合法則と単位法則）は可換図式で次のように書けます。 は代数〈プレ不動点〉を定義する不等式で…

…して、解 は関数 の不動点となります。このことから、上の形の方程式は（パラメータ付き）不動点方程式〈{fixed-point | fixpoint} equation〉と呼ばれます。再帰的型がうまく定義できる圏とは、不動点方程式が解ける圏です。カザネスク／ステファネスク／ハイランド／長谷川の定理によると、不動点方程式が解けるデカルト圏はトレース付きデカルト圏〈traced cartesian category〉と同じことになります。このことについては、以下の記事を参照してくだ…

…素〈交代化作用素〉の不動点である。 「関数の平均・偏差-分解と交代化・歪対称性」では、「歪対称性」「交代化作用素」という言葉を使ってましたが、不揃いなので「歪対称性」「歪対称化作用素」にします。「歪対称」「反対称」「交代」は同義なので、何を使おうが好みの問題です。さて、x1 から xp に関して歪対称な(p + 1)変数関数をfを、すべての変数 x0, x1, ..., xp （(p + 1)個）に関して歪対称化することを考えます。fは、p個の変数に関しては歪対称なので、その…

…Fix(P) をPの不動点空間〈fixpoint space〉とも呼びます。射影では、不動点空間と像空間が一致します。w-平均化作用素 Mw の場合、相方となる射影 I - Mw をDwと書きw-偏差作用素〈deviation operator〉と呼ぶことにします。MwとDw は互いに相補的な射影作用素のペアなので、すぐ上の一般論を適用することができます。例えば、b∈Im(Mw) であることを次のように言えます。 bは、Mwの像空間に属する ⇔ bは、なんらかの関数 a のw…