4.4: Декартові продукти

Last updated
Save as PDF

Page ID: 64149

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Інший спосіб отримання нового множини з двох заданих множин$A$ і$B$ полягає у формуванні впорядкованих пар. Впорядкована пара$(x,y)$ складається з двох значень$x$ і$y$. Їх порядок появи важливий, тому ми називаємо їх першим і другим елементами відповідно. Отже,$(a,b)\neq (b,a)$ хіба що$a=b$. Загалом,$(a,b)=(c,d)$ якщо і тільки якщо$a=c$ і$b=d$.

Визначення: Декартовий продукт

Декартовий твір$A$ і$B$ є множиною

\[A \times B = \{ (a,b) \mid a \in A \wedge b \in B \} \nonumber\]

Таким чином,$A \times B$ (читається як «$A$хрест$B$») містить всі впорядковані пари, з яких вибираються перші елементи$A$, з яких вибираються другі елементи$B$.

Приклад$\PageIndex{1}\label{eg:cartprod-01}$

Нехай$A = \{\mbox{John}, \mbox{Jim}, \mbox{Dave}\}$ і$B = \{\mbox{Mary}, \mbox{Lucy}\}$. Визначте$A\times B$ і$B\times A$.

Рішення: Знаходимо\[\displaylines{ A\times B = \{ (\mbox{John},\mbox{Mary}), (\mbox{John},\mbox{Lucy}), (\mbox{Jim}, \mbox{Mary}), (\mbox{Jim}, \mbox{Lucy}), (\mbox{Dave},\mbox{Mary}), (\mbox{Dave},\mbox{Lucy})\}, \cr B\times A = \{ (\mbox{Mary},\mbox{John}), (\mbox{Mary},\mbox{Jim}), (\mbox{Mary},\mbox{Dave}), (\mbox{Lucy},\mbox{John}), (\mbox{Lucy},\mbox{Jim}), (\mbox{Lucy},\mbox{Dave})\}. \cr} \nonumber\] Загалом,$A\times B \neq B\times A$.

Приклад$\PageIndex{2}\label{eg:cartprod-02}$

Визначте$A \times B$ і$A \times A$:

$A=\{1,2\}$і$B=\{2,5,6\}$.
$A=\{5\}$і$B=\{0,7\}$.

Рішення

(а) Ми знаходимо\[\begin{array}{r c l} A\times B &=& \{(1,2), (1,5), (1,6), (2,2), (2,5), (2,6)\}, \\ A\times A &=& \{(1,1), (1,2), (2,1), (2,2)\}. \end{array} \nonumber\]

(б) Відповіді є$A\times B = \{(5,0), (5,7)\}$, і$A\times A = \{(5,5)\}$.

практичні вправи$\PageIndex{1}\label{he:cartprod-01}$

Нехай$A=\{a,b,c,d\}$ і$B=\{r,s,t\}$. Знайти$A\times B$,$B\times A$, і$B\times B$.

Приклад$\PageIndex{3}\label{eg:cartprod-03}$

Визначте$\wp(\{1,2\}) \times \{3,7\}$. Обов'язково використовуйте правильні позначення.

Рішення: Для складної проблеми розділіть її на більш дрібні завдання і вирішуйте кожну окремо. Потім зберіть їх, щоб сформувати остаточну відповідь. У цій задачі ми спочатку оцінюємо\[\wp(\{1,2\}) = \big\{\emptyset, \{1\}, \{2\}, \{1,2\} \big\}. \nonumber\] Це призводить до\[\begin{array}{r c l} \wp(\{1,2\}) \times \{3,7\} &=& \big\{\emptyset, \{1\}, \{2\}, \{1,2\} \big\} \times \{3,7\} \\ &=& \big\{ (\emptyset,3), (\emptyset,7), (\{1\},3), (\{1\},7), (\{2\},3), (\{2\},7), (\{1,2\},3), (\{1,2\},7) \big\}. \end{array} \nonumber\] перевірки, щоб переконатися, що у нас є відповідні ліві та праві дужки та відповідні ліві та праві фігурні дужки.

