4.4: Функції та коди сполучення

Template:MathJaxZach

Цигзагоподібний метод Кантора робить перераховуваність\(\Nat^n\) візуально очевидною. Але давайте зосередимося на нашому масиві із зображенням\(\Nat^2\). Слідуючи зигзагоподібному рядку в масиві і підраховуючи місця, ми можемо перевірити, що\(\tuple{1,2}\) пов'язано з числом\(7\). Однак було б непогано, якби ми могли обчислити це більш безпосередньо. Тобто непогано було б здати зворотне зигзагоподібного перерахування, таке\(g\colon \Nat^2 \to \Nat\), що б\[g(\tuple{0,0}) = 0, \; g(\tuple{0,1}) = 1, \; g(\tuple{1,0}) = 2, \; \dots, g(\tuple{1,2}) = 7, \; \dots\nonumber\] це дало можливість обчислити, де саме\(\tuple{n, m}\) буде відбуватися в нашому перерахуванні.

Насправді ми можемо визначити\(g\) безпосередньо, зробивши два спостереження. По-перше: якщо\(n\) той рядок і\(m\) стовпець містять значення\(v\), то\((n+1)\) перший рядок і\((m-1)\) перший стовпець містять значення\(v + 1\). Друге: перший ряд нашого перерахування складається з трикутних чисел, починаючи з\(0\),\(1\),\(3\)\(5\), і т.д. трикутне число - це сума натуральних чисел\(< k\),\(k\) які можна обчислити як\(k(k+1)/2\). Склавши ці два спостереження воєдино, розглянемо цю функцію:\[g(n,m) = \frac{(n+m+1)(n+m)}{2} + n\nonumber\] ми часто просто пишемо\(g(n, m)\) скоріше що\(g(\tuple{n, m})\), так як легше на очах. Це говорить вам спочатку визначити число\((n+m)^\text{th}\) трикутника, а потім відняти\(n\) від нього. І він заповнює масив саме так, як ми хотіли б. Так, зокрема, пара\(\tuple{1, 2}\) відправляється в\(\frac{4 \times 3}{2} + 1 = 7\).

Ця функція\(g\) є оберненою перерахуванням множини пар. Такі функції називаються функціями сполучення.

Визначення\(\PageIndex{1}\): Pairing function

Функція\(f\colon A \times B \to \Nat\) - це арифметична функція сполучення, якщо вона\(f\) є ін'єкційною. Ми також говоримо, що\(f\) \(A \times B\)кодує, і\(f(x,y)\) це код для\(\tuple{x,y}\).

Ми можемо використовувати функції сполучення кодувати, наприклад, пари натуральних чисел; або, іншими словами, ми можемо представляти кожну пару елементів за допомогою одного числа. Використовуючи обернену функцію сполучення, ми можемо розшифрувати число, тобто з'ясувати, яку пару воно представляє.

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

Дайте перерахування множини всіх невід'ємних раціональних чисел.

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

Покажіть,\(\Rat\) що підраховується. Нагадаємо, що будь-яке раціональне число можна записати у вигляді дробу\(z/m\) з\(z \in \Int\),\(m \in \Nat^+\).

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

Визначте перерахування\(\Bin^*\).

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

Згадайте з вашого вступного логічного курсу, що кожна можлива таблиця істини виражає функцію істини. Іншими словами, функції істини - це всі функції з\(\Bin^k \to \Bin\) для деяких\(k\). Доведіть, що множина всіх функцій істини перелічити.

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

Показати, що множина всіх скінченних підмножин довільної нескінченної обчислювальної множини є підрахунковою.

Проблема\(\PageIndex{6}\)

Підмножина, як кажуть,\(\Nat\) є коскінченним, якщо це доповнення скінченної\(\Nat\) множини; тобто\(A \subseteq \Nat\) є кофінітним iff\(\Nat\setminus A\) є кінцевим. \(I\)Дозволяти множина, чиї елементи є точно скінченними і коскінченними підмножинами\(\Nat\). Покажіть,\(I\) що підраховується.

Проблема\(\PageIndex{7}\)

Покажіть, що обчислювальний союз лічильних множин підлягає підрахунку. Тобто всякий раз, коли\(A_1\)\(A_2\),,,... є множинами, і кожен\(A_i\) підлягає зліченню, тоді союз\(\bigcup_{i=1}^\infty A_i\) усіх з них також підраховується. [NB: це важко!]

Проблема\(\PageIndex{8}\)

\(f \colon A \times B \to \Nat\)Дозволяти довільна функція сполучення. Показати, що\(f\) зворотне - це перерахування\(A \times B\).

Проблема\(\PageIndex{9}\)

Вкажіть функцію, яка кодує\(\Nat^3\).