『一般性を失うことなく』ってどういうこと？

今回は「一般性を失うことなく」という表現を扱おうと思います。証明の中で「一般性を失うことなく～と仮定する」 (Assume without loss of generality that ...) のように使います。

この表現が使えるのは次の2つの条件が成立しているときです。

・証明の中で場合分けがある．
・場合分けのどの場合をとっても記号の違いを除いて証明が同じである．

例えば、次のような定理を考えてみましょう。

定理．m, n を正の整数とする．もし m ≠ n ならば gcd(m,n) = gcd(s, l mod s) である．ここで、s = min(m,n), l = max(m,n) である．

ここで、gcd は最大公約数 (greatest common divisor) を返す関数，max, min はそれぞれ最大値、最小値を返す関数、l mod s は l を s で割った余りです。

この定理は言わずと知れたユークリッドの互除法の正当性を保証する定理です。

ユークリッドの互除法 - Wikipedia

以下、この定理を証明してみます。

[証明] g = gcd(m,n) とおき、m = gM, n = gN とする。ここで、M, N はそれぞれ正の整数で、互いに素である。以下、m > n と m < n の 2 つの場合がある。

m > n のとき、s = n = gN かつ l = m = gM である。また、l mod s = g(M mod N) である。gcd(N, M mod N) ≠ 1 と仮定する。このとき、2 以上の整数 G と正の整数 K, L を用いて N = GK, M mod N = GL とおける。このとき、ある正の整数 Q を用いて M = N × Q + GL = G(KQ + L) となるので、m = gM = gG(KQ + L), n = gN = gGK となり、gcd(m,n) ≧ gG > g であるので矛盾する。したがって、gcd(M, M mod N) = 1、すなわち、M と M mod N は互いに素であるので、gcd(s, l mod s) = g が成り立つ。

m < n のとき、s = m = gM かつ l = n = gN である。また、l mod s = g(N mod M) である。gcd(M, N mod M) ≠ 1 と仮定する。このとき、2 以上の整数 G と正の整数 K, L を用いて M = GK, N mod M = GL とおける。このとき、ある正の整数 Q を用いて N = M × Q + GL = G(KQ + L) となるので、m = gM = gGK, n = gN = gG(KQ + L) となり、gcd(m,n) ≧ gG > g であるので矛盾する。したがって、gcd(M, M mod N) = 1、すなわち、M と M mod N は互いに素であるので、gcd(s, l mod s) = g が成り立つ。[証明終]

さて、読んで気が付くと思いますが、m > n の場合と n < m の場合で同じような議論が繰り返されています。しかし、証明に本質的な違いはありません。単に記号が違うだけです。このようなときに、無駄に長い議論を避けるために使われるのが「一般性を失うことなく～と仮定する」という表現です。これを使うと証明は次のようになります。

[証明] g = gcd(m,n) とおき、m = gM, n = gN とする。ここで、M, N はそれぞれ正の整数で、互いに素である。

一般性を失うことなく m > n と仮定する。このとき、s = n = gN かつ l = m = gM である。また、l mod s = g(M mod N) である。gcd(N, M mod N) ≠ 1 と仮定する。このとき、2 以上の整数 G と正の整数 K, L を用いて N = GK, M mod N = GL とおける。このとき、ある正の整数 Q を用いて M = N × Q + GL = G(KQ + L) となるので、m = gM = gG(KQ + L), n = gN = gGK となり、gcd(m,n) ≧ gG > g であるので矛盾する。したがって、gcd(M, M mod N) = 1、すなわち、M と M mod N は互いに素であるので、gcd(s, l mod s) = g が成り立つ。[証明終]

見ての通り、後半の m < n の場合の証明を省略していますが、証明で「一般性を失うことなく m > n と仮定する」と述べることによって、m < n の場合の証明が m > n の場合の証明と本質的に変わらないことを主張していて、記号をちょっと変えれば m < n の場合の証明を完成させられるから省略することを宣言しています。こうすることによって同じ議論を二度行うことが避けられる、便利な表現なのです。

もちろん、「一般性を失うことなく」という言葉は乱用すべきではありません。今回のように「記号を機械的に入れ替える」程度の変更で残りの場合が証明出来るときにのみ使われます。

あくまで、文章の中で同じ表現が繰り返されるのは避けるべきという、通常の文章でも存在するルールの一環として使われる言葉が「一般性を失うことなく」なのです。