合同とは
Rがなんらかの代数構造で、代数構造を保存する同値関係を合同(congruence)と呼ぶ。これは曖昧すぎるが、個々のケースでは厳密な定義ができる。たとえば、モノイド上の合同は:
- 〜は同値関係
- a〜a'、bからb' ならば ab〜a'b'
〜がM上の合同なら、商M/〜を再びモノイドになる。圏論的にいえば、具象圏があって、台集合の〜による商が再び圏の対象とみなすことができれば、〜は合同ってことだろう。
合同は同値関係なので、対角を含む集合として外延化できる。外延の大小により、合同の大小も定義できる。小さいほど弱く、大きいほど強いと表現して強弱を考えることができる。通常、強い(強すぎる)合同は興味の対象にはならず、できるだけ弱い合同を求めることが問題になる。
合同を計算する一般的な手段は項書き換え系である。うまく項書き換え系を作れば、合同をアルゴリズム的に判断できるようになる。が、一般的には、合同を判定するアルゴリズムがあるとは限らないし、あっても発見は難しい。
多項式のイデアル論は、合同の定義と判定がうまくいった典型例だろう。合同の理論的な側面はイデアルの抽象的一般論でうまく展開できて、具体的なアルゴリズムはグレブナー基底で計算可能。