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

date2026-07-14document_iddoc_d461d0f391135f5db5f6f49f46c80085description和集合、共通部分、差集合、補集合を、条件の論理演算として読み替え、包含関係と集合等式の証明へ接続する講義である。prerequisites命題・述語と量化 / 証明法と反例 / 集合の基本type講義content_typelecturestatusactive

mathdiscrete-mathset-operationlecture

Set operations集合演算しゅうごうえんざん and inclusion relations包含関係ほうがんかんけい

1導入どうにゅう

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

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

1Introduction

The important point in set operations集合演算しゅうごうえんざん is not coloring regions in a diagram, but transforming the condition条件じょうけん that an element元げん satisfies. Union和集合わしゅうごう corresponds to "or", intersection共通部分きょうつうぶぶん corresponds to "and", and complement補集合ほしゅうごう corresponds to "not".

Once this correspondence is fixed, De Morgan's lawsド・モルガンの法則 and the distributive law分配法則ぶんぱいほうそく are not memorized rules. They are derived by transforming logical conditions.

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

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

A \cup B = {x ∣ x \in A または x \in B}

A \cap B = {x ∣ x \in A かつ x \in B}

A ∖ B = {x ∣ x \in A かつ x \notin B}

で定義ていぎする。

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

A^{c} = U ∖ A = {x \in U ∣ x \notin A}

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

2Terms and definitions

For sets集合しゅうごう $A, B$ , define union和集合わしゅうごう, intersection共通部分きょうつうぶぶん, and set difference差集合さしゅうごう by

A \cup B = {x ∣ x \in A or x \in B}

A \cap B = {x ∣ x \in A and x \in B}

A ∖ B = {x ∣ x \in A and x \notin B}

After fixing a universal set全体集合ぜんたいしゅうごう $U$ , the complement補集合ほしゅうごう of $A$ is

A^{c} = U ∖ A = {x \in U ∣ x \notin A} .

The complement depends on which universal set is being used. If this premise is omitted, the same $A$ can have different complements.

3方針ほうしん

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

x \in A かつ (x \in B または x \in C)

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

(x \in A かつ x \in B) または (x \in A かつ x \in C)

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

data/lecture/math/discrete-math/set-basics.lecture.n.md

3Method

To prove an identity of set operations集合演算しゅうごうえんざん, take arbitrary $x$ and translate the statement into a membership condition. For example, $x \in A \cap (B \cup C)$ means

x \in A and (x \in B or x \in C) .

Using the distributive law分配法則ぶんぱいほうそく of logic, this becomes

(x \in A and x \in B) or (x \in A and x \in C),

which is equivalent to $x \in (A \cap B) \cup (A \cap C)$ .

data/lecture/math/discrete-math/set-basics.lecture.n.md

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

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

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

(A \cup B)^{c} = A^{c} \cap B^{c}, (A \cap B)^{c} = A^{c} \cup B^{c}

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

4Intuitive explanation

A set operation集合演算しゅうごうえんざん is a way to view a combination of conditions条件じょうけん as a set. The set $A \cup B$ consists of objects that have the label $A$ or the label $B$ . The set $A \cap B$ consists of objects that have both labels. The set $A ∖ B$ consists of objects that have label $A$ but not label $B$ .

In this view, De Morgan's lawsド・モルガンの法則

(A \cup B)^{c} = A^{c} \cap B^{c}, (A \cap B)^{c} = A^{c} \cup B^{c}

are natural. The negation of "in $A$ or in $B$ " is "not in $A$ and not in $B$ ". The negation of "in $A$ and in $B$ " is "not in $A$ or not in $B$ ".

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

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

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

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

5Rigorous explanation

The statement $A \subseteq B$ means that, for every $x$ , $x \in A \Rightarrow x \in B$ holds. Therefore a proof of an inclusion relation包含関係ほうがんかんけい must make the starting point and the target clear.

For example, $A \cap B \subseteq A$ is proved in one sentence: take arbitrary $x \in A \cap B$ . Then $x \in A$ and $x \in B$ , so in particular $x \in A$ .

On the other hand, $A \subseteq A \cup B$ is proved as follows. Take arbitrary $x \in A$ . Then $x \in A$ or $x \in B$ is true, so $x \in A \cup B$ . Here no information about $x \in B$ is needed because an "or" statement is true when one side is true.

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

6Worked example: proving De Morgan's law by elements

6.1問題もんだい

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

6.1Problem

For subsets $A, B$ of a universal set全体集合ぜんたいしゅうごう $U$ , prove $(A \cup B)^{c} = A^{c} \cap B^{c}$ .

