壁紙はいくつかの変換に対して不変です。この壁紙は、水平方向と垂直方向の移動、そして180°の回転に対して不変です（ただし、鏡映変換では不変ではありません）。

数学において、不変量とは、数学的対象（または数学的対象のクラス）の特性であり、特定の種類の演算や変換をその対象に適用した後も変化しないものである。 [1] [2]特定の対象クラスと変換の種類は、通常、用語が使用される文脈によって示される。例えば、三角形の面積はユークリッド平面の等長変換に関して不変量である。「変換に対して不変である」という表現と「変換に対して不変である」という表現はどちらも使用される。より一般的には、同値関係に関して不変量とは、各同値クラスにおいて一定である特性である。[3]

不変量は、幾何学、位相幾何学、代数学、離散数学など、数学の様々な分野で用いられています。いくつかの重要な変換クラスは、変換によって変化しない不変量によって定義されます。例えば、等角写像は、角度を保存する平面の変換として定義されます。不変量の発見は、数学的対象を分類するプロセスにおける重要なステップです。[2] [3]

例

不変性の簡単な例は、を数える能力に表れます。あらゆる種類のオブジェクトの有限集合には、集合内のオブジェクトをどのような順序で数えたとしても、必ず到達する数が存在します。その量（基数）は集合に関連付けられており、数え上げの過程で不変です。

恒等式とは、変数の値がどのような値であっても成立する方程式です。また、変数の値が変わっても成立する 不等式も存在します。

数直線上の2点間の距離は、両方の数に同じ量を加えても変化しません。一方、乗算にはこの性質がありません。なぜなら、距離は乗算に対して不変ではないからです。

角度と距離の比は、拡大縮小、回転、並進、鏡映変換に対して不変です。これらの変換は相似形を生み出し、これが三角法の基礎となります。一方、角度と比は、非均一な拡大縮小（伸縮など）に対しては不変ではありません。三角形の内角の和（180°）は、上記のすべての操作に対して不変です。別の例として、すべての円は相似です。円は互いに変形でき、円周と直径の比は不変です（ギリシャ文字π（パイ）で表されます）。

もう少し複雑な例をいくつか挙げます。

MUパズル

MUパズル[7]は、不変量の決定が不可能性の証明に役立つ論理問題の良い例です。このパズルでは、単語MIから始めて、各ステップで以下の変換規則のいずれかを用いて単語MUに変換します。

  1. 文字列がIで終わる場合は、Uを追加することができます（x I → x IU）
  2. Mの後の文字列は完全に重複している可能性がある（M x → M xx）
  3. 連続する3つのI（III）は、1つのU（x III y → x U y）に置き換えることができる。
  4. 連続する2つのUは削除できる（x UU y → xy）

導出の例（上付き文字は適用された規則を示す）は次の通りである。

MI → 2 MII → 2 MIIII → 3 MUI → 2 MUIUI → 1 MUIUIU → 2 MUIUIUUIUIU → 4 MUIUIUIU → ...

これを踏まえると、これらの4つの変換規則だけを使ってMIをMUに変換できるのではないかと疑問に思う人もいるかもしれません。これらの変換規則を文字列に適用するには、何時間もかかるでしょう。しかし、すべての規則に対して不変（つまり、どの規則によっても変化しない）で、MUへの変換が不可能であることを示す特性を見つける方が早いかもしれません。このパズルを論理的な観点から見ると、文字列中にIをすべて取り除く唯一の方法は、Iが3つ連続することだと気づくかもしれません。これは、次の不変式を検討する上で興味深いものです。

文字列内の I の数は 3 の倍数ではありません。

これは、各変換規則について以下の条件が成り立つ場合、問題に対する不変式です。規則を適用する前に不変式が成り立っていた場合、適用後も不変式が成り立ちます。規則を適用した場合のIとUの数への純粋な影響を見ると、これはすべての規則に当てはまることがわかります。

上の表は、不変条件がそれぞれの可能な変換規則に当てはまることを明確に示しています。つまり、どの規則を選択しても、どのような状態でも、規則を適用する前に I の数が 3 の倍数でなかった場合は、適用後も 3 の倍数にはなりません。

最初の文字列 MI には I が 1 つしかなく、それが 3 の倍数ではないことを考えると、MI から MU に移行することは不可能であると結論付けることができます (I の数が 3 の倍数になることは決してないため)。

不変集合

