1.1: Набори та відносини
- Page ID
- 62444
1.1.1 Цілі числа
Кронекер одного разу сказав: «Бог створив цілі числа; все інше - це робота людини». Беручи це за нашу відправну точку, ми припускаємо існування безлічі.
\[\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3, \ldots\}.\]
множина цілих чисел. Більш того, ми припускаємо властивості операцій додавання і множення цілих чисел, поряд з іншими елементарними властивостями, такими як Фундаментальна теорема арифметики, тобто твердження про те, що кожне ціле число може бути враховано у добуток простих чисел і ця факторизація по суті унікальний.
1.1.2 Набори
Ми візьмемо наївне уявлення про множини: враховуючи будь-яку властивість,\(p,\) ми можемо визначити набір, збираючи разом усі об'єкти, які мають властивість\(p .\) Це може бути зроблено або шляхом явного перерахування, наприклад,\(p\) є властивістю бути одним з\(a, b,\) або\(c,\) який створює набір \(\{a, b, c\},\)або вказавши бажану властивість, наприклад,\(p\) є властивістю бути додатним цілим числом, яке створює множину
\[\mathbb{Z}^{+}=\{1,2,3,4, \ldots\}.\]
Позначення\(x \in A\) вказує на те, що\(x\) є елементом множини\(A .\) Дано множини\(A\) і\(B,\) ми говоримо\(A\) є підмножиною\(B,\) позначається\(A \subset B,\) якщо з того, що\(x \in A\) обов'язково випливає, що\(x \in B .\) Ми говоримо множини\(A\) і\(B\) є дорівнює, якщо обидва\(A \subset B\) і\(B \subset A .\)
Дано два\(A\) набори і\(B,\) ми називаємо множиною.
\[A \cup B=\{x: x \in A \text { or } x \in B\}\]
об'єднання\(A\)\(B\) і безлічі
\[A \cap B=\{x: x \in A \text { and } x \in B\}\]
перетин\(A\) і\(B .\) називаємо безліч
\[A \backslash B=\{x: x \in A, x \notin B\}\]
різниця\(A\) і\(B\).
Більш загально, якщо\(I\) це набір і\(\left\{A_{\alpha}: \alpha \in I\right\}\) є колекцією наборів, по одному для кожного елемента,\(I,\) то у нас є об'єднання
\[\bigcup_{\alpha \in I} A_{\alpha}=\left\{x: x \in A_{\alpha} \text { for some } \alpha\right\}\]
і перехрестя
\[\bigcap_{\alpha \in I} A_{\alpha}=\left\{x: x \in A_{\alpha} \text { for all } \alpha\right\}.\]
Наприклад, якщо\(I=\{2,3,4, \ldots\}\) і ми дозволимо
\[A_{2}=\left\{n: n \in \mathbb{Z}^{+}, n>1, n \neq 2 m \text { for any } m \in \mathbb{Z}^{+} \text {with } m>1\right\}\]
і, для будь-якого\(i \in I, i>2\),
\[A_{i}=\left\{n: n \in A_{i-1}, n \neq m i \text { for any } m \in \mathbb{Z}^{+} \text {with } m>1\right\},\]
\(\cap_{i \in I} A_{i}\)то набір простих чисел.
Якщо\(A\) і\(B\) є обома множинами, ми називаємо множиною
\[A \times B=\{(a, b): a \in A, b \in B\}\]
декартовий добуток\(A\) і\(B .\) якщо\(A=B,\) ми пишемо
\[A^{2}=A \times A.\]
\(\mathbb{Z}^{2}=\{(m, n): m \in \mathbb{Z}, n \in \mathbb{Z}\}\)множина всіх впорядкованих пар цілих чисел.
1.1.3 Відносини
Дано два\(A\)\(B,\) множини і ми називаємо\(R\)\(A \times B\) підмножину відношення. Враховуючи відношення,\(R,\) ми напишемо\(a \sim _{R} b\), або просто\(a \sim b\) якщо\(R\) це зрозуміло з контексту, щоб вказати, що\((a, b) \in R .\)
Ми говоримо, що ціле\(m\) ділить і ціле число,\(n\) якщо\(n=m i\) для деякого цілого,\(i .\) якщо ми дозволимо
\[R=\{(m, n): m \in \mathbb{Z}, n \in \mathbb{Z}, m \text { divides } n\},\]
то\(R\) це відношення. Наприклад,\(3 \sim_{R} 12\).
Розглянемо набір\(A\) і відношення\(R \subset A^{2} .\) Для цілей стислості ми говоримо просто, що\(R\) це відношення на\(A .\) Якщо\(R\) таке, що\(a \sim _{R} a\) для кожного, що\(a \in A,\) ми говоримо,\(R\) є рефлексивним; якщо\(R\) таке, що\(b \sim R a\) кожного разу, коли\(a \sim _{R} b,\) ми говоримо \(R\)симетричний; якщо\(a \sim_{R} b\) і\(b \sim_{R} c\) разом означає, що\(a \sim_{R} c,\) ми говоримо\(R\), є перехідним. Ми називаємо відношення, яке є рефлексивним, симетричним та перехідним відношенням еквівалентності.
Показати, що відношення\(R\) на\(\mathbb{Z}\) визначеному\(m \sim_{R} n\) if\(m\) dives\(n\) є рефлексивним і перехідним, але не симетричним.
Показати, що відношення\(R\) на\(\mathbb{Z}\) визначеному\(m \sim_{R} n\) if\(m-n\) є парним відношення еквівалентності.
Задано відношення еквівалентності\(R\) на множині\(A\) та елементі, який\(x \in A,\) ми називаємо
\[[x]=\left\{y: y \in A, y \sim_{R} x\right\}\]
клас еквівалентності\(x .\)
З урахуванням співвідношення еквівалентності\(R\) на множині\(A,\) показують, що
а.\([x] \cap[y] \neq \emptyset\) Якщо і тільки якщо\(x \sim_{R} y\)
б.\([x]=[y]\) якщо і тільки якщо\(x \sim_{R} y .\)
Як наслідок попередньої вправи, класи еквівалентності відношення еквівалентності на множині\(A\) складають поділ\(A\) (тобто\(A\) може бути записаний як неспільний союз класів еквівалентності).
Знайдіть класи еквівалентності для співвідношення еквівалентності у вправі 1.1.2.