1.1: Набори та відносини

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\}.$$

Приклад$\PageIndex{1}$

Наприклад, якщо$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.$$

Приклад$\PageIndex{2}$

$\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 .$

Приклад$\PageIndex{3}$

Ми говоримо, що ціле$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$, є перехідним. Ми називаємо відношення, яке є рефлексивним, симетричним та перехідним відношенням еквівалентності.

Вправа$\PageIndex{1}$

Показати, що відношення$R$ на$\mathbb{Z}$ визначеному$m \sim_{R} n$ if$m$ dives$n$ є рефлексивним і перехідним, але не симетричним.

Вправа$\PageIndex{2}$

Показати, що відношення$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 .$

Вправа$\PageIndex{3}$

З урахуванням співвідношення еквівалентності$R$ на множині$A,$ показують, що

а.$[x] \cap[y] \neq \emptyset$ Якщо і тільки якщо$x \sim_{R} y$

б.$[x]=[y]$ якщо і тільки якщо$x \sim_{R} y .$

Як наслідок попередньої вправи, класи еквівалентності відношення еквівалентності на множині$A$ складають поділ$A$ (тобто$A$ може бути записаний як неспільний союз класів еквівалентності).

Вправа$\PageIndex{4}$

Знайдіть класи еквівалентності для співвідношення еквівалентності у вправі 1.1.2.