写像T : U → Uの領域Uの部分集合 Sは、次の場合の写像の下で不変集合 となる。Sの元は、 SがUの冪集合において固定されているとしても、必ずしも固定されているとは限らない。（これらの場合を区別するために、一部の著者は集合不変[8]と点不変[9]という用語を使用している。）例えば、円は、円の中心の周りの回転に関して平面の不変部分集合である。さらに、円錐面は空間の相似性に関して集合として不変である。

演算Tの不変集合はTのもとで安定で あるとも言われる。例えば、群論で非常に重要な正規部分群は、周囲群の内部自己同型のもとで安定な部分群である。[10] [11] [12]線型代数 において、線型変換T が固有ベクトルvを持つ場合、 0とvを通る直線はTのもとで不変集合となり、この場合、固有ベクトルはTのもとで安定な不変部分空間を張る。

Tがスクリューの変位である場合、スクリュー軸は不変線ですが、ピッチがゼロでない場合、T には固定点がありません。

確率論とエルゴード理論では、不変集合は通常、より強い性質[13] [14] [15]を介して定義されます。写像が測定可能な場合、不変集合はシグマ代数、つまり不変シグマ代数を形成します。

正式な声明

数学では、不変性の概念は、群作用、表現、変形という 3 つの異なる方法で形式化されます。

集団行動では変化なし

まず、数学的対象（または対象集合）Xに作用する群 G がある場合、群作用のもとで、または群の要素gのもとで、どの点xが不変、つまり「不変」であるかを問うことができます。

集合Xに作用する群が存在する場合、関連する集合F ( X )内のどのオブジェクトが不変であるかを判定する必要があります。例えば、平面内で点を中心とした回転は、回転の中心となる点を不変に保ちますが、平面内での並進運動は、どの点も不変にしませんが、並進運動の方向に平行なすべての直線は直線として不変のままです。正式には、平面P上の直線の集合をL ( P )と定義します。すると、平面の剛体運動は直線を直線へと移動させます。つまり、剛体運動の群は直線の集合に作用します。そして、どの直線が作用によって変化しないのかを問うことができます。

さらに重要なことは、 「平面上の円の半径」などの集合上の 関数を定義し、この関数が剛体運動などのグループ動作に対して不変であるかどうかを尋ねることができることです。

不変量の概念の双対として、共変量（軌道とも呼ばれる）があり、これは合同性の概念を形式化します。合同性とは、群の作用によって互いに引き寄せられる物体のことです。例えば、平面の剛体運動群の下では、三角形の周長は不変量であり、与えられた三角形と合同な三角形の集合は共変量です。

これらは次のように関連しています。不変量は共変量に対して一定です（例えば、合同な三角形は同じ周囲長を持ちます）。一方、一方の不変量の値が一致する2つのオブジェクトは、合同である場合もそうでない場合もあります（例えば、同じ周囲長を持つ2つの三角形は必ずしも合同である必要はありません）。分類問題では、不変量の完全な集合を見つけようとする場合があります。この場合、2つのオブジェクトがこの不変量の集合に対して同じ値を持つ場合、それらは合同です。

例えば、3辺がすべて等しい三角形は、SSS合同性により剛体運動において合同であり、したがって3辺の長さは三角形の完全な不変量集合を形成します。三角形の3つの角度の測度も剛体運動において不変ですが、不合同な三角形が同じ角度の測度を共有できるため、完全な不変量集合を形成しません。しかし、剛体運動に加えてスケーリングを許容する場合、AAA相似基準はこれが完全な不変量集合であることを示します。

プレゼンテーションに依存しない

第二に、関数は数学的対象の何らかの表現または分解によって定義される場合があります。たとえば、セル複体のオイラー特性は、各次元のセルの数の交代和として定義されます。セル複体構造を忘れて、基礎となる位相空間(多様体) のみに注目することもできます。異なるセル複体は同じ基礎となる多様体を与えるため、関数が表現の選択に依存しないかどうかを尋ねることができます。その場合、関数は本質的に定義された不変量です。これはオイラー特性の場合であり、不変量を定義および計算する一般的な方法は、それらを特定の表現に対して定義し、次にそれらが表現の選択に依存しないことを示すことです。この意味での群作用の概念は存在しないことに注意してください。

最も一般的な例は次のとおりです。

摂動下でも変化なし

第三に、代数幾何学や微分幾何学でよくあるように、族内で変化するオブジェクトを研究している場合、摂動を受けてもその特性が変化しないかどうかを尋ねることがあります（たとえば、オブジェクトが族に対して定数であるか、または計量の変化に対して不変であるか）。

コンピュータサイエンスにおける不変量

コンピュータサイエンスにおいて、不変式とは、コンピュータプログラムの実行における特定のフェーズにおいて常に真であるとされる論理的主張のことです。例えば、ループ不変式とは、ループの各反復処理の開始時と終了時に真となる条件のことです。

