直積集合ちょくせきしゅうごうCartesian productの基本きほん

date2026-07-14document_iddoc_20bb474f575682f4f6f5f9adee836187description直積集合を、複数の集合から順序付きの組を作る操作として導入し、座標、表、関係、写像への接続を整理する講義である。prerequisites集合の基本 / 集合演算と包含関係type講義content_typelecturestatusactive

mathdiscrete-mathcartesian-productlecture

Basics of the Cartesian product直積集合ちょくせきしゅうごう

1導入どうにゅう

直積集合ちょくせきしゅうごうCartesian productで最初さいしょに理解りかいすべきことは、「複数ふくすうの選択せんたくを順序じゅんじょつきで一ひとつの対象たいしょうobjectにする」操作そうさだという点てんである。 $A$ から 1 つ、 $B$ から 1 つ選えらんだ結果けっかを、単たんに $a, b$ と並ならべるのではなく、順序対じゅんじょついordered pair $(a, b)$ として記録きろくする。

この順序じゅんじょが重要じゅうようである。 $(a, b)$ と $(b, a)$ は、一般いっぱんには別べつの対象たいしょうobjectである。したがって直積集合ちょくせきしゅうごうCartesian productは、関係かんけいrelation、写像しゃぞうmap、座標ざひょうcoordinate、状態空間じょうたいくうかんstate spaceの共通きょうつうの土台どだいになる。

順序対じゅんじょついordered pairでは成分せいぶんの順番じゅんばんが情報じょうほうの一部いちぶである。そのため、一般いっぱんに $A \times B$ と $B \times A$ は同おなじではなく、第だい 1 成分せいぶんと第だい 2 成分せいぶんの役割やくわりを区別くべつする。

1Introduction

The first thing to understand about the Cartesian product直積集合ちょくせきしゅうごう is that it turns several choices into one ordered object. Choosing one element from $A$ and one from $B$ is not recorded as the unordered list $a, b$ , but as the ordered pair順序対じゅんじょつい $(a, b)$ .

The order is important. In general, $(a, b)$ and $(b, a)$ are different objects. Therefore the Cartesian product is a common foundation for relations関係かんけい, maps写像しゃぞう, coordinates座標ざひょう, and state spaces.

Thus $A \times B$ and $B \times A$ are generally different: the roles of the first and second components must be distinguished.

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

集合しゅうごうset $A, B$ に対たいして、直積集合ちょくせきしゅうごうCartesian product $A \times B$ を

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

で定義ていぎする。ここで $(a, b)$ は順序対じゅんじょついordered pairであり、第だい 1 成分せいぶんが $a$ 、第だい 2 成分せいぶんが $b$ である。

より一般いっぱんに、 $n [PARSE ERROR: Undefined("Command(\"ge\")")] 1$ として $A_{1}, A_{2}, [PARSE ERROR: Undefined("Command(\"dots\")")], A_{n}$ の直積集合ちょくせきしゅうごうCartesian productは

A_{1} \times \dots \times A_{n} = {(a_{1}, [PARSE ERROR: Undefined("Command(\"dots\")")], a_{n}) ∣ a_{i} \in A_{i} forevery i}

である。これは順序付じゅんじょづき組くみordered tupleを集あつめた集合しゅうごうsetである。

2Terms and definitions

For sets $A$ and $B$ , the Cartesian product直積集合ちょくせきしゅうごう $A \times B$ is defined by

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

Here $(a, b)$ is an ordered pair順序対じゅんじょつい; its first component is $a$ and its second component is $b$ .

More generally, for $n [PARSE ERROR: Undefined("Command(\"ge\")")] 1$ and sets $A_{1}, A_{2}, [PARSE ERROR: Undefined("Command(\"dots\")")], A_{n}$ ,

A_{1} \times \dots \times A_{n} = {(a_{1}, [PARSE ERROR: Undefined("Command(\"dots\")")], a_{n}) ∣ a_{i} \in A_{i} forevery i} .

This is the set of ordered tuples[順序付き組].

