集合しゅうごうと写像しゃぞうの基本きほん

date2026-07-14document_iddoc_b74e514fff9b51f3ab8732d3410fb63ddescription集合の演算と写像の基本概念を厳密に定義し、アルゴリズムとグラフを記述するための基礎を構成する。prerequisites離散数学への導入 / 論理と真理値表の基本type講義statusactive

informationdiscrete-mathundergraduatelecture

1導入どうにゅう

この講義こうぎでは、集合しゅうごうの基本演算きほんえんざんと写像しゃぞうの性質せいしつを定義ていぎし、アルゴリズムの入出力にゅうしゅつりょくやグラフの頂点集合ちょうてんしゅうごうを記述きじゅつするための基礎きそを構成こうせいする。

2集合しゅうごうと包含ほうがん

集合しゅうごうとは、対象たいしょうを要素ようそとしてまとめたものである。 $x$ が集合しゅうごう $A$ の要素ようそであることを $x \in A$ 、要素ようそでないことを $x \notin A$ と記しるす。要素ようそを一ひとつも持もたない集合しゅうごうを空集合くうしゅうごうといい、 $[PARSE ERROR: Undefined("Command(\"varnothing\")")]$ と記しるす。

任意にんいの $x$ について $x \in A$ ならば $x \in B$ であるとき、 $A$ は $B$ の部分集合ぶぶんしゅうごうであるといい、 $A \subseteq B$ と記しるす。 $A \subseteq B$ かつ $B \subseteq A$ であることと $A = B$ であることは同値どうちである。

3集合演算しゅうごうえんざん

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

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}

と定義ていぎする。補集合ほしゅうごうには、考察対象こうさつたいしょうを含ふくむ全体集合ぜんたいしゅうごう $U$ の指定していが必要ひつようである。 $A \subseteq U$ の補集合ほしゅうごうは

A^{c} = U ∖ A

である。したがって、全体集合ぜんたいしゅうごうを変更へんこうすれば補集合ほしゅうごうも変化へんかする。

集合しゅうごう $A, B$ の直積ちょくせきは、順序対じゅんじょついの集合しゅうごう

A \times B = {(a, b) ∣ a \in A, b \in B}

である。一般いっぱんには $(a, b) \neq (b, a)$ であり、順序じゅんじょを区別くべつする。

4関係かんけい

集合しゅうごう $A, B$ の二項関係にこうかんけい $R$ とは、直積ちょくせきの部分集合ぶぶんしゅうごう $R \subseteq A \times B$ である。 $(a, b) \in R$ のとき、 $a$ と $b$ の間あいだに関係かんけい $R$ が成立せいりつするといい、 $a R b$ とも記しるす。 $A = B$ の場合ばあいは、 $A$ 上じょうの関係かんけいという。

有向ゆうこうグラフの辺集合へんしゅうごう $E \subseteq V \times V$ は、頂点集合ちょうてんしゅうごう $V$ 上じょうの二項関係にこうかんけいである。無向むこうグラフでは端点たんてんの順序じゅんじょを区別くべつせず、二要素部分集合にようそぶぶんしゅうごう ${u, v}$ を辺へんとして使用しようする。この相違そういは、後続こうぞくするグラフの講義こうぎで厳密げんみつに定義ていぎする。

5写像しゃぞう

集合しゅうごう $A, B$ に対たいして、写像しゃぞう $f : A \to B$ とは、 $A$ の各要素かくようそ $a$ に $B$ の要素ようそをただ一ひとつ対応たいおうさせる規則きそくである。 $A$ を定義域ていぎいき、 $B$ を終域しゅういきといい、 $a$ に対応たいおうする要素ようそを $f (a)$ と記しるす。定義域ていぎいきの全要素ぜんようそに値あたいが指定していされ、しかも各要素かくようその値あたいが一意いちいであることが必要ひつようである。

部分集合ぶぶんしゅうごう $S \subseteq A$ の像ぞうと、 $T \subseteq B$ の逆像ぎゃくぞうを

f (S) = {f (a) ∣ a \in S}, f^{- 1} (T) = {a \in A ∣ f (a) \in T}

