集合の講座5(ドモルガンの法則)

[解説・集合の一致]

ふたつの集合AとBがあったとします。AとBとが「等しい集合である」ということはどういうことでしょうか。一般に、ひとつの集合の記述の仕方にはいろいろあります。たとえば、

A={1,2,3}、B={ x | x は3以下の自然数 }、C={ y | y は自然数で、1≦y≦3 }

とすると、A、B、Cの表現のしかたはみな異なりますが、これらはすべて等しい集合であると考えたいものです。なぜなら、これらの集合が持っている要素がすべて等しいからです。そこで、「集合の一致」を次のように定義します。

ふたつの集合AとBに対して、AとBとが等しいとは、
A⊂B と B⊂A が両方とも成り立つ
ときをいう。またこのときA=Bと書く。

この定義を図で見てみましょう。「A⊂B」とは、「Aのすべての要素がBに含まれる」ということでした。「A⊂B」と「B⊂A]がともに成り立つとすると、この二つの集合はいわば「互いに相手を含んでいる」わけです。この状態を「AとBが等しい」と表現するのは自然ではないでしょうか。

具体例を見ていきましょう。

(例1) A={1,2,3,4}、B={1、2}、C={3,4}のとき、A=B∪Cが成り立ちます。

(例2) Ω={1,2,3,4,5}、A={1,3,5}、B={2,4}のとき、B= が成り立ちます。

この定義から、与えられた集合AとBが等しいことを示すためには、A⊂BとB⊂Aを示す必要があるわけです。一見まどろっこしいようですが、次の問題でこの定義の使い方を見てみます。

(例3) 集合A、Bを

A={ x | x は、ある整数aとbを用いて x = 3a + 7b と表される数である }
B={ y | y は、ある整数cとdを用いて、y = 4c + 5d と表される数である }

と定義します。このとき、実はA=Bなのですが、一息で「等しい」ことを言うことは難しそうですね。そこで、(1)A⊂B と (2)B⊂A とにわけて、それぞれを示すのです。

(1) A⊂Bの証明:Aに属する要素 x は、x = 3a + 7b という形で表せます。ここで、a と b がどんな整数であるかは、x の取り出し方によって変わるので正体不明です。さて、このxの式を変形すると、

x = 3a + 7b = 4( 2a + 3b ) + 5( -a - b )

となりますが、右辺を良く見ると、「4▲+5■」という形をしていますね。このことは、「x がBの要素でもある」ことを示しています。どの x ∈Aをとってきても、上の変形によって x ∈Bであるわけです。よってA⊂Bが示されました。

(2) B⊂Aの証明:(1)と同様の手法です。Bに属する要素 y は、 y = 4c + 5d と表せます。この y の式を変形すると、

y = 4c + 5d = 3( -c - 3d ) + 7( c + 2d )

となります。この右辺は、「3▲+7■」という形をしています。したがって、「y がAの要素でもある」ことが示されました。どの y ∈Bをとってきても、上の変形によって y ∈Aであるわけです。よってB⊂Aが示されました。

(1)(2)からA=Bとなることがわかりました。「どうやって上の変形を思いつくのか?」という声も聞こえてきそうですが、とりあえず「思い付きです」としておきましょう^^ただ、数学の「線形代数」あるいは「環論」を学ぶと、上の変形は自然に感じられるようになります。

一般に、与えられた二つの集合AとBが等しいことを判定するのに、何か「これさえあれば大丈夫」といった公式はありません。数学の分野によっては、いまだに等しいことが(あるいは、等しくないことが)証明されていない2つの集合もあるのです。

[解説・ドモルガンの法則]

上で学んだ「集合の一致」の定義を用いて、次の有名な定理を示してみましょう。

証明に先立って、下の図でこの定理の意味を見てみましょう。図で見るとわかるように、ほとんど明らかですね。

この定理を、(1) と、(2) とにわけて証明してみましょう。

(1)の証明: x ∈をとると、補集合の意味から、x は A∩Bの要素ではありません。したがって、x はAの要素ではないか、またはBの要素でないかのいずれかは成り立ちます(そうでないと、x はA、B両方に含まれることになってしまいます)。よって、x ∈が成り立ちます。
結局、すべての x ∈に対して、x がの要素でもあることが示されましたから、が成り立ちます。

(2)の証明:x ∈をとると、x はまたはの少なくとも一方には属しています。いま、かりに x ∈とすると、x はAに含まれないのですから、当然A∩Bにも含まれません。したがって x ∈が成り立ちます。同様に、かりに x ∈とすると、x はBに含まれないのですから、当然A∩Bにも含まれません。したがって、やはり x ∈が成り立ちます。
結局、すべての x ∈に対して、x がの要素でもあることが示されましたから、が成り立ちます。

以上のように証明できました。「図で見たほうがよっぽどわかりやすい!」とお思いの方もいることでしょう。確かに図は直感的な理解の助けになりますが、扱う集合の個数が増えてきたりすると(無限個かもしれません!)、図示が困難だったり、そもそも図にかけない場合がでてくるかもしれません。
上で扱ったような論法は、そのような場合にも威力を発揮するのです。

(例4) Ωを「ある学級の生徒全体」とし、

A={ x | x ∈Ωで、x はパソコンを持っている }
B={ x | x ∈Ωで、x は下駄を持っている }

とします。このとき、


={ x | x ∈Ωで、x はパソコンか下駄かの少なくとも一方を持っていない }
と表せます。補集合がからんだ集合の演算を、「少なくとも〜」という表現で表すことが多いです。

また、上の定理と同様に次も成り立ちます。(これもド・モルガンの法則と呼びます)

やはり図を描けばほとんど明らかですね^^証明も上と同様にしてできます。
次節では、このド・モルガンの法則のような、一般の集合に対して成立するいくつかの関係式について見ていきます。