不変式は、コンピュータプログラムの正しさを推論する際に特に役立ちます。コンパイラの最適化理論、契約による設計の方法論、そしてプログラムの正しさを判定するための形式手法はすべて、不変式に大きく依存しています。

プログラマーは、不変条件を明示的に示すために、コード内でアサーションを使用することがよくあります。一部のオブジェクト指向 プログラミング言語には、クラス不変条件を指定するための特別な構文があります。

命令型プログラムにおける不変条件の自動検出

抽象解釈ツールは、与えられた命令型コンピュータプログラムの単純な不変量を計算できます。発見できる特性の種類は、使用される抽象ドメインによって異なります。典型的な特性の例としては、 のような単一の整数変数の範囲0<=x<1024、 のような複数の変数間の関係0<=i-j<2*n-1、 のような係数情報などが挙げられますy%4==0。学術研究のプロトタイプでは、ポインタ構造の単純な特性も考慮されています。[16]

より高度な不変条件は、一般的に手動で提供する必要があります。特に、ホーア計算[17]を用いて命令型プログラムを検証する場合、プログラム内のループごとにループ不変条件を手動で提供する必要があります。これが、このアプローチがほとんどのプログラムにとって一般的に非実用的である理由の一つです。

上記のMUパズルの例において、MIからMUへの導出が規則1～4のみを用いて不可能であることを検出できる汎用的な自動ツールは現時点では存在しません。しかし、文字列からその中の「I」の数への抽象化を手作業で行い、例えば以下のCプログラムを作成すれば、抽象解釈ツールはそれがICount%30にはなり得ないこと、つまり「while」ループが決して終了しないことを検出できるようになります。 

void MUPuzzle ( void ) { volatile int RandomRule ; int ICount = 1 , UCount = 0 ; while ( ICount % 3 != 0 ) // 非終了ループswitch ( RandomRule ) { case 1 : UCount += 1 ; break ; case 2 : ICount *= 2 ; UCount *= 2 ; break ; case 3 : ICount -= 3 ; UCount += 1 ; break ; case 4 : UCount -= 2 ; break ; } // 計算された不変式: ICount % 3 == 1 || ICount % 3 == 2 }

参照

注記

  1. ^ 「不変式の定義（図解数学辞典）」www.mathsisfun.com . 2019年12月5日閲覧。
  2. ^ ab Weisstein, Eric W. 「Invariant」. mathworld.wolfram.com . 2019年12月5日閲覧。
  3. ^ ab 「不変量 – 数学百科事典」www.encyclopediaofmath.org . 2019年12月5日閲覧。
  4. ^ Qiao, Xiaoyu (2015年1月20日). "Tricolorability.pdf" (PDF) .結び目理論 第2週: Tricolorability . 2024年5月25日時点のオリジナル(PDF)からアーカイブ。 2024年5月25日閲覧。
  5. ^ フレイリー (1976、pp. 166–167)
  6. ^ ケイ（1969年、219ページ）
  7. ^ ホフスタッター、ダグラス・R. (1999) [1979]、「ゲーデル、エッシャー、バッハ：永遠の黄金の三つ編み」、ベーシックブックス、ISBN 0-465-02656-7 ここでは、第 1 章です。
  8. ^ バリー・サイモン『有限群とコンパクト群の表現』アメリカ数学会、16ページ、ISBN 978-0-8218-7196-6。
  9. ^ ジュディス・セダーバーグ (1989). 『現代幾何学講座』 シュプリンガー. p. 174. ISBN 978-1-4757-3831-5。
  10. ^ フレイリー（1976年、103ページ）
  11. ^ ハーシュタイン（1964年、42ページ）
  12. ^ マッコイ（1968年、183ページ）
  13. ^ ビリングスリー（1995年）、313-314ページ
  14. ^ Douc et al. (2018)、99ページ
  15. ^ クレンケ（2020）、494-495ページ
  16. ^ Bouajjani, A.; Drǎgoi, C.; Enea, C.; Rezine, A.; Sighireanu, M. (2010). 「無制限データを持つリストを操作するプログラムのための不変合成」(PDF) . Proc. CAV . doi : 10.1007/978-3-642-14295-6_8 .
  17. ^ Hoare, CAR (1969年10月). 「コンピュータプログラミングの公理的基礎」(PDF) . Communications of the ACM . 12 (10): 576– 580. doi :10.1145/363235.363259. S2CID  207726175. 2016年3月4日時点のオリジナル(PDF)からのアーカイブ。

参考文献