4.2: Перерахування та підрахункові набори

Last updated
Save as PDF

Page ID: 53098

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

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

Визначення$\PageIndex{1}$: Enumeration, informally

Неофіційно, перерахування множини$A$ - це список (можливо, нескінченний)$A$ таких елементів, що кожен елемент$A$ з'являється у списку на певній кінцевій позиції. Якщо$A$ має перерахування, то, як кажуть,$A$ підраховується.

Пара моментів про перерахування:

Ми вважаємо як перерахування лише списки, які мають початок і в яких кожен елемент, крім першого, має один елемент, який безпосередньо передує йому. Іншими словами, між першим елементом списку і будь-яким іншим елементом є лише скінченно багато елементів. Зокрема, це означає, що кожен елемент перерахування має кінцеве положення: перший елемент має позицію$1$, другий позицію і$2$ т.д.
Ми можемо мати різні перерахування одного і того ж набору,$A$ які відрізняються порядком, в якому з'являються елементи:$4$$1$,$25$,$16$,,$9$ перераховує (набір) перших п'яти квадратних чисел так само добре$1$, як$4$,$9$,$16$,$25$ робить.
Надлишкові перерахування все ще є перерахуваннями:$1$$1$,$2$,$2$,$3$,$3$,,... перераховує той самий набір як$1$,,$2$,$3$,... робить.
Порядок і надмірність мають значення, коли ми вказуємо перерахування: ми можемо перерахувати позитивні цілі числа$1$$2$, що починаються з$3$$1$,,,..., але шаблон легше бачити при перерахуванні стандартним способом як $1$,$2$,$3$,$4$,...
Зчислення повинні мати початок:...,,$3$$2$, не$1$ є перерахуванням натуральних чисел, оскільки воно не має першого елемента. Щоб побачити, як це випливає з неформального визначення, запитайте себе: «на якій позиції в списку фігурує число 76?»
Нижче наведено не перерахування натуральних чисел:$1$,,,...$3$$5$,,,$2$$4$$6$,... Проблема полягає в тому, що парні числа зустрічаються місцями$\infty + 1$, $\infty + 2$,$\infty + 3$, А не на кінцевих позиціях.
Порожній набір можна перелічити: він перераховується порожнім списком!

Пропозиція$\PageIndex{1}$

Якщо$A$ має перерахування, воно має перерахування без повторень.

Доказ. Припустимо,$A$ має перерахування$x_1$$x_2$,... в якому кожен$x_i$ є елементом$A$. Ми можемо видалити повторення з перерахування, видаливши повторювані елементи. Наприклад, ми можемо перетворити перерахування на нове, в якому ми перераховуємо,$x_i$ якщо це елемент,$A$ який не є серед$x_1$,...,$x_{i-1}$ або видалити$x_i$ зі списку, якщо він вже з'являється серед $x_1$,...,$x_{i-1}$. ◻

Останній аргумент показує, що для того, щоб добре впоратися з перерахуваннями та підрахунковими множинами та довести речі про них, нам потрібно більш точне визначення. Це передбачено наступним чином.

Визначення$\PageIndex{2}$: Enumeration, formally

Перерахування множини$A \neq \emptyset$ - це будь-яка суб'єктивна функція$f \colon \PosInt \to A$.

Давайте переконаємо себе, що формальне визначення та неформальне визначення з використанням можливо нескінченного списку еквівалентні. По-перше, будь-яка суб'єктивна функція від$\PosInt$ до$A$ множини перераховує$A$. Така функція визначає перерахування, як визначено неофіційно вище: список$f(1)$,$f(2)$,$f(3)$,... Оскільки$f$ є суб'єктивним, кожен елемент$A$ гарантовано буде значенням$f(n)$ для деяких$n \in \PosInt$. Отже, кожен елемент$A$ з'являється на певній кінцевій позиції в списку. Оскільки функція може бути не ін'єкційною, список може бути надлишковим, але це допустимо (як зазначалося вище).

З іншого боку, враховуючи список, який перераховує всі елементи$A$, ми можемо визначити суб'єктивну функцію,$f\colon \PosInt \to A$ дозволяючи$f(n)$ бути$n$ й елемент списку, або кінцевий елемент списку, якщо немає$n$ го елемент. Єдиний випадок, коли це не виробляє суб'єктивну функцію -$A$ це коли порожній, а отже, список порожній. Отже, кожен непорожній список визначає суб'єктивну функцію$f\colon \PosInt \to A$.

