集合演算しゅうごうえんざんset operationと包含関係ほうがんかんけいinclusion relation

1導入どうにゅう

集合演算しゅうごうえんざんset operationで重要じゅうようなのは、図形ずけいの領域りょういきを塗ぬることではなく、元げんelementが満みたす条件じょうけんconditionを論理的ろんりてきに変形へんけいすることである。和集合わしゅうごうunionは「または」、共通部分きょうつうぶぶんintersectionは「かつ」、補集合ほしゅうごうcomplementは「でない」に対応たいおうする。

この対応たいおうを先さきに押おさえると、ド・モルガンの法則ほうそくDe Morgan's lawsや分配法則ぶんぱいほうそくdistributive lawは暗記あんきではなく、条件じょうけんconditionの変形へんけいとして導みちびかれる。

2用語ようごと定義ていぎ

集合しゅうごうset $$A,B$$A,B に対たいして、和集合わしゅうごうunion、共通部分きょうつうぶぶんintersection、差集合さしゅうごうset differenceを

で定義ていぎする。

全体集合ぜんたいしゅうごうuniversal set $$U$$U を固定こていしたとき、$$A$$A の補集合ほしゅうごうcomplementは

である。補集合ほしゅうごうcomplementは、どの全体集合ぜんたいしゅうごうuniversal setを見みているかに依存いぞんする。この前提ぜんていを省略しょうりゃくすると、同おなじ $$A$$A でも $$A^c$$A^c が変かわる。

3方針ほうしん

集合演算しゅうごうえんざんset operationの式しきを証明しょうめいするときは、任意にんいの $$x$$x を取とり、$$x\in$$x\in で始はじまる条件じょうけんへ翻訳ほんやくする。たとえば $$x\in A\cap (B\cup C)$$x\in A\cap(B\cup C) は

という命題めいだいである。ここから論理ろんりの分配法則ぶんぱいほうそくdistributive lawを用もちいれば、

となる。これは $$x\in (A\cap B)\cup (A\cap C)$$x\in(A\cap B)\cup(A\cap C) と同値どうちである。

4直感的ちょっかんてきな説明せつめい

集合演算しゅうごうえんざんset operationは、条件じょうけんconditionの結合けつごうを集合しゅうごうsetの形かたちで見みる方法ほうほうである。$$A\cup B$$A\cup B は「$$A$$A の名札なふだまたは $$B$$B の名札なふだを持もつもの」、$$A\cap B$$A\cap B は「$$A$$A と $$B$$B の両方りょうほうの名札なふだを持もつもの」、$$A\setminus B$$A\setminus B は「$$A$$A の名札なふだは持もつが $$B$$B の名札なふだは持もたないもの」である。

この見方みかたでは、ド・モルガンの法則ほうそくDe Morgan's laws

は自然しぜんである。「$$A$$A または $$B$$B に入はいる」の否定ひていは、「$$A$$A に入はいらず、かつ $$B$$B に入はいらない」である。「$$A$$A かつ $$B$$B に入はいる」の否定ひていは、「$$A$$A に入はいらない、または $$B$$B に入はいらない」である。

5厳密げんみつな説明せつめい

$$A\subseteq B$$A\subseteq B とは、任意にんいの $$x$$x について $$x\in A\Rightarrow x\in B$$x\in A\Rightarrow x\in B が成立せいりつすることである。したがって、包含関係ほうがんかんけいinclusion relationの証明しょうめいでは、出発点しゅっぱつてんと到達点とうたつてんを明確めいかくにする。

たとえば $$A\cap B\subseteq A$$A\cap B\subseteq A は、任意にんいの $$x\in A\cap B$$x\in A\cap B を取とると $$x\in A$$x\in A かつ $$x\in B$$x\in B なので、とくに $$x\in A$$x\in A である、という一文いちぶんで証明しょうめいできる。

一方いっぽう、$$A\subseteq A\cup B$$A\subseteq A\cup B は、任意にんいの $$x\in A$$x\in A を取とると、$$x\in A$$x\in A または $$x\in B$$x\in B が成立せいりつするため $$x\in A\cup B$$x\in A\cup B である、という構造こうぞうである。ここで $$x\in B$$x\in B は不要ふようである。「または」は片方かたほうが真しんなら真しんである。

