Теорема (принцип математической индукции)

Теорема (принцип  математической индукции). Предположим, что для каждого натурального числа ≥ есть утверждение Р(), обладающее двумя свойствами:

1) Р() истинно;

2) для любого натурального k ≥ из справедливости Р(k) вытекает истинность P(k + 1) , т. е. Р(k) => Р(k + 1).

Тогда утверждение Р(n) верно для любого натурального числа n ≥ .

Доказательство. Докажем теорему методом «от противного». Допустим, что условия теоремы выполнены, но утверждение Р(m) ложно для какого-то натурального числа m ≥ .Пусть m₀ — самое маленькое натуральное число среди всех таких. Очевидно, m ≠ , поскольку истинность утверждения Р() известна из условий теоремы. Поэтому m₀ - 1 ≥ и, по выбору m₀, утверждение P(m₀ - 1) — справедливо. Тогда из второго условия теоремы следует, что Р(m₀) тоже верно. Полученное противоречие доказывает теорему.

 

Допустим мы доказываем серию  утверждений Р(n) при ≥ индуктивным методом. Первый шаг, проверка истинности утверждения Р(), называется базой индукции. Допущение о справедливости высказывания Р(k) для произвольного натурального числа k называют предположением индукции или индуктивным предположением. И наконец, индуктивный переход или шаг индукции заключается в доказательстве импликации P(k) => Р(k + 1).

 

Теорема (принцип  строгой математической индукции). Предположим, что для каждого натурального числа ≥ сформулировано утверждение Р(n), обладающее следующими двумя свойствами:

1. Р() истинно;
2. если Р(т) справедливо при n = , + 1 ,...,  к , то утверждение  

Р(k + 1) тоже верно. Тогда для любого натурального ≥ утверждение Р(n) истинно.

Несмотря на громкое название, доказательство этой теоремы практически ничем не отличается от доказательства слабого принципа математической индукции. Поэтому мы оставим его читателю.

 

2.1 ПОНЯТИЕ МНОЖЕСТВА

Под множеством понимается некоторая, вполне определенная совокупность объектов или элементов. Это утверждение не следует рассматривать как строгое определение. Такое “определение” напоминает данное основоположником теории множеств Георгом Кантором определение множества как “объединения в одно целое объектов, хорошо различимых нашей интуицией или мыслью". Расплывчатость, недостаточность этого определения стала понятной, когда в 1879 году итальянский логик Бурали-Форти, а немного позже выдающийся философ и логик Бертран Рассел открыли парадоксы, указывающие на внутреннюю противоречивость канторовой теории множеств. Для устранения таких противоречий и парадоксов для теории множеств были предложены аксиоматические системы. Наиболее известны системы Цермело-Френкеля-фон Неймана. Гильберта-Бернайса- Геделя и Рассела-Уайтхеда. В силу ограниченности объема книги мы не будем изучать эти системы. Поэтому, по сути, мы оставим понятие множества неопределенным и будем считать множество заданным, если его элементы однозначно определены и это не приводит к каким-либо противоречиям.

Конечные множества можно  описывать, перечисляя их элементы. Элементы, принадлежащие конечному множеству, условимся записывать между двумя фигурными скобками и разделять их запятыми. Например, {1,2,3,4} есть множество, содержащее натуральные числа 1, 2, 3 и 4. Множество гласных можно представить как {а, о, у, э, и, ы}. Как правило, для обозначения множеств будем использовать прописные буквы. A = {Боб, Джейн, Нэнси} есть множество, состоящее из Боба, Джейн и Нэнси. Множество первых п положительных целых чисел обозначаем {1,2,3,4,...,n}, где точками показано продолжение перечисления элементов. Это же обозначение можно использовать для некоторых бесконечных множеств. Например, множество положительных целых чисел можно обозначить как {1,2,3,4,...}. Часто при перечислении множества используется описание характеристического свойства элементов этого множества. Например, С = {1,8,27,...,k³,...} описывает множество кубов всех положительных чисел, а S = {1,4,9,... ,n²} описывает множество квадратов всех положительных чисел.

 