практичні вправи$\PageIndex{2}\label{he:cartprod-02}$

Знайти$\{a,b,c\}\times\wp(\{d\})$.

Приклад$\PageIndex{4}\label{eg:cartprod-04}$

Як ми могли б описати вміст декартового продукту$[1,3] \times \{2,4\}$? Оскільки$[1,3]$ є нескінченним набором, неможливо перерахувати всі впорядковані пари. Нам потрібно використовувати позначення set-builder:\[[1,3] \times \{2,4\} = \{ (x,y) \mid 1\leq x\leq3, y=2,4\}. \nonumber\] Ми також можемо писати$[1,3] \times \{2,4\} = \{ (x,2), (x,4) \mid 1\leq x\leq3\}$.

практичні вправи$\PageIndex{3}\label{HE:cartprod-03}$

Опишіть, використовуючи позначення set-builder, декартовий твір$[1,3] \times [2,4]$.

Декартові вироби можуть бути розширені до більш ніж двох наборів. Замість впорядкованих пар нам потрібні упорядковані$n$ -кортежі. $n$-fold декартовий продукт$n$ наборів$A_1, A_2, \ldots, A_n$ - це набір

\ [$A_1\ раз A_2\ раз\ cdots\ раз a_n
=\ {(a_1, a_2,\ ldots, a_n)\ середина a_i\ в a_i\ mbox {для кожного} i,
1\ leq i\ leq n\}\ nonumber\]

Зокрема, коли$A_i=A$ для всіх$i$ ми скорочуємо декартове твір як$A^n$.

Приклад$\PageIndex{5}\label{eg:cartprod-05}$

Позначається$n$ -мірний простір$\mathbb{R}^n$. Це$n$ -fold декартової продукт$\mathbb{R}$. В особливих випадках,$\mathbb{R}^2$ це$xy$ -plane, і$\mathbb{R}^3$ є$xyz$ -space.

практичні вправи$\PageIndex{5}\label{he:cartprod-04}$

Нехай$A=\{1,2\}$,$B=\{a,b\}$, і$C=\{r,s,t\}$. Знайти$A\times B\times C$.

Приклад$\PageIndex{6}\label{eg:cartprod-06}$

З технічної точки зору,$(A \times B) \times C$ відрізняється від$A \times B \times C$. Чи можете ви пояснити чому? Чи можете ви обговорити різницю, якщо така є, між$(A \times B) \times C$ і$A \times (B \times C)$? Наприклад, наведіть деякі конкретні приклади елементів$(A \times B)\times C$ і$A \times (B \times C)$ проілюструйте їх відмінності.

Рішення: Елементи є$(A\times B)\times C$ впорядкованими парами, в яких перші координати самі є впорядкованими парами. Типовий елемент в$(A\times B)\times C$ приймає форму Елементи\[\big((a,b),c\big). \nonumber\] в$A\times B\times C$ впорядковані трійки форми\[(a,b,c). \nonumber\] Оскільки їх елементи виглядають по-різному, зрозуміло, що$(A\times B)\times C \neq A\times B\times C$. Аналогічним чином, типовий елемент в$A\times (B\times C)$ виглядає як\[\big(a,(b,c)\big). \nonumber\] Тому$(A\times B)\times C \neq A\times(B\times C)$, і$A\times (B\times C)\neq A\times B\times C$.

Теорема$\PageIndex{1}$

Для будь-яких наборів$A$$B$, і$C$, у нас є\[\begin{array}{r c l} A \times (B \cup C) &=& (A \times B) \cup (A \times C), \\ A \times (B \cap C) &=& (A \times B) \cap (A \times C), \\ A \times (B - C) &=& (A \times B) - (A \times C).\end{array} \nonumber\]

Зауваження

