【数学・論理学】演繹定理
公理系と仮定 $P$ から命題 $Q$ の証明ができる(これを$P\vdash Q$ で表す)とき、「 $Q$ は $P$ の演繹である」「 $Q$ は $P$ から演繹可能である」という。
これについてエルブランによる次の演繹定理が成り立つ:
$P\vdash Q$ ならば、 $\vdash P\rightarrow Q$
証明は演繹の長さの帰納法でできる。
$P\vdash\lnot\lnot P$を例としてみていく。まずは証明図を書く。
\begin{align*} \text{公理}&:P\rightarrow(\lnot P\rightarrow P)\\ \text{仮定}&:P\\ \text{推論}&:\lnot P\rightarrow P\\ \text{公理}&:\lnot P\rightarrow\lnot P\lor P\\ \text{公理}&:(\lnot P\rightarrow\lnot P\lor P)\rightarrow[(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)]\\ \text{推論}&:(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)\\ \text{公理}&:\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P)\\ \text{推論}&:\lnot P\rightarrow\lnot P\\ \text{公理}&:(\lnot P\rightarrow P)\rightarrow[(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P]\\ \text{推論}&:(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P\\ \text{推論}&:\lnot\lnot P \end{align*}
$\lnot\lnot P$ は 証明図で前にある $$\lnot P\rightarrow\lnot P$$ と $$(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P$$ から推論された。前にあるから、
$$P\vdash\lnot P\rightarrow\lnot P,\;P\vdash(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P$$
である。
$$P\rightarrow\color{red}{(\lnot P\rightarrow\lnot P)},\;P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P})$$
が証明できるなら、三段論法
$$(A\rightarrow\color{red}{B})\rightarrow[(A\rightarrow(\color{red}{B}\rightarrow\color{blue}{C}))\rightarrow(A\rightarrow\color{blue}{C})]$$
が公理にあるから、 $$P\rightarrow\color{blue}{\lnot\lnot P}$$ も証明できる。
$$P\rightarrow\color{red}{(\lnot P\rightarrow\lnot P)}$$ については、 $$\color{green}{\lnot P\rightarrow\lnot P}$$ が証明できるから、公理
$$\color{green}{A}\rightarrow(B\rightarrow\color{green}{A})$$
を使えば、証明できる。
$$P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P})$$ については、証明図をみると、 $$\lnot P\rightarrow P$$ と公理 $$(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)$$ から、 $$(\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P$$ が推論されている。 よって、同様に、 $$P\rightarrow(\lnot P\rightarrow P)$$ と $$P\rightarrow[(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)]$$ が証明できればよい。 前者は公理だから証明できて、後者は $P\rightarrow(\text{公理})$ の形だから、 公理 $$\color{green}{[(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)]}\rightarrow(P\rightarrow\color{green}{[(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)]})$$ を使えば、証明できる。
以上の準備をまとめると、 $$P\rightarrow\lnot\lnot P$$ の証明図は次のようになる。
\begin{align*} \text{公理}&:\lnot P\rightarrow\lnot P\lor P\\ \text{公理}&:(\lnot P\rightarrow\lnot P\lor P)\rightarrow[(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)]\\ \text{推論}&:(\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P))\rightarrow(\lnot P\rightarrow\lnot P)\\ \text{公理}&:\lnot P\rightarrow(\lnot P\lor P\rightarrow\lnot P)\\ \text{推論}&:\lnot P\rightarrow\lnot P\\ \text{公理}&:\color{green}{\lnot P\rightarrow\lnot P}\rightarrow(P\rightarrow\color{green}{\lnot P\rightarrow\lnot P})\\ \text{推論}&:P\rightarrow(\lnot P\rightarrow\lnot P)\cdots(1)\\ \text{公理}&:P\rightarrow(\lnot P\rightarrow P)\cdots(2)\\ \text{公理}&:(\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)\cdots(3)\\ \text{公理}&:(P\rightarrow\color{red}{\lnot P\rightarrow P})\rightarrow[(P\rightarrow(\color{red}{(\lnot P\rightarrow P)}\rightarrow\color{blue}{((\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)}) )\rightarrow(P\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)})]\cdots(4)\\ \text{推論(2)(4)}&:[(P\rightarrow(\color{red}{(\lnot P\rightarrow P)}\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)}) )\rightarrow(P\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)})]\cdots(5)\\ \text{公理}&:\color{green}{( (\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P) )}\rightarrow[P\rightarrow\color{green}{( (\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P) )}]\cdots(6)\\ \text{推論(3)(6)}&:P\rightarrow\color{green}{( (\lnot P\rightarrow P)\rightarrow( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P) )}\cdots(7)\\ \text{推論(5)(7)}&:P\rightarrow\color{blue}{( (\lnot P\rightarrow\lnot P)\rightarrow\lnot\lnot P)})\cdots(8)\\ \text{公理}&:(P\rightarrow\color{red}{(\lnot P\rightarrow\lnot P) })\rightarrow[(P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P}) )\rightarrow(P\rightarrow\color{blue}{\lnot\lnot P})]\cdots(9)\\ \text{推論(1)(9)}&:(P\rightarrow(\color{red}{(\lnot P\rightarrow\lnot P)}\rightarrow\color{blue}{\lnot\lnot P}) )\rightarrow(P\rightarrow\color{blue}{\lnot\lnot P})\cdots(10)\\ \text{推論(8)(10)}&:P\rightarrow\lnot\lnot P \end{align*}
【数学・論理学】$\lnot(P\lor Q)\vdash\lnot P\land\lnot Q$ の形式証明
ただの備忘録。命題論理のある体系での形式証明。 \begin{align*} \text{公理}&:P\rightarrow P\lor Q\\ \text{公理}&:\lnot(P\lor Q)\rightarrow(P\rightarrow\lnot(P\lor Q))\\ \text{仮定}&:\lnot(P\lor Q)\\ \text{2,3行からの推論}&:P\rightarrow\lnot(P\lor Q)\\ \text{公理}&:(P\rightarrow P\lor Q)\rightarrow( (P\rightarrow\lnot(P\lor Q) )\rightarrow\lnot P)\\ \text{1,5行からの推論}&:(P\rightarrow\lnot(P\lor Q) )\rightarrow\lnot P\\ \text{4,6行からの推論}&:\lnot P\\ \text{公理}&:Q\rightarrow P\lor Q\\ \text{公理}&:\lnot(P\lor Q)\rightarrow(Q\rightarrow\lnot(P\lor Q))\\ \text{3,9行からの推論}&:Q\rightarrow\lnot(P\lor Q)\\ \text{公理}&:(Q\rightarrow P\lor Q)\rightarrow( (Q\rightarrow\lnot(P\lor Q) )\rightarrow\lnot Q)\\ \text{8,11行からの推論}&:(Q\rightarrow\lnot(P\lor Q) )\rightarrow\lnot Q\\ \text{10,12行からの推論}&:\lnot Q\\ \text{公理}&:\lnot P\rightarrow(\lnot Q\rightarrow\lnot P\land\lnot Q)\\ \text{7,14行からの推論}&:\lnot Q\rightarrow\lnot P\land\lnot Q\\ \text{13,15行からの推論}&:\lnot P\land\lnot Q \end{align*}
【数学】$\Phi_n(x)$ の $\varphi(n)-1$ 次の係数
reisr.hatenablog.com の続きで、$G$の生成元の和を求めます。
皆の投稿 - 原始根の和が0,-1,1のいずれかになることの証明 - 数学博物館 すうじあむ のように包除原理を使って直接求めるのが上手い気がしますが、円分多項式の係数と結びつけたのでその方向で行きます。
まず、 $n(\in\mathbb{N})$ 位の円分多項式の係数を文字でおいて $$\Phi_n(x)=\sum_{i=0}^{\varphi(n)}a_n(i)x^i$$ とします。
$p$ を $n$ の素因数にならない素数とすると、
$$\Phi_{np}(x)=\frac{\Phi_n(x^ p)}{\Phi_n(x)}$$
が成立するので
$$\Phi_n(x)\Phi_{np}(x)=\Phi_n(x^p)$$
が得られます。
両辺の $x^{p\varphi(n)-1}$ の係数(最高次より $1$ 小さい次数の係数)を比較すると
$$a_n(\varphi(n)-1)a_{np}(\varphi(np))+a_n(\varphi(n))a_{np}(\varphi(np)-1)=0$$
です。ここで、円分多項式はモニックより
$$a_n(\varphi(n))=a_{np}(\varphi(np))=1$$
なので、漸化式
$$a_{np}(\varphi(np)-1)=-a_n(\varphi(n)-1)$$
が成立します。
$n$ が相異なる素数の積 $n=p_1p_2\cdots p_r$ とすると、この漸化式から
$$a_n(\varphi(n)-1)=-a_{np_1^{-1}}(\varphi(np_1^{-1})-1)$$ $$=(-1)^2a_{np_1^{-1}p_2^{-1}}(\varphi(np_1^{-1}p_2^{-1})-1)$$ $$=\cdots=(-1)^{r-1}a_p(\varphi(p)-1)=(-1)^{r-1}=-\mu(n)$$
(ただし、 $\mu(n)$ はメビウス関数) したがって、
$$(G\text{の生成元の和 })=-(\Phi_{q-1}(x)\text{の}\varphi(q-1)-1\text{次の係数})=\mu(q-1)$$
【数学】有限体の乗法群と円分多項式の係数
$F_q$を位数$q$の有限体とします。$F_q$の標数を$p$とすれば、ある自然数$f$に対して、 $$q=p^f$$ を満たします。
$G$を$F_q$の乗法群(乗法逆元を持つような元全体からなる群)とすると、$G$の位数は$q-1$になります。
この辺のことは代数学の教科書見れば載っているよく知られた事実です。
$G$の生成元を $$a_1,\dots,a_{\varphi(q-1)}$$ ($\varphi$はオイラー関数)とすると、それらは位数がちょうど$q-1$であるような$F_q$の元なので、$F_q$係数の多項式として $$\prod_{i=1}^{\varphi(q-1)}(x-a_i)=\Phi_{q-1}(x)$$ ($\Phi_n(x)$は$n$位の円分多項式)が成り立ちます。
すると、係数を比較することにより、 $$(G\text{の生成元の和})=-(\Phi_{q-1}(x)\text{の}x^{\varphi(q-1)-1}\text{の係数})$$ が分かります。
ここで、$q-1$が素数の平方で割れる、すなわち、ある素数$l$と自然数$n$に対して、$q-1=l^2n$が成り立つとすると、 $$\Phi_{q-1}(x)=\Phi_{ln}(x^l)$$ となるので(これも円分多項式について載っている代数学の教科書にほぼ載っている)、$\Phi_{q-1}(x)$の$x^{\varphi(q-1)-1}$の係数は$0$になるしかありません。 したがって、この場合$G$の生成元の和は$0$です。
【その他】(アマチュアの)研究に役立ちそうなもの
テキストに載ってない(≒広くは知られていないもしくは知られていない)ような細かいことを知りたいときに使えそうなサイト候補
scholar.google.co.jphttps://scholar.google.co.jp/
論文とか検索できるGoogleの検索エンジン。数学科の大学院だとMathSciNetを論文検索手段として教えられるが、ログインしないと使えない。Google scholarは(少なくとも)検索は誰でもできる
まあ、他の説明はWikipediaかなんかを参照して下さい
ja.m.wikipedia.orghttps://ja.m.wikipedia.org/wiki/Google_Scholar
Math stack exchange
プロ(?)が質問に答えてくれるらしい数学質問サイト。自分が知りたい些細なことに近いことが載ってることもあるからGoogle scholarでヒットしなかったらこっちで質問するのもアリ。英語だけど
【技術】\[tex:とか使わずにtexコマンドで数式かけるように
フッターにhtmlという名の呪文を挿入して, texコマンドで数式書けるようにしてみた
参考にしたのは
1つ留意すべきなのはそれだけではダメで, 一部を差し替えなければいけないこと
お分かりだろうか？
ちなみに、インラインモードだと$で囲むのはいいけど、\(で囲むのはなんかダメっぽい
ディスプレイ表示は$$も\[もどちらもいけるっぽい
ピタゴラス数
ふと、 mizumiya-umi.hatenablog.comを読んで数時間考えてたら、予想が証明できてしまったので、載せます。
$a_1,a_2,b_1,b_2,c_1,c_2\in\mathbb{Z}\setminus{0}$
を
$$a_1^2+b_1^2=c_1^2, a_2^2+b_2^2=c_2^2$$
を満たすものとする.ただし, $2\mid b_1,b_2$
となるように取る.
$$D_1=a_1a_2+b_1b_2,D_2=a_1b_2-a_2b_1$$
とおく.
ピタゴラス数の性質より,
$$\begin{cases} a_1=a_1'^2-b_1'^2,\\ b_1=2a_1'b_1' \end{cases},\quad \begin{cases} a_2=a_2'^2-b_2'^2,\\ b_2=2a_2'b_2' \end{cases}$$
を満たす $a_1',a_2',b_1',b_2'\in\mathbb{Z}$
が取れるから,
$$D_1+D_2i=(a_1-b_1i)(a_2+b_2i)=(a_1'-b_1'i)^2(a_2'+b_2'i)^2$$
となり, $x,y\in\mathbb{Z}$
で
$$x^2-y^2=D_1, 2xy=D_2$$
を満たすものが存在する.
よって,
$$\begin{cases} -D_2^2+4x^4=4x^4-4x^2y^2=4D_1x^2,\\ D_2^2-y^4=4x^2y^2-y^4=4D_1y^2 \end{cases}$$
$$\therefore x^2=\frac{D_1\pm\sqrt{D_1^2+D_2^2}}{2}, y^2=\frac{-D_1\pm\sqrt{D_1^2+D_2^2}}{2}$$
ここで,
$$2x^2-D_1=x^2+y^2, 2y^2+D_1=x^2+y^2$$
であるから, 根号の前は正符号であり,
$$x^2=\frac{D_1+\sqrt{D_1^2+D_2^2}}{2}, y^2=\frac{-D_1+\sqrt{D_1^2+D_2^2}}{2}$$
となる.
一方, $c_1^2c_2^2=(a_1^2+b_1^2)(a_2^2+b_2^2)=D_1^2+D_2^2=(x^2-y^2)^2+(2xy)^2=(x^2+y^2)^2$
より, $c_1c_2=x^2+y^2$
であるから,
$$\frac{a_1a_2+b_1b_2-c_1c_2}{2}=\frac{D_1-(x^2+y^2)}{2}=\frac{(x^2-y^2)-(x^2+y^2)}{2}=-y^2$$
したがって,
\begin{align*} \left(\frac{a_1+a_2}{2}\right)^2+\left(\frac{b_1+b_2}{2}\right)^2+y^2 &=\frac{a_1^2+b_1^2+a_2^2+b_2^2+2a_1a_2+2b_1b_2}{4}+\frac{-a_1a_2-b_1b_2+c_1c_2}{2}\\ &=\frac{c_1^2+c_2^2+2c_1c_2}{4}\\ &=\left(\frac{c_1+c_2}{2}\right)^2 \end{align*}