В общем случае множество  задается путем указания характеристического  свойства, т.е. свойства, которому удовлетворяют  элементы данного множества, и только они. Для задания обычно используются фигурные скобки, а внутри них приводится характеристическое свойство, описывающее  множество. Таким образом. множество {x : х обладает свойством Р} предполагается содержащим только те объекты, которые имеют свойство Р. Например, {x : x — футболист, играющий за Юго-западный колледж} — множество, состоящее из всех футбольных игроков, выступающих за Юго-западный колледж. Запись {х: х — гражданин Англии} описывает множество всех граждан Англии. Способ задания множества должен быть адекватным, т.е. должен полностью определять множество. Это не представляет труда, если объекты множества перечислены. Рассмотрим, однако, множество А = {х : х — высокий студент данной группы} или В - [х : х — хороший студент данной группы}. Если различным студентам группы предложить определить множества A и B, они могут сделать это неоднозначно, выбирая в качестве элементов как множества А, так и множества В не одних и тех же людей. При рассмотрении множества С = {х : х — привлекательная (или красивая) студентка группы} выбрать элементы множества С не только трудно, но не стоит даже пытаться это сделать. Однако, если множество А = {х : х — студент данной группы, рост которого выше 180см} и В = {х : х — студент данной группы, средний балл которого не ниже 4}, то можно сказать определенно, является ли данный студент элементом А или В, так что А и В действительно есть множества.

Таким образом, мы приходим к  следующему формальному определению.

 

ОПРЕДЕЛЕНИЕ 2.1. Если а есть один из объектов множества А. мы говорим, что а есть элемент А, или а принадлежит А. Принадлежность элемента а множеству А записывается как а А. Если а не является элементом А, это записывается как а А.

 

Например, 3 {1,2,3.4}, но 5 {1,2,3.4}. Если Р есть множество {x : х был президентом Соединенных Штатов}, то Авраам Линкольн Р. а Патрик Гэнри Р.

 

ОПРЕДЕЛЕНИЕ 2.2. Множество А есть подмножество множества В (обозначается А В), если каждый элемент А есть элемент В; т.е. если х А, то x В. В частности, каждое множество есть подмножество самого себя. Если А не является подмножеством В, это записывается как А В. Таким образом, А В. если существует элемент А, не принадлежащий B.

 

Множества равны, если они  содержат одни и те же элементы. Если А есть множество {2,4,6}, а В есть множество {х : х есть четное положительное целое число, которое меньше 7}, тогда А и В — равные множества. Таким образом, мы приходим к следующему определению.

 

ОПРЕДЕЛЕНИЕ 2.3. Пусть А и В — некоторые множества. Говорят, что А равно В. и пишут А = В, если для любого х имеем: х А тогда и только тогда, когда х В. Иначе говоря, А = В тогда и только тогда, когда А В и В А. Если А В и А ≠ В, то это записывают А В и говорят, что А есть собственное подмножество В.

 

Таким образом, доказательство равенства множеств А и В состоит из двух этапов:

 

1. Доказать, что А есть подмножество В.
2. Доказать, что В есть подмножество А.

 

Поскольку множество однозначно определяется только элементами, которые  оно содержит, порядок их перечисления роли не играет. Например, {1,2,4,6} = {2,1,6,4}. Кроме того, любой элемент либо принадлежит данному множеству, либо нет. Каждый элемент может входить  во множество не более одного раза.

 

С этого момента вводится два новых множества: универсальное  множество, или универсум, и пустое множество. В известном смысле они  представляют собой противоположности, поскольку пустое множество не содержит элементов, а универсальное множество содержит “все" элементы.

 

ОПРЕДЕЛЕНИЕ 2.4. Пустое множество, обозначаемое Ø или {}, есть множество, которое не содержит элементов. Универсальное множество U есть множество, обладающее таким свойством, что все рассматриваемые множества являются его подмножествами.

В теории чисел универсальное  множество обычно совпадает со множеством всех целых или натуральных чисел. В математическом анализе универсальное  множество может быть множеством всех действительных чисел или множеством всех точек 71-мерного пространства. Следует отметить, что универсальное  множество U, хотя и названо универсальным, однозначно не определено, если точно не указана область рассмотрения (предметная область). Конечно, любое множество, содержащее U, может быть использовано как универсальное множество.

По определению, каждое множество  есть подмножество универсального множества. Пустое множество есть подмножество любого данного множества А, поскольку каждый элемент пустого множества содержится в А. Можно сказать, что не существует элементов пустого множества, которые не принадлежали бы А.

 

2.2.ОПЕРАЦИИ НАД  МНОЖЕСТВАМИ

 

Рассмотренные ниже операции над множествами позволяют строить  новые множества, используя уже  существующие.

ОПРЕДЕЛЕНИЕ 2.5. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и А, и В. Пересечение множеств A и В обозначается А В. Это определение равносильно следующему: А В = {х : х А и х В].

Например, если А = {1,2,3,4,5} и В = {1,3,5,7,9}, тогда А В = {1,3,5}. Если С = {х : х имеет рост выше 180см} и D - {х : х любит играть в шахматы}, тогда С D = {х : х имеет рост выше 180см и любит играть в шахматы}. Обратите внимание, что в описании пересечения множеств В С использована связка “и”. В дальнейшем мы убедимся, что символы и . введенные в главе 1, связаны между собой и имеют схожие свойства.

