3.6: Докази та спростування екзистенціальних тверджень
- Page ID
- 64829
З певної точки зору в поточному розділі немає необхідності. Якщо ми доводимо екзистенціальне твердження, ми спростовуємо якесь універсальне твердження. (Про що вже йшлося.) Точно так само, якщо ми намагаємося спростувати екзистенціальне твердження, то ми фактично доводимо пов'язане універсальне твердження. Проте іноді спосіб викладання теореми підкреслює питання існування над відповідним універсалом — і тому люди говорять про доведення та спростування екзистенційних тверджень як окреме питання від універсальних тверджень.
Докази екзистенціальних питань бувають двох основних різновидів: конструктивні і неконструктивні. Конструктивні докази концептуально легше з двох - ви насправді називаєте приклад, який показує, що екзистенціальне питання є істинним. Наприклад:
Є рівний прайм.
- Доказ
-
Число\(2\) буває як парним, так і простим.
Q.E.D.
Числа Фібоначчі визначаються початковими значеннями\(F(0) = 1\)\(F(1) = 1\) та рекурсивною формулою\(F(n + 1) = F(n) + F(n − 1)\) (для отримання наступного числа в ряді ви додаєте останнє і передостаннє).
| \(n\) | \(F(n)\) |
|---|---|
| \ (n\) ">\(0\) | \ (F (n)\) ">\(1\) |
| \ (n\) ">\(1\) | \ (F (n)\) ">\(1\) |
| \ (n\) ">\(2\) | \ (F (n)\) ">\(2\) |
| \ (n\) ">\(3\) | \ (F (n)\) ">\(3\) |
| \ (n\) ">\(4\) | \ (F (n)\) ">\(5\) |
| \ (n\) ">\(5\) | \ (F (n)\) ">\(8\) |
| \ (n\) ">\(⋮\) | \ (F (n)\) ">\(⋮\) |
Доведіть, що існує число Фібоначчі, яке є ідеальним квадратом.
Неконструктивний доказ існування є складнішим. Один підхід полягає в тому, щоб сперечатися протиріччям - якщо річ, яку ми шукаємо, не існує, це призведе до абсурду. Інший підхід полягає в тому, щоб окреслити алгоритм пошуку потрібного елемента і надати аргумент, чому він не може вийти з ладу!
Особливо акуратний підхід - сперечатися, використовуючи дилему. Це моя улюблена неконструктивна екзистенціальна теорема/доказ.
Є ірраціональні числа\(α\) і\(β\) такі, які\(α^β\) є раціональними.
- Доказ
-
Якщо\(\sqrt{2}^{\sqrt{2}}\) раціонально, то ми закінчили. (Нехай\(α = β = \sqrt{2}\).) В іншому випадку нехай\(α = \sqrt{2}^{\sqrt{2}}\) і\(β = \sqrt{2}\). Результат випливає тому\(\left( \sqrt{2}^{\sqrt{2}} \right)^{\sqrt{2}} = \sqrt{2}^{(\sqrt{2}\sqrt{2})} = \sqrt{2}^{2} = 2\), що явно раціонально.
Q.E.D.
Багато екзистенціальних доказів включають властивість натуральних чисел, відомих як принцип упорядкування. Принцип добре впорядкування іноді скорочується WOP. Якщо набір має WOP, це не означає, що набір впорядкований особливо добре, а скоріше, що його підмножини схожі на свердловини - вид, який піднімає воду з відром на мотузці. Ви не повинні бути стурбовані WOP взагалі в цей момент, але зверніть увагу, що підмножини натуральних чисел мають особливо приємну властивість - будь-який непорожній набір натуральних чисел повинен мати найменший елемент (так само, як і кожен колодязь води має дно).
Оскільки натуральні числа мають принцип упорядкування, ми можемо довести, що існує найменше натуральне число з властивістю\(\text{X}\), просто знаходячи будь-яке натуральне число з властивістю\(\text{X}\) - зробивши це, ми показали, що набір натуральних чисел з властивістю не\(\text{X}\) є порожнім. і це єдина гіпотеза, яка потрібна WOP.
Наприклад, у вправах в Розділі 3.5 ми ввели числа вампірів. Число вампіра - це\(2n\) цифрове число\(v\), яке фактори, як\(v = xy\) де\(x\) і\(y\) є\(n\) цифрами, а цифри\(v\) - це саме цифри в\(x\) і\(y\) в певному порядку. Цифри\(x\) і\(y\) відомі як «ікла»\(v\). Для усунення банальних випадків обидва ікла можуть не закінчуватися нулями.
Існує найменший\(6\) -значне число вампіра.
- Доказ
-
Число\(125460\) - це число вампіра (насправді це найменший приклад числа вампіра з двома наборами іклів:\(125460 = 204 · 615 = 246 · 510\)). Оскільки набір чисел вампірів\(6\) -цифри непорожній, то принцип упорядкування натуральних чисел дозволяє зробити висновок, що існує найменший\(6\) -значний номер вампіра.
Q.E.D.
Це досить цікава ситуація в тому, що ми знаємо, що є найменший\(6\) -цифрове число вампіра, не маючи уявлення про те, що це таке!
Покажіть, що\(102510\) є найменшим\(6\) -значним числом вампіра.
Є досить багато випадків, коли нам потрібно довести твердження, що включають унікальний квантор існування\((∃!)\). У таких випадках нам потрібно зробити трохи більше роботи. Нам потрібно показати існування - конструктивно чи неконструктивно - і нам також потрібно проявити унікальність. Щоб навести приклад унікального доказу існування, ми повернемося до концепції, вперше обговорюваної в Розділі 1.5, і закінчимо якийсь бізнес, який був заглянутий там.
Нагадаємо алгоритм Евкліда, який використовувався для обчислення найбільшого спільного дільника двох цілих чисел\(a\) і\(b\) (який ми позначимо\(\text{gcd}(a, b)\)). Існує досить важливе питання щодо алгоритмів, відомих як «проблема зупинки». Чи програма в кінцевому підсумку зупиняється, або вона застряє в нескінченному циклі? Ми знаємо, що алгоритм Евкліда зупиняється (і виводить правильний результат), тому що ми знаємо наступний унікальний результат існування.
\(∀a, b ∈ \mathbb{Z} +, ∃! d ∈ \mathbb{Z}^+\)такий, що\(d = \text{gcd}(a, b)\)
Тепер, перш ніж ми зможемо довести цей результат, нам знадобиться точне визначення для\(\text{gcd}(a, b)\). По-перше, a\(\text{gcd}\) повинен бути загальним дільником, що означає, що він повинен розділити обидва\(a\) і\(b\). По-друге, серед усіх загальних дільників він повинен бути найбільшим. Цей другий пункт, як правило, вирішується, вимагаючи, щоб кожен інший загальний дільник ділив\(\text{gcd}\). Нарешті, ми повинні зазначити, що a\(\text{gcd}\) завжди позитивний, бо кожного разу, коли число ділить інше число, так і його негативне, і залежно від того, що з цих двох є позитивним, явно буде більшим! Це дозволяє нам розширити визначення\(\text{gcd}\) до всіх цілих чисел, але речі концептуально простіше, якщо ми тримаємо нашу увагу обмеженими позитивними цілими числами.
Найбільший спільний дільник, або gcd, з двох натуральних чисел\(a\) і\(b\) є додатним числом\(d\) таким, що\(d | a\)\(d | b\) і якщо\(c\) є будь-яким іншим натуральним числом, таким, що\(c |a\) і\(c | b\) тоді\(c |d\).
\[∀a, b, c, d ∈ \mathbb{Z}^+ d = \text{gcd}(a, b) \iff d|a ∧ d| b ∧ (c |a ∧ c | b \implies c |d)\]
Озброївшись цим визначенням, повернемо нашу увагу на доведення унікального існування\(\text{gcd}\). Унікальність частина простіше, тому ми зробимо це спочатку. Ми сперечаємося протиріччям. Припустимо, що було два різних числа\(d\) і\(d'\) задовольняють визначенню\(\text{gcd}(a, b)\). Поставте\(d'\) на місце\(c\) у визначенні, щоб побачити, що\(d' | d\). Аналогічно, ми можемо зробити висновок, що\(d | d'\) і якщо два числа кожне ділиться на інше, вони повинні бути рівними. Це протиріччя, оскільки ми\(d'\) припускали\(d\) і були різними.
Для частини існування нам потрібно визначити набір - відомий як\(\mathbb{Z}\) -модуль, згенерований\(a\) і\(b\) - який складається з усіх чисел форми\(xa+yb\) де\(x\) і\(y\) діапазону над цілими числами.
Цей набір має дуже приємний геометричний характер, який часто не отримує тієї уваги, яку він заслуговує. Кожен елемент\(\mathbb{Z}\) -модуля, породженого двома числами (\(15\)і\(21\) в прикладі) відповідає точці в евклідовій площині. Як зазначено на малюнку,\(3.6.1\) існує розділова лінія між додатними та негативними елементами в\(\mathbb{Z}\) -модулі. Також легко помітити, що є багато повторень однакового значення в різних точках площини.
Значення\(0\) явно виникає в\(\mathbb{Z}\) -модулі, коли обидва\(x\) і самі по собі\(y\) є нулем. Знайдіть іншу пару\((x, y)\) значень, таких, що\(21x + 15y\) дорівнює нулю. Який нахил прямої, яка відокремлює позитивні значення від негативних у нашому\(\mathbb{Z}\) -модулі?
Думаючи про цей\(\mathbb{Z}\) -модуль, і переглядаючи рисунок\(3.6.1\), ви, можливо, помітили, що найменше позитивне число в\(\mathbb{Z}\) -модулі є\(3\). Якщо ви цього не помітили, озирніться назад і перевірте цей факт зараз.
Як ми знаємо, що деяке менше позитивне значення (а\(1\) чи а\(2\)) не відбувається десь у евклідовій площині?
Те, що ми тільки що спостерігали, є конкретним екземпляром загального результату.
Найменше додатне число у\(\mathbb{Z}\) -модулі, що генерується\(a\) і\(b\) є\(d = \text{gcd}(a, b)\).
- Доказ
-
Припустимо, що d є найменшим додатним числом у модулі Zmodule\(\{xa+yb x, y ∈ \mathbb{Z}\}\). Існують особливі значення\(x\) і\(y\) (які ми будемо розрізняти з надмірними лініями) такі, що\(d = xa + yb\). Тепер легко побачити, що якщо\(c\) є будь-яким спільним дільником,\(a\) а\(b\) потім\(c |d\), так що залишається довести, що\(d\) сам по собі є дільником обох\(a\) і\(b\). Розглянемо\(d\) поділ на\(a\). За алгоритмом ділення існують однозначно\(q\) визначені числа і\(r\) такі, що\(a = qd+r\) з\(0 ≤ r < d\). Ми\(r = 0.\) покажемо, що Припустимо, навпаки, що r позитивний. Зверніть увагу, що ми можемо писати\(r\) як\(r = a − qd = a − q(\overline{x}a + \overline{y}b) = (1 − q \overline{x})a − q \overline{y}b\). Остання рівність показує, що\(r\) знаходиться в розглянутому\(\mathbb{Z}\) модулі, і так, оскільки\(d\) є найменшим натуральним числом в цьому\(\mathbb{Z}\) -модулі випливає те,\(r ≥ d\) що суперечить раніше зазначеним фактом\(r < d\). Таким чином,\(r = 0\) і так випливає, що\(d | a\). Цілком аналогічний аргумент може бути використаний, щоб показати те,\(d| b\) що завершує доказ цього\(d = \text{gcd}(a, b)\).
Q.E.D.
Вправи:
Покажіть, що існує ідеальний квадрат, який є сумою двох ідеальних квадратів.
Покажіть, що існує ідеальний куб, який є сумою трьох ідеальних кубиків.
Показати, що WOP не утримується в цілих числах. (Це доказ існування, ви показуєте, що існує підмножина\(\mathbb{Z}\), яка не має найменшого елемента.)
Покажіть, що WOP не тримається\(\mathbb{Q}^+\).
На доказ\(3.6.3\) Теореми ми визволили з того, щоб показати, що\(d | b\). Заповніть цю частину доказу.
Наведіть доказ унікального існування\(q\) і\(r\) в алгоритмі поділу.
Диграф - це малюнок, що містить сукупність точок, які з'єднані стрілками. Гра, відома як ножиці-папір-рок, може бути представлена диграфом, який збалансований (кожна точка має таку ж кількість стрілок, що виходять). Покажіть, що існує збалансований диграф, що має\(5\) точки.
