Basics of sets集合しゅうごう

date2026-07-14document_iddoc_df3d016f09b51e6d16617f93dff49281description集合を、対象を条件で集めて議論するための基本言語として導入し、元、空集合、部分集合、外延性を整理する講義である。prerequisites命題・述語と量化 / 証明法と反例type講義content_typelecturestatusactive

mathdiscrete-mathsetlecture

1Introduction

The first question to fix when studying sets集合しゅうごう is this: what are we treating as one collection, and what are we treating as a different collection? A set is not merely a bag. It is a language for collecting objects対象たいしょう that satisfy a condition条件じょうけん and then reasoning by whether each object is included.

This lecture organizes elements元げん, membership所属しょぞく, the empty set空集合くうしゅうごう, subsets部分集合ぶぶんしゅうごう, and extensionality外延性がいえんせい. If this point is vague, later topics such as relations関係かんけい, maps写像しゃぞう, and power sets冪集合べきしゅうごう become confusing because one loses track of whether something is an element or a subset.

For a set集合しゅうごう, only membership matters, not order or repetition. Thus two sets with the same elements元げん are equal even if their elements are written in a different order or repeated in the notation.

2Terms and definitions

A set集合しゅうごう is a collection of objects対象たいしょう. We write

x \in A

when an object $x$ is contained in a set $A$ , and we call $x$ an element元げん of $A$ . The notation $x \notin A$ means that $x$ is not an element of $A$ .

The empty set空集合くうしゅうごう $[PARSE ERROR: Undefined("Command(\"varnothing\")")]$ is the set with no elements. It is not a nonexistent set; it is an existing set that contains no elements.

A subset部分集合ぶぶんしゅうごう expresses inclusion包含ほうがん. The statement $A \subseteq B$ means that, for every $x$ ,

x \in A ⟹ x \in B

holds. Here $A \subseteq B$ allows $A = B$ . The notation $A ⊊ B$ means $A \subseteq B$ and $A \neq B$ .

3Method

When working with sets集合しゅうごう, do not decide only from a picture or intuition. First take an arbitrary element元げん $x$ and transform the condition $x \in A$ into another membership condition.

This method is simple but powerful. To prove a set equality $A = B$ , it is enough to prove

A \subseteq B and B \subseteq A .

This checks that the two sets have exactly the same elements from both directions.

To prove an inclusion包含ほうがん $A \subseteq B$ , take an arbitrary $x$ , assume $x \in A$ , and derive $x \in B$ . Checking a few examples can suggest a conjecture, but a proof must use logic that covers every element元げん.

4Intuitive explanation

It is useful to imagine a set集合しゅうごう as a collection of objects carrying a label. The statement $x \in A$ says that $x$ has the label $A$ . The statement $A \subseteq B$ says that every object with label $A$ also has label $B$ .

From this point of view, the empty set空集合くうしゅうごう is an empty box. Therefore it is a subset部分集合ぶぶんしゅうごう of every set $A$ . There is no $x$ with $x \in [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ , so the conditional statement "if $x \in [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ , then $x \in A$ " has no counterexample.

5Rigorous explanation

The identity of a set集合しゅうごう is determined by extensionality外延性がいえんせい. Extensionality is the principle that if

x \in A ⟺ x \in B

holds for every $x$ , then $A = B$ . In other words, a set is determined by its elements, not by the way it was written.

For example,

A = {1, 2, 3}, B = {3, 2, 1, 1}

still gives $A = B$ . In a set, order and repetition are not recorded. If order must be recorded, use an ordered pair順序対じゅんじょつい or a sequence列れつ. If repetition must be recorded, use a multiset多重集合たじゅうしゅうごう.

By extensionality外延性がいえんせい, two sets with the same elements元げん are the same set. A rigorous comparison therefore uses membership conditions, not names or notation.

6Worked example: checking a subset relation from the definition

6.1Problem

Let $A = {2, 4, 6}$ and $B = {n \in Z ∣ n isevenand 1 [PARSE ERROR: Undefined("Command(\"le\")")] n [PARSE ERROR: Undefined("Command(\"le\")")] 6}$ . Prove $A = B$ .

6.2Explanation

A set equality is proved by proving inclusion包含ほうがん in both directions.

First take $x \in A$ . Then $x$ is one of $2, 4, 6$ . Each of these is an integer整数せいすう, is an even number偶数ぐうすう, and satisfies $1 [PARSE ERROR: Undefined("Command(\"le\")")] x [PARSE ERROR: Undefined("Command(\"le\")")] 6$ . Hence $x \in B$ , so $A \subseteq B$ .

Conversely, take $x \in B$ . Then $x$ is an even integer satisfying $1 [PARSE ERROR: Undefined("Command(\"le\")")] x [PARSE ERROR: Undefined("Command(\"le\")")] 6$ . Therefore $x$ is one of $2, 4, 6$ , so $x \in A$ . Hence $B \subseteq A$ .

Both inclusions hold, so $A = B$ . This example checks the central point of this page: sets are compared by equality of elements, not by the surface form of their descriptions.

7What changes and what is preserved

Operation or viewpoint	What changes	What is preserved
Rewriting in set-builder notation内包的記法ないほうてききほう	The form of the description	The whole collection of elements元げん
Rewriting in roster notation外延的記法がいえんてききほう	The way the elements are listed	The set集合しゅうごう itself
Reordering the list	The written order	The set集合しゅうごう itself
Listing an element repeatedly	The visual appearance	Whether each element元げん is present

Notation and the way a condition is written may change; what must be preserved is the truth value of membership for every object対象たいしょう. The same viewpoint is used later when comparing sets obtained by set operations集合演算しゅうごうえんざん.

8How to distinguish the ideas

If the question is whether $x \in A$ , it is a question about membership所属しょぞく.
If the question is whether $A \subseteq B$ , start from an arbitrary $x \in A$ and derive $x \in B$ .
If the question is whether $A = B$ , check $A \subseteq B$ and $B \subseteq A$ separately.
If order or repetition matters, a plain set集合しゅうごう does not contain enough information.

When in doubt, rewrite the conditions for whether a candidate element元げん $x$ belongs to the left and right sides. A single counterexample反例はんれい disproves an inclusion, whereas equality requires inclusions in both directions.

9Exercise link

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