Визначення$\PageIndex{3}$

Набір$A$ підраховується, якщо він порожній або має перерахування.

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

Функція, що перераховує натуральні числа ($\PosInt$) - це просто функція ідентичності, задана$f(n) = n$. Функція, що перераховує натуральні числа$\Nat$, є функцією$g(n) = n - 1$.

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

Функції$f\colon \PosInt \to \PosInt$ і$g \colon \PosInt \to \PosInt$ задані шляхом\[\begin{aligned} f(n) & = 2n \text{ and}\\ g(n) & = 2n+1\end{aligned}\] перерахування парних натуральних чисел і непарних натуральних чисел відповідно. Однак жодна функція не є перерахуванням$\PosInt$, оскільки жодна з них не є суб'єктивною.

Проблема$\PageIndex{1}$

Визначте перерахування позитивних квадратів$1$,$4$,$9$,$16$,...

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

Функція$f(n) = (-1)^{n} \lceil \frac{(n-1)}{2}\rceil$ (де$\lceil x \rceil$ позначає функцію стелі, яка округляється$x$ до найближчого цілого числа) перераховує безліч цілих чисел$\Int$. Зверніть увагу, як$f$ генерує значення$\Int$ шляхом «стрибків» вперед і назад між позитивними та негативними цілими числами:\[\begin{array}{c c c c c c c c} f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & f(7) & \dots \\ \\ - \lceil \tfrac{0}{2} \rceil & \lceil \tfrac{1}{2}\rceil & - \lceil \tfrac{2}{2} \rceil & \lceil \tfrac{3}{2} \rceil & - \lceil \tfrac{4}{2} \rceil & \lceil \tfrac{5}{2} \rceil & - \lceil \tfrac{6}{2} \rceil & \dots \\ \\ 0 & 1 & -1 & 2 & -2 & 3 & \dots \end{array}\nonumber\] Ви також можете думати про те,$f$ як визначено випадками наступним чином:\[f(n) = \begin{cases} 0 & \text{if $n = 1$}\\ n/2 & \text{if $n$ is even}\\ -(n-1)/2 & \text{if $n$ is odd and $>1$} \end{cases}\nonumber\]

Проблема$\PageIndex{2}$

Покажіть, що якщо$A$ і$B$ підраховуються, так і є$A \cup B$. Для цього припустимо, що існують суб'єктивні функції$f\colon \PosInt \to A$ і$g\colon \PosInt \to B$, і визначити суб'єктивну функцію$h\colon \PosInt \to A \cup B$ і довести, що вона є суб'єктивною. Також розглянемо випадки, коли$A$ або$B = \emptyset$.

Проблема$\PageIndex{3}$

Покажіть, що якщо$B \subseteq A$ і$A$ підраховується, так і є$B$. Для цього припустимо, що існує суб'єктивна функція$f\colon \PosInt \to A$. Визначте суб'єктивну функцію$g\colon \PosInt \to B$ і доведіть, що вона є суб'єктивною. Що станеться, якщо$B = \emptyset$?

Проблема$\PageIndex{4}$

Покажіть за допомогою індукції$A_1$,$n$ що якщо$A_2$,,...,$A_n$ всі лічильні, так і є$A_1 \cup \dots \cup A_n$. Ви можете припустити той факт, що якщо два$A$ набори і$B$ є підрахунковими, так і є$A \cup B$.

Хоча це, мабуть, більш природно при перерахуванні елементів набору, щоб почати відлік від$1$ st елемента, математики люблять використовувати натуральні числа$\Nat$ для підрахунку речей. Вони говорять про те,$0$$1$ й,$2$ і так далі, елементах списку. Відповідно, ми можемо визначити перерахування як суб'єктивну функцію від$\Nat$ до$A$. Звичайно, два визначення рівнозначні.

Пропозиція$\PageIndex{2}$

Відбувається$f\colon \PosInt \to A$ відрив, якщо відбувається відрив$g\colon \Nat \to A$.

