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

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

mathdiscrete-mathcartesian-productlecture

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.

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[順序付き組].

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

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.

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.

6Worked example: Cartesian products and order

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

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

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.

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

10Exercise links

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