A.4: Шаблони висновків
- Page ID
- 52789
Докази складаються з індивідуальних висновків. Коли ми робимо висновок, ми зазвичай вказуємо, що, використовуючи таке слово, як «так», «таким чином» або «отже». Висновок часто спирається на один або два факти, які ми вже маємо в нашому доказі - це може бути те, що ми припустили, або те, що ми вже зробили висновок. Щоб бути зрозумілим, ми можемо позначити ці речі, і у висновку ми вказуємо, які інші твердження ми використовуємо у висновку. Висновок часто також містить пояснення того, чому наш новий висновок випливає з речей, які приходять до нього. Є деякі загальні шаблони висновку, які дуже часто використовуються в доказах; ми розглянемо деякі нижче. Деякі закономірності висновку, такі як докази шляхом індукції, більш залучені (і будуть розглянуті пізніше).
Ми вже обговорювали одну модель висновку: розпакування або застосування визначення. Коли ми розпаковуємо визначення, ми просто повторюємо щось, що включає definiendum, використовуючи definiens. Наприклад, припустимо, що ми вже встановили в ході доказу, що\(D = E\) (а). Тоді ми можемо застосувати визначення\(=\) для множин і зробити висновок: «Таким чином, за визначенням з (a), кожен елемент\(D\) є елементом\(E\) і навпаки».
Дещо заплутано, ми часто не пишемо виправдання висновку, коли насправді робимо це, а раніше. Припустимо, ми цього ще не довели\(D = E\), але хочемо. Якщо\(D = E\) є висновком, до якого ми прагнемо, то ми можемо повторити цю мету також, застосувавши визначення: щоб довести\(D = E\), що кожен елемент\(D\) є елементом\(E\) і навпаки. Таким чином, наше доказ матиме вигляд: (а) довести, що кожен елемент\(D\) є елементом\(E\); (b) кожен елемент\(E\) є елементом\(D\); (c) отже, від (a) і (b) за визначенням\(=\), \(D = E\). Але ми зазвичай не писали б це так. Замість цього ми могли б написати щось на кшталт
Ми хочемо показати\(D = E\). За визначенням\(=\), це означає показ того, що кожен елемент\(D\) є елементом\(E\) і навпаки.
(а)... (доказ того, що кожен елемент\(D\) є елементом\(E\))...
(б)... (доказ того, що кожен елемент\(E\) є елементом\(D\))...
Використання кон'юнкції
Мабуть, найпростішим зразком висновку є те, що зробити висновок одного з кон'юнктів сполучника. Іншими словами: якщо ми припустили або вже довели, що\(p\) і\(q\), то ми маємо право зробити висновок, що\(p\) (а також що\(q\)). Це такий базовий висновок, що про нього часто не згадується. Наприклад, як тільки ми розпакували визначення\(D = E\) ми встановили, що кожен елемент\(D\) є елементом\(E\) і навпаки. З цього можна зробити висновок, що кожен елемент\(E\) є елементом\(D\) (це частина «навпаки»).
Доведення кон'юнкції
Іноді те, що вас попросять довести, матиме форму кон'юнкції; вас попросять «довести\(p\) і»\(q\). В цьому випадку вам просто доведеться зробити дві речі: довести\(p\), а потім довести\(q\). Ви можете розділити свій доказ на два розділи, і для наочності позначити їх. Коли ви робите свої перші нотатки, ви можете написати «(1) Довести\(p\)» у верхній частині сторінки та «(2) Довести\(q\)» в середині сторінки. (Звичайно, вас не можуть явно попросити довести кон'юнкцію, але виявите, що ваш доказ вимагає, щоб ви довели сполучення. Наприклад, якщо вас попросять довести, що\(D = E\) ви виявите, що після розпакування визначення\(=\), ви повинні довести: кожен елемент\(D\) є елементом\(E\) і кожен елемент \(E\)є елементом\(D\)).
Доведення диз'юнкції
Коли те, що ви доводите, набуває форми диз'юнкції (тобто це твердження форми «\(p\)або\(q\)»), досить показати, що один з диз'юнктів є істинним. Однак в основному ніколи не буває, що або диз'юнкт просто випливає з припущень вашої теореми. Найчастіше припущення вашої теореми самі по собі диз'юнктивні, або ви показуєте, що всі речі певного роду мають одну з двох властивостей, але деякі речі мають одну, а інші мають іншу властивість. Ось де доказ за випадками є корисним (див. Нижче).
Умовний доказ
Багато теорем, з якими ви зіткнетеся, знаходяться в умовній формі (тобто показують, що якщо\(p\) тримає,\(q\) то також вірно). Ці випадки приємні і прості в налаштуванні - просто припустити попереднє умовне (в даному випадку\(p\)) і довести висновок\(q\) з нього. Отже, якщо ваша теорема говорить: «Якщо\(p\) тоді»\(q\), ви починаєте свій доказ з «припустити\(p\)», і в кінці ви повинні були довести\(q\).
Умовні умови можуть бути викладені по-різному. Таким чином, замість «Якщо\(p\) тоді»\(q\), теорема може стверджувати, що «\(p\)тільки якщо»\(q\), «\(q\)якщо\(p\)» або «\(q\), за умови»\(p\). Всі вони означають те ж саме і вимагають припущення\(p\) та підтвердження\(q\) з цього припущення. Нагадаємо, що двозастережний («\(p\)якщо і тільки якщо (iff)\(q\)») - це дійсно два умовні умови, зібрані разом: якщо\(p\) тоді\(q\), а якщо\(q\) тоді\(p\). Все, що вам потрібно зробити, це два екземпляри умовного доказу: один для першого умовного та інший для другого. Іноді, однак, можна довести твердження «iff», об'єднавши купу інших тверджень «iff», так що ви починаєте з «\(p\)» і закінчуєте «\(q\)» - але в цьому випадку ви повинні переконатися, що кожен крок дійсно є «iff».
Універсальні претензії
Використовувати універсальну претензію просто: якщо щось вірно для чогось, це вірно для кожної конкретної речі. Отже, якщо, скажімо, гіпотеза вашого доказу полягає в тому\(A \subseteq B\), що означає (розпакування визначення\(\subseteq\)), що, для кожного\(x \in A\),\(x \in B\). Таким чином, якщо ви вже знаєте\(z \in A\), що, ви можете зробити висновок\(z \in B\).
Доведення універсальної претензії може здатися трохи складним. Зазвичай ці твердження набувають такого вигляду: «Якщо\(x\) has\(P\), то воно has\(Q\)» або «Все\(P\) s є\(Q\) s». Звичайно, це може не відповідати цій формі ідеально, і потрібно трохи практики, щоб з'ясувати, що ви просять довести точно. Але: нам часто доводиться доводити, що всі об'єкти з якоюсь властивістю мають певну іншу властивість.
Спосіб довести універсальну претензію полягає у введенні імен або змінних для речей, які мають одну властивість, а потім показати, що вони також мають іншу властивість. Ми могли б поставити це, сказавши, що довести щось для всіх\(P\) s ви повинні довести це для довільного\(P\). І введене ім'я - це ім'я для довільного\(P\). Зазвичай ми використовуємо окремі літери як ці назви для довільних речей, а літери зазвичай відповідають умовам: наприклад, ми використовуємо\(n\) для натуральних чисел,\(A\) для формул,\(A\)\(f\) для множин, функцій тощо.
Хитрість полягає в тому, щоб підтримувати загальність протягом усього доказу. Ви починаєте з припущення, що довільний об'єкт («\(x\)») має властивість\(P\), і показати (тільки на основі визначень або того, що ви можете припустити), що\(x\) має властивість\(Q\). Оскільки ви не обумовили,\(x\) що конкретно, інше, що воно має властивість\(P\), то ви можете стверджувати, що всі\(P\) мають властивість\(Q\). Коротше кажучи,\(x\) це стенд-ін для всіх речей з майном\(P\).
Пропозиція\(\PageIndex{1}\)
Для всіх наборів\(A\) і\(B\),\(A \subseteq A \cup B\).
Доказ. \(B\)Дозволяти\(A\) і бути довільними множинами. Ми хочемо це показати\(A \subseteq A \cup B\). За визначенням\(\subseteq\), це становить: для кожного\(x\), якщо\(x \in A\) тоді\(x \in A \cup B\). Так нехай\(x \in A\) бути довільним елементом\(A\). Ми мусимо це показати\(x \in A \cup B\). З тих пір\(x \in A\),\(x \in A\) або\(x \in B\). Таким чином,\(x \in \Setabs{x}{x \in A \lor x \in B}\). Але це, за визначенням\(\cup\), означає\(x \in A \cup B\). ◻
Доказ у справах
Припустимо, у вас є диз'юнкція як припущення або як вже встановлений висновок - ви припустили або довели, що\(q\) це\(p\) чи правда. Ти хочеш довести\(r\). Ви робите це в два кроки: спочатку ви припускаєте, що\(p\) це правда, і доводите\(r\), потім припускаєте, що\(q\) це правда і\(r\) знову доводите. Це працює, тому що ми припускаємо або знаємо, що одна з двох альтернатив має місце. Два кроки встановлюють, що будь-якого з них достатньо для правди\(r\). (Якщо обидва вірні, у нас є не одна, а дві причини, чому\(r\) це правда. Не варто окремо доводити, що\(r\) це правда, припускаючи\(p\) і те й інше\(q\).) Щоб вказати, що ми робимо, ми оголошуємо, що «розрізняємо випадки». Наприклад, припустимо, ми це знаємо\(x \in B \cup C\). \(B \cup C\)визначається як\(\Setabs{x}{x \in B \text{ or } x \in C}\). Іншими словами, за визначенням,\(x \in B\) або\(x \in C\). Ми б довели, що\(x \in A\) з цього спочатку припускаючи\(x \in B\), що, і доводячи\(x \in A\) з цього припущення, а потім припустимо\(x \in C\), і знову\(x \in A\) довели з цього. Ви б написали «Ми розрізняємо випадки» під припущенням, потім «Справа (1):\(x \in B\)» під ним і «Справа (2): на\(x \in C\) півдорозі вниз сторінки. Потім ви перейдете до заповнення верхньої половини та нижньої половини сторінки.
Доказ випадків особливо корисний, якщо те, що ви доказуєте, саме по собі диз'юнктивне. Ось простий приклад:
Пропозиція\(\PageIndex{2}\)
Припустимо\(B \subseteq D\), і\(C \subseteq E\). Потім\(B \cup C \subseteq D \cup E\).
Доказ. Припустимо (а) що\(B \subseteq D\) і (б)\(C \subseteq E\). За визначенням, будь-який також\(x \in B\) є\(\in D\) (c) і any\(x \in C\) також\(\in E\) (d). Щоб показати це\(B \cup C \subseteq D \cup E\), ми повинні показати, що якщо\(x \in B \cup C\) потім\(x \in D \cup E\) (за визначенням\(\subseteq\)). \(x \in B \cup C\)iff\(x \in B\) або\(x \in C\) (за визначенням\(\cup\)). Аналогічно,\(x \in D \cup E\) якщо\(x \in D\) або\(x \in E\). Отже, ми повинні показати: для будь-якого\(x\), якщо\(x \in B\) або\(x \in C\), то\(x \in D\) або\(x \in E\).
Поки що ми тільки розпаковані визначення! Ми переформулювали нашу пропозицію без\(\subseteq\)\(\cup\) і залишаємося з намагатися довести універсальну умовну претензію. За тим, що ми обговорювали вище, це робиться, припускаючи, що\(x\) це те, про що ми припускаємо, що частина «якщо» вірна, і ми продовжимо показувати, що «тоді» частина вірна, а також. Іншими словами, ми будемо вважати, що\(x \in B\) або\(x \in C\) і показати, що\(x \in D\) або\(x \in E\). 1
Припустимо, що\(x \in B\) або\(x \in C\). Ми повинні показати, що\(x \in D\) або\(x \in E\). Розрізняємо випадки.
Випадок 1:\(x \in B\). За (с),\(x \in D\). Таким чином,\(x \in D\) або\(x \in E\). (Тут ми зробили висновок, обговорюваний у попередньому підрозділі!)
Випадок 2:\(x \in C\). За (г),\(x \in E\). Таким чином,\(x \in D\) або\(x \in E\). ◻
Доведення претензії про існування
Коли його просять довести існування претензії, питання, як правило, буде форми «довести, що є\(x\) таке, що\(\dots x \dots\)», тобто, що якийсь об'єкт, який має властивість, описану «\(\dots x \dots\)». У цьому випадку вам доведеться визначити відповідний об'єкт, показати, що він має необхідну властивість. Це звучить просто, але доказ такого роду може бути складним. Як правило, це передбачає побудову або визначення об'єкта та доведення того, що об'єкт, визначеного таким чином, має необхідну властивість. Знайти потрібний об'єкт може бути важко, довести, що він має необхідну властивість може бути важко, а іноді навіть складно показати, що вам вдалося визначити об'єкт взагалі!
Як правило, ви б виписати це, вказавши об'єкт, наприклад, «нехай\(x\) бути...» (де... вказує, який об'єкт ви маєте на увазі), можливо, доводячи, що\(\dots\) насправді описує об'єкт, який існує, а потім продовжуйте показувати, що\(x\) має властивість \(Q\). Ось простий приклад.
Пропозиція\(\PageIndex{3}\)
Припустимо, що\(x \in B\). Тоді є\(A\) таке, що\(A \subseteq B\) і\(A \neq \emptyset\).
Доказ. Припустимо\(x \in B\). Нехай\(A = \{x\}\).
Тут ми визначили набір\(A\), перерахувавши його елементи. Оскільки ми припускаємо, що\(x\) це об'єкт, і ми завжди можемо сформувати набір, перераховуючи його елементи, ми не повинні показати, що нам вдалося визначити набір\(A\) тут. Однак ми все ще повинні показати, що\(A\) має властивості, необхідні пропозицією. Доказ не є повним без цього!
З тих пір\(x \in A\),\(A \neq \emptyset\).
Це спирається на визначення\(A\) як\(\{x\}\) і очевидні факти, які\(x \in \{x\}\) і\(x \notin \emptyset\).
Оскільки\(x\) є єдиним елементом\(\{x\}\)\(x \in B\), і, кожен елемент також\(A\) є елементом\(B\). За визначенням\(\subseteq\),\(A \subseteq B\). ◻
Використання претензій про існування
Припустимо, ви знаєте, що якесь твердження про існування є істинним (ви це довели, або це гіпотеза, яку ви можете використовувати), скажімо\(x\), «для деяких\(x \in A\)» або «є»\(x \in A\). Якщо ви хочете використовувати його у своєму доказі, ви можете просто зробити вигляд, що у вас є ім'я для однієї з речей, які, за словами вашої гіпотези, існують. Оскільки\(A\) містить принаймні одну річ, є речі, до яких це ім'я може посилатися. Ви, звичайно, не зможете вибрати один з них або описати його далі (крім того, що це є\(\in A\)). Але з метою доказу ви можете зробити вигляд, що ви його вибрали, і дати йому ім'я. Важливо вибрати ім'я, яке ви ще не використовували (або яке відображається у ваших гіпотезах), інакше все може піти не так. У своєму доказі ви вказуєте це\(x\), перейшовши від «для деяких\(x \in A\)» до «Нехай»\(a \in A\). Тепер ви можете міркувати про\(a\), використовувати деякі інші гіпотези і т.д., поки не прийдете до висновку,\(p\). Якщо більше\(p\) не\(p\) згадує\(a\), не залежить від припущення, що\(a \in A\), і ви показали, що це випливає лише з припущення «для деяких\(x\)»\(x \in A\).
Пропозиція\(\PageIndex{4}\)
Якщо\(A \neq \emptyset\), то\(A \cup B \neq \emptyset\).
Доказ. Припустимо\(A \neq \emptyset\). Так для деяких\(x\),\(x \in A\).
Тут ми спочатку щойно переосмислювали гіпотезу цієї пропозиції. Ця гіпотеза, т. Е.\(A \neq \emptyset\), приховує екзистенціальне твердження, до якого ви отримаєте лише розпакувавши кілька визначень. Визначення\(=\) говорить нам, що\(A = \emptyset\) якщо кожен\(x \in A\) є також\(\in \emptyset\) і кожен також\(x \in \emptyset\) є\(\in A\). Заперечуючи обидві сторони, отримуємо:\(A \neq \emptyset\) якщо або деякі\(x \in A\) є,\(\notin \emptyset\) або деякі\(x \in \emptyset\) є\(\notin A\). Оскільки нічого немає\(\in \emptyset\), другий диз'юнкт ніколи не може бути правдою, а «\(x \in A\)і\(x \notin \emptyset\)» зводиться до справедливого\(x \in A\). Так що\(x \neq \emptyset\), якщо для деяких\(x\),\(x \in A\). Це претензія на існування. Тепер ми використовуємо цю претензію існування, вводячи ім'я для одного з елементів\(A\):
Нехай\(a \in A\).
Тепер ми ввели назву для однієї з речей\(\in A\). Ми будемо продовжувати сперечатися\(a\), але будемо обережні, щоб тільки припустити, що\(a \in A\) і нічого іншого:
Так як\(a \in A\)\(a \in A \cup B\), за визначенням\(\cup\). Так для деяких\(x\)\(x \in A \cup B\), тобто,\(A \cup B \neq \emptyset\).
На цьому останньому кроці ми перейшли від «\(a \in A \cup B\)» до «для деяких\(x\)»\(x \in A \cup B\). Це\(a\) більше не згадує, тому ми знаємо\(x\), що «для деяких\(x \in A \cup B\)» випливає з «для деяких\(x\),\(x \in A\) поодинці». Але це означає, що\(A \cup B \neq \emptyset\).
◻
Це, можливо, хороша практика, щоб тримати пов'язані змінні, як «\(x\)» окремо від гіпотетичних імен\(a\), як, як ми зробили. На практиці, однак, ми часто не використовуємо і просто використовуємо\(x\), як так:
Припустимо\(A \neq \emptyset\), тобто існує\(x \in A\). За визначенням\(\cup\),\(x \in A \cup B\). Отже\(A \cup B \neq \emptyset\).
Однак, коли ви робите це, ви повинні бути дуже обережними, що ви використовуєте різні\(x\) і\(y\) для різних екзистенціальних претензій. Наприклад, наступне не є правильним доказом «Якщо\(A \neq \emptyset\) і\(B \neq \emptyset\) тоді\(A \cap B \neq \emptyset\)» (що не відповідає дійсності).
Припустимо\(A \neq \emptyset\), і\(B \neq \emptyset\). Так для деяких\(x\),\(x \in A\) а також для деяких\(x\),\(x \in B\). Так як\(x \in A\) і\(x \in B\)\(x \in A \cap B\), за визначенням\(\cap\). Отже\(A \cap B \neq \emptyset\).
Чи можете ви помітити, де відбувається неправильний крок і пояснити, чому результат не тримається?
-
Цей абзац просто пояснює, що ми робимо - це не частина доказу, і вам не доведеться вдаватися до всіх цих деталей, коли ви записуєте власні докази. ↩ ︎