Доказ. З огляду на$f\colon \PosInt \to A$ відмову, ми можемо визначити$g(n) = f(n+1)$ для всіх$n \in \Nat$. Легко помітити, що$g\colon \Nat \to A$ є суб'єктивним. І навпаки, з огляду на відхилення$g\colon \Nat \to A$, визначте$f(n) = g(n+1)$. ◻

Це дає нам наступний результат:

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

Набір$A$ підраховується, якщо він порожній або є суб'єктивна функція$f\colon \Nat \to A$.

Вище ми обговорювали, що список елементів набору$A$ можна перетворити в список без повторів. Це справедливо і для перерахувань, але трохи складніше сформулювати і доводити суворо. Будь-яка функція$f\colon \PosInt \to A$ повинна бути визначена для всіх$n \in \PosInt$. Якщо є тільки скінченно багато елементів,$A$ то ми явно не можемо мати функцію, визначену на нескінченно багато елементів$\PosInt$, що приймає як значення всі елементи,$A$ але ніколи не приймає однакове значення двічі. У такому випадку, тобто у випадку, коли список без повторень є кінцевим, ми повинні вибрати інший домен для$f$, один з лише скінченно багатьма елементами. Відсутність повторень означає, що$f$ він повинен бути ін'єкційним. Оскільки він також є суб'єктивним, ми шукаємо біекцію між деякими скінченними множинами$\{1, \dots, n\}$ або$\PosInt$ і$A$.

Пропозиція$\PageIndex{3}$

Якщо$f\colon \PosInt \to A$ є суб'єктивним (тобто перерахуванням$A$), існує біекція,$g\colon Z \to A$ де$Z$ є$\PosInt$ або$\{1, \dots, n\}$ для деяких$n \in \PosInt$.

Доказ. Визначаємо функцію$g$ рекурсивно: Нехай$g(1) = f(1)$. Якщо$g(i)$ вже було визначено, нехай$g(i+1)$ буде перше значення$f(1)$,$f(2)$,... вже не серед$g(1)$,...$g(i)$,, якщо є. Якщо$A$ має тільки$n$ елементи, то$g(1)$,...,$g(n)$ всі визначені, і тому ми визначили функцію$g\colon \{1, \dots, n\} \to A$. Якщо$A$ має нескінченно багато елементів, то для будь-якого$i$ повинен бути елемент$A$ у перерахуванні$f(1)$,$f(2)$,..., який ще не є серед$g(1)$,...,$g(i)$. У цьому випадку ми визначили функцію$g\colon \PosInt \to A$.

Функція$g$ є суб'єктивною, оскільки будь-який елемент$A$ є серед$f(1)$,$f(2)$,... (оскільки$f$ є суб'єктивним) і так в кінцевому підсумку буде значенням$g(i)$ для деяких$i$. Це також ін'єкційно, оскільки якби було$j < i$ таке$g(j) = g(i)$, то вже було$g(i)$ б серед,...$g(1)$, всупереч тому$g(i-1)$, як ми визначили$g$. ◻

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

Набір$A$ підраховується, якщо він порожній або є біекція$f\colon N \to A$, де$N = \Nat$ або$N = \{0, \dots, n\}$ для деяких$n \in \Nat$.

Доказ. $A$$A$підраховується, якщо порожній або є примірник$f\colon \PosInt \to A$. За пропозицією$\PageIndex{3}$, останній тримає, якщо є двооб'єктивна функція$f\colon Z \to A$ де$Z = \PosInt$ або$Z = \{1, \dots, n\}$ для деяких$n \in \PosInt$. За тим же аргументом, що і в доказі Пропозиції$\PageIndex{2}$, що, в свою чергу, є випадок, якщо є біекція$g\colon N \to A$ де$N = \Nat$ або$N = \{0, \dots, n-1\}$. ◻

Проблема$\PageIndex{5}$

Згідно з $\PageIndex{3}$Визначенням,$A$ множина перераховується,$A = \emptyset$ якщо або є суб'єктивна$f\colon \PosInt \to A$. Також можна точно визначити «лічильну множину»: множина перелічується, якщо є ін'єкційна функція$g\colon A \to \PosInt$. Показати, що визначення еквівалентні, тобто показати, що існує$g\colon A \to \PosInt$ ін'єкційна функція, якщо$A = \emptyset$ або є суб'єктивна$f\colon \PosInt \to A$.