2022-12-24

左逆行列と右逆行列の一致

線形代数数学

こんにちは．simulo(simulo (@simulo_) / Twitter)です．

今日はほぼすべての理系大学生が学ぶ，線形代数の基礎の基礎である逆行列に関する記事です．

逆行列の定義は，以下のものです．

$A$ を体 $\mathbf{K}$ 上の $n\times n$ 行列であるとする．この時，ある $\mathbf{K}$ 上の $n\times n$ 行列 $B$ について， \begin{align} AB=BA=E_n \end{align} をみたすなら， $B$ は $A$ の逆行列であるという．

この定義を素直に受け入れると， $AB=E_n$ だからといって $B$ は $A$ の逆行列とは限らないでしょう．なぜならば， $AB=E_n$ であるときに $BA=E_n$ である，というのは正しいかどうかわからないし，仮に正しかったとしても(数が並んだ行列の見方をする限りは)自明ではないからです．しかし， $AB=E_n$ なら $B$ は $A$ の逆行列である，という議論を疑問に思うことなくしてきた方が多いのではないでしょうか． $AB=E_n$ あるいは $BA=E_n$ ならば $B$ は $A$ の逆行列であるということは事実であるので，何気なくしてきた議論自体に問題はありません．多くのインターネット上の線形代数の資料や(少なくとも自分が受けた)大学での授業では，自明ではないこの重要な事実は証明されない，あるいは触れられすらしない傾向にあります．この記事では，その証明をします．

基本変形・基本行列

まず，行基本変形や列基本変形について復習しましょう．証明に使います．

まず，行基本変形とは $m\times n$ 行列に対し，

$i$ 行目の $c$ 倍を $j$ 行目に加えること $(i\neq j)$
$i$ 行目と $j$ 行目を入れ替えること $(i\neq j)$
$i$ 行目を $c \neq 0$ 倍すること

のいずれかを言います．

同様に，列基本変形とは $m\times n$ 行列に対し，

$i$ 列目の $c$ 倍を $j$ 列目に加えること $(i\neq j)$
$i$ 列目と $j$ 列目を入れ替えること $(i\neq j)$
$i$ 列目を $c \neq 0$ 倍すること

のいずれかを言います．

このように定義したとき，行基本変形の1から3の操作はそれぞれ，行列に左から \begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 0 & \cdots& 1& & \\ & & \vdots& \ddots &\vdots & & \\ & & 1& \cdots& 0 & & \\ & & & & & \ddots&\\ & & & & & & 1 \end{pmatrix} \begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & & & & \\ & & \vdots& \ddots & & & \\ & & c& \cdots& 1 & & \\ & & & & & \ddots&\\ & & & & & & 1 \end{pmatrix} \begin{pmatrix} 1 & & & & & \\ & 1 & & & & \\ & & \ddots & & & \\ & & & c & & \\ & & & & \ddots & \\ & & & & &1 \end{pmatrix} をかけることと同じです(実際に計算するとわかる)．数字が書いていない要素は全て0です．ただし，1つ目の行列は $(i,i),(j,j)$ 番目の要素が $0$ で $(i,j),(j,i)$ 番目の要素が $1$ ，2つ目の行列は $(j,i)$ 番目の要素が $c$ ，3つ目の行列は $(i,i)$ 番目の要素が $c$ であるような行列です．これらには逆行列が存在し， \begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 0 & \cdots& 1& & \\ & & \vdots& \ddots &\vdots & & \\ & & 1& \cdots& 0 & & \\ & & & & & \ddots&\\ & & & & & & 1 \end{pmatrix} \begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & & & & \\ & & \vdots& \ddots & & & \\ & & -c& \cdots& 1 & & \\ & & & & & \ddots&\\ & & & & & & 1 \end{pmatrix} \begin{pmatrix} 1 & & & & & \\ & 1 & & & & \\ & & \ddots & & & \\ & & & c^{-1} & & \\ & & & & \ddots & \\ & & & & &1 \end{pmatrix} です．実際に左右から掛けてみるとわかります．

列基本変形も同様に特定の形の行列を右からかけることに対応していて，それらの行列には逆行列が存在しています．これらの行列を基本行列とよび，基本行列は正則行列(逆行列が存在する行列)であることを示したわけです．

証明

証明に取り掛かる前に，右逆行列，左逆行列という言葉を定義します．

