同値関係

同値関係とは、反射的、対称的、推移的な、集合上の二項関係のことです。

はじめに

同値関係は、等号の関係をいわばゆるめたものです。集合の2つの要素が同じかどうか、つまり a = b かどうかは、いつでも判断できます。しかし、2つの要素が必ずしも同じではなく、似ているだけかどうかを知りたいこともあります。言いかえると、ある大切な性質が同じかどうかです。例えば、2冊の本はジャンルが同じなら似ていると考えることができます。同値関係を使っていえば、2冊の本はジャンルが同じなら同値です。

このような同値関係には、どんなことを期待するでしょうか。別の例で考えましょう。2つの単語は、かなで書いたときの文字数が同じなら、似ている、つまり同値であるとします。

まず、同じ単語どうしが似ているかを調べたら、似ているという結果になってほしいはずです。したがって、どの単語も自分自身と似ている、すなわち同値でなければなりません。関係のことばでいえば、同値関係は反射的でなければなりません。

次に、単語「みずうみ」が単語「ひまわり」と似ている、つまり同値なら、「ひまわり」も「みずうみ」と同値であることを当然期待します。言いかえると、順序は関係ありません。関係のことばでいえば、同値関係は対称的でなければなりません。

最後に、単語「かえる」が単語「つばめ」と似ている、つまり同値で、単語「つばめ」が単語「すずめ」と同値なら、「かえる」と「すずめ」の対も同値であることを期待します。つまり、同値関係は推移的でもなければなりません。

同値関係にそれ以上のことは期待しません。

例

同値関係のほかの例を見てみましょう。

• 同じ市に住んでいる。健太は、もちろん健太と同じ市に住んでいます（反射律）。健太が翔太と同じ市に住んでいるなら、翔太も健太と同じ市に住んでいます（対称律）。そして、翔太が大輝と同じ市に住んでいるなら、健太も大輝と同じ市に住んでいます（推移律）。
• 作曲者が同じ曲。曲「月の坂道」は、もちろん曲「月の坂道」と作曲者が同じです（反射律）。曲「月の坂道」と「夏のバス停」の作曲者が同じなら、「夏のバス停」と「月の坂道」の作曲者も同じです（対称律）。そして、「夏のバス停」と「遠い灯台」の作曲者が同じなら、「月の坂道」と「遠い灯台」の作曲者も同じです（推移律）。
• (a, b) ∈ R となるのは、a − b が偶数であるとき、かつそのときに限ります。ただし、a, b は整数です。反射律：a − a = 0 で、0は偶数です。対称律：c = a − b とおきます。すると b − a = −(a − b) = −c です。c が偶数なら、−c も偶数です。推移律：p = a − b、q = b − c とおきます。p と q はどちらも偶数です。ここで、a − c が偶数であることを証明します。この式の c に c = b − q を代入すると a − (b − q) となり、これは a − b + q に等しくなります。仮定から、a − b は偶数です。偶数にさらに偶数 q を足すと、やはり偶数になります。
• 等号。等号は同値関係で、しかも任意の集合 M 上で最小の同値関係です。

自明な同値関係

空でない集合 M があるとします。集合 M 上の最小の同値関係 R は何でしょうか。直積 M × M の部分集合で最小のものは空集合 ∅ です。空集合は同値関係の条件を満たすでしょうか。

対称律はたしかに満たします。関係 R には要素が一つもないので、対称律の条件は自動的に、自明に満たされます。推移律も同じです。問題は反射律です。定義によれば、集合 M のすべての要素 x について (x, x) ∈ R が成り立たなければなりません。これは満たされているでしょうか。集合 M は空ではないので、何か要素、例えば q を含みます。対 (q, q) は関係 R に属するでしょうか。属しません。したがって、関係 R は反射的ではありません。

反射律を満たす最小の関係は何でしょうか。等号の関係です。関係 R は、M のすべての要素について、少なくとも対 (x, x) を含まなければなりません。これが恒等関係です。この関係は対称的でしょうか。簡単にわかるように、対称的です。同じように、推移的であることもすぐにわかります。したがって、集合 M 上の最小の同値関係は恒等関係です。これを id_M で表し、すべての x ∈ M について対 (x, x) を含みます。

集合 M 上の最大の同値関係は何でしょうか。最大の部分集合は集合 M × M 全体です。これは同値関係の条件を満たすでしょうか。満たすことはほとんど自明でしょう。

同値類

どの同値関係も、集合 M を互いに素な集合の族に分けます。これらの集合を同値類といいます。

すべての単語の集合を M とし、同値関係 R を「文字数が同じ単語」とします。つまり、(a, b) ∈ R となるのは、単語 a と b の文字数が同じとき、かつそのときに限ります。この同値関係によって、単語の集合はいくつかの小さな集合に分かれ、それぞれの集合には文字数が同じ単語が入ります。それぞれの同値類は下付き添え字で区別できます。添え字は、その集合に入っている単語の文字数も表します。