3方針ほうしん

直積集合ちょくせきしゅうごうCartesian productを扱あつかうときは、元げんが 1 つの値あたいではなく、順序対じゅんじょついordered pairや組くみtupleであることを意識いしきする。したがって $x \in A \times B$ と書かかれていたら、 $x$ を $(a, b)$ と置おき、 $a \in A$ と $b \in B$ を取とり出だす。

この方針ほうしんは、後あとで関係かんけいrelationを理解りかいするときにそのまま使つかう。関係かんけいrelationは $A \times B$ の部分集合ぶぶんしゅうごうsubsetである。つまり、関係かんけいrelationは「どの順序対じゅんじょついordered pairを採用さいようするか」という選択せんたくである。

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

3Strategy

When working with a Cartesian product直積集合ちょくせきしゅうごう, remember that an element is not a single unstructured value. It is an ordered pair or tuple. Thus, if $x \in A \times B$ , write $x = (a, b)$ and extract the facts $a \in A$ and $b \in B$ .

This strategy is used directly when studying relations関係かんけい. A relation is a subset of $A \times B$ . In other words, a relation is a choice of which ordered pairs to accept.

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

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

$A \times B$ は、表ひょうの行ぎょうと列れつcolumnを作つくる操作そうさとして見みると理解りかいしやすい。 $A$ の元げんelementを行ぎょうの見出みだし、 $B$ の元げんelementを列れつcolumnの見出みだしにすると、各かくマスが 1 つの順序対じゅんじょついordered pair $(a, b)$ に対応たいおうする。

たとえば $A = {1, 2}$ 、 $B = {x, y, z}$ なら

A \times B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}

である。この例れいでは $| A | = 2$ 、 $| B | = 3$ なので、 $| A \times B | = 6$ である。有限集合ゆうげんしゅうごうでは一般いっぱんに

| A \times B | = | A | | B |

が成立せいりつする。選択せんたくの段階だんかいが 2 つあり、第だい 1 選択せんたくに $| A |$ 通とおり、第だい 2 選択せんたくに $| B |$ 通とおりあるためである。

4Intuitive explanation: tables and counting

It is often useful to view $A \times B$ as the operation of forming rows and columns of a table. Use the elements of $A$ as row labels and the elements of $B$ as column labels. Each cell corresponds to one ordered pair $(a, b)$ .

For example, if $A = {1, 2}$ and $B = {x, y, z}$ , then

A \times B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)} .

In this example, $| A | = 2$ and $| B | = 3$ , so $| A \times B | = 6$ . For finite sets, in general,

| A \times B | = | A | | B | .

There are two stages of choice: $| A |$ choices for the first component and $| B |$ choices for the second component.

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

順序対じゅんじょついordered pairで本質的ほんしつてきなのは、次つぎの同値性どうちせいである。

(a, b) = (a^{'}, b^{'}) ⟺ (a = a^{'} かつ b = b^{'})

この性質せいしつにより、第だい 1 成分せいぶんと第だい 2 成分せいぶんを別々べつべつに比較ひかくできる。直積集合ちょくせきしゅうごうCartesian productの等式とうしきや包含ほうがんinclusionを示しめすときも、元げんを順序対じゅんじょついordered pairとして分解ぶんかいする。

境界例きょうかいれいも重要じゅうようである。 $A = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ または $B = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ なら、 $A \times B = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ である。なぜなら、 $(a, b)$ を作つくるには $a \in A$ と $b \in B$ の両方りょうほうが必要ひつようであり、片方かたほうの集合しゅうごうsetに元げんelementが存在そんざいしなければ順序対じゅんじょついordered pairを作つくれないからである。

順序対じゅんじょついordered pairの等号とうごうは成分せいぶんごとに判定はんていする。 $(a, b) = (a^{'}, b^{'})$ なら $a = a^{'}$ かつ $b = b^{'}$ であり、直積集合ちょくせきしゅうごうCartesian productへの所属しょぞくも各かく座標ざひょうが正ただしい集合しゅうごうに入はいることを同時どうじに要求ようきゅうする。