定義
$A$ を体 $\mathbf{K}$ 上の $n\times n$ 行列であるとする．この時，ある $\mathbf{K}$ 上の $n\times n$ 行列 $B$ について， \begin{align} AB=E_n \end{align} をみたすなら， $B$ は $A$ の右逆行列であるという．また， \begin{align} BA=E_n \end{align} をみたすなら， $B$ は $A$ の左逆行列であるという．

すると，示すべき事実は， $A,B$ を $n\times n$ の正方行列としたときに,

$B$ が $A$ の右逆行列 $\,\, \Leftrightarrow\,\,$ $B$ が $A$ の左逆行列

が成立することであることがわかるでしょう． $\Rightarrow$ さえ示せれば逆は同様に示せるので， $\Rightarrow$ のみ示します．以下，証明の間は常体で日本語を表記します．

$n$ に関する帰納法で示す． $n=1$ のときは明らかに成立している．以下， $n>1$ とすると， $A$ は基本変形を繰り返すことによって, \begin{align} C=\begin{pmatrix} 1&{}^to\\ o&A_1 \end{pmatrix} \end{align} という形になる．つまり，基本行列の積で表される $P,Q$ を用いて， $PAQ=C$ となる．ここで， $P,Q$ は正則行列である基本行列の積であるので，また正則である．ここで， $D=Q^{-1}BP^{-1}$ とし， \begin{align} D=\begin{pmatrix} u& {}^tz\\ y&B_1 \end{pmatrix} \end{align} と表す．このとき， $CD=(PAQ)(Q^{-1}BP^{-1})=PABP^{-1}=PP^{-1}=E_n$ で， \begin{align} E_n=\begin{pmatrix} 1& {}^to\\ o&E_{n-1} \end{pmatrix} \end{align} \begin{align} E_n=CD=\begin{pmatrix} u& {}^tz\\ A_1y&A_1B_1 \end{pmatrix} \end{align} よって，帰納法の仮定より， $A_1$ は正則で， $A_1B_1=B_1A_1=E_{n-1}$ である，また， $z=o$ と， $y=o\ (\because A_1$ は正則 $)$ もわかり， \begin{align} D=\begin{pmatrix} 1& {}^to\\ o&B_1 \end{pmatrix} \end{align} で， $CD=DC=E_n$ がわかる．よって， $C$ は正則で， $A=P^{-1}CQ^{-1}$ も正則である．

注意

左逆行列と右逆行列が一致することを以上のように証明できました．行列の要素が体の元である限りはこの事実は成り立つのですが，行列の要素が非可換環だと一般には左逆行列と右逆行列は一致しないようです．

2021-07-15

有理数のmodを駆使して数オリの有名整数問題を解く

数学整数論数オリ

こんばんは、simulo_yuiです。

simulo_yui (@simulo_yui) | Twitter

今回は、有理数のmodに関する記事です。合同式の基本的な知識を前提にします。合同式をご存じでない方は下の記事をご覧ください。

問題
一般的な解答
解説
Fermatの小定理について
有理数のmodについて
問題への適用
終わりに

問題

数列 $a_n$ を $a_n=2^n+3^n+6^n-1$ で定義する。このとき、 $a_n$ の全ての項と互いに素となるような自然数を全て求めよ。(IMO 2005 problem 4)

一般的な解答

$p$ を $2$ と $3$ 以外の素数とする。以下、法は明記されない限り $p$ とする。

ここで、 $2^{p-2} + 3^{p-2} + 6^{p-2}\equiv 1$ を示す。

(i) $p \equiv 1 \mod 6$ のとき

Fermatの小定理より、 $2^{p-1}\equiv 3^{p-1}\equiv 6^{p-1}\equiv 1$ である。 $2*2^{p-2}\equiv 1$ を解き、 $2^{p-2}\equiv \frac{p+1}{2}$ である。
同様に、
$3^{p-2}\equiv \frac{2p+1}{3}$
$6^{p-2}\equiv \frac{5p+1}{6}$
であり、

$2^{p-2} + 3^{p-2} + 6^{p-2}\equiv \frac{p+1}{2} + \frac{2p+1}{3} + \frac{5p+1}{6} \equiv 2p + 1 \equiv 1$
が確かに成立する。

(ii) $p \equiv 5 \mod 6$ のとき

