6.1: Декартовий продукт

Спілки та перехрестя ми обговорили в розділі\(3.3\). Декартовий продукт - ще одна важлива операція набору. Перед його введенням згадаємо позначення для впорядкованої пари.

Позначення\(6.1.1\).

Для будь-яких об'єктів\(x\) і\(y\) математики використовують для позначення\((x, y)\) впорядкованої пари, перша координата якої є,\(x\) а друга координата якої\(y\). Важливо знати, що порядок має значення:\((x, y)\) зазвичай не такий, як\((y, x)\). (Ось чому вони називаються впорядкованими парами. Зверніть увагу, що множини не такі: множини невпорядковані,\(\{x, y\}\) тому завжди такі ж, як\(\{y, x\}\).) Важливо усвідомлювати, що:\[\left(x_{1}, y_{1}\right)=\left(x_{2}, y_{2}\right) \quad \Leftrightarrow \quad x_{1}=x_{2} \text { and } y_{1}=y_{2}\]

Приклад\(6.1.2\).

Особливий випадок декартового добутку знайомий всім учням алгебри: нагадаємо, що\((6.1.3)\)\[\mathbb{R}^{2}=\{(x, y) \mid x \in \mathbb{R}, y \in \mathbb{R}\}\]
це множина всіх впорядкованих пар дійсних чисел. Це «координатна площина» (або «\(xy\)-plane»), яка використовується для малювання графіків функцій.

Формула\(y = f(x)\) часто з'являється в елементарній алгебрі, і, в цьому суб'єкті, змінні\(x\) і\(y\) представляють дійсні числа. Однак розширені курси математики\(y\) дозволяють\(x\) і бути елементами будь-яких наборів\(A\) і\(B\), не тільки з\(\mathbb{R}\). Тому важливо узагальнити вищевказаний приклад, замінивши два виступи\(\mathbb{R}\) у правій частині Рівняння\(6.1.3\) довільними множинами\(A\) та\(B\):

Визначення\(6.1.4\).

Для будь-яких множин\(A\) і\(B\), ми дозволяємо\[A \times B=\{(a, b) \mid a \in A, b \in B\} .\]
Це позначення означає, для всіх\(x\), що\[x \in A \times B \text { iff } \exists a \in A, \exists b \in B, x=(a, b) .\]
\(A \times B\) множина називається декартовим добутком\(A\) і\(B\).

Приклад\(6.1.5\).

1. \(\mathbb{R} \times \mathbb{R} = \mathbb{R}^{2}\).
2. \(\{1,2,3\} \times\{\mathrm{a}, \mathrm{b}\}=\{(1, \mathrm{a}),(1, \mathrm{~b}),(2, \mathrm{a}),(2, \mathrm{~b}),(3, \mathrm{a}),(3, \mathrm{~b})\}\).
3. \(\{a, b\} \times\{1,2,3\}=\{(a, 1),(a, 2),(a, 3),(b, 1),(b, 2),(b, 3)\}\).

Порівнюючи (2) і (3), ми бачимо, що\(\times\) це не\(A \times B\) комутативно: зазвичай не дорівнює\(B \times A\).

Вправа\(6.1.6\).

Вкажіть кожен набір, перерахувавши його елементи.

1. \(\{a, i\} \times\{n, t\}=\)
2. \(\{\mathrm{Q}, \mathrm{K}\} \times\){♣, ♦, ♥, ♠} =
3. \(\{1,2,3\} \times\{3,4,5\}=\)

Зауваження\(6.1.7\).