5Precise explanation

The essential equality rule for ordered pairs順序対じゅんじょつい is

(a, b) = (a^{'}, b^{'}) ⟺ (a = a^{'} and b = b^{'}) .

This property lets us compare the first and second components separately. When proving equality or inclusion involving Cartesian products, decompose elements as ordered pairs.

The boundary case involving the empty set is also important. If $A = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ or $B = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ , then

A \times B = [PARSE ERROR: Undefined("Command(\"varnothing\")")] .

To make an ordered pair $(a, b)$ , both $a \in A$ and $b \in B$ are required. If one side has no elements, no ordered pair can be made.

6例題れいだい：直積集合ちょくせきしゅうごうCartesian productと順序じゅんじょ

6Worked example: Cartesian products and order

6.1問題もんだい

$A = {0, 1}$ 、 $B = {1, 2}$ とする。 $A \times B$ と $B \times A$ を書かき出だし、両者りょうしゃが一般いっぱんに等ひとしくないことを確認かくにんせよ。

6.1Problem

Let $A = {0, 1}$ and $B = {1, 2}$ . List $A \times B$ and $B \times A$ , and confirm that they are not generally equal.

6.2解説かいせつ

定義ていぎより

A \times B = {(0, 1), (0, 2), (1, 1), (1, 2)}

である。一方いっぽう、

B \times A = {(1, 0), (1, 1), (2, 0), (2, 1)}

である。たとえば $(0, 1) \in A \times B$ だが、 $(0, 1) \notin B \times A$ である。したがって $A \times B \neq B \times A$ である。

ここで確認かくにんしているのは、直積集合ちょくせきしゅうごうCartesian productが単たんなる組合くみあわせではなく、順序じゅんじょを記録きろくする操作そうさであるという点てんである。

6.2Explanation

By definition,

A \times B = {(0, 1), (0, 2), (1, 1), (1, 2)} .

On the other hand,

B \times A = {(1, 0), (1, 1), (2, 0), (2, 1)} .

For example, $(0, 1) \in A \times B$ , but $(0, 1) \notin B \times A$ . Therefore $A \times B \neq B \times A$ .

This confirms that the Cartesian product直積集合ちょくせきしゅうごう is not just an unordered combination. It records order.

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

操作そうさ	変かわるもの	保存ほぞんされるもの
$A \times B$ から $B \times A$ への入いれ替かえ	成分せいぶんの位置いち	選えらんだ材料ざいりょうの集合しゅうごう
$A \times B$ の部分集合ぶぶんしゅうごうsubsetを取とる	採用さいようする順序対じゅんじょついordered pair	成分せいぶんが $A$ と $B$ から来くること
$A_{1} \times \dots \times A_{n}$ に拡張かくちょうする	成分せいぶんの数かず	各かく成分せいぶんが指定していされた集合しゅうごうsetから来くること

片方かたほうの因子いんしを変かえると、表ひょうでいえば行ぎょうまたは列れつcolumnが変かわる。一方いっぽう、各かく元げんelementが順序対じゅんじょついであり、第だい 1 成分せいぶんと第だい 2 成分せいぶんを区別くべつすることは保存ほぞんされる。

7What changes and what is preserved

Operation	What changes	What is preserved
switching from $A \times B$ to $B \times A$	positions of the components	the sets used as materials for selection
taking a subset of $A \times B$	which ordered pairs順序対じゅんじょつい are accepted	each component still comes from $A$ and $B$
extending to $A_{1} \times \dots \times A_{n}$	the number of components	each component comes from its specified set

8見分みわけ方かた

複数ふくすうの選択せんたくを同時どうじに記録きろくするなら、直積集合ちょくせきしゅうごうCartesian productを考かんがえる。
順序じゅんじょが意味いみを持もつなら、順序対じゅんじょついordered pairとして扱あつかう。
関係かんけいrelation を定義ていぎするなら、まず母体ぼたいとなる $A \times B$ を確認かくにんする。
写像しゃぞうmap を定義ていぎするなら、 $A \times B$ の内うち「各かく $a \in A$ に対たいして第だい 2 成分せいぶんが一意いちいに存在そんざいする」部分集合ぶぶんしゅうごうsubsetを考かんがえる。