(i)と同様に、 $2^{p-2} + 3^{p-2} + 6^{p-2}\equiv \frac{p+1}{2} + \frac{p+1}{3} + \frac{p+1}{6} \equiv p + 1 \equiv 1$

$p$ は $2,3$ を除く素数であるので、(i),(ii)の場合で尽くされている。よって、 $a_{p-2}\equiv0$ が $2,3$ を除くすべての素数 $p$ で成り立ち、 $a_1=10\equiv 0 \mod 2, a_2=48 \equiv 0 \mod 3$ より、全ての素数について、それと互いに素でない項が存在する。つまり、 $2$ 以上の全ての整数についても同様にそれと互いに素でない項が存在する。
また、 $1$ については、全ての整数と互いに素なので、要件を満たす。よって、求める自然数は、 $1$ のみである。

解説

まず、多くの素数についてそれと互いに素でない $a_n$ の項が存在するならば、それらを素因数に持つ全ての整数もその項と互いに素ではない上、素数は扱いやすい様々ないい性質を持つので、素数のみについて考えようと思うのは自然でしょう。つまり、素数 $p$ と互いに素でない項の存在を具体的な構成をするなりして示せばいいのです。すると、整数の $n$ 乗と素数 $p$ に関する問題に変わるので、似た形である、Fermatの小定理を使いたくなるのは自然でしょう。でもなぜ、 $p-1$ 乗でなく、 $p-2$ 乗を考えるのでしょうか。

ある人は、様々な素数 $p$ で試していった結果 $p-2$ 乗でうまくいくことに気づくのだ、というのかもしれません。実際、試験でこの問題が出てきたのならば、それが一番現実的でしょう。しかし、何か理由を考えたくなるのが、数学が好きな人の定めではないでしょうか。考えていきましょう。

Fermatの小定理について

ご存じの方はこの項を読み飛ばしていただいて結構です。
Fermatの小定理とは以下のようなものです。

Fermatの小定理

$p$ を素数、 $a$ を $p$ と互いに素な数とすると、
$a^{p-1}\equiv 1 \mod p - (1)$ が成立する。

簡単な証明をします。

一般に、 $n$ を自然数とするとき、 $a \equiv b \mod p \Rightarrow a^n \equiv b^n \mod p$ なので、 $1 \leq a \leq p-1$ の場合を考える。

$1\leq k \leq p-1$ について、 ${}_p C_k=\frac{p!}{(p-k)!k!}\equiv 0 \mod p$
$(\because 分子はpの倍数、分母はpの倍数でない)$
なので、 $a^p=((a-1)+1)^n=\sum_{k=0}^p {}_{p}C_{k} (a-1)^k\equiv (a-1)^p+1 \mod p$ であり、これを繰り返し用いて、 $a^p\equiv (a-1)^p+1\equiv (a-2)^p+1+1=\cdots \equiv a \mod p$ であり、 $a$ と $p$ は互いに素なので、最左辺と最右辺を $a$ で割ると $(1)$ が得られる。証明終。

有理数のmodについて

合同式の概念は整数の世界で導入され、整数の合同式をご存じの方は多いと思います。実は、合同式は有理数の世界にも拡張できるのです。具体的には、

$n$ を整数として、有理数 $r$ が、 $r=\frac{a}{b}$ と $a,b \in \mathbb{Z}, \gcd (a,b) = 1, \gcd (b,n)=1$ を満たす $a,b$ を用いて表されるとき、 $bc\equiv a \mod n$ をみたす $c \in \mathbb{Z}$ を以て、 $r \equiv c \mod n$ と定義されます。

つまり、既約分数の形で表したとき、分母が $n$ と互いに素になる有理数について、合同式が定義されました。このような $c$ が合同な数を除いて一意に存在することは簡単に示せます。

このように定義された有理数のmodにおいても、整数の世界で成り立つ合同室の性質、つまり、法を $n$ 、 $a,b,c,d$ を定義に出てきた条件を満たす有理数として、
$a \equiv c \land b \equiv d \Rightarrow a+b \land c +d$
$a \equiv c \land b \equiv d \Rightarrow a-b \land c -d$
$a \equiv c \land b \equiv d \Rightarrow ab \land c d$
$m$ を $n$ と互いに素な整数とするとき、 $a\equiv b \Rightarrow \frac{a}{m} \equiv \frac{b}{m}$
$a \equiv b \Rightarrow a^m \equiv b^m$
$f(x)$ を整数、または分母がnと互いに素な係数をもつ多項式とするとき、 $a \equiv b \Rightarrow f(a) \equiv f(b)$
などといった性質がなりたちます。これは簡単に証明できます。