• M₁ = {え, き, て, め, …}
• M₂ = {いぬ, ねこ, やま, うみ, そら, …}
• M₃ = {さくら, つくえ, かもめ, とけい, …}
• M₄ = {ひまわり, みずうみ, たまねぎ, おとうと, …}
• …

2つのことに注目しましょう。1) それぞれの集合は互いに素で、共通の要素をもちません。2) それぞれの集合の中のすべての要素は、たがいに同値です。集合 M₃ のすべての単語はたがいに同値です。どの単語も文字数が3、つまり同じ文字数で、これが同値の条件だからです。

さらに、どの要素も、それが属する同値類をただ一つに決めます。これはふつう M[x] という書き方で表します。ただし x ∈ M です。M[さくら] と書けば、すでに M₃ と名づけた同値類がただ一つに決まります。（日本の教科書では、x の同値類を表すのに、x を角かっこで囲んだ記号もよく使います。）

ある x ∈ M がわかっているとき、同値類はどうやって求めればよいでしょうか。M のすべての要素を調べ、そのうちどれが要素 x と同値かを確かめます。それらがすべて、同値類 M[x] に属する要素です。

M[さくら] なら、M のすべての単語を調べ、文字数が3の単語を M₃ に残せばよいのです。

同値類の定義と性質

同値類は次のように定義できます。集合 M と、その上に定義された同値関係 R があるとします。このとき、要素 x ∈ M を含む同値類とは、次の集合のことです。

$$M[x]=\{y\in M;(x,y)\in R\}$$

この定義は、与えられた要素 x と同値なすべての y の集合を表しています。同値関係は反射的なので、この方法で要素 x 自身も入ります。x は自分自身と同値だからです。

同値関係による分割とは、すべての同値類の集合のことです（商集合ともいいます）。単語の例でいえば、すべての単語の集合の分割は集合 {M₁, M₂, M₃, …} です。

同値類の基本的な性質は次のとおりです。

• (a, b) ∈ R となるのは、M[a] = M[b] のとき、かつそのときに限ります。2つの要素 a, b が同値なら、その同値類は等しくなければなりません。
• 逆に、(a, b) ∈ R が成り立たないなら、M[a] ≠ M[b] で、より正確には M[a] ∩ M[b] = ∅ です。同値でない2つの要素の同値類は、互いに素です。
• すべての同値類の和集合は、もとの集合 M になります。M₁ ∪ M₂ ∪ … ∪ M_n = M です。（この書き方は同値類が有限個の場合だけですが、一般には無限個あることもあります。）

同値関係による分割の例

1つ目の例は奇数と偶数です。

自然数 N 上に定義された簡単な同値関係 R を考えます。(a, b) ∈ R となるのは、a と b がどちらも奇数であるか、a と b がどちらも偶数であるとき、かつそのときに限ります。要素の例は (1, 7), (13, 9), (4, 6), (8, 136) です。この同値関係による同値類への分割を求めましょう。

順に考えていきます。同値類 N[1] は何になるでしょうか。1と同値なすべての数を見つけなければなりません。同値の条件から、それはすべての奇数なので、N[1] = {1, 3, 5, 7, 9, …} です。

同値類 N[2] は何になるでしょうか。2と同値なすべての数を見つけます。それはすべての偶数です。N[2] = {2, 4, 6, 8, 10, …} です。

次は N[3] です。3と同値な数はどれでしょうか。すべての奇数です。しかし、これでは2つ前の段落で求めた集合 N[1] が得られるだけです。N[4] も同じで、やはり偶数の集合が得られます。

この先は、同じ集合がくり返し出てくるだけだとわかります。これは、どんな自然数 n をとっても、n ∈ N[1] または n ∈ N[2] が成り立つことからもわかります。奇数と偶数以外の自然数はないので、この2つの集合が同値関係による分割になります。

これは、人の集合上で「a と b がどちらも男性であるか、a と b がどちらも女性である」という同値関係を考えるのと似ています。このとき、分割として女性の集合と男性の集合が得られます。

2つ目の例は絶対値です。

整数の集合 Z 上の同値関係 R を次のように定義します。(a, b) ∈ R となるのは、|a| = |b| のとき、かつそのときに限ります。（縦線は絶対値を表します。）ここでも順に考えていきましょう。

• Z[0] = {0}。0は0とだけ関係にあります。
• Z[1] = {−1, 1}。1は1とも、マイナス1とも関係にあります。|1| = |−1| だからです。
• Z[2] = {−2, 2}。2は2とも、マイナス2とも関係にあります。
• Z[3] = {−3, 3}。
• …

この先どう続くかは明らかでしょう。したがって、分割全体は次の同値類の集合になります。

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

（つまり、a が0以上の整数であるときの、すべての a, −a の組です。）同値類が無限個あることがわかります。