判定はんていでは、まず対象たいしょうが順序対じゅんじょついになっているかを見みる。次つぎに第だい 1 成分せいぶんが $A$ に、第だい 2 成分せいぶんが $B$ に入はいっているかを確認かくにんする。どちらか 1 つでも外はずれれば $A \times B$ の元げんelementではない。

8Recognition criteria

Use a Cartesian product直積集合ちょくせきしゅうごう when several choices are recorded simultaneously.
If order matters, treat the result as an ordered pair順序対じゅんじょつい.
To define a relation関係かんけい, first identify the ambient set $A \times B$ .
To define a map写像しゃぞう, consider a subset of $A \times B$ in which, for each $a \in A$ , there exists exactly one second component.

9証明しょうめい補足ほそく：直積ちょくせきが包含ほうがんを保たもつ条件じょうけん

直積集合ちょくせきしゅうごうCartesian product は各成分かくせいぶんの包含ほうがんを保存ほぞんする。つまり

A \subseteq A^{'}, B \subseteq B^{'} ⟹ A \times B \subseteq A^{'} \times B^{'}

である。

証明しょうめいする。 $(a, b) \in A \times B$ とする。この意味いみは $a \in A$ かつ $b \in B$ である。 $A \subseteq A^{'}$ と $B \subseteq B^{'}$ より $a \in A^{'}$ かつ $b \in B^{'}$ である。したがって $(a, b) \in A^{'} \times B^{'}$ である。

逆向ぎゃくむきには空集合くうしゅうごうの注意ちゅういが必要ひつようである。もし $A \times B \subseteq A^{'} \times B^{'}$ で、さらに $A$ と $B$ がどちらも空からでないなら、 $A \subseteq A^{'}$ かつ $B \subseteq B^{'}$ が従したがう。たとえば $a \in A$ を取とり、 $B$ が空からでないので $b \in B$ を取とる。すると $(a, b) \in A \times B \subseteq A^{'} \times B^{'}$ だから $a \in A^{'}$ である。同おなじ議論ぎろんで $B \subseteq B^{'}$ も分わかる。

この非空ひくうの仮定かていを落おとすと、 $A \times [PARSE ERROR: Undefined("Command(\"varnothing\")")] = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ となり、左辺さへんだけから $A$ の情報じょうほうを読よみ取とれない。

9Proof supplement: when products preserve inclusion

The Cartesian product直積集合ちょくせきしゅうごう preserves inclusion in each component. That is,

A \subseteq A^{'}, B \subseteq B^{'} ⟹ A \times B \subseteq A^{'} \times B^{'} .

Proof. Take $(a, b) \in A \times B$ . This means $a \in A$ and $b \in B$ . Since $A \subseteq A^{'}$ and $B \subseteq B^{'}$ , we have $a \in A^{'}$ and $b \in B^{'}$ . Therefore $(a, b) \in A^{'} \times B^{'}$ .

The converse direction needs a nonempty-set condition. If $A \times B \subseteq A^{'} \times B^{'}$ and both $A$ and $B$ are nonempty, then $A \subseteq A^{'}$ and $B \subseteq B^{'}$ . For example, take $a \in A$ . Since $B$ is nonempty, choose $b \in B$ . Then $(a, b) \in A \times B \subseteq A^{'} \times B^{'}$ , so $a \in A^{'}$ . The same argument shows $B \subseteq B^{'}$ .

If the nonempty assumption is omitted, this conclusion can fail. Since $A \times [PARSE ERROR: Undefined("Command(\"varnothing\")")] = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ , the left-hand side may contain no information about $A$ .

10演習えんしゅうリンク

data/exercise/math/discrete-math/cartesian-products-and-power-sets.exercise.n.md

10Exercise links