Глухов М. М. Алгебра том 1, страница 5

Символически это утверждение можно записать так: Чх, у Е Й: Их ф 0) Й (у ф 0) =Ф (ху ф 0)). Для его доказательства нужно показать, что предикат (х ф ОЙ у ф 0) =~ =~ (ху ф 0) принимает истинное значение при любых значениях х, у из й. Допустим, что это не так, то есть при некоторых а ложна импликация: (а ф 0) Й (6 ф О) =~ (а6 ф 0).

Это означает, что ее посылка "(а ф 0) й (6 ф 0)" = А истинна, а заключение "(а6 ф 0)" = В ложно, т. е. а6 = О. Умножив обе части последнего равенства на число а 1, обратное к а (которое существует в силу условия а ф 0), и воспользовавшись известными свойствами умножения, получим равенство 6 = О, которое свидетельствует об истинности утверждения А.

Таким образом, наше допущение о том, что утверждение теоремы неверно, привело нас к противоречию с условием А. Значит такое допущение неверно, и тем самым наше утверждение доказано. 3. Метод полной математической индукции Этот метод применяют для доказательства таких утверждений, в формулировке которых участвует числовой параметр $, принимающий все значения из множества Я натуральных чисел. По существу, такое утверждение А(1) является предикатом от переменного ~ на множестве Я, а доказать требуется истинность формулы ИА($).

Сам процесс доказательства методом полной математической индукции состоит из двух этапов. 1. Доказывают, что утверждение А(~) истинно при 1 = 1 (это чаще всего удается сделать непосредственной проверкой). 2. Исходя из допущения, что утверждение А(1) верно для произвольного фиксированного значения $ = п доказывают его истинность при Ф = и+1. После выполнения обоих этапов доказательства делается вывод об истинности утверждения А(1) для всех значений ~ из множества Я. 23 Первый этап доказательства обычно называют началом индукции, второй — индуктивным шагом, или переходом от п к п+ 1. С содержательной точки зрения метод полной математической индукции обычно не вызывает возражений.

Интуитивно всем кажется ясным, что указанные два этапа метода вполне законно заменяют перебор бесконечного ряда значений параметра 1 = 1,2,3,.... Теоретической основой метода является одна из аксиом натурального ряда чисел, называемая аксиомой полной математической индукции. Аксиоматическое построение арифметики натуральных чисел независимо было осуществлено в 1888 г.

немецким математиком Р. Дедекиндом (1831 — 1916) и в 1889 г. итальянским математиком Д. Пеано (1858 — 1932). Натуральный ряд чисел Пеано определил как произвольное множество Я с заданным на нем отношением "следовать за", удовлетворяющим аксиомам: 1. Существует элемент множества Я, не следующий ни за каким элементом из )Ч (любой из них назовем единицей и обозначим символом 1); 2. Для каждого элемента п б Я существует единственный элемент, следующий, за п (обозначим его через и'); 3. Для каждого элемента п б 1Ч существует не более одного элемента, за которым следует и; 4.

(Аксиома полной математической индукции.) Пусть М подмножество множества Я, удовлетворяющее условиям: а) 11=М; б) Мп Е Я: (и Е М =~ п' б М). Тогда М = 1Ч. В приведенном определении множества Я ничего не говорится о природе его элементов. Она может быть какой угодно, лишь бы их совокупность удовлетворяла аксиомам 1 — 4. Выбирая в качестве 1Ч некоторое конкретное множество с определенным отношением "следовать за", удовлетворяющем аксиомам 1 — 4, мы получим интерпретацию, или модель множества натуральных чисел.

В качестве стандартной модели обычно берут выработанный в процессе исторического развития человечества ряд символов 1, 2, 3, 4,... Используя аксиомы 1 — 4, можно определить операции сложения и умножения натуральных чисел, отношения "меньше", "больше" и др. на множестве натуральных чисел и доказать известные факты арифметики. Мы не будем здесь этим заниматься. Сделаем лишь отдельные замечания. 1. Операции сложения и умножения в )Ч однозначно определяются равенствами (Ча,б б Я): а+1=а', а 1=а, а + Ь' = (а + 6)', а Ь' = а6+ а.