Доведемо в теоремі\(9.1.18\), що\[\#(A \times B)=\# A \cdot \# B .\]

Іншими словами: поки\[\text { cardinality of a Cartesian product is the product of the cardinalities.}\]
давайте просто наведемо неформальне обгрунтування:

Припустимо\(\#A = m\), і\(\#B = n\). Потім, перерахувавши елементи цих множин, ми можемо записати\[A=\left\{a_{1}, a_{2}, a_{3}, \ldots, a_{m}\right\} \quad \text { and } \quad B=\left\{b_{1}, b_{2}, b_{3}, \ldots, b_{n}\right\} .\]
\(A \times B\) елементи:\ [\ begin {масив} {ccccc}
\ left (a_ {1}, b_ {1}\ right), &\ left (a_ {1}, b_ {2}\ right), &\ left (a_ {1}, b_ {3}\ right), &\ cdots &\ left (a_ {1}, b_ {n}\ право)\\
\ ліворуч (a_ {2}, b_ {1}\ праворуч), &\ ліворуч (a_ {2}, b_ {2}\ праворуч), &\ ліворуч (a_ {2}, b_ {3}\ праворуч), &\ cdots &\ ліворуч (a_ {2}, b_ {n}\ праворуч),\
\ ліворуч (a_ {3}, b_ {1}\ праворуч), &\ ліворуч (a_ {3}, b_ {2}\ праворуч), &\ ліворуч (a_ {3}, b_ {3}\ праворуч), &\ cdots &\ ліворуч (a_ {3}, b_ {n}\ праворуч),\\
\ vdots &\ vdots &\ ddots &\ vdots\\
\ вліво (a_ {m}, b_ {1}\ праворуч), &\ ліворуч (a_ {m}, b_ {2}\ праворуч), &\ ліворуч (a_ {m}, b_ {3}\ праворуч), &\ cdots &\ ліворуч (a_ {m}, b_ {n}}\ праворуч).
\ end {array}\]
У цьому масиві

• кожен ряд має точно\(n\) елементи, і
• є\(m\) ряди,

тому кількість елементів - це твір\(m n=\# A \cdot \# B .\)

Ось кілька прикладів доказів, що стосуються декартових продуктів.

Приклад\(6.1.8\).

Якщо\(A\) і\(B\) є непорожніми множинами, і\(A \times B = B \times A\), то\(A = B\).

Рішення

ДОКАЗ.

Припустімо\(A\) і\(B\) є непорожніми множинами, такими, що\(A \times B = B \times A\). Досить показати\(A \subset B\) і\(B \subset A\). За симетрії нам потрібно лише показати\(A \subset B\).

\(a_{0}\)Дозволяти бути довільним елементом\(A\). Оскільки\(B\) непорожній, існує деякі\(b_{0} \in B\). Тоді\[\left(a_{0}, b_{0}\right) \in A \times B=B \times A=\{(b, a) \mid b \in B, a \in A\} ,\]
так існують\(b \in B\) і\(a \in A\), такі що\(\left(a_{0}, b_{0}\right)=(b, a)\). Тому\(a_{0} = b\) (і\(b_{0} = a\), але нам цей факт не потрібен). Звідси\(a_{0} = b \in B\).

Приклад\(6.1.9\).

Якщо\(B\) від'єднується від\(C\), то\(A \times B\) від'єднується від\(A \times C\).

Рішення

ДОКАЗ.

Доведемо контрапозитив: Припустимо, що не\(A \times B\) від'єднується від\(A \times C\), і ми покажемо,\(B\) що не від'єднується від\(C\).

За припущенням, перетин\(A \times B\) і не\(A \times C\) є порожнім, тому ми можемо вибрати деякі\[x \in(A \times B) \cap(A \times C) .\]
Тоді:

• Так як\(x \in A \times B\), існують\(a_{1} \in A\) і\(b \in B\), такі що\(x=\left(a_{1}, b\right)\).
• Так як\(x \in A \times C\), існують\(a_{2} \in A\) і\(c \in C\), такі що\(x = (a_{2}, c)\).

Значить\(\left(a_{1}, b\right)=x=\left(a_{2}, c\right)\), так\(b = c\). Тепер\(b \in B\) і\(b = c \in C\), так\(b \in B \cap C\). Тому так\(B \cap C \neq \varnothing\), як хочеться,\(B\) і\(C\) не розмежовуються.

Зауваження\(6.1.10\).

Читаючи докази вище, ви, можливо, помітили, що змінна\(x\) (одна буква) використовувалася для представлення впорядкованої пари\((a, b)\). У цьому немає нічого поганого, тому що впорядкована пара - це єдиний об'єкт, а змінна взагалі може представляти будь-який математичний об'єкт, будь то елемент множини, або ціла множина, або функція, або впорядкована пара, або щось інше.

Приклад\(6.1.11\).

Припустимо\(A\),\(B\), і\(C\) є множинами. Доведіть\(A \times (B \cup C) = (A \times B) \cup (A \times C)\).

Рішення

ДОКАЗ.

(\(\subset\)) З огляду на\(x \in(A \times B) \cup(A \times C)\), у нас є\(x \in A \times B\) або\(x \in A \times C\). За симетрії ми можемо припустити\(x \in A \times B\), так\(x = (a, b)\) для деяких\(a \in A\) і\(b \in B\). Зверніть увагу на те\(b \in B \cup C\), що, таким чином, у нас є\(a \in A\) і\(b \in B \cup C\). Тому\[x=(a, b) \in A \times(B \cup C)\]
Оскільки\(x\) є довільним елементом\((A \times B) \cup (A \times C)\), це має на увазі\((A \times B) \cup(A \times C) \subset A \times(B \cup C)\).

(\(\subset\)) З огляду на\((a, x) \in A \times(B \cup C),\), у нас є\(a \in A\), і або\(x \in B\) або\(x \in C\). За симетрії ми можемо припустити\(x \in B\). Потім\((a, x) \in A \times B \subset(A \times B) \cup(A \times C)\), так\((a, x) \in(A \times B) \cup(A \times C)\). Оскільки\((a, x)\) є довільним елементом\(A \times (B \cup C)\), це має на увазі\(A \times(B \cup C) \subset(A \times B) \cup(A \times C)\).

Вправа\(6.1.12\).

1. Припустимо\(A\),\(B\), і\(C\) є множинами.
   1. Покажіть, що якщо\(B \subset C\), то\(A \times B \subset A \times C\).
   2. Покажіть, що якщо\(A \times B = A \times C\), і\(A \neq \varnothing\), то\(B = C\).
2. Припустимо,\(A\) це набір.
   1. Показати\(A \times \varnothing=\varnothing\).
   2. Показувати,\(A \times A=\varnothing\) якщо і тільки якщо\(A=\varnothing\).
3. Сказати, що\(\times\) є розподільним над\(\cup\) означає, що для всіх множин\(A\), і\(B\)\(C\), у нас є\[A \times(B \cup C)=(A \times B) \cup(A \times C) \quad \text { and } \quad(B \cup C) \times A=(B \times A) \cup(C \times A) .\]
   Перше рівняння було встановлено в прикладі\(6.1.11\). Завершіть доказ, який\(\times\) є розподільним,\(\cup\) доводячи друге рівняння.
4. Показати, що\(\times\) є розподільним над\(\cap\). Тобто для всіх наборів\(A\), і\(B\)\(C\), у нас є
   1. \(A \times(B \cap C)=(A \times B) \cap(A \times C)\), і
   2. \((B \cap C) \times A=(B \times A) \cap(C \times A)\).