また、参考として、分母が $n$ と互いに素でない有理数に拡張してしまうと次のような問題が生じることも書いておきます。その問題というのは、上の定義で、 $b$ が $n$ と互いに素でないとき、 $bc\equiv a \mod n$ となるような $c$ が一般には存在しないことです。 $a=1,b=2,n=4$ などとすると、分かると思います。 $b$ と $n$ が互いに素でないとき、 $\mod n$ の世界では $b$ は $0$ の要素(= $n$ の素因数)を含んでいるから、こんな不都合が生じる、という感覚的な説明もできます。

問題への適用

先程の問題に有理数のmodを適用してみましょう。
フェルマーの小定理より、 $a^{p-1}\equiv 1 \mod p$ より、 $a^{p-2}\equiv \frac{1}{a} \mod p$ が成立します。すると、 $a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1=0 \mod p$ となります。この式を見ると、なぜ $p-2$ 乗を考えるのか、なんとなくわかった気になりませんか？つまり、 $a_n$ の式に $n=-1$ を代入すると、 $a_{-1}=0$ になることに気づくので、 $\mod p$ の世界でも逆元(=かけて $1$ になるもの。ここでは $2$ に対する $\frac{1}{2}$ )である、 $p-2$ 乗を考えよう、というモチベーションがあったのです。

こうやって書くと、何だか数オリの問題が可愛く見えますね。とても可愛い。綺麗でかわいいなんて最高ですね。

終わりに

誤りなどありましたら教えてください。
こうやって記事を書き終わってみると、この問題の作問者はきっと、小学生でも知っている $\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1$ という等式をどれだけドラマチックなものに昇華できるかを考えていたんじゃないかな、と思います。最後に、改悪した問題を貼って記事を終わりにします。

冒頭の問題の $a_n$ を $a_n=2^n+4^n+7^n+14^n+28^n-1$ と定義して、 $a_n$ の全ての項と互いに素となるような自然数を全て求めよ。
Hint(なのか？):6も28も嬉しい性質が成り立っているので、この問題はうまくいきます。

2021-07-10

サイクロイドと等積変形～カヴァリエリの原理の面白い応用～

数学

こんばんは、simulo_yuiです。

simulo_yui (@simulo_yui) | Twitter

現在の日本の学習指導要領では数Ⅲで学ぶことになっているサイクロイド。最速降下曲線(スロープのようにしたときに一番早くボールが下りてくる曲線)であることや、その等時性などさまざまな面白い性質を持っています。数Ⅲを学習したことがある方なら、その長さや、サイクロイドとx軸で囲まれる面積をいやというほど計算した記憶があるのではないでしょうか。今回はそんなサイクロイドとx軸で囲まれる面積を数Ⅲを使わずとも中学生でも出すことができる、というお話です。

サイクロイドとは？

サイクロイドとは円が直線上を滑らずに転がるときに、直線と接していた円上の点がまた直線と接するまでに動く軌跡のことを言います。口で説明するよりも下の図を見てもらった方が理解が早いと思います。

f:id:cute_1iYui:20210710154922g:plain

上の図では半径1の円が転がっています。中心 $O'$ が $(t,1)(t \in \mathbb{R}, 0 \leq t \leq 2\pi)$ にあるとき、点 $P$ の座標は以下のようにパラメータ表示されます。

$P(t-\sin t,1 - \cos t)$

サイクロイドとx軸で囲まれる部分の面積

f:id:cute_1iYui:20210710154955p:plain

ここで、サイクロイドとx軸で囲まれる部分の面積、すなわち上の図の赤線部の面積 $S$ を考えると、パラメータ表示を利用して、

$S =\int^{2 \pi}_0 y dx = \int^{2 \pi}_0 y \frac{dx}{dt} dt = \int^{2 \pi}_0 (1-\cos t)^2 dt =3\pi$

となり、求める面積は $3\pi$ であったことが分かる。

カヴァリエリの原理を用いて面積を求める

f:id:cute_1iYui:20210710155004p:plain

