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

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

mathdiscrete-mathset-operationlecture

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.

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.

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

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$ ".

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.

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

6.1Problem

For subsets $A, B$ of a universal set全体集合ぜんたいしゅうごう $U$ , prove $(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}$ .

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.

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.

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.

10Exercise link

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