1.5: Пари, кортежі, декартові продукти
- Page ID
- 53146
З розширеності випливає, що набори не мають порядку до своїх елементів. Так що, якщо ми хочемо представляти порядок, ми використовуємо впорядковані пари\(\tuple{x, y}\). У невпорядкованої\(\{x, y\}\) парі порядок не має значення:\(\{x, y\} = \{y, x\}\). У впорядкованій парі він робить: якщо\(x \neq y\), то\(\tuple{x, y} \neq \tuple{y, x}\).
Як ми повинні думати про впорядковані пари в теорії множин? Що найважливіше, ми хочемо зберегти ідею, що впорядковані пари ідентичні, якщо вони поділяють один і той же перший елемент і мають один і той же другий елемент, тобто:
\[\tuple{a, b}= \tuple{c, d}\text{ iff both }a = c \text{ and }b=d.\nonumber\]
Ми можемо визначити впорядковані пари в теорії множин за допомогою визначення Вінера-Куратовського.
Проблема\(\PageIndex{1}\)
Використовуючи визначення\(\PageIndex{1}\), довести, що\(\tuple{a, b}= \tuple{c, d}\) якщо обидва\(a = c\) і\(b=d\).
Закріпивши визначення впорядкованої пари, ми можемо використовувати її для визначення подальших множин. Наприклад, іноді ми також хочемо впорядковані послідовності з більш ніж двох об'єктів, наприклад\(\tuple{x, y, z}\), трійок\(\tuple{x, y, z, u}\), чотирикраток тощо. Ми можемо розглядати трійки як спеціальні впорядковані пари, де перший елемент сам по собі є впорядкованою парою:\(\tuple{x, y, z}\) є\(\tuple{\tuple{x, y},z}\). Те ж саме справедливо і для четвірки:\(\tuple{x,y,z,u}\) є\(\tuple{\tuple{\tuple{x,y},z},u}\), і так далі. Загалом, мова йде про упорядкованих\(n\) -кортежах\(\tuple{x_1, \dots, x_n}\).
Будуть корисні певні набори впорядкованих пар, або інші\(n\) упорядковані -кортежі.
Визначення\(\PageIndex{2}\): Cartesian product
Задані\(B\) множини\(A\) і, їх декартовий\(A \times B\) добуток визначається
\[A \times B = \Setabs{\tuple{x, y}}{x \in A \text{ and } y \in B}.\nonumber\]
Приклад\(\PageIndex{1}\)
Якщо\(A = \{0, 1\}\), і\(B = \{1, a, b\}\), то їх продукт
\[A \times B = \{ \tuple{0, 1}, \tuple{0, a}, \tuple{0, b}, \tuple{1, 1}, \tuple{1, a}, \tuple{1, b} \}.\nonumber\]
Приклад\(\PageIndex{2}\)
Якщо набір,\(A\) то твір\(A\) з собою\(A \times A\), також пишеться\(A^2\). Вона являє собою набір всіх пар\(\tuple{x, y}\) с\(x, y \in A\). Набір всіх трійок\(\tuple{x, y, z}\) є\(A^3\), і так далі. Ми можемо дати рекурсивне визначення:\[\begin{aligned} A^1 & = A\\ A^{k+1} & = A^k \times A\end{aligned}\]
Проблема\(\PageIndex{2}\)
Перерахуйте всі елементи\(\{1, 2, 3\}^3\).
Пропозиція\(\PageIndex{1}\)
Якщо\(A\) має\(n\) елементи і\(B\) має\(m\) елементи, то\(A \times B\) має\(n\cdot m\) елементи.
Доказ. Для кожного елемента\(x\) в\(A\), є\(m\) елементи форми\(\tuple{x, y} \in A \times B\). Нехай\(B_x = \Setabs{\tuple{x, y}}{y \in B}\). З тих пір\(x_1 \neq x_2\), коли\(\tuple{x_1, y} \neq \tuple{x_2, y}\),,\(B_{x_1} \cap B_{x_2} = \emptyset\). Але якщо\(A = \{x_1, \dots, x_n\}\), то\(A \times B = B_{x_1} \cup \dots \cup B_{x_n}\), і так має\(n\cdot m\) елементи.
Щоб це візуалізувати, розташуйте елементи\(A \times B\) в сітці:
\[\begin{array}{rcccc} B_{x_1} = & \{\tuple{x_1, y_1} & \tuple{x_1, y_2} & \dots & \tuple{x_1, y_m}\}\\ B_{x_2} = & \{\tuple{x_2, y_1} & \tuple{x_2, y_2} & \dots & \tuple{x_2, y_m}\}\\ \vdots & & \vdots\\ B_{x_n} = & \{\tuple{x_n, y_1} & \tuple{x_n, y_2} & \dots & \tuple{x_n, y_m}\} \end{array}\nonumber\]
Оскільки всі\(x_i\) різні, і всі\(y_j\) різні, жодна з двох пар в цій сітці не однакова, і є\(n\cdot m\) з них. ◻
Проблема\(\PageIndex{3}\)
Покажіть, шляхом індукції\(k\), що для всіх\(k \ge 1\), якщо\(A\) має\(n\) елементи, то\(A^k\) має\(n^k\) елементи.
Приклад\(\PageIndex{3}\)
Якщо\(A\) є множиною, слово over\(A\) - це будь-яка послідовність елементів\(A\). Послідовність може розглядатися як\(n\) -кортеж елементів\(A\). Наприклад, якщо\(A = \{a, b, c\}\), то послідовність «\(bac\)» може розглядатися як потрійна\(\tuple{b, a, c}\). Слова, тобто послідовності символів, мають вирішальне значення в інформатиці. За умовністю підраховуємо елементи\(A\) як послідовності довжини\(1\),\(\emptyset\) так і як послідовність довжини\(0\). Сукупність усіх слів\(A\) над тим
\[A^* = \{\emptyset\} \cup A \cup A^2 \cup A^3 \cup \dots\nonumber\]