上の図の横線部の面積 $T$ を考えます。真ん中の円の面積は $\pi$ なので、 $S=3\pi$ を示すには、 $T=\pi$ になることを示せばよさそうです。。

真ん中の円の中心を $O'$ 、円上の点で $O'M$ がx軸と平行になるような点を $M$ とし、 $\angle AOM=\angle BOM = \theta (0 \leq \theta \leq \frac{\pi}{2})$ となるような円上の点 $A,B$ をとり、サイクロイド上の点 $P,Q$ を $AP \parallel BQ \parallel x軸$ となろようにとり、 $C(\pi,0),O(0,0)$ とします。

f:id:cute_1iYui:20210710155020p:plain

このとき、 $AP+BQ=OC=\pi \qquad \cdots (1)$ が成立しています！

今からこれを示します。

f:id:cute_1iYui:20210710155024p:plain

上の図のように、動円が $P$ を通るときの中心を $O''$ すると、 $AP=O'O''$

が成立しています。ここで、動円が円 $O''$ の位置から円 $O'$ の位置に動くまでには、円は $\frac{\pi}{2}+\theta$ 回転しているので、 $O'O''$ は、円の中心角が $\frac{\pi}{2}+\theta$ の弧の長さに等しく、 $O'O''=\frac{\pi}{2}+\theta$ で、 $AP=\frac{\pi}{2}+\theta$ である。

同様に、 $BQ=\frac{\pi}{2}-\theta$ となる。よって、 $AP+BQ=(\frac{\pi}{2}+\theta)+(\frac{\pi}{2}-\theta)=\pi$ で $(1)$ が確かに成立します。

ここで、面積 $T$ を求めるために次のような操作をします。

f:id:cute_1iYui:20210710155029p:plain

$y=1/2$ の線で図形を切り、上の部分を横に持ってきます。操作後の図が下図です。

f:id:cute_1iYui:20210710155039p:plain

そしてこれをカヴァリエリの原理を用いて等積変形すると $(1)$ より、底辺が $\pi$ 高さが $1$ の長方形になります。

f:id:cute_1iYui:20210710155054p:plain

よって、 $T=\pi$ が分かりました。よって、 $S=3\pi$ になることも分かりました。

カヴァリエリの原理について

カヴァリエリの原理とはある2つの立体や平面図形を同じ面で切断した時の面積や長さが常に等しいならば、二つの立体や平面図形の体積や面積は等しいというものです。詳しくはWikipediaを参照してください。

ja.wikipedia.org

2021-03-25

定規のみを用いて与えられた線分に平行な直線を引けるのか？

数学初等幾何

こんばんは、simulo_yuiです。

simulo_yui (@simulo_yui) | Twitter

A. 引けません

これで記事を終わりにすると、とてつもなくつまらないので、もう少しだけお付き合いください。

世の中には定規とコンパスによる作図という概念があります。これについては以下のurlを参照してください。定規とコンパスによる作図 - Wikipedia

この定規とコンパスによる作図、中学生の時にやったことがある方もいらっしゃるのではないでしょうか。正三角形の作図だったり、角の二等分線の作図だったり、垂直二等分線の作図だったり。その作図の要領で、与えられた線分に平行な直線を引けるか？という問題です。この場合、定規は二定点を通る直線を引くことか、あるいは無作為に平面上に直線を引くことにしか使えません。

あるいは、コンパスを使用していいルールだったら、与えられた線分に平行な直線を引く方法を知っている方も多いかも知れません。では、定規しか使えない場合はどうなのでしょうか。この場合、以下の定理が成り立ちます。

定理

定規のみを用いて与えられた線分に平行な直線を引くことはできない。

この定理の証明に移る前に、次の補題の証明をしておきましょう。

補題

平面上に円がすでに与えられているとする。この際、定規のみを用いて円の中心を得ることはできない。

補題の証明

$xy$ 平面で考える。平面上に与えられている円を $C$ とする。以下の条件を満たす、 $P$ から $P$ への射影 $T$ を考える。

(1)直線を直線に移す

(2)円 $C$ を円 $C'$ に移す。

(3)円 $C$ の中心 $O$ を、円 $C'$ の中心 $O'$ に移さない。

