3.1: Прямі докази універсальних тверджень
- Page ID
- 64820
Якщо сформувати добуток\(4\) послідовних чисел, результат буде на одиницю менше ідеального квадрата. Спробуйте!
\(1 · 2 · 3 · 4 = 24 = 5^2 − 1\)
\(2 · 3 · 4 · 5 = 120 = 11^2 − 1\)
\(3 · 4 · 5 · 6 = 360 = 19^2 − 1\)
Це завжди працює!
Три розрахунки, які ми провели вище, є індуктивним аргументом на користь результату. Якщо вам подобається, ми можемо спробувати купу подальших прикладів,
\(13 · 14 · 15 · 16 = 43680 = 209^2 − 1\)
\(14 · 15 · 16 · 17 = 571200 = 239^2 − 1\)
але насправді, незалежно від того, скільки прикладів ми створюємо, ми не довели твердження - ми щойно дали докази.
Як правило, перше, що потрібно зробити, доводячи універсальне твердження, подібне до цього, - це перефразувати його як умовне. Отриманий оператор є універсальним умовним оператором або ПСК. Причина цього кроку полягає в тому, що гіпотези тоді будуть зрозумілі — вони формують попередник ПСК. Отже, хоча ви дійсно не досягли жодного прогресу в доказі, скориставшись цією порадою, ви принаймні будете знати, які інструменти у вас є під рукою. Беручи приклад, з якого ми почали, і перефразуючи його як UCS, ми отримуємо
\[∀a, b, c, d ∈ Z,(a,b,c,d \text{ consecutive}) \implies ∃k ∈ Z, a·b·c·d = k^2 − 1\]
Переднім ПСК є те\(a\), що\(b\),\(c\) і\(d\) повинні бути послідовними. Концентруючи свою увагу на тому, що означає бути послідовними, ми повинні швидко усвідомити, що оригінальний спосіб, яким ми думали про проблему, пов'язаний з червоною оселедець. Ми не повинні мати змінні для всіх чотирьох чисел; тому що вони послідовні, а однозначно визначає інші три. Нарешті, у нас є версія заяви, яку ми хотіли б довести, що має піддаватися нашим зусиллям щодо доказів.
\[∀a ∈ \mathbb{Z}, ∃k ∈ \mathbb{Z}, a(a + 1)(a + 2)(a + 3) = k^2 − 1.\]
У цьому спрощеному прикладі єдине, що нам потрібно зробити, це придумати значення для\(k\) даного, що ми знаємо, що\(a\) таке. Іншими словами, «доказ» цього твердження передбачає виконання деякої алгебри.
Без зайвих прихильностей.
- Доказ
-
Припустимо, що\(a\) це конкретне, але довільно вибране ціле число. Розглянемо добуток\(4\) послідовних цілих чисел\(a\),\(a + 1\),,\(a + 2\) і\(a + 3\). Ми хотіли б показати, що цей добуток на одиницю менше квадрата цілого числа\(k\). Нехай\(k\) буде\(a^2 + 3a + 1\).
По-перше, зверніть увагу, що
\[a(a + 1)(a + 2)(a + 3) = a^4 + 6a^3 + 11a^2 + 6a.\]
Потім зверніть увагу, що
\[k^2 − 1 = (a^2 + 3a + 1)^2 − 1 = (a^4 + 6a^3 + 11a^2 + 6a + 1) − 1 = a^4 + 6a^3 + 11a^2 + 6a.\]
Q.E.D.
Тепер, якщо ви дотримувалися алгебри вище, (жодна з яких не була особливо складною) доказ виступає цілком вагомим аргументом, що показує правдивість нашої пропозиції, але це дуже незадовільно! Вся справжня робота була прихована в одному суворому маленькому реченні: «Нехай\(k\) буде»\(a^2 + 3a + 1\). Звідки на Землі взялася ця особлива\(k\) цінність? Відповідь на це питання повинна, сподіваємось, переконати вас, що існує величезна різниця між розробкою доказів та написанням. Хороший доказ іноді може бути дещо схожим на гарну демонстрацію магії, маг не розкриває внутрішню роботу свого трюку, і математик не повинен відчувати себе винним у тому, щоб залишити деякі деталі за роботою! Чорт візьми, є багато разів, коли ви просто повинні здогадатися на щось, але якщо ваше припущення працює, ви можете написати абсолютно правильний доказ.
Розробляючи докази вище, ми помножили послідовні числа, а потім зрозуміли, що ми будемо зроблено, якби ми могли знайти многочлен в квадраті якого був\(a^4 + 6a^3 + 11a^2 + 6a + 1\). Тепер, очевидно, нам знадобиться квадратичний многочлен, і тому, що провідний термін є\(a^4\) і постійний термін є\(1\), він повинен бути форми\(a^2 + ma + 1\). Квадратуючи це дає\(a^4 + 2ma^3 + (m^2 + 2)a^2 + 2ma + 1\) і порівнюючи цей результат з тим, що ми хочемо, ми досить швидко розуміємо\(m\), що краще бути\(3\). Так що це не було магія зрештою!
Це здається вдалим часом, щоб прокоментувати поліноміальну арифметику. Багато людей здаються (або йдуть шукати систему комп'ютерної алгебри), коли мають справу з продуктами чогось більшого, ніж біноміали. Це прикро, тому що існує легкий метод з використанням таблиці для виконання таких множень. Як приклад, при розробці попереднього доказу нам потрібно було сформувати продукт\(a(a + 1)(a + 2)(a + 3)\), тепер ми можемо використовувати розподільний закон або сумнозвісне правило F.O.I.L, щоб помножити їх пари, але нам все одно потрібно\((a^2 + a)\) помножити\((a^2 + 5a + 6)\). Створіть таблицю, яка містить терміни цих двох многочленів як заголовки рядків і стовпців.
| \(a^2\) | \(5a\) | \(6\) | |
|---|---|---|---|
| \(a^2\) | \ (a^2\) "> | \ (5а\) "> | \ (6\) "> |
| \(a\) | \ (a^2\) "> | \ (5а\) "> | \ (6\) "> |
Тепер заповніть записи таблиці, множивши відповідні заголовки рядків і стовпців.
| \(a^2\) | \(5a\) | \(6\) | |
|---|---|---|---|
| \(a^2\) | \ (a^2\) ">\(a^4\) | \ (5а\) ">\(5a^3\) | \ (6\) ">\(6a^2\) |
| \(a\) | \ (a^2\) ">\(a^3\) | \ (5а\) ">\(5a^2\) | \ (6\) ">\(6a\) |
Нарешті складіть всі записи таблиці, поєднуючи будь-які подібні терміни.
Слід зазначити, що правило F.O.I.L - це всього лише мнемоніка для випадку, коли таблиця має\(2\) рядки та\(2\) стовпці.
Гаразд, давайте повернемося до того, щоб робити докази. Ми збираємося зробити багато доказів, що включають поняття елементарної теорії чисел, тому, як зручність, всі визначення, які були зроблені в главі 1, зібрані разом в таблиці нижче.
| Ім'я | Визначення |
|---|---|
| Навіть | \(∀n \in \mathbb{Z}\),\(n\) парний\ (\ якщо кз, n = 2k\) |
| Непарні | \(∀n \in \mathbb{Z}\),\(n\) є непарним\(\iff ∃k∈Z,n=2k+1\) |
| подільність | \(∀n \in \mathbb{Z}\),\(∀ d>0 \in \mathbb{Z}\),\(d|n \iff ∃k∈\mathbb{Z},n=kd\) |
| Поверх | \(∀x \in \mathbb{R}\),\(y=⌊x⌋ \iff y∈\mathbb{Z}∧y≤x<y+1\) |
| Стельові | \(∀x \in \mathbb{R}\),\(y=⌈x⌉ \iff y∈\mathbb{Z}∧y−1<x≤y\) |
| Теорема частки-залишки, Div і Mod | \(∀n, d>0 \in \mathbb{Z}\),\(∃!q,r∈\mathbb{Z},n=qd+r∧0≤r<d n \text{ div } d=q n \text{ mod } =r\) |
| Прем'єр | \(∀p \in \mathbb{Z}\),\(p\) є основним\(\iff (p>1)∧(∀x,y∈\mathbb{Z}^+,p=xy \implies x=1∨y=1) \) |
У цьому розділі ми переймаємося прямими доказами універсальних висловлювань. Такі заяви мають два смаки - ті, які, здається, включають умовні, і ті, які не:
Кожне просте число більше двох є непарним.
проти
Для всіх цілих чисел\(n\), якщо\(n\) просте число більше двох, то\(n\) непарне.
Ці дві форми легко трансформуються одна в іншу, тому ми завжди будемо концентруватися на останній. Прямий доказ ПСК завжди слідує за формою, відомою як «узагальнююча від загальної особливості». Ми намагаємося довести, що x U, P (x) =⇒ Q (x). Аргумент (в скелетному контурі) буде виглядати так:
Доказ: Припустимо, що a є певним, але довільним елементом\(U\) такого, що\(P(a)\) тримає.
Тому\(Q(a)\) вірно.
Таким чином, ми показали, що для всіх\(x\) в\(U\),\(P(x) \implies Q(x)\).
Q.E.D.
Гаразд, так що цей контур досить дерьмово. Це говорить вам, як почати і закінчити прямий доказ, але ці неприємні точки-крапки посередині - це те, куди повинна йти вся реальна робота. Якби я міг сказати вам (навіть у контурі), як заповнити ці крапки, це означало б математичне доказ насправді не дуже цікаве заняття. Заповнення цих крапок іноді (рідко) буде очевидним, частіше це буде надзвичайно складним; це вимагатиме великої творчості, навантажень концентрації, ви зателефонуєте на всі ваші попередні математичні переживання, і ви, швидше за все, відчуєте певний ступінь туги. Просто пам'ятайте, що ваше почуття виконань пропорційно складності головоломок, які ви намагаєтеся. Отже, давайте спробуємо інше.
У таблиці 3.1.1 одне з дуже зручних понять визначено - це підлога дійсного числа.
\[y = \lfloor x \rfloor \iff (y ∈ \mathbb{Z} ∧ y ≤ x < y + 1).\]
Існує сумна тенденція у людей застосовувати старі правила в нових ситуаціях тільки через випадкову схожість в позначеннях. Дужки, що використовуються при позначенні функції статі, виглядають дуже схожими на звичайні дужки, тому часто пропонується наступне «правило»
\[\lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor\]
Знайдіть контрприклад до попереднього «правила».
Що (можливо) дивно, що якщо одне з задіяних чисел є цілим, то «правило» дійсно працює.
\[∀x ∈ \mathbb{R}, ∀n ∈ \mathbb{Z}, \lfloor x + n \rfloor = \lfloor x \rfloor + \lfloor n \rfloor\]
Так як підлогу ціле число, що ціле, ми могли б повторно це як\(\lfloor x+n \rfloor = \lfloor x \rfloor + n\).
Тепер давайте спробуємо перефразувати цю теорему як ПСК: Якщо\(x\) є дійсним числом, а n - ціле число, то\(\lfloor x + n \rfloor = \lfloor x \rfloor + n\). Це погано... здається, що єдині гіпотези, які ми можемо використовувати, стосуються того, які типи чисел\(x\) і\(n\) є - наші гіпотези не особливо потужні. Ваші наступні найкорисніші союзники у побудові доказів - це визначення задіяних понять. Кількість\(\lfloor x \rfloor\) з'являється в теоремі, скористаємося визначенням:
\[a = \lfloor x \rfloor \iff a ∈ \mathbb{Z} ∧ a ≤ x < a + 1.\]
Єдина інша функція підлоги, яка з'являється у твердженні теореми (можливо, навіть більш помітною)\(\lfloor x + n \rfloor\), - це, тут визначення дає нам
\[b = \lfloor x + n \rfloor \iff b ∈ Z ∧ b ≤ x + n < b + 1.\]
Ці визначення є нашими єдиними доступними інструментами, тому нам, безумовно, доведеться їх використовувати, і важливо помітити, що це добре; визначення дозволяють нам працювати з чимось добре зрозумілим (нерівності, які з'являються всередині них), а не з чимось новим і відносно підозрілим ( позначення підлоги). Складання доказів цього твердження разом - це вправа дивитися на два визначення вище і відзначити, як одне можна перетворити в інше. Це також є свідченням сили іменування речей.
- Доказ
-
Припустимо, що\(x\) це конкретне, але довільне дійсне число і що\(n\) є певним, але довільним цілим числом. Нехай\(a = \lfloor x \rfloor\). За визначенням функції статі випливає, що a - ціле число і\(a ≤ x < a + 1\). Додаючи\(n\) до кожної з частин цієї нерівності, ми виводимо нову (і однаково справедливу) нерівність,\(a + n ≤ x + n < a + n + 1\). Зверніть увагу, що\(a + n\) це ціле число і нерівність вище разом з цим фактом складають саме визначення\(a + n = \lfloor x + n \rfloor\). Нарешті, нагадавши, що\(a = \lfloor x \rfloor\) (за припущенням), і переписуючи, отримуємо бажаний результат
\[\lfloor x + n \rfloor = \lfloor x \rfloor + n.\]
Q.E.D.
Як ми бачили на прикладах, представлених у цьому розділі, придумування доказів іноді може включати трохи винахідливості. Але, іноді, є «слідувати за своїм носом» свого роду підхід, який дозволить вам розробити вагомий аргумент, не обов'язково показуючи будь-які великі стрибки генія! Ось кілька порад щодо коректури:
- Перш ніж що-небудь ще, визначте, які саме гіпотези ви можете використовувати.
- Запишіть визначення чого-небудь в твердженні теореми.
- У вашому розпорядженні 26 букв (і навіть більше, якщо ви знаєте грецьку мову) (і ви завжди можете кинути на індекси!) не скупіться на букви. Найнеприємніша помилка, яку ви можете зробити, - це використовувати одну і ту ж змінну для двох різних речей.
- Будь ласка, напишіть спочатку чорновий проект. Напишіть два чернетки! Навіть якщо ви можете написати красиву, зрозумілу прозу на першому обході, вона не летить, коли мова йде про організацію доказу.
- Висловлювання в доказі повинні бути логічними твердженнями. Це означає, що вони повинні бути логічними (твердження, які або true або false). Алгебраїчний вираз сам по собі не рахується, нерівність чи рівність робить.
- Не кажіть «якщо», коли ви маєте на увазі «з тих пір». Дійсно! Якщо ви починаєте доказ про раціональні числа так:
Доказ: Припустимо, що\(x\) це конкретне, але довільне раціональне число. Якщо\(x\) раціональне число, то з цього випливає.
люди будуть дивитися на вас смішно. Який сенс припускати, що\(x\) це раціонально, а потім діяти так, ніби ви сумніваєтеся в цьому факті, написавши «якщо»? Ви маєте на увазі «з тих пір».
- Відзначте початок і кінець своїх доказів як натяк своїм читачам. У цій книзі ми починаємо доказ, написавши курсивом «Proof:», а кожен доказ закінчуємо абревіатурою Q.E.D. 1
Ми закриємо цей розділ словом про аксіоми. Аксіоми в будь-якій даній області математики є вашими найбільш фундаментальними інструментами. Аксіоми не потрібно доводити - ми повинні просто прийняти їх! Дуже поширеною проблемою для початківців письменників доказів є розповідь про різницю між аксіоматичними твердженнями та твердженнями, які вимагають певних доказів. Наприклад, у вправах для цього розділу є проблема, яка просить нас довести, що сума двох раціональних чисел є раціональною. Хіба це не здається, що це може бути однією з аксіом раціональних чисел? Невже це те, що можна довести? Ну, ми знаємо, як працює процес додавання раціональних чисел: ставимо дроби над спільним знаменником, а потім просто додаємо чисельники. Ви бачите, як додавання дробів дійсно спирається на нашу здатність додавати чисельники (які є цілими числами). Таким чином, у виконанні цієї вправи ви можете використовувати факт (дійсно, вам потрібно буде використовувати той факт), що сума двох цілих чисел є цілим числом. Так як щодо цього твердження? Чи потрібно доводити, що додавання цілих чисел дає ціле число? Насправді, це необхідно, оскільки структура цілих чисел спирається на фундамент, відомий як аксіоми Пеано для природних - і аксіоми Пеано не включають той, який гарантує, що сума двох натуральних також є природною. Якщо у вас є спокуса простежити все це назад, щоб «дізнатися, наскільки глибоко йде кроляча нора», я рекомендую вам. Але, якщо ви просто хочете мати можливість продовжувати робити ваші домашні завдання проблеми, я також співчуваю цим настроям. Давайте погодитися, що цілі числа поводяться так, як ми очікували - якщо додати або помножити цілі числа, результат буде цілим числом.
Вправи:
Кожне просте число більше ніж\(3\) є однієї з двох форм\(6k + 1\) або\(6k + 5\). Яке твердження (и) може бути використано як гіпотези при доведенні цієї теореми?
Доведіть, що\(129\) це дивно.
Довести, що сума двох раціональних чисел є раціональним числом.
Доведіть, що сума непарного числа і парного числа непарна.
Доведіть, що якщо сума двох цілих чисел парна, то так їх різниця.
Доведіть, що для кожного реального числа\(x\),\(\dfrac{2}{3} < x < \dfrac{3}{4} \implies \lfloor 12x \rfloor = 8\).
Доведіть, що якщо\(x\) непарне ціле число,\(x^2\) то має вигляд\(4k + 1\) для деякого цілого числа\(k\).
Доведіть, що для всіх цілих чисел\(a\) і\(b\), якщо\(a\) непарний і\(6 |(a + b)\), то\(b\) непарний.
Доведіть це\(∀x ∈ \mathbb{R}, x \notin \mathbb{Z} \implies \lfloor x \rfloor + \lfloor−x \rfloor = −1\).
Визначте рівність цілого числа\(n\) за допомогою:
\(\text{evenness}(n) = k \iff 2^k |n ∧ 2^{k+1} - n∤\)
Створіть і доведіть теорему, що стосується рівності виробів.
Припустимо\(a\), що,\(b\) і\(c\) є цілими числами такі, що\(a| b\) і\(b | c\). Доведіть це\(a| c\).
Припустимо\(a\), що\(b\),\(c\) і\(d\) є цілими числами с\(a \neq c\). Далі, припустимо, що\(x\) це дійсне число, що задовольняє рівнянню
\(\dfrac{ax+b}{cx+d} = 1.\)
Покажіть,\(x\) що раціонально. Де\(a \neq c\) використовується гіпотеза?
Показати, що якщо два натуральних числа\(a\)\(a | b\) і\(b\) задовольняють,\(b | a\) а потім вони рівні.