算法

//n// 項演算は、集合の用語で説明すると、集合 //A// の直積集合 //An// の部分集合 //D// から //A// への写像であり、ここではそれを //f// とする。またこの //D// を定義域という。//n// は任意の順序数でよい。これを//f// の項数とよぶ。//An// は、 //i// < //n// をみたす順序数 //i// を添数とする //A// の元の族 //i//<//n// すべてからなる集合を表す。 集合 //A// とそこにおける演算の族 //R// との組  を代数系という。

この記事では以下これを「算法」と呼んでいる。"operation" の訳としては他に「作用」もあり、 "operator" を「演算子」ではなく「作用素」とするのはその流儀である。他言語において相互に連想されるような語が使われている場合、日本語訳としてもそれに対応するような語が選べれば望ましいが、難しい場合も多い。

他の「算法」の語については、算法  の記事を参照。

1. 全域的算法
--------

通常は、//D// = //An// の場合を考えることが多く、そういう算法 //f// を全域的算法とよぶ。 また、//n// が有限順序数の場合を考えることが多い。 その場合、//An// は //A// の //n// 個の元の組み  の全体であって、//f// によってこれをうつしたものは //f// と書くことができる。 しかしさらに、//n = 2// の場合を考えることが多く、この場合、 //f// を //a//0 //f// //a//1 とか //a//0 //a//1 //f// とか書くことが多い。

従って、全域的な 2 項算法とは、//A// の元の二つ組み  の各々に //A// の何らかの元を対応させる写像のことである。

例えば、二つの実数 //a//, //b// にその和 //a// + //b// を対応させる写像は、実数すべての集合における全域的 2 項算法であって、和の記号 + はこの算法の上記二番目の記法 //a//0 //f// //a//1 の //f// に当たるものと解される。 加法は普通の中置記法では //a// + //b// と書くが、逆ポーランド記法では //a b// + と書く。 これは、上記の //a//0 //a//1 //f// という記法に当たるものと解される。 実数の減法・乗法・除法についても同様である。 ただし除法は、0 で割ることができないから、全域的ではない。

1 項算法も珍しくはない。 例えば、複素数にその共役複素数を対応させる写像は 1 項算法である。 また、体 //K// 上の線型空間 //V// においては、 //K// の任意の元 //a// と //V// の任意の元 //v// に対して //V// の元 //av// が存在するが、これは、//K// を添数集合とする //V// の 1 項算法族 //a//∈//K// があって //fav// を //av// で表していると解される。 こう考えれば、例えば環 //R// 上の加群 //M// における //R// の元の //M// への作用のような「外的算法」は、すべて 1 項算法とみなされる。 なお、1 項算法は単項算法とよぶ方が語呂がいい。

2. 非全域的算法
---------

非全域的な算法も珍しくはない。 例えば、あらゆるサイズの行列の全体を //M// で表すとき、//M// の二元 //A//, //B// にその和 //A + B// を対応させる写像は //M// における 2 項算法であるが、//A//, //B// が同サイズのときにしか //A + B// が定義されないから、非全域的算法である。//A//, //B// にその積 //AB// を対応させる写像も //M// における 2 項算法であるが、//A// の列の個数と //B// の行の個数が等しいときにしか //AB// が定義されないから、やはり非全域的算法である。

形式言語における算法は、非全域的のものが一般的である。 例えば、述語言語における論理記号は、論理式に対してのみ適用可能な 2 項または 1 項の非全域的算法を表すと解される。

項数が 2 より多い非全域的算法も珍しくはない。 例えば、述語言語における //n// 変数関数記号や //n// 変数述語記号は、項に対してのみ適用可能な //n// 項算法を表すと解される。

3. 超限的な項数を持つ算法
--------------

超限順序数を項数とする算法もある。 例えば、最小の超限順序数を ω で表し、実数の全体を R で表すと、直積 Rω は実数列 //a//0, //a//1, ... の全体であるが、収束する実数列にその極限を対応させる写像は、非全域的の ω 項算法である。 数列の極限をこのように ω 項算法とみなすことには効用もある。 たとえば、数列の極限の ε-//n// 式定義を ω 項算法の代数的条件によって書き換えて、極限を公理化することができる。 つまり、R における次の六条件をみたす ω 項算法 //L// が極限に他ならない。