このような $T$ が確かに存在すると仮定する。さらに、平面上に円がすでに与えられているとき、定規のみを用いて円の中心を得ることができると仮定する。このとき、円 $C$ の中心 $O$ を作図するような直線の列が存在する。このとき、直線の列の移る先の直線の列も円 $C'$ の中心 $O'$ を作図する。( $T$ は2曲線が交わる/接する/共有点を持たないといった性質を保存し、定規は二定点を通る直線を引くことか、あるいは無作為に平面上に直線を引くことにしか使えないため。)しかし、これは(3)に矛盾する。

さて、仮定したような $T$ は確かに存在する。例として、 $(x,\,y)$ を $(\frac{\sqrt{2}x+1}{x+\sqrt{2}}, \, \frac{y}{x+\sqrt{2}})$ に移すような射影は $T$ の条件を満たす。 $_\Box$

よって補題が証明された。定理の証明に移る。定規のみを用いて与えられた線分に平行な直線を引けると仮定する。ここで、平面上に円 $D$ があるとする。円 $D$ と2点で交わるような、互いに平行で異なる3直線 $L,\, L', \, L''$ を考える。また、 $L$ と平行ではなく、 $D$ と2点で交わるような、互いに平行で異なる3直線 $M,\, M', \, M''$ を考える。ここで、 $L, \, L'$ と円 $D$ の4交点のなす四角形の対角線の交点を $X$ 、 $L, \, L''$ と円 $D$ の4交点のなす四角形の対角線の交点を $Y$ とすると、 $XY$ は円 $D$ の中心を通る。同様に、 $M, \, M'$ と円 $D$ の4交点のなす四角形の対角線の交点を $X'$ 、 $M, \, M''$ と円 $D$ の4交点のなす四角形の対角線の交点を $Y'$ とすると、 $X'Y'$ は円 $D$ の中心を通る。このとき、 $XY$ と $X'Y'$ の交点は円 $D$ の中心を通る。これは、補題に矛盾する。 $_\Box$

以下の図では、線や点の名前などは違いますが、状況を模しています。

f:id:cute_1iYui:20210325235205p:plain — 図

2020-04-17

Javaにおけるクラスのアップキャストについて分かったこと

Java

こんばんは、simulo_yuiです。

simulo_yui (@simulo_yui) | Twitter

主にタイトルの通りのことについて語ります。

以下の記事を読んでいて不思議に思う部分があったことがきっかけです。

www.sejuku.net

その部分とはこちらです。

サブクラスのオブジェクトをスーパークラス型のオブジェクトでアップキャストする際、注意点があります。スーパークラスとサブクラスに、同じ名前のフィールド変数やメソッドがある場合には、フィールド変数はスーパークラス、メソッドはサブクラスが優先される、という点です。

この文章中に出てくる単語で分からないものがあったとしたら、上記の記事を読むことを推奨します。

なぜフィールドとメソッドに対して違う扱いがされるのでしょうか？上記の引用文の事柄について初めて知った方の多くがその疑問を持つと思います。本記事はそれについて調べました。

本編

Javaにおいて(おそらくは多くのオブジェクト指向言語において)クラスの継承はどのように内部で実現されてるのでしょうか。以下に図を用意しました。

f:id:cute_1iYui:20200417230649p:plain — 継承とキャスト

継承される側のクラスをスーパークラス、する側のクラスをサブクラスと呼びます。

サブクラスはその最初の部分にスーパークラスのコピーを持っています。継承時にスーパークラスからサブクラスへとコピーされます。オーバーライドではないサブクラス独自のメソッドやサブクラス内で宣言される変数たちはそのコピーのあとに追加されます。この追加された部分を以降、便宜上非共有部分と呼びます。サブクラスからスーパークラスへとアップキャストをするときは、このコピーの部分が抜き取られます。スーパークラスへキャストされたサブクラスからは非共有部分に入っている情報を得ることはできません。

※抜き取られる、は適切な表現ではありません。その部分以外へのアクセスが制限される、という表現が適切だと考えられますが、直感的なので用いています。

サブクラスからスーパークラスへのキャストは行うことができますが、一般的にはスーパークラスからサブクラスへのキャスト(ダウンキャスト)は行うことができません。サブクラスはスーパークラスが持っているすべてのフィールド変数とメソッドを持っていることを保証できますが、スーパークラスがサブクラスの持っているすべての変数とメソッドを持っていることが保証できないためです。

