Skip to main content
LibreTexts - Ukrayinska

1.5: Пари, кортежі, декартові продукти

  • Page ID
    53146
  • \( \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}}\)

    Template:MathJaxZach

    З розширеності випливає, що набори не мають порядку до своїх елементів. Так що, якщо ми хочемо представляти порядок, ми використовуємо впорядковані пари\(\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}\): Ordered pair

    \(\tuple{a, b} = \{\{a\}, \{a, b\}\}\).

    Проблема\(\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\]