Определим пересечение трех и более множеств. Пусть А₁, А₂ и А₃ — множества. Их пересечение можно определить следующим образом:

 

В = A₁

(А₂ A₃).

 

Далее будет показано, что  А₁ (А₂ Аз) = (А₁ A₂) Аз, поэтому можно использовать запись

 

В = А₁

А₂ A₃ .

 

Очевидно, х В тогда и только тогда, когда х   A₁ , х A₂ и x A₃; иными словами, х В тогда и только тогда, когда х принадлежит всем трем множествам А₁, A₂ и Аз. Пусть J = {1,2,3}. В таком случае х В тогда и только тогда, когда х А_j для всех j J. что равносильно записи

 

В = {х : х

A_j для всех j J }.

 

Пересечение множеств в общем  случае определяется следующим образом.

ОПРЕДЕЛЕНИЕ 2.6. Если I = {1,2,3,...,k}, то

 A_j = A₁ А₂ Аз … А_к = {х : х A, для всех i I}.

 

Объединением множеств A и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A или В. Объединение множеств А и В обозначается A U В. Сформулированное выше определение можно записать так: A U B = {х : х A или х В).

 

Объединение множеств в общем  случае определим следующим образом.

 

ОПРЕДЕЛЕНИЕ 2.6. Если I = {1,2,3,...,k}, то

 A_j = A₁ U А₂ U Аз U …U А_к = {х : существует i   I, такое что x A_i}.

ОПРЕДЕЛЕНИЕ 2.9. Пусть А и В множества. Разностью множеств А - В

называется множество  всех тех и только тех элементов  А, которые не содержатся в В. Или, что то же самое, А - В = {х : х А и х В). Симметрическая разность множеств А и В, обозначаемая А В, есть множество (A-B)U(B-A).

 

Например, если А = {1.2,4,6,7}, а В = {2,3.4,5,6}, то А - В = {1,7} , а A B есть множество {1.3,5,7}. Симметричная разность множеств А и В состоит из тех элементов, которые принадлежат в точности одному из двух множеств А или В. Если А = {х : х играет в теннис}, а В = {х : х играет в гольф}, то А — В = {х : х играет в теннис, но не играет в гольф}. Множество А В = {х : х играет только в теннис или играет только в гольф}. Обратите внимание на сходство со связкой "исключающее или” из главы 1.

ОПРЕДЕЛЕНИЕ 2.10. Дополнение множества А, обозначаемое А'. — это множество элементов универсума, которые не принадлежат А. Следовательно, А' = U - А = {х : х U и х А).

ОПРЕДЕЛЕНИЕ 2.14. Множество всех подмножеств множества А, или бу- леан множества А, обозначаемый , есть множество, состоящее из всех подмножеств множества А.

Следовательно, булеан множества А = {1,2,3} есть множество

  = {Ø, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}}.

Когда А содержит 3 элемента. состоит из 2³ = 8 элементов или, что то же самое, А включает 2³ = 8 подмножеств. Это будет показано в главе 8. В общем случае, если А содержит n элементов, множество включает 2ⁿ элементов, т.к. А имеет 2ⁿ подмножеств. По этой причине часто обозначают через 2^A.

 

Еще одной часто используемой операцией над множествами является декартово произведение, которое определяется следующим образом.

 

ОПРЕДЕЛЕНИЕ 2.15. Декартово произведение множеств А и В, обозначаемое А В, есть множество {(a, b) : а А и b В}. Объект (а, b) называется упорядоченной парой с первой компонентой а и второй компонентой b.

Множество А × В состоит из всех упорядоченных пар имеющих в качестве первой компоненты элемент из A, а в качестве второй компоненты — элемент из В. По существу, это та же упорядоченная пара, которую мы обычно используем в алгебре. Порядок компонент в паре существенен! Например, рисуя график функции, мы знаем, что точка (1,2) не совпадает с точкой (2,1).

 

Пусть A = {1,2,3}, а В = {r,s}. Тогда

 

A × В = {(1,r), (1,s), (2,r), (2,s), (3,r), (3,s)}.

 

Если каждое из множеств А и В представляет собой множество действительных чисел, то А × В представляет собой декартову плоскость, на которой упорядоченные пары чисел используются для графического изображения функций.

 

Если A содержит n элементов, а В содержит m элементов, тогда А × В содержит n•m элементов. В частности, если A пусто или В пусто, то, по определению, А × В пусто.