ここでは、データの順序に依存しないアルゴリズムをプログラミング言語のデータ構造で表すことを考えています。単項イデアル整域のイデアルの演算を抽象化したものを考えます。いったん今までの結果をまとめます。
を可換モノイドで簡約可能とします。単位元を
とします。
は二元の最大公約数をとる演算
をもち、最大公約数に関して可換べき等半群とします。
が成り立つとします。
に順序
を
で定義します。
のとき
を
の約数、
を
の倍数と呼びます。
とおき、 の元を素元と呼びます。
とおき、 の元を既約元と呼びます。
[証明]
これは最大公約数の存在に関係なく成り立ちます。
とし
とします。
であり
であることから
または
となります。
のときは
となります。
のときは
となります。
よって ならば
となります。[証明終わり]
の部分集合
が生成する
の部分モノイドを
と書きます。
最大公約数の存在に関係なく以下が成り立ちます。
[証明] とすると
となる
が存在します。
よりある一つの
以外は
となります。
よって となって
となります。
は最大公約数の存在に関係なく成り立つので
となります。[証明終わり]
任意の自然数 に対して
が定義されて任意の自然数
に対して
であるとき、元の列
を
の無限下降列と呼びます。
以下の条件を考えます。
の任意の部分集合
で
の任意の元
の最大公約数
が
に属するもの(最大公約数に関して閉じているもの)には最小元
が存在する。
[証明] とし
をとります。
の無限下降列
で
であるものを以下のように帰納的に定義することができます。
とおきます。
に対して
であるから
、
、
となる
が存在します。
ならば
となりますが
なので
または
となります。よってこのどちらかをとれば
となる
をとることができます。これを
とおくと
となります。なぜなら
のときを考えると、
とすると
となって
に反するので
となるので、
となるためです。
以上で の無限下降列
を定義することができました。
なので
は最大公約数に関して閉じています。
より
が存在します。
となって
の最小性に矛盾。
よって が成り立ちます。[証明終わり]