と定義ていぎする。特とくに $f (A)$ を $f$ の像ぞうという。 $f (A) \subseteq B$ であり、像ぞうと終域しゅういきは必かならずしも一致いっちしない。また、 $f^{- 1} (T)$ という記法きほうは、 $f$ が逆写像ぎゃくしゃぞうを持もたない場合ばあいにも使用しようできる。

6単射たんしゃ・全射ぜんしゃ・全単射ぜんたんしゃ

写像しゃぞう $f : A \to B$ が単射たんしゃであるとは、

f (a_{1}) = f (a_{2}) ⟹ a_{1} = a_{2}

がすべての $a_{1}, a_{2} \in A$ について成立せいりつすることである。すなわち、異ことなる入力にゅうりょくは異ことなる出力しゅつりょくを持もつ。

$f$ が全射ぜんしゃであるとは、すべての $b \in B$ に対たいして $f (a) = b$ となる $a \in A$ が存在そんざいすることである。これは $f (A) = B$ と同値どうちである。単射たんしゃかつ全射ぜんしゃである写像しゃぞうを全単射ぜんたんしゃという。全単射ぜんたんしゃに限かぎり、各かく $b \in B$ をその唯一ゆいいつの原像げんぞうへ対応たいおうさせる逆写像ぎゃくしゃぞう $f^{- 1} : B \to A$ が存在そんざいする。

7例れい

$A = {1, 2, 3}$ 、 $B = {a, b, c, d}$ とし、

f (1) = a, f (2) = b, f (3) = b

とする。このとき $f (A) = {a, b}$ であり、 $f^{- 1} ({b, c}) = {2, 3}$ である。 $f (2) = f (3)$ なので $f$ は単射たんしゃでなく、 $c, d$ が像ぞうに含ふくまれないので全射ぜんしゃでもない。

8情報科学じょうほうかがくへの接続せつぞく

長ながさ $n$ の配列はいれつは、添字集合そえじしゅうごう ${0, 1, \dots, n - 1}$ から値あたいの終域しゅういきへの写像しゃぞうとして表現ひょうげんできる。各入力かくにゅうりょくに出力しゅつりょくが一意いちいに定さだまる決定的けっていてきなアルゴリズムは、許容入力集合きょようにゅうりょくしゅうごうから出力集合しゅつりょくしゅうごうへの写像しゃぞうとして仕様化しようかできる。複数ふくすうの正解せいかいを許容きょようする問題もんだいの出力仕様しゅつりょくしようは、入力にゅうりょくと許容出力きょようしゅつりょくの関係かんけいとして表現ひょうげんできる。一方いっぽう、グラフ $G = (V, E)$ は、頂点集合ちょうてんしゅうごう $V$ と、直積ちょくせきまたは $V$ の二要素部分集合にようそぶぶんしゅうごうからなる辺集合へんしゅうごう $E$ によって記述きじゅつされる。

data/lecture/information/algorithm/algorithms-portal.lecture.n.md data/lecture/information/graph/graph-basics.lecture.n.md

9まとめ

集合しゅうごうは要素ようその所属しょぞくによって定さだまり、 $A \subseteq B$ は任意にんいの $x$ について $x \in A \Rightarrow x \in B$ が成立せいりつすることを意味いみする。
補集合ほしゅうごうの定義ていぎには全体集合ぜんたいしゅうごうが必要ひつようであり、直積ちょくせきでは順序じゅんじょを区別くべつする。
写像しゃぞうは定義域ていぎいきの各要素かくようそに終域しゅういきの要素ようそを一意いちいに対応たいおうさせる。
単射たんしゃでは異ことなる入力にゅうりょくが異ことなる出力しゅつりょくに対応たいおうし、全射ぜんしゃでは終域しゅういきの全要素ぜんようそが像ぞうに含ふくまれ、全単射ぜんたんしゃでは一対一対応いちたいいちたいおうが成立せいりつする。

Sets and Maps

1Introduction

This lecture defines the basic operations on sets and the principal properties of maps. These concepts provide the language for specifying algorithmic input and output and for defining the vertex set of a graph.

2Sets and inclusion

A set is a collection of objects called its elements. The notation $x \in A$ states that $x$ is an element of $A$ , whereas $x \notin A$ states that it is not. The empty set, denoted by $[PARSE ERROR: Undefined("Command(\"varnothing\")")]$ , has no elements.

