A.4: Шаблони висновків
Докази складаються з індивідуальних висновків. Коли ми робимо висновок, ми зазвичай вказуємо, що, використовуючи таке слово, як «так», «таким чином» або «отже». Висновок часто спирається на один або два факти, які ми вже маємо в нашому доказі - це може бути те, що ми припустили, або те, що ми вже зробили висновок. Щоб бути зрозумілим, ми можемо позначити ці речі, і у висновку ми вказуємо, які інші твердження ми використовуємо у висновку. Висновок часто також містить пояснення того, чому наш новий висновок випливає з речей, які приходять до нього. Є деякі загальні шаблони висновку, які дуже часто використовуються в доказах; ми розглянемо деякі нижче. Деякі закономірності висновку, такі як докази шляхом індукції, більш залучені (і будуть розглянуті пізніше).
Ми вже обговорювали одну модель висновку: розпакування або застосування визначення. Коли ми розпаковуємо визначення, ми просто повторюємо щось, що включає 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 hasP, то воно hasQ» або «ВсеP s єQ s». Звичайно, це може не відповідати цій формі ідеально, і потрібно трохи практики, щоб з'ясувати, що ви просять довести точно. Але: нам часто доводиться доводити, що всі об'єкти з якоюсь властивістю мають певну іншу властивість.
Спосіб довести універсальну претензію полягає у введенні імен або змінних для речей, які мають одну властивість, а потім показати, що вони також мають іншу властивість. Ми могли б поставити це, сказавши, що довести щось для всіхP s ви повинні довести це для довільногоP. І введене ім'я - це ім'я для довільногоP. Зазвичай ми використовуємо окремі літери як ці назви для довільних речей, а літери зазвичай відповідають умовам: наприклад, ми використовуємоn для натуральних чисел,A для формул,Af для множин, функцій тощо.
Хитрість полягає в тому, щоб підтримувати загальність протягом усього доказу. Ви починаєте з припущення, що довільний об'єкт («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) і anyx \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 Ciffx \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 Aa \in A \cup B, за визначенням\cup. Так для деякихxx \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 Bx \in A \cap B, за визначенням\cap. ОтжеA \cap B \neq \emptyset.
Чи можете ви помітити, де відбувається неправильний крок і пояснити, чому результат не тримається?
-
Цей абзац просто пояснює, що ми робимо - це не частина доказу, і вам не доведеться вдаватися до всіх цих деталей, коли ви записуєте власні докази. ↩ ︎