クラスはフィールドとメソッドから構成されています。一般にフィールド変数はプリミティブ型なら変数の値、参照型なら変数のアドレスへの参照を持っています。対して、クラスはメソッドそのものを格納しません。メモリ内のどこかほかの場所に格納されているメソッド本体への参照を持っています。上の図における参照の矢印を見て下さい。

サブクラスにおいて、スーパークラスの持っているメソッドのオーバーライドを行った場合、コピーされた部分にあるスーパークラスのそのメソッドへの参照がオーバーライドされたメソッドへの参照に切り替わります。メソッドの名前が同じでも中身(参照先)が違うのです。こちらも上の図における関数ポインタb、メソッドb、メソッドb'を見ていただきたいです。

また、これは推奨されるコードではないですが、サブクラス内においてスーパークラスと同名の新しい変数を宣言した場合、その変数は非共有部分に置かれます。この際、サブクラス内に同名の変数が二つあるような状況に思えますが、そこは闇の処理が行われてサブクラスとして扱う際には非共有部分に入っている変数を使われるようになります。

ここで私が最初に疑問に思ったことに戻ります。サブクラスからスーパークラスへのキャストが行われる際、同名のフィールド変数やメソッドがある場合はフィールド変数はスーパークラスのものが優先され、メソッドはサブクラスのものが優先されるのはなぜでしょうか？

アップキャストが行われる際、サブクラス内にあるスーパークラスのコピーの部分が抜き取られるという話をしました。スーパークラスとサブクラスに同名の変数があっても、その変数は非共有部分に入っているため切り取られず、コピー部分に入っていたスーパークラスのコピーの変数(=スーパークラスのものと同じ変数)が抜き取られるのです。対してスーパークラスとサブクラスに同名のメソッド(つまりオーバーライドされたメソッド)が存在する場合でも、サブクラス内のオーバーライド後のメソッドへの参照はコピー部分に入っているため、サブクラスのメソッドがそのまま抜き取られます。

抜き取られたオーバーライド後のメソッドの中でサブクラス内で新しく宣言された非共有部分にあるスーパークラスに同名の変数がある変数が使用されている場合は、アップキャストされた後でもそのメソッド内では非共有部分にある変数を用います。これはその変数への参照先にあるメソッドの内部では非共有部分にある変数への参照が入っているためです。(サブクラスとして扱われているうちは非共有部分にある変数が使われるため。)

感想その他

ややこしいですね。

2019-11-12

数の構成❶　ペアノの公理を満たす集合の存在

数学数の構成

こんばんは、simuloです。

simulo (@simulo_) / Twitter

自分はここしばらく独学でペアノの公理について勉強しています。参考にしている文献(PDF)はこちらです。

https://mathematics-pdf.com/pdf/construction_of_numbers.pdf

もともと数学に対する素養もなく、独学なので間違いも多いかと思われますが、間違いを見つけられましたらコメントにて教えていただけると幸いです。集合論もあいまいにしか勉強してないので、集合論における間違いが一番心配です。

また、今回の記事は上の文献に記述がなかった部分なので、自分で証明をしています。なおのこと心配ですね。

今回はZFC公理系からペアノの公理を満たす集合の存在を示します。必要となる公理は以下の二つです:

1.無限公理: $\exists A(\emptyset \in A \land \forall x \in A ( x \cup \{ x \} \in A ) )$

空集合を要素にもち、xを要素にもつならx∪{x}を要素に持つ集合Aが存在する。

無限公理 - Wikipedia

2.正則性公理: $\forall A (A \neq \emptyset \Rightarrow \exists x \in A \forall t \in A(t \notin x))$

空でない集合は必ず自分自身と交わらない要素を持つ。

正則性公理 - Wikipedia

また、これからの話題の中心となるであろうペアノの公理についてまとめます。

集合 $N$ がペアノの公理を満たすとは、集合 $N$ が以下の条件を満たすことを指す。

$0 \in N$
写像 $\sigma: N \mapsto N$ が存在する。
写像 $\sigma$ が単射である。 $\sigma (x_1)=\sigma(x_2) \Rightarrow x_1=x_2$
写像 $\sigma(x) x\in N$ がなす全体の集合を $\sigma(N)$ として、 $0\notin\sigma(N)$
集合 $S$ を $S\subset N$ として、 $(0 \in S \land x \in S \Rightarrow \sigma(x) \in S) \Rightarrow S=N$

