内容はACA $_0$ でのRameyの定理の証明です． Prehomogeneous setを取る際に，よく知られたErdös/Radó treeを使う方法ではなく，超フィルターを使った証明の形式化を与えました． Ramsey型の定理で超フィルターが有効に働くのは，無限集合有限個の共通部分が再び無限集合となるように扱えるからですが， Ramseyの定理を証明する際にはその部分の議論をRT $^1$ で代用できる，というのが基本的な議論です．

drive.google.com

2020-12-07

Hessianを計算するのがめんどくさかった話

この記事は

日曜数学 Advent Calendar 2020 - Adventar 7日目の記事です

前日の6日目はmath_Kantenさんによる一風変わった切り口の記事でとても面白かったです．

導入

突然ですが，次のような問題を考えてみましょう：

関数 $f(x,y) = \frac{xy}{x^4+y^4+2}$ について， $(x,y)$ が平面全体を動く時の極値をすべて求めよ．

いかにも偏微分を習いたての頃に演習問題で出てきそうな趣の問題です．

この問題を考える時，まず有用なのが次の事実です：

(十分滑らかで，平面全体を定義域とする)関数 $f(x,y)$ について， $f(a,b)$ が極値となるとすると， $f_x(a,b) = f_y(a,b) = 0$ である．

さて，上の事実を逆に言えば *1 極値を考える時は $f_x(a,b) = f_y(a,b) = 0$ となるような場所だけを考えれば良いということになります．というわけでまずは一階偏導関数を求めてみましょう．ちょっと計算が大変ですが，この程度なら気合いでなんとかなります．計算結果は次のようになります:

$f_x = \frac{y(-3x^4 + y^4 + 2)}{(x^4+y^4+2)^2},f_y = \frac{x(-3y^4 + x^4 + 2)}{(x^4+y^4+2)^2}$

ここから $f_x = f_y = 0$ となる点を求めると， $(0,0),(1,1),(1,-1),(-1,1),(-1,-1)$ の五つであることがわかります．

Hessian

したがって，あとは上の五つの点がそれぞれ極値を与えるか否かを考えれば良いことになります．このうち $(0,0)$ については，付近での $f$ の符号を考えれば極値になり得ないことがすぐにわかります．残りの4点について考える上で，よく知られた次の事実は有用そうです：

(十分滑らかで，平面全体を定義域とする)関数 $f(x,y)$ について， $f_x(a,b)= f_y(a,b) = 0$ であるとする．このとき $(f_{xx}f_{yy} - (f_{xy})^2)(a,b) \gt 0$ であれば $f(a,b)$ は極値であり $(f_{xx}f_{yy} - (f_{xy})^2)(a,b) \lt 0$ であれば $f(a,b)$ は極値でない．

この $(f_{xx}f_{yy} - (f_{xy})^2)$ にはHessianという名前がついています．上記の通り関数の極値を求める上で有用なものですが，いかんせん今回の場合は計算がめんどくさい！上で求めた一階微分の式からも容易に想像がつく通り，今回の $f$ の二階微分を求めるのは計算量が多くなかなか大変です．そこでできればもっと単純な方法で求めたい，というのが今回の記事の主旨になります．

(多変数版)最大値原理

とりあえず残りの4点について $f$ による値を計算してみると，それぞれ $f(1,1) = f(-1,-1) = \frac{1}{4} , f(-1,1) = f(1,-1) = -\frac{1}{4}$ となることがわかります．また $f$ をググッと睨むと $\lim_{x^2+y^2 \to \infty}f(x,y) = 0$ であることもわかります．したがって，十分大きい $R \gt 2$ をとると， $x^2 + y^2 \geq R$ のとき $|f(x,y)| \lt \frac{1}{4}$ となります．ところで，次の多変数版最大値原理を考えれば， $f$ は $x^2 + y^2 \leq R$ での最大値，最小値を持つがわかります．

$f(x_1,\ldots,x_n)$ を連続関数として， $R>0$ とする．このとき $f$ は $x_1^2+ \cdots + x_n^2 \leq R$ 上での最大値，最小値を持つ．

(これが1変数の最大値原理(連続関数は閉区間上での最大値，最小値を持つ)の自然な拡張であることはすぐにわかると思います)

ところで， $(1,1)$ や $(-1,1)$ は $x^2 + y^2 \leq R$ を満たすため， $f$ の $x^2 + y^2 \leq R$ での最大値は $f(1,1) = \frac{1}{4}$ 以上，最小値は $f(-1,1) = -\frac{1}{4}$ 以下となることがわかります．したがって $R$ の定義から $x^2 + y^2 = R$ となる点では $x^2 + y^2 \leq R$ での最大値や最小値を与える点は存在しません．すると $f$ は $x^2 + y^2 \lt R$ での最大値,最小値を持つことになります．すぐわかることとして，この範囲での最大値最小値は $f$ の微分零点によって与えられます．すなわち， $f$ の $x^2 + y^2 \leq R$ での最大値最小値は $f(1,1),f(-1,1),f(1,-1),f(-1,-1)$ の中に存在することになります．つまり， $f$ の $x^2 + y^2 \leq R$ での最大値は $f(1,1) = f(-1,-1) = \frac{1}{4}$ ，最小値は $f(-1,1) = f(1,-1) = -\frac{1}{4}$ となります．ところで $R$ の取り方からこれは平面全体での $f$ の最大値，最小値をそれぞれ与えることもすぐわかります．最大値は極大値であり最小値は極小値であることから，当初の問題の答えは以下のようになります．

$f$ は極大値 $f(1,1) = f(-1,-1) = \frac{1}{4}$ ，極小値 $f(-1,1) = f(1,-1) = -\frac{1}{4}$ を持つ．

