4.4: Правила введення та усунення для кількісних показників
- Page ID
- 65361
Як відомо, існує два квантора (\(\exists\)і\(\forall\)). Кожен з них має правило введення та правило усунення, тому є\(4\) правила, які слід представити в цьому розділі. Докази в можуть використовувати обидва ці правила, плюс всі правила (такі як правила заперечення і основні теореми, включаючи правила введення і усунення), а також будь-які інші теореми, які були раніше доведені.
4.4А. \(\exists\)-введення
Потрібно визначитися з тим, як довести висновок бланка\(\exists x \in X, \dots\). Наприклад, у таємниці вбивства, можливо, інспектор Thinkright збирає підозрюваних в кімнаті і каже їм: «Хтось у цій кімнаті руде волосся». Тобто\(\exists\) -заяву. (З відповідним ключем символізації, в якому\(P\) знаходиться безліч всіх людей в кімнаті, і\(R(x)\) є присудок «\(x\)має руде волосся», це твердження\(\exists p \in P, R(p)\).) Як би інспектор переконав скептика в тому, що претензія вірна? Найпростішим способом буде виставити явний приклад людини в кімнаті, у якого руде волосся. Наприклад, якщо Джим знаходиться в кімнаті, і у нього руде волосся, інспектор може сказати:
«Подивіться, Джим сидить прямо там біля дверей, і тепер, коли я знімаю перуку, ви самі можете переконатися, що у нього руде волосся. Тож я маю рацію, що хтось у цій кімнаті має руде волосся».
Загалом, найпростіший спосіб довести, що\(\exists p \in P, R(p)\) це правда, - знайти конкретний приклад\(p\), який робить\(R(p)\) правдою. У цьому і полягає суть правила\(\exists\) -intro.
Ось принцип, про який слід пам'ятати:
Доказ твердження, яке починається
«існує\(x \in X\), таке, що.»
зазвичай базуватимуться на заяві. «Нехай»\(x = \square\),
де поле заповнюється відповідним елементом\(X\).
Більшість математиків не знайомі з термінологією правил введення і правил ліквідації. Замість того, щоб сказати, що це правило\(\exists\) -введення, вони назвали б це «доказом шляхом побудови прикладу», або «даючи явний приклад», або іншими словами з тим самим ефектом.
Ось кілька доказів, які використовують\(\exists\) -intrection, але ми не можемо зробити дуже багато з одним правилом квантора - приклади будуть цікавішими, коли у нас є більше правил для роботи.
Доведіть, що є натуральне число\(n\), таке, що\(n^2 = 64\).
Рішення
Доказ.
Нехай\(n = 8 \in \natural\). Потім\(n^2 = 8^2 = 64\).
Доведіть, що є дійсне число\(c\), таке, що\(5c^2 - 5c + 1 < 0\).
Рішення
Доказ.
Нехай\(c = 1/2 \in \mathbb{R}\). Тоді\[\begin{aligned} 5c^2 - 5c + 1 = 5 \left(\frac{1}{2}\right)^2 - 5 \left(\frac{1}{2}\right) + 1 = \frac{5}{4} - \frac{5}{2} + 1 = -\frac{1}{4} < 0 . & \end{aligned}\]
Нехай\(N = \{1,3,5,7\}\). Доведіть, що існує\(n \in N\), такий, що\(n^3-11n^2+31n \neq 21\).
Рішення
Доказ.
Нехай\(n = 5 \in N\). Тоді\[\begin{aligned} n^3-11n^2+31n = 5^3-11(5^2)+31(5) = 125 - 11(25) + 155 = 125 - 275 + 155 = 5 \neq 21 . \end{aligned}\]
- Доведіть, що є дійсне число\(r\), таке, що\(2r^2 + 9r + 4 = 0\).
- Нехай\(B = \{1,3,5,7\}\). Доведіть, що існує\(b \in B\), такий, що\(3b + 1 = (b-1)^2\).
- Доведіть, що існують натуральні числа\(m\) і\(n\), такі, що\(m^2 = n^3 + 1 > 1\).
- Показати є ціле число\(n\), таке, що\(3n^2 = 5n + 2\).
- Припустимо,\(a\) це дійсне число. Показати є дійсне число\(x\), таке, що\(7x - 5 = a\).
\(\exists\)-ліквідація
Можливо, інспектор Thinkright знає, що один з чоловіків запалив сірник опівночі, але не знає, хто це був. Інспектор може сказати:
«Ми знаємо, що один з чоловіків запалив сірник опівночі. Давайте назвемо цього таємничого джентльмена «містер Х». Оскільки правші матчі заборонені на острові, ми знаємо, що містер Х ліворукий. Отже, містер Ікс не дворецький, тому що всі дворечі в цьому місті правші.
і так далі, і так далі, розповідаючи нам все більше і більше про містера Ікс, грунтуючись тільки на припущенні, що він запалив сірник опівночі.
Аналогічна ситуація в математичних доказах. Припустимо, ми знаємо, що існує елемент множини\(A\). Тоді було б корисно мати назву для цього таємничого елемента, щоб ми могли говорити про нього. Але математик не назвав би елемент «Містер Х»: якщо це елемент множини\(A\), то він чи вона, ймовірно, назвав би його\(a\) (або\(a_1\) якщо будуть інші елементи, про які можна\(A\) говорити). Загалом, ідея правила\(\exists\) -елімінації така:
Якщо\(\exists x \in X\), як\(P(x)\) відомо, правда, то ми можемо
дозволити\(x\) бути елементом\(X\), такий,\(P(x)\) що вірно.
В решті доказів ми можемо припустити лише дві речі\(x\): це\(x \in X\), і\(P(x)\) це правда.
Покажіть, що якщо існує\(a \in \mathbb{R}\), таке що\(a^3 + a + 1 = 0\), то існує\(b \in \mathbb{R}\), таке що\(b^3 + b - 1 = 0\).
Рішення
Доказ.
Припустимо\(a \in \mathbb{R}\), існує, таке, що\(a^3 + a + 1 = 0\). Нехай\(b = -a\). Потім\(b \in \mathbb{R}\), і\ [\ почати {вирівняний}
b^ {3} +b-1 & =( -a) ^ {3} + (-a) -1\\
&=-a^ {3} -а-1\
&=-\ ліворуч (a^ {3} +a+1\ праворуч)\\
&=0\\
&= 0
\ кінець {вирівняний}\]
(Четвертий рядок: по визначення\(a\)) за
бажанням.
Припустимо\(A\) і\(B\) є множинами дійсних чисел.
- Покажіть, що якщо існує\(a \in A\), таке що\(2a > 5\), то існує\(b \in A\), таке що\(b > 0\).
- Покажіть, що якщо існує\(x \in \mathbb{R}\), таке що\(x - 2 \in A\), то існує\(y \in \mathbb{R}\), таке що\(3y \in A\).
- Покажіть, що якщо\(A \cap B \neq \emptyset\), то\(A \neq \emptyset\).
\(\forall\)-ліквідація
Можливо, інспектор Thinkright знає, що Дживз є дворецьким у місті, і що всі дворечі в місті правші. Ну, тоді інспектору очевидно, що Дживз правша. Це приклад\(\forall\) -elimination: якщо ви знаєте, що щось вірно щодо кожного елемента множини, то це вірно щодо будь-якого конкретного елемента множини. \[\text { If } \forall x \in X, P(x) \text { is true, and } a \in X \text {, then } P(a) \text { is true. }\]
Припустимо
- \(C \subset \mathbb{R}\), і
- \(\forall x \in \mathbb{R}, \bigl( (x^2 = 9) \Rightarrow (x \in C) \bigr)\).
Показати\(\exists c \in \mathbb{R}, c \in C\).
Рішення
Доказ.
Нехай\(c = 3 \in \mathbb{R}\). Тоді\(c^2 = 3^2 = 9\), і впускаючи\(x = c\) гіпотезу (2) говорить нам, що\[( c^2 = 9) \Rightarrow ( c \in C) .\] Тому\(c \in C\).
Припустимо\(A \neq \emptyset\) і\(A \subset B\). Доведіть\(\exists b, (b \in B)\).
Рішення
Доказ.
Тому що\(A\) це не порожній набір, ми знаємо, що він має принаймні один елемент; тобто ми маємо\(\exists x, (x \in A)\). Отже, ми можемо дозволити\(a\) бути деяким елементом\(A\). Тепер давайте\(b = a\). Тому що\(A \subset B\), ми знаємо, що кожен елемент\(A\) є елементом\(B\). Зокрема, оскільки\(b = a \in A\), це означає, що\(b \in B\).
При застосуванні\(\forall\) -elimination змінну не потрібно називати «\(x\),» (це може бути\(y\)\(z\) або будь-яка інша змінна), а константу не потрібно називати «\(a\)» (це може бути будь-який елемент \(X\)). Однак якщо змінна зустрічається більше одного разу у формулі, важливо замінити всі її входження на\(a\). Наприклад, якщо\(a \in X\), то, з\(\forall x \in X, \bigl( A(x) \Rightarrow B(x) \bigr)\), можна зробити висновок\(A(a) \Rightarrow B(a)\), але ні\(A(a) \Rightarrow B(x)\) або\(A(x) \Rightarrow B(a)\).
- Припустимо\(\forall x \in \mathbb{R}, (x^2 \in Z)\). Показати\(16 \in Z\).
- Припустимо\(A \subset B\) і\(A \neq \emptyset\). Показати\(B \neq \emptyset\).
- Припустимо
- для кожного\(x \in A\), або\(x \in B\), або\(x < 0\), і
- існує\(a \in A\), таке, що\(a > 0\).
Показати\(B \neq \emptyset\).
\(\forall\)-введення
Якщо інспектору Thinkright потрібно перевірити, що всі дворецьких у місті бачили полярне сяйво, він, ймовірно, отримає список усіх дворецьких і перевіряє їх один за одним. Це дійсний підхід, але це може зайняти багато часу, якщо список буде дуже довгим. У математиці така одноосібна перевірка часто не просто трудомістка, а неможлива. Наприклад, набір\(\natural\) нескінченний, так що, якщо ми хочемо показати\(\forall n \in \natural, (\text{$2n$ is even})\), то ми ніколи б не закінчити, якщо ми спробуємо пройти через всі натуральні числа один за одним. Таким чином, нам потрібно мати справу з багатьма числами відразу.
Розглянемо наступні прості відрахування:
Гіпотеза:
Кожен дворецький у місті встав до 6 ранку сьогодні.
Всі, хто встав сьогодні до 6 ранку, бачили полярне сяйво.
Висновок:
Кожен дворецький в місті бачив сяйво.
Це явно дійсний відрахування англійською мовою. Давайте переведемо його в аналіз того, як нам вдалося дійти висновку про всіх дворецьких, не перевіряючи кожного з них окремо. Ось ключ символізації:
\(B\): Набір всіх дворецьких в місті.
\(P\): Безліч всіх людей.
\(U(x)\):встав сьогодні до 6 ранку.
\(S(x)\):побачив полярне сяйво.
Тепер ми можемо перевести наш англійський відрахування наступним чином:
Гіпотеза:
\(\forall b \in B, U(b)\).
\(\forall p \in P, \bigl( U(p) \Rightarrow S(p) \bigr)\).
Висновок:\(\forall b \in B, S(b)\).
Як ми обгрунтуємо висновок? Ну, припустимо на мить, що ми починаємо перевіряти кожного дворецького в місті, і це\(j\) представляє Джиммі, який є одним з дворецьких у місті. Тоді наша перша гіпотеза дозволяє зробити висновок\(U(j)\). Оскільки Джиммі - особистість, наша друга гіпотеза дозволяє зробити висновок про це\(U(j) \Rightarrow S(j)\). Потім, використовуючи\(\Rightarrow\) -elimation, робимо висновок\(S(j)\). Але нічого особливого в нашому виборі Джиммі не було. Все, що ми знаємо про нього, це те, що він дворецький у місті. Таким чином, ми могли б використовувати точно такий же аргумент, щоб вивести\(S(b)\) для будь-якого дворецького\(b\) в місті.
Ось як ми виправдовуємо\(\forall\) -вступ. Якщо ми можемо довести, що бажаний висновок вірний для довільного елемента множини, коли ми не припускаємо нічого про елемент, крім того, що він належить множині, то висновок повинен бути істинним для кожного елемента множини.
Вищевказане відрахування пишемо наступним чином:
Припустимо, що кожен дворецький у місті встав до 6 ранку сьогодні. Також припустимо, що всі, хто встав до 6 ранку сьогодні, бачили полярне сяйво. Тоді кожен дворецький в місті побачив сяйво.
- Доказ
-
Нехай\(b\) представляють довільного дворецького в місті. Потім, так як всі дворецьких встали до 6 ранку, ми знаємо, що\(b\) встали до 6 ранку. За гіпотезою це має на увазі, що\(b\) побачили сяйво. Оскільки\(b\) це довільний дворецький у місті, ми робимо висновок, що кожен дворецький у місті бачив полярне сяйво.
Це міркування призводить до правила\(\forall\) -введення: щоб довести, що кожен елемент множини\(X\) має певну властивість, досить показати, що довільний елемент\(X\) має шукане властивість. Наприклад, якщо ми хочемо довести\(\forall b \in B, P(b)\), то наше доказ має починатися з речення «\(b\)Дозволяти бути довільним елементом»\(B\). (Однак це може бути скорочено до: «Given\(b \in B\),...») Після цього нашим завданням буде довести, що\(P(b)\) це правда, не припускаючи нічого\(b\) іншого, ніж це елемент\(B\).
Доказ твердження, яке починається «для всіх»\(x \in X\)
, зазвичай починається з «Дозволяти\(x\) бути довільним елементом\(X\)"
(або, коротше кажучи, «Given\(x \in X\),»).
Важливо не припускати нічого\(x\) іншого, крім того, що це елемент\(X\). Якщо ви\(x\) вирішите бути певним елементом,\(X\) який має якесь особливе властивість, то ваш відрахування буде дійсним не для всіх елементів набору.
Припустимо, ми хотіли б обґрунтувати наступне відрахування:
Всі дворечі в місті не люблять Джиммі, а Джиммі - дворецький у місті.
Тому всі дворечі в місті не люблять себе.
Тоді досить показати, для довільного дворецького\(b\), що\(b\) не любить\(b\). Ми можемо спробувати наступний доказ:
Рішення
Доказ спроби.
Нехай\(b\) буде Джиммі, який є дворецьким у місті. Потім, оскільки всі дворечі в місті не люблять Джиммі, ми знаємо, що\(b\) не любить Джиммі. Так як\(\text{Jimmy} = b\), це означає\(b\) не любить\(b\), за бажанням. Так що кожен дворецький в місті не любить себе.
Однак цей доказ, безумовно, не є дійсним. Дозволяючи\(b = \text{Jimmy}\) не робити\(b\) довільного дворецького; скоріше,\(b\) це робить дуже особливого дворецького - того, який не подобається всім. У цьому випадку висновки, які відповідають дійсності\(b\), не обов'язково вірні щодо інших дворецьких.
Ще один момент, який слід підкреслити, полягає в тому, що довільний член множини - це не те саме, що випадковий член множини. Якщо ми хочемо довести, що всі дворецьких бачили полярне сяйво, недостатньо вибрати дворецького навмання, запитати, чи бачив він полярне сяйво, і зробити висновок про всіх дворецьких на основі цієї єдиної відповіді. Тільки якщо ми зможемо визначити за допомогою логічного вирахування, що незалежно від того, якого дворецького ми вибрали, ця людина побачила сяйво, ми можемо зробити висновок, що всі дворецьких бачили полярне сяйво.
Яке з правил\(4\) кількісного визначення ілюструє кожне вирахування?
- Всі, хто вчора їли в кафетерії, сьогодні хворіють. О, ні! Сьюзі їла в кафетерії — вона, мабуть, хворіє!
- Сьюзі вчора їла в кафетерії, тож я впевнена, що хтось вчора їв у кафетерії.
- Не знаючи, хто з спортсменів це був, я зрозумів, що він або вона, мабуть, вчора їли в кафетерії. Єдиний спосіб, який може бути правдою, - якщо кожен спортсмен вчора їв у кафетерії.
- Наш продовольчий репортер каже, що якась жінка перекинула велику коробку з квасолею ліми, поки вона вчора їла в кафетерії. Хто б вона не була, назвемо її «Міс Незграбна». Так що сьогодні вранці заголовок може бути «Міс незграбна пролила боби!»