僕らが慣れ親しんでいる自然数という集合はこのペアノの公理を満たすとされています。というより、このような公理を満たす集合として自然数の存在を示していくわけです。自分も読んでいて驚いたのですが、これだけの公理(定義?)から足し算と同じ性質を持つ写像、掛け算と同じ性質を持つ写像があっという間に構成されていくのです。さて、ペアノの公理を満たす集合の存在の証明をしていきます。

証明

命題

ペアノの公理を満たすような集合 $N$ が存在する。

まず次の補題が正則性公理から導かれることを示す。

補題1: $\lnot (\forall x_1 (x_1 \ni x_2 \ni x_3 ...))$

任意の $x_1$ に対して $x_1 \ni x_2 \ni x_3......$ と続く無限降下列が存在しない。

証明: 無限降下列が存在したとし、ある一つの無限降下列 $x_1 \ni x_2 \ni x_3......$ を用意し、それらすべてを含む集合 $X$ を考える。このとき任意の要素 $x_n$ に対し、 $A \cup x_n = x_{n+1}$ となり、正則性公理: $\forall A (A \neq \emptyset \Rightarrow \exists x \in A \forall t \in A(t \notin x))$ に矛盾。よって無限降下列は存在しない。Q.E.D.

補題2: 無限公理における集合 $A$ がペアノの公理の条件1.～4.を満たす。また $0=\emptyset$ とする。

無限公理における集合 $A$ の条件より、 $0=\emptyset \in A$ 。
$x \in A$ に対して $x \cup \{ x \}$ を対応させる写像を $\sigma$ とすれば、無限公理の集合の構成の仕方より写像 $\sigma: X \mapsto X$ が存在する.。
$x_1 \neq x_2 \land \sigma(x_1) = \sigma(x_2)$ 、すなわち $x_1 \neq x_2 \land x_1 \cup \{ x_1 \} = x_2 \cup \{ x_2 \}$ となる $x_1,x_2 \in A$ の存在を仮定する。すると、 $x_1 \neq x_2$ より、 $\{ x_1 \} \neq \{ x_2 \}$ なので、 $\{ x_1 \} \subset x_2$ である必要がある。同様に、 $\{ x_2 \} \subset x_1$ である。つまり、 $\{ x_1 \} \subset x_2 \in \{ x_2 \} \subset x_1 \in \{ x_1 \}$ $x_1 \in x_2 \in x_1$ となり、補題1に反する。
$0=\emptyset \in \sigma(N)$ とすると、ある要素 $ρ \in A$ によって $\emptyset=ρ \cup \{ ρ \}$ と表せることになり、矛盾。

Q.E.D.

を要素に持つとき、 $x\cup \{ x \}$ を要素に持つような集合を帰納的集合とよぶ。無限公理は、空集合を要素に持つ帰納的集合の存在を示している。つまり、0を要素に持つ帰納的集合は存在し、補題2でそのような集合はペアノの公理の条件1. ～4.を満たすことを確認した。

$0=\emptyset$ を要素に持つ帰納的集合を $A$ とし、そのような $A$ 全体の集合を $\mathfrak{A}$ とする。また、 $\bigcap_{\forall A \in \mathfrak{A}}{A}=B$ とする。補題2は $\forall A \in \mathfrak{A}$ に対し成り立つのであった。このとき、 $B$ はペアノの公理を満たす集合であることを示す。

$\forall A \in \mathfrak{A}$ について、 $\emptyset \in A$ なので、 $\emptyset \in B$
$\forall A \in \mathfrak{A}$ について、 $x \in A \Rightarrow x \cup \{ x \} \in A$ なので、 $\tau : B \mapsto B$ を $\tau(x) = x \cup \{ x \}$ と取ることが出来る。
ここで、1.と2.より、集合 $B$ は無限公理における集合 $A$ の一つであることが分かる。補題2より、また、上で取った写像 $\tau$ の取り方が補題2の2.の写像 $\sigma$ と一致しているので、写像 $\tau$ は単射である。
3.と同様に、 $B \in \mathfrak{A}$ であることが確かめられるので、 $0 \notin \tau(B)$
集合 $S$ はその取り方から $S \in \mathfrak{A}$ である。ここで、集合 $B$ はその取り方より、 $\forall A \in \mathfrak{A}(B \subset A)$ となるので、 $B \subset S$ 。これと、 $S \subset B$ より、 $S=N$ 。