Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 20
Текст из файла (страница 20)
Обычно целые числа "упорядочены" следующим образом: ., -4,-3, -2, -1,0,1,2, 3,4,5, где все положительные числа "идут за" нулем, а нуль "идет за" или "больше,чем" любое отрицательное число. Трихотомия позволяет установить, является ли число положительным, поэтому отношение > на множестве Я х Я можно определить так; а > Ь тогда и только тогда, когда а — Ь положительно. В силу трихотомии, а — 6 либо положительно, либо нуль, либо отрицательно. Поэтому можно объединить две из этих возможностей в одну и говорить, что а > Ь тогда и только тогда, когда а > Ь или а = Ь.
Сказанное выше формализуем в виде следующего определения. ОПРЕДЕЛЕНИЕ 3.9. Для целых чисел а и Ь имеем; а > Ь тогда и только тогда, когда а — Ь положительно; а > Ь тогда и только тогда, когда а > 6 или а = 6. Кроме того, Ь < а равносильно а > 6 и Ь < а равносильно а > 6. Очевидно, а > О равносильно утверждению, что а положительное, потому что а > О тогда и только тогда, когда а — О = а положительное. Аналогично, а < О равносильно утверждению, что а отрицательно. Хотя приведенные ниже утверждения хорошо известны и могут рассматриваться как предположения, они приведены для практики доказательства теорем.
ТЕОРЕМА 3.10. Для целых чисел а и Ь: а) (а>Ь)д(6>а) — а=6; б) (а>6)д(Ь>с)- а>с. ДОКАЗАТЕЛЬСТВО. а) Здесь мы используем принцип сведения к абсурду. Если, предположив, что утверждение в части (а) ложно, мы получим противоречие, то 'В отечественной литературе положительные целые числа принято называть числами натуральнымн. — Прим. ред. 128 ГЛДВА 3. Логика, целые числа и доказательства истинность этого утверждения будет доказана. Предположим, что утверждение в части (а) ложно. Тогда, если а > 6, Ь > а и а Ф Ь, то а > Ь и Ь > а.
Но в этом случае а — Ь положительно и 6 — а = — (а — 6) положительно, что противоречит аксиоме трихотомии (чЗ. Так как мы пришли к противоречию, должен иметь место случай а = Ь. б) Если а > Ь и 6 > с, то а — 6 и Ь вЂ” с положительны. Следовательно, согласно Ы2 число (а — Ь) + (Ь вЂ” с) = а — с положительно, и а > с. ТЕОРЕМА 3.11. Пусть а, 6, с и д — целые числа. Тогда а) (а > Ь) д (с > д) — а + с > Ь + д; б) (а>0)Л(с>г()- ас>аа; в) (а>Ь>0)д(с>д>0) — ас>Ы; г) (а > Ь > 0) д (с > д > 0) — ас > Ы.
ДОКАЗАТЕЛЬСТВО. а) Если а > Ь и с > д, то числа а — Ь и с — д положительны. Следовательно, (а — 6)+(с — д) положительно. Но (а — 6)+(с — д) = (а+с) — (Ь+д), и поэтому а+ с > с+ д. б) Если с > д, то разность с — д положительна. Поскольку а положительно, а(с — д) = ас — ад также положительно, и ас > ад. в) Если а > 6 > 0 и с > д > О, то ас > Ьс и Ьс > Ы. Поэтому ас > Ы. г) Доказательство этой части предоставляется читателю. Далее иллюстрируется применение доказательства перебором.
Выбор из трех возможностей обычно имеет вид р р (гх«ганг) г — ««г г — «я г — «д ТЕОРЕМА 3.12. Пусть и — целое число. Тогда из > О. ДОКАЗАТЕЛЬСТВО. Поскольку и — целое число, согласно аксиоме трихотомии оно либо положительно, либо отрицательно, либо равно О. Если и положительно, то и и положительно по аксиоме й)2, и из > О. Если и отрицательно, то и = — т для некоторого положительного целого числа ги.
Поэтому из = ( — ги)( — ги) = тз опять является положительным, и и > О. Если и = О, то ип = О, так что и > О. Следовательно, из > О. ° УПРАЖНЕНИЯ 1. Пусть а, Ь и с — целые числа. Докажите, что а) если Ь+ а = с+ а, то 6 = с; б) а 0 = 0 для любого целого числа а; в) — ( — а) = а для любого целого числа а; г) а. ( — 6) = — (аЬ); д) ( — а) ( — 6)=а Ь; е) — (а + Ь) = ( — а) + ( — 6). РдЗДЕЛ З.З. Математическая индукция 129 2. Докажите, что если а + Ь = а, то Ь = О.
3. Докажите, что если а > Ь > О и с > й > О, то ас > Ы, 4. Докажите, что аз > а для любого целого числа а. 5. Докажите неравенство аз + Ьз > 2аЬ для целых чисел а и Ь. 3.3. МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ Одна из наиболее сложных проблем теории чисел состоит в доказательстве истинности утверждений для всех положительных целых чисел. Если утверждение истинно для первых десяти положительных чисел или даже для первых десяти биллионов положительных чисел, то из этого еще не следует, что утверждение истинно для всех положительных целых чисел. Обычно легко доказать, что утверждение не является истинным для всех положительных целых чисел.
В самом деле, используя тот факт, что отрицание (сх)Р(х) есть (Эх) Р(х), необходимо найти только одно положительное целое число, для которого утверждение Р(а) не является истинным. Эта процедура известна как нахождение комгпрлримера. Инструментом для доказательства истинности утверждений относительно всех положительных чисел является принцип индукции, который будет нашей последней аксиомой для множества положительных чисел Х. Это вовсе не означает, что доказательство любого утверждения относительно положительных чисел требует индукции. Многие теоремы могут быть доказаны на основе других теорем и аксиом.
Тем не менее, в основе доказательств многих рассматриваемых ниже теорем лежит принцип индукции. В дальнейшем принцип индукции будет сформулирован в другой, эквивалентной форме. (й)4) (Принцип математической индукции) Пусть Р(п) есть такое утверждение, что а) Р(1) истинно, и б) для каждого й, если Р(й) истинно, то Р(9+ 1) истинно. Тогда Р(п) истинно для любого целого положительного числа и.
В символической записи принцип математической индукции имеет вид (Р(1) д ((Ж) Р(к) — Р(lс + 1)) — (Уп) Р(п) . Математическую индукцию можно сравнить с бесконечным рядом костяшек домино. Свойство выстроенных в ряд домино состоит в том, что если опрокинуть одну костяшку, падает следующая. Пусть утверждение Р(п) состоит в том, что падает и-я костяшка. Опрокидывание первой костяшки домино обозначим Р(1), т.е. истинность Р(1) состоит в том, что первая костяшка падает.
Поскольку каждая костяшка опрокидывает следующую, то из истинности Р(й) следует истинность Р(й+ 1). Поскольку падают все костяшки, Р(п) истинно для каждого положительного целого числа п. В дальнейшем, проводя доказательство при помощи описанного выше принципа математической индукции, мы будем просто говорить, что доказываем утверждение по индукции. 130 ГЛАВА 3. Логика, целые чосла и оокаэательотеа ПРИМЕР 3.13.
Допустим, необходимо найти формулу для вычисления суммы первых и положительных целых чисел, 1+2+3+ +и. Такая формула была бы полезна, если надо было бы, например, найти сумму первых 100000 положительных целых чисел, не выполняя для этого 99999 операций сложения. Предположим, у нас имеются основания полагать, что сумма первых и положительных чисел равна -"-(-"з'— 'с. Докажем это утверждение по индукции.
Пусть Я„есть утверждение 1+2+3+ +и= п(п+ 1) 2 (1) Сначала покажем, что Яэ истинно. При и = 1 левая часть равенства 1+2+3+ .+и равна 1. Справа получаем п(п+ 1) 1(1+ 1) 2 2 так что Яэ истинно. Затем предполагаем, что для любого положительного числа й Яь истинно, т.е.
равенство (1) истинно для и = к. Это означает, что 1+2+3+ . +/с = к(й + 1) 2 Теперь необходимо доказать, что Яььэ истинно, т.е. равенство Я„истинно для и = й+ 1. Другими словами, требуется доказать, что 1 + 2 + 3 + + й + (/с + 1) = 2 Используя предположение 1+2+3+. +/с= й(й + 1) 2 и сравнивая это равенство с предыдущим, мы замечаем, что, добавив й + 1 к обеим частям последнего равенства, получим левую часть искомого равенства: 1+2+3+ +/с= й(й + 1) 2 1+2+3+- +Й+(/с+1) = +(0+1) = й(й+ 1) 2 й = (/с + 1)(- + 1) = 2 (й + 1)((й + 1) + 1) 2 Итак, доказано равенство 1+2+3+ +й+(9+1) = которое означает, что соотношение (1) справедливо для и = 0+1. Этот результат обеспечивает истинность Як+э.
Следовательно, в силу аксиомы й)4, Я„истинно для любого положительного целого числа п. П РЯЗДЕЛ З.З. Математическая индукция 131 ПРИМЕР 3.14. Требуется доказать, что 1+2+3+ +п п(п + 1)(2п + 1) 6 (2) Ц1+ 1)(2 1+ 1) 6 что дает нам 1 = 1 и обеспечивает истинность утверждения Я„при п = 1. Затем мы предполагаем, что равенство Я„истинно для п = й. То есть, г г й(й+ 1)(2й+ 1) 1г+2г+3г+ . +йг = 6 Теперь требуется доказать, что равенство Я„истинно для п = й+1. Иначе говоря, требуется доказать, что ,г .
г (й + 1)Ий + 1) + 1)(2(й + 1) + 1) (й + 1)(й + 2)(2й + 3) 6 Используя предположение й(й + 1Н2й + 1) 1+2+3+...+йг = замечаем, что, прибавив к обеим частям последнего равенства (й+ 1)г, мы полу- чим левую часть искомого равенства. Таким образом, г й(й+ 1)(2й+ 1), 1+2+3+ . +йг й(й + 1) (2й + 1) 1+2+3+ +й~+(й+1) = ' '' ' +(й+1) 6 й(й+1)(2й+1) 6(й+1)г 6 6 й(й+1)(2й+1) +6(й+1)' 6 (й + 1) [й(2й + 1) + 6(й + 1)] 6 (й+ 1)(2йг + тй+ 6) 6 (й+ 1)(2й+3)(й+2) 6 Пусть Я„обозначает утверждение, что равенство в уравнении (2) выполняется.
Сначала покажем, что утверждение Я„истинно для и = 1. Подставляя 1 в обе части равенства, получаем 132 ~ЛАВА 3. Пегова, целые числа и докаэательсгпва Итак, доказано равенство РАЗДЕЛ З.Э гаагпемагпичеекея индукцон 133 Поскольку в формулировке задачи сирашиваетси о всех возможных случаях оасиоложеиии облассей и лиииЙ, ззо иоивоаис к бескоиечио большому числ1 134 ГЛДИА 3. Логока, цепые виспа о дпказатепьгппаа РАЗДЕЛ 3.3.
Математическая индукцюя 135 цвет был изменен по обе стороны от 1, делая цвета разли ~нв1ми по обе стороны от такой гоанииы. Таким обоазом. зтот чеотеж. выполненный с использованием 136 ГЛК8А 3. Логика, целые числа и доказательства ТЕОРЕМА 3.18. Если множество целых чисел имеет наименьшее целое число, то такое число единственно. ДОКАЗАТЕЛЬСТВО.
Допустим, что числа а и Ь оба являются наименьшими элементами множества А. По определению наименьшего элемента а < Ь и Ь < а. Следовательно, а = Ь. Теперь сформулируем два утверждения, эквивалентные принципу индукции. (Хб) (Принцип полного упорядочения) Каждое непустое множество положительных целых чисел содержит наименьший элемент. (Хб) 1'Второй принцип индукции) Пусть Р(п) — утверждение. Если а) Р(1) истинно, и б) для произвольного к из истинности Р(т) для всех т < 9 следует истинность Р(п), то Р(п) истинно для всех положительных целых чисел и. В символической форме принцип индукции имеет вид (Р(1) д ((Уй)(Ут < й)Р(т)) — Р(9)) — (чп) Р(п) . Пример использования второго принципа индукции Хб будет приведен ниже при доказательстве того, что каждое целое число представляет собой произведение простых чисел.
Следующая теорема — пример утверждения, которое может показаться слишком очевидным для проведения его доказательства, но поскольку рассматриваемая модель целых чисел определена совокупностью правил, для наших "целых чисел" эти утверждения могут не оказаться столь очевидными или даже истинными. Мы можем установить это, доказывая соответствующую теорему с использованием имеющихся правил. Доказательство является хорошим примером использования принципа полного упорядочения Х5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