6例題れいだい：ド・モルガンの法則ほうそくDe Morgan's lawsを元げんelementで証明しょうめいする

6.1問題もんだい

全体集合ぜんたいしゅうごうuniversal set $$U$$U の部分集合ぶぶんしゅうごうsubset $$A,B$$A,B について、$$(A\cup B{)}^c=A^c\cap B^c$$(A\cup B)^c=A^c\cap B^c を示しめせ。

6.2解説かいせつ

任意にんいの $$x\in U$$x\in U を取とる。すると

である。和集合わしゅうごうunionの定義ていぎより、$$x\notin A\cup B$$x\notin A\cup B は「$$x\in A$$x\in A または $$x\in B$$x\in B ではない」という意味いみである。したがって

である。これは

と同値どうちであり、すなわち $$x\in A^c\cap B^c$$x\in A^c\cap B^c である。任意にんいの $$x$$x について同値どうちが成立せいりつするので、外延性がいえんせいextensionalityより $$(A\cup B{)}^c=A^c\cap B^c$$(A\cup B)^c=A^c\cap B^c である。

7変かわるものと保存ほぞんされるもの

和集合わしゅうごうunionと共通部分きょうつうぶぶんintersectionは所属条件しょぞくじょうけんを組くみ合あわせる操作そうさである。一方いっぽう、補集合ほしゅうごうcomplementは全体集合ぜんたいしゅうごうに依存いぞんし、ド・モルガンの法則De Morgan's lawsでは論理結合ろんりけつごうの向むきが入いれ替かわる。

8見分みわけ方かた

• 条件じょうけんに「または」が表あらわれたら、和集合わしゅうごうunionを考かんがえる。
• 条件じょうけんに「かつ」が表あらわれたら、共通部分きょうつうぶぶんintersectionを考かんがえる。
• 条件じょうけんに「でない」が表あらわれたら、補集合ほしゅうごうcomplementまたは差集合さしゅうごうset differenceを考かんがえる。
• 補集合ほしゅうごうcomplement を用もちいるときは、全体集合ぜんたいしゅうごうuniversal setが何なにかを確認かくにんする。

見分みわけるときは、任意にんいの $$x$$x について左辺さへんの所属条件しょぞくじょうけんと右辺うへんの所属条件しょぞくじょうけんを並ならべる。Venn図ずVenn diagramは予想よそうを助たすけるが、証明しょうめいでは条件じょうけんの同値変形どうちへんけいを書かく。

9証明しょうめい補足ほそく：集合演算しゅうごうえんざんが包含ほうがんを保たもつ理由りゆう

ここでは、保存ほぞんpreservation という言葉ことばを具体的ぐたいてきに証明しょうめいする。仮定かていは

である。このとき、任意にんいの集合しゅうごう $$C$$C について

が成立せいりつする。

証明しょうめいする。まず $$x\in A\cup C$$x\in A\cup C とする。このとき $$x\in A$$x\in A または $$x\in C$$x\in C である。$$x\in A$$x\in A なら、$$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B である。したがって $$x\in B\cup C$$x\in B\cup C である。$$x\in C$$x\in C の場合ばあいも $$x\in B\cup C$$x\in B\cup C である。よって $$A\cup C\subseteq B\cup C$$A\cup C\subseteq B\cup C である。

つぎに $$x\in A\cap C$$x\in A\cap C とする。このとき $$x\in A$$x\in A かつ $$x\in C$$x\in C である。$$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B なので、$$x\in B\cap C$$x\in B\cap C である。よって $$A\cap C\subseteq B\cap C$$A\cap C\subseteq B\cap C である。

補集合ほしゅうごうでは向むきが反転はんてんする。全体集合ぜんたいしゅうごう $$U$$U を固定こていすると、

である。$$x\in U\setminus B$$x\in U\setminus B なら $$x\notin B$$x\notin B である。もし $$x\in A$$x\in A なら $$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B となり矛盾むじゅんする。したがって $$x\notin A$$x\notin A であり、$$x\in U\setminus A$$x\in U\setminus A である。

この証明しょうめいは、集合演算しゅうごうえんざんを記号きごうの操作そうさとしてではなく、元げんが属ぞくするかどうかの条件じょうけんとして読よむ練習れんしゅうでもある。

10演習えんしゅうリンク

11関連かんれんリンク