//L// = //a//
//L// = //a//, //L// = //b//, //an// ≤ //bn//  なら //a// ≤ //b//
//L// = //a// なら //a//1, //a//2, ... の任意の部分列 //b//1, //b//2, ... に対して //L// = //a//
//L// = //L// = //a//, //an// ≤ //cn// ≤ //bn//  なら //L// = //a//
//L//, //a//±, //a//±, ...) = //a//
//a//1, //a//2, ... の任意の部分列 //b//1, //b//2, ... に //L// = //a// なる部分列 //c//1, //c//2, ... があれば //L// = //a//大学 1, 2 年次の学生や高校生に「行列の算法は非全域的算法である」とか「極限は ω 項算法である」とか教えるのは勧められないが、数理科学者がそういうことを認識するのは、視野が広がるので好ましいであろう。

4. 算法概念の拡張
----------

冒頭に定義したとおり、//f// が集合 //A// における //n// 項算法であるとは、//f// が //An// のある部分集合 //D// から //A// への写像であることをいう。 そうすると //f// は、//An//×//A// の部分集合 ∈//D//, //f// = //y// } と同一視される。 従って、もしも //f, g, ... // が //n// 項算法なら、それらの集合としての和を考えることができる。 しかし一般には、//f// を動かせば、それに応じて //n// も動く。 そこで、より一般に、//An//  の集合としての直和を //A//* で表し、//A//* × //A// の部分集合 //R// のことまでも算法とよぶことにする。 ただしこういう//広義// の算法については、α ∈ //A//* と //y// ∈ //A// とが  ∈ //R// をみたすことを通常の算法のように //R// = //y// と書き表すことはできず、α //R// //y// と書かなければならない。 一つの α ∈ //A//* に対して  ∈ //R// をみたす //y// が唯一つとは限らないからである。 この意味でこれは、もはや算法ではなく関係とよぶべきかもしれない。

こういう広義の算法・関係は、数理論理学にしばしば現れる。 例えば述語言語 //A// において、意味写像 //f// * の下で inf {//f// *, ... , //f// *} ≤ //f// * をみたす論理式 //a//1, ... , //a//n, //b// から出来る //A//*×//A// の元 , //b//) の全体を //R// で表せば、これは上記の意味での広義の算法・関係である。

このように算法の概念と関係の概念をともに拡張して統合すると、算法と関係とを統一的に扱うことができて極めて有効である。

5. 命名について
---------

算法を「演算」とよぶことも多い。 しかし、ここで考えた「算法の概念」の名前としては、「算法」も「演算」も相応しくはないであろう。 「算法」は「計算の規則」あるいは「計算の方法」を連想させ、「演算」は「計算を演ずるという行為」を連想させ、ともに「写像」としての「算法の概念」を連想させにくい。 一つの写像に対しても、それの「計算の方法」は一般に複数あり、「計算する方法」も「計算の規則」も具体的に記述できない場合さえあり、人や機械が「計算を演ずるという行為」はもちろん写像とは異なるからである。 「写像」という概念が未発達で「計算」と「計算の仕方」の違いも曖昧であった時代に生まれた「算法」とか「演算」とかの言葉を用いるのが間違っているのであろう。

冒頭に記したとおり、計算機科学の分野ではアルゴリズムを「算法」とよぶこともあり、その場合には上記の意味での「算法」は「演算」とよぶ方がよいかもしれない。 しかし数学の分野では、上記の意味での「算法」という術語も昔から定着しているdate=2023年2月}}。 むしろアルゴリズムを「算法」ではなく「計算手順」とする方が、意味からいっても先例を尊ぶ点でも、好ましいであろう。

6. 脚注
-----

6.1. 注釈
-------

7. 関連項目
-------

代数系
代数学
演算子
単項演算
二項演算