以上のようにして面倒な微分を計算することなく極大値極小値を求めることができました．

おまけ

上記の議論は次のような形で一般化することができます．

連続関数 $f(x_1,\ldots,x_n)$ は， $\lim_{x_1^2 + \cdots x_n^2 \to \infty} f(x_1,\ldots,x_n )= 0$ を満たすとする．このとき 1. ある点で $f$ が正となるとき $f$ は最大値を持ち， 2. ある点で $f$ が負となるとき $f$ は最小値を持つ．

*1:この場合の逆に言えばは日常語であって，論理的な意味での逆向きのimplicationの意味ではありません．対偶を取れば，という方がいいかも…

2020-12-06

ACA_0とATR_0の間の体系について

この記事は Mathematical Logic Advent Calendar2020(https://adventar.org/calendars/5002)の6日目の記事です．

概要

二階算術の部分体系では，ビッグ5と呼ばれる五つの体系( $\text{RCA}_0,\text{WKL}_0,\text{ACA}_0,\text{ATR}_0,\Pi^1_1\text{-CA}_0$ )がよく扱われます．昨年の記事二階算術の諸体系のモデル - お勉強の記録ではこれらについて述べたので，本記事ではビッグ5以外の体系について述べたいと思います．その中でも特に $\text{ACA}_0$ と $\text{ATR}_0$ の間にある二つの体系， $\text{ACA}_0'$ と $\text{ACA}_0^+$ について解説します．

$\text{ACA}_0$ と $\text{ATR}_0$

$\text{ACA}_0$ は，任意の(集合パラメータありの)算術的論理式 $\varphi(n)$ に対して，集合 $\{n: \varphi(n)\}$ が存在する(算術的内包公理)という体系でした．一方 $\text{ATR}_0$ は，この操作を任意の(可算)順序数に沿って行える，というものでした．もう少しフォーマルに述べると， $\text{ATR}_0$ では任意の順序数 $\alpha$ と任意の算術的論理式 $\varphi(n,X)$ に対して，次のようにして集合族 $\{A_\beta:\beta \lt \alpha\}$ を定義することができます：

$A_0 = \{n:\varphi(n,\varnothing)\}$

$A_\beta = \{n:\varphi(n,A_{\lt \beta})\}$

ここで， $A_{\lt \beta}$ は $\{(n,\gamma) : \gamma \lt \beta, n \in A_\gamma\}$ という集合で，今まで定義された $A_\gamma$ たちの情報をすべて持っているような集合になります．

$\text{ACA}_0'$ と $\text{ACA}_0^+$

$\text{ATR}_0$ の例からもわかるように，算術的内包公理を繰り返すことでより複雑な集合を作ることができるようになります．そこで算術的内包公理の繰り返しにより体系を複雑化させることを考えたいのですが，まず $\text{ACA}_0$ でどの程度の繰り返しができるかを考えてみましょう．すると，任意の標準自然数 $k \in \omega$ に対しては $k$ 回の繰り返しができることがわかります(つまり，上の $\text{ATR}_0$ の説明で $\alpha = k$ の場合は $\text{ACA}_0$ でも証明できます)．ところが，これより少し複雑な，「任意の有限順序数 $k \in \mathbb{N}$ に対して $k$ 回の繰り返し」は $\text{ACA}_0$ では一般にできません．この $\text{ACA}_0$ に「任意の有限順序数 $k \in \mathbb{N}$ に対して $k$ 回算術的内包公理を繰り返せる」という公理を付け加えた体系を $\text{ACA}_0'$ と呼びます．そして， $\text{ACA}_0'$ より強い体系として，「最小の無限順序数( $\mathbb{N}$ の順序型)回」の繰り返し」を認める体系を $\text{ACA}_0^+$ と言います．

体系たちの強さ

定義から明らかに $\text{ACA}_0 \leq \text{ACA}_0' \leq \text{ACA}_0^+ \leq \text{ATR}_0$ となることがわかりますが，これらの不等号はすべて真の不等号になります．

定理： $\text{ACA}_0 \lt \text{ACA}_0'$

(証明) 任意にPAの超準モデル $M$ を取る． $\text{ARITH}^M$ を $M$ で集合パラメータなしの算術的論理式で定義できる集合全体とすると， $(M,\text{ARITH}^M)$ は $\text{ACA}_0$ のモデルだが $\text{ACA}_0'$ のモデルではない．

系： $\text{ACA}_0 \not \vdash \Sigma^1_1帰納法$

(証明) $\text{ACA}_0 + \Sigma^1_1帰納法 \vdash \text{ACA}_0'$ より明らか．

定理： $\text{ACA}_0' \lt \text{ACA}_0^+$

(証明) 明らかに $\omega$ モデルにおいては $\text{ACA}_0'$ と $\text{ACA}_0$ に違いはなく，したがって $\omega$ 上で算術的パラメータなしで定義できる集合の全体ARITHは $\text{ACA}_0'$ のモデルである．一方でこれは $\text{ACA}_0^+$ のモデルではない．

定理： $\text{ACA}_0^+ \lt \text{ATR}_0$

(証明) $\{ A \subseteq \omega: A \leq_T \emptyset^{(\omega\cdot n)} \text{ for some } n\}$ は $:\text{ACA}_0'^+$ のモデルだが $\text{ATR}_0$ のモデルでない．

おまけ

以上のように，算術的内包公理の繰り返し回数を適当に制限することによって $\text{ACA}_0$ と $\text{ATR}_0$ の間に様々な体系を作ることができます．このような形で作られる体系は，他にもあり，例えば繰り返しの回数を原始再帰的順序数に制限した $\text{ATR}_0^J$ などが知られています．