6.2解説かいせつ

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

x \in (A \cup B)^{c} ⟺ x \notin A \cup B

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

x \notin A \cup B ⟺ (x \notin A かつ x \notin B)

である。これは

x \in A^{c} かつ x \in B^{c}

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

6.2Explanation

Take arbitrary $x \in U$ . Then

x \in (A \cup B)^{c} ⟺ x \notin A \cup B .

By the definition of union和集合わしゅうごう, $x \notin A \cup B$ means that it is not true that $x \in A$ or $x \in B$ . Hence

x \notin A \cup B ⟺ (x \notin A and x \notin B) .

This is equivalent to

x \in A^{c} and x \in B^{c},

that is, $x \in A^{c} \cap B^{c}$ . Since the equivalence holds for every $x$ , extensionality外延性がいえんせい gives $(A \cup B)^{c} = A^{c} \cap B^{c}$ .

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

操作そうさ	変かわるもの	保存ほぞんされるもの
$A \cup B$	条件じょうけんを「または」で緩ゆるめる	$A$ と $B$ の元げんelementはすべて含ふくむ
$A \cap B$	条件じょうけんを「かつ」で厳きびしくする	両方りょうほうに属ぞくする元げんelementだけを残のこす
$A ∖ B$	$B$ に属ぞくする元げんelementを除のぞく	$A$ の外そとの元げんelementは追加ついかしない
$A^{c}$	視点してんを $A$ の外側そとがわへ移うつす	全体集合ぜんたいしゅうごうuniversal set $U$ は固定こていする

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

7What changes and what is preserved

Operation	What changes	What is preserved
$A \cup B$	The condition is weakened by "or"	All elements元げん of $A$ and $B$ are included
$A \cap B$	The condition is tightened by "and"	Only elements belonging to both sets remain
$A ∖ B$	Elements belonging to $B$ are removed	No element outside $A$ is added
$A^{c}$	The viewpoint moves outside $A$	The universal set全体集合ぜんたいしゅうごう $U$ is fixed

Union和集合わしゅうごう and intersection共通部分きょうつうぶぶん combine membership conditions. A complement補集合ほしゅうごう instead depends on the universal set, and De Morgan's lawsド・モルガンの法則 interchange the logical connectives.

8見分みわけ方かた

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

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

8How to distinguish the ideas

If the condition contains "or", think of a union和集合わしゅうごう.
If the condition contains "and", think of an intersection共通部分きょうつうぶぶん.
If the condition contains "not", think of a complement補集合ほしゅうごう or a set difference差集合さしゅうごう.
When using a complement, first check what the universal set全体集合ぜんたいしゅうごう is.

To distinguish the operations, place the membership conditions for the left and right sides next to each other for an arbitrary $x$ . A Venn diagramVenn図べんず can suggest the result, but a proof should write the logical equivalences between the conditions.

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

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

A \subseteq B

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

A \cup C \subseteq B \cup C, A \cap C \subseteq B \cap C

が成立せいりつする。

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

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

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

A \subseteq B ⟹ U ∖ B \subseteq U ∖ A

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

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

9Proof supplement: why set operations preserve inclusion

Here we prove concretely what preservation保存ほぞん means. Assume

A \subseteq B .

Then, for every set $C$ ,

A \cup C \subseteq B \cup C, A \cap C \subseteq B \cap C

hold.

To prove the first inclusion, take $x \in A \cup C$ . Then $x \in A$ or $x \in C$ . If $x \in A$ , then $x \in B$ by $A \subseteq B$ , hence $x \in B \cup C$ . If $x \in C$ , then again $x \in B \cup C$ . Therefore $A \cup C \subseteq B \cup C$ .

Next take $x \in A \cap C$ . Then $x \in A$ and $x \in C$ . Since $A \subseteq B$ , we have $x \in B$ , so $x \in B \cap C$ . Therefore $A \cap C \subseteq B \cap C$ .

For complements, the direction reverses. If the universal set $U$ is fixed, then

A \subseteq B ⟹ U ∖ B \subseteq U ∖ A .

Indeed, if $x \in U ∖ B$ , then $x \notin B$ . If $x \in A$ were true, then $A \subseteq B$ would imply $x \in B$ , a contradiction. Hence $x \notin A$ , so $x \in U ∖ A$ .

This proof is also practice in reading set operations not as symbol manipulation, but as conditions on whether an element belongs to a set.

10演習えんしゅうリンク

data/exercise/math/discrete-math/sets-and-set-operations.exercise.n.md

10Exercise link