A set $A$ is a subset of a set $B$ , written $A \subseteq B$ , if $x \in A$ implies $x \in B$ for every $x$ . The conjunction of $A \subseteq B$ and $B \subseteq A$ is equivalent to $A = B$ .

3Operations on sets

For sets $A$ and $B$ , their union, intersection, and difference are defined 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} .

A complement requires a specified universal set $U$ containing the objects under consideration. For $A \subseteq U$ , the complement of $A$ is

A^{c} = U ∖ A .

Changing the universal set can therefore change the complement.

The Cartesian product of sets $A$ and $B$ is the set of ordered pairs

A \times B = {(a, b) ∣ a \in A, b \in B} .

Order matters: in general, $(a, b) \neq (b, a)$ .

4Relations

A binary relation $R$ from a set $A$ to a set $B$ is a subset $R \subseteq A \times B$ of their Cartesian product. If $(a, b) \in R$ , we say that $a$ is related to $b$ by $R$ and may write $a R b$ . When $A = B$ , this is called a relation on $A$ .

The edge set $E \subseteq V \times V$ of a directed graph is a binary relation on its vertex set $V$ . In an undirected graph, the order of endpoints is ignored, and a two-element subset ${u, v}$ is used as an edge. The following graph lecture defines this distinction precisely.

5Maps

For sets $A$ and $B$ , a map $f : A \to B$ is a rule that assigns exactly one element of $B$ to every element $a$ of $A$ . The set $A$ is the domain, the set $B$ is the codomain, and the assigned element is denoted by $f (a)$ . Thus every domain element must receive a value, and that value must be unique.

For $S \subseteq A$ and $T \subseteq B$ , the image of $S$ and the preimage of $T$ are

f (S) = {f (a) ∣ a \in S}, f^{- 1} (T) = {a \in A ∣ f (a) \in T} .

In particular, $f (A)$ is the image of the map. Although $f (A) \subseteq B$ , the image need not equal the codomain. The notation $f^{- 1} (T)$ for a preimage remains valid even when $f$ has no inverse map.

6Injective, surjective, and bijective maps

A map $f : A \to B$ is injective if

f (a_{1}) = f (a_{2}) ⟹ a_{1} = a_{2}

for all $a_{1}, a_{2} \in A$ . Equivalently, distinct inputs have distinct outputs.

The map is surjective if, for every $b \in B$ , there exists $a \in A$ such that $f (a) = b$ . This condition is equivalent to $f (A) = B$ . A map that is both injective and surjective is bijective. Exactly for a bijection, there is an inverse map $f^{- 1} : B \to A$ that assigns each $b \in B$ its unique preimage.

7Example

Let $A = {1, 2, 3}$ and $B = {a, b, c, d}$ , and define

f (1) = a, f (2) = b, f (3) = b .

Then $f (A) = {a, b}$ and $f^{- 1} ({b, c}) = {2, 3}$ . Because $f (2) = f (3)$ , the map is not injective. Because $c$ and $d$ do not belong to its image, it is not surjective either.

8Connections to computer science

An array of length $n$ can be represented as a map from the index set ${0, 1, \dots, n - 1}$ to a codomain of values. A deterministic algorithm whose output is uniquely determined for every input can be specified as a map from its set of admissible inputs to its set of outputs. When a problem permits more than one correct output, its output specification can instead be represented as a relation between inputs and admissible outputs. A graph $G = (V, E)$ is described by a vertex set $V$ and an edge set $E$ whose elements are ordered pairs in a Cartesian product or two-element subsets of $V$ .

data/lecture/information/algorithm/algorithms-portal.lecture.n.md data/lecture/information/graph/graph-basics.lecture.n.md

9Summary

A set is determined by element membership, and $A \subseteq B$ means that $x \in A \Rightarrow x \in B$ holds for every $x$ .
A complement requires a universal set, while a Cartesian product distinguishes the order of its coordinates.
A map assigns exactly one codomain element to every domain element.
Under an injective map, distinct inputs have distinct outputs; under a surjective map, every codomain element lies in the image; and a bijection gives a one-to-one correspondence.