Як би ми показали, що два$S$ набори$T$ і рівні? Нам потрібно показати, що\[x\in S \Leftrightarrow x\in T. \nonumber\] Ускладнення в цій проблемі полягає в тому, що обидва$S$ і$T$ є декартовими продуктами, тому$x$ набуває особливої форми, а саме впорядкованої пари. Розглянемо першу ідентичність як приклад; нам потрібно показати, що\[(u,v)\in A \times (B \cup C) \Leftrightarrow (u,v)\in (A \times B) \cup (A \times C). \nonumber\] Ми доводимо це двома кроками: спочатку показуючи$\Rightarrow$, потім$\Leftarrow$, що еквівалентно першому показу$\subseteq$, потім$\supseteq$. Як варіант, ми можемо використовувати$\Leftrightarrow$ протягом усього аргументу.

Доказ 1

Нехай$(u,v)\in A\times(B\cup C)$. Потім$u\in A$, і$v\in B\cup C$. Визначення союзу має на увазі, що$v\in B$ або$v\in C$. До теперішнього часу ми знайшли

$u\in A$і$v\in B$, або
$u\in A$і$v\in C$.

Це еквівалентно

$(u,v)\in A\times B$, або
$(u,v)\in A\times C$.

Таким чином,$(u,v)\in (A\times B)\cup(A\times C)$. Це доводить це$A\times(B\cup C) \subseteq (A\times B)\cup(A\times C)$.

Далі нехай$(u,v)\in (A\times B)\cup(A\times C)$. Потім$(u,v)\in A\times B$, або$(u,v)\in A\times C$. Це означає

$u\in A$і$v\in B$, або
$u\in A$і$v\in C$.

Обидві умови вимагають$u\in A$, тому ми можемо переписати їх як

$u\in A$, і
$v\in B$або$v\in C$;

що еквівалентно

$u\in A$, і
$v\in B\cup C$.

Таким чином,$(u,v)\in A\times(B\cup C)$. Ми це довели$(A\times B) \cup(A\times C) \subseteq A\times(B\cup C)$. Разом з тим$A\times (B\cup C) \subseteq (A\times B)\cup(A\times C)$, що ми довели раніше, робимо висновок про це$A\times(B\cup C) = (A\times B)\cup (A\times C)$.

Доказ 2: Доведемо лише перше рівність. Так як\[\begin{array}{r l l} (u,v) \in A \times (B \cup C) & \Leftrightarrow u \in A \wedge v \in (B \cup C) & (\text{defn. of Cartesian product}) \\ & \Leftrightarrow u \in A \wedge (v \in B \vee v \in C) & (\text{defn. of union}) \\ & \Leftrightarrow (u \in A \wedge v \in B) \vee (u \in A \wedge v \in C) & (\text{distributive law}) \\ & \Leftrightarrow (u, v) \in A \times B \vee (u, v) \in A \times C & (\text{defn. of Cartesian product}) \\ & \Leftrightarrow (u,v) \in (A \times B) \cup (A \times C) & (\text{defn. of union}) \end{array}\] ми робимо висновок, що$A\times(B\cup C) = (A\times B)\cup(A\times C)$.

Теорема$\PageIndex{2}\label{cartprodcard}$

Якщо$A$ і$B$ є кінцевими множинами, з$|A|=m$ і$|B|=n$, то$|A\times B| = mn$.

Доказ: Елементи$A\times B$ впорядковані пари виду$(a,b)$, де$a\in A$, і$b\in B$. Є$m$ вибір$a$. Для кожного фіксованого$a$ ми можемо сформувати впорядковану пару$(a,b)$$n$ способами, тому що є$n$ вибір для$b$. Разом впорядковані пари$(a,b)$ можуть формуватися$mn$ способами.

Аргумент, який ми використовували в доказі, називається принципом множення. Ми вивчимо його ще раз у главі 8. Якщо коротко, то це говорить про те, що якщо завдання можна виконати в кілька кроків, то кількість способів закінчити роботу є твором кількості способів завершення кожного кроку.

Кораллярний$\PageIndex{3}$

Якщо$A_1,A_2,\ldots,A_n$ кінцеві множини, то$|A_1\times A_2\times \cdots\times A_n| = |A_1| \cdot |A_2|\,\cdots\, |A_n|$.