2. Неравенства (, > для чисел а, Ь б Я определяются с использованием операции сложения: а с6~6>а~ЗЙЕЯ: (Ь=а+й). Подчеркнем, что, наряду с другими известными свойствами неравенств, из аксиом 1 — 4 следует свойство, называемое аксиомой Архимеда 1: Ча, 6 1= И, Зд 1= Я: (а ( Ьц). 3. Для обоснования изложенного выше метода доказательства утверждения ИА(1) достаточно взять в качестве фигурирующего в аксиоме 4 множества М множество тех значений параметра $, при которых утверждение А(~) истинно, и заметить, что и' = п+ 1. 4.

С помощью аксиом 1 — 4 можно обосновать и несколько более общий метод доказательства утверждений вида Ч$А($) с параметром 1, принимающим все целые значения, начиная с некоторого целого числа по. А именно, можно доказать следующую теорему. Если утверждение А(~) истинно при некотором 1 = по б Ж и для любого фиксированного целого числа п > по из истинности А(1) при всех значениях 1 б по,п следует истинность А(1) при 1 = п + 1, то утверждение А(~) истинно при всех целых ~ > по. Особо подчеркнем тот факт, что здесь допускать истинность доказываемого утверждения А(~) можно не только для ~ = п, но и для всех 1, удовлетворяющих неравенствам по ( 1 ( п. 5.

Используя аксиомы 1 — 4, можно доказать, что в любом не пустом подмножестве М множества целых неотрицательных чисел Яо существует наименьшее число. Это утверждение в арифметике называют иринцииом наименыиего числа. Заметим, что, используя указанные выше аксиомы 1 — 3 и принцип наименьшего числа, можно доказать аксиому полной математической индукции. В этом смысле говорят, что 1 Архимед — древнегреческий математик (287-212 до н.

э.). 24 25 АП(АОВ) = А0(АПВ) = А, Ал (В и С) = (Ап В) и (А и С), Ао(ВПС) = (АиВ) п(АиС). )А и В~ = ~А~+ ~В~ — ~А и В~. а = р1... р~, Ь = о1 ое, ~(ДА1)) = А1,Щ '(В1)) = В1. и + 1 = р1... р~ц1... р. О ЛУ1 = ЛУг =~ У1 = Уг, ЛУ1 =,1гУ1--"' Ь = Уг. Задачи 11. Доказать утверждения: и а) ~> гг а=1 и б) ~> гз 6 > 4 26 27 принцип наименьшего числа эквивалентен принципу полной математической индукции. В заключение данного параграфа приведем одну известную из средней школы теорему, доказываемую методом полной математической индукции.

Любое натуральное число, большее единицы, либо является простым, либо разлагается в произведение иростых чисел. (Напомним, что натуральное число р > 1 называется простым, если оно делится лишь на 1 и на себя. В противном случае, оно называется составным. Единица не относится ни к простым, ни к составным числам.) О Докажем теорему методом полной математической индукции. При этом в качестве ~ выберем то самое число, которое фигурирует в формулировке данной теоремы. По условию оно может быть любым натуральным числом, начиная с числа 2. Так как 2 — простое число, то для 1 = 2 утверждение теоремы верно.

Допустим, что оно верно для всех $ Е 2,и при любом фиксированном натуральном и > 2, и докажем его истинность для 1 = и + 1. Если число и+ 1 простое, то для него утверждение теоремы верно. Пусть и+ 1 — составное. Тогда оно делится на некоторое число а, такое, что 1 ( а ( и+ 1. Следовательно, и+1 = а 6, где 1 ( 6 ( и+1. По предположению индукции каждое из чисел а, Ь или простое, или разлагается в произведение простых чисел, то есть имеем: где р1...рь ц1... ое — простые числа, Й,К б Я. Отсюда и из равенства и + 1 = а6 получаем разложение числа и+ 1 в произведение простых чисел: 1.

Выразить операцию объединения (пересечения) множеств через операции пересечения (объединения) и вычитания множеств. 2. Выразить операцию объединения (пересечения) подмножеств фиксированного множества А через операции пересечения (объединения) и дополнения. 3. Доказать равенства (для любых множеств А, В, С): 4. Показать, что из любого семейства и множеств с помощью операции пересечения и объединения можно построить лишь конечное число различных множеств.

5. Доказать, что для любых двух конечных множеств А, В справедливо равенство 6. Найти мощность декартова произведения конечных множеств А1,...,А„. 7. Сколько существует различных отображений ~: А ~ В, если А,  — конечные множества и ~А~ = т, ~В~ = и? 8. Пусть ~: М ~ №, А1,Аг С М,В1,Вг С № Выяснить, какие из следующих равенств справедливы в любых случаях, а какие — не всегда: ДА1*Аг) = ДА1) *ДАг), Г'(В, * В,) = ~-'(В,) * У-'(Вг), (* ~ (и, и, ~)). 9. В обозначениях задачи 8 выяснить условия, при которых справедливы равенства: 10. Пусть ~1, ~г. А ~ В и ~р1, уг. 'В ~ С.

Выяснить, при каких условиях справедливы импликации методом полной математической индукции следующие Ом' 1<11 <1р <е и частичного порядка 29 в) если М1,..., М„конечные множества, то и = ~')м,1 — ~' 1м;, пм,,~+ + ~' ~м,,пм,,пм,,~ —...+(-1)"-'1м,пм,п...лм„~. 1 <11 <1~ <1з <и Это равенство называется формулой включения-исключения. 12. Пользуясь аксиомами натурального ряда, доказать свойства ассоциативности и коммутативности операций сложения и умножения натуральных чисел. Глава П ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Комбинаторика, или комбинаторный анализ, является большим самостоятельным разделом современной математики, играющим важную роль во всех других областях математики и ее приложениях. В комбинаторике изучаются методы построения и перечисления различных комбинаций объектов, удовлетворяющих тем или иным условиям.