Слідство$\PageIndex{4}$

Якщо$A$ є кінцевим множиною з$|A|=n$, то$|\wp(A)|=2^n$.

Доказ: Нехай елементи$A$ будуть$a_1,a_2,\ldots,a_n$. Елементи$\wp(A)$ є підмножинами$A$. Кожна підмножина$A$ містить деякі елементи з$A$. \[b_i = \cases{ 0 & if $a_i\notin S$, \cr 1 & if $a_i\in S$. \cr} \nonumber\]Пов'язати з кожною$A$ підмножиною$S$ впорядкованого$n$ -кортежу$\big(b_1,b_2,\ldots,b_n\big)$ з$\{0,1\}^n$ такого, що Значення$i$ th елемента в цьому$n$ впорядкованому -кортежі вказує, чи$S$ містить підмножина елемент$a_i$. Зрозуміло, що підмножини$A$ знаходяться в однозначній відповідності з$n$ -кортежів. Це означає, що набір потужності$\wp(A)$ і декартовий продукт$\{0,1\}^n$ мають однакову кардинальність. Оскільки існують$2^n$ упорядковані$n$ -кортежі, ми робимо висновок, що є і$2^n$ підмножини.

Ця ідея однозначного листування є дуже важливим поняттям в математиці. Ми вивчимо його ще раз у главі 6.

Резюме та огляд

Декартове добуток двох множин$A$ і$B$, позначається$A\times B$, складається з впорядкованих пар виду$(a,b)$, звідки$a$ походить$A$, і$b$ походить від$B$.
Так як впорядковані пари беруть участь,$A\times B$ зазвичай не дорівнює$B\times A$.
Поняття впорядкованих пар може бути розширено аналогічно$n$ впорядкованим -кортежів, тим самим отримуючи декартовий твір$n$ -fold.
Якщо$A$ і$B$ є кінцевими множинами, то$|A\times B| = |A|\cdot|B|$.

Вправа$\PageIndex{1}\label{ex:cartprod-01}$

Нехай$X=\{-2,2\}$,$Y=\{0,4\}$ і$Z=\{-3,0,3\}$. Оцініть наступні декартові продукти.

$X\times Y$
$X\times Z$
$Z\times Y\times Y$

Вправа$\PageIndex{2}\label{ex:cartprod-02}$

Розглянемо$Y$ набори$X$, і$Z$ визначені в попередній вправі. Оцініть наступні декартові продукти.

$X\times Y\times Z$
$(X\times Y)\times Z$
$X\times (Y\times Z)$

Вправа$\PageIndex{3}\label{ex:cartprod-03}$

Не перераховуючи всі елементи$X\times Y\times X\times Z$, де$X$$Y$, і$Z$ визначаються в першій вправі, визначте$|X\times Y\times X\times Z|$.

Вправа$\PageIndex{4}\label{ex:cartprod-04}$

Визначте$|\wp(\wp(\wp(\{1,2\})))|$.

Вправа$\PageIndex{5}\label{ex:cartprod-05}$

Розглянемо набір$X=\{-2,2\}$. Оцініть наступні декартові продукти.

$X\times\wp(X)$
$\wp(X)\times\wp(X)$
$\wp(X\times X)$

Вправа$\PageIndex{6}\label{ex:cartprod-06}$

$B$Дозволяти$A$ і бути довільними непорожніми множинами.

За якої умови робить$A\times B = B\times A$?
За яких умов$(A\times B)\cap(B\times A)$ порожній?

Вправа$\PageIndex{7}\label{ex:cartprod-07}$

Нехай$A$$B$, і$C$ бути будь-які три набори. Доведіть, що

$A\times(B\cap C) = (A\times B)\cap (A\times C)$
$A\times(B - C) = (A\times B) - (A\times C)$

Вправа$\PageIndex{8}\label{ex:cartprod-08}$

Нехай$A$$B$, і$C$ бути будь-які три набори. Доведіть, що якщо$A\subseteq B$, то$A\times C \subseteq B\times C$.