Множества. Комбинаторика. Отношения (стр. 3 )

Пусть А и В – частично упорядоченные множества и f – функция из А в В. Если "x1,x2ÎA: x1£x2 => f(x1) £ f(x2), то функция называется монотонной. Если f – взаимно однозначное соответствие между А и В и f и f--1 монотонны, то f называется изоморфизмом частично упорядоченных множеств А и В, а множества А и В называются изоморфными.

Упражнения

1) Докажите, что множество всех подмножеств данного множества частично упорядочено отношением включения Í.

2) Всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента. Докажите.

3) Постройте линейный порядок на N2.

1.1.8. Мощность множества

Множество А называется эквивалентным множеству В, если между А и В можно установить взаимнооднозначное соответствие. В этом случае применяется обозначение А~В.

Свойства эквивалентности:

1) А~А (рефлексивность),

2) если А~В, то В~А (симметричность),

3) если А~В, В~С, то А~С (транзитивность).

Мощностью множества А называется класс всех множеств, эквивалентных множеству А, и обозначается он через Ā или card А. Эквивалентные множества называют равномощными. Обозначим через 0 мощность пустого множества Æ, через 1 мощность множества {0}, через 2 мощность множества {0, 1},..., n = card{0, 1,..., n-1}. Если существует натуральное n такое, что n = card А, то множество называют конечным, а n – числом элементов множества A, n = |A|. Всякое подмножество конечного множества конечно, объединение конечного числа конечных множеств конечно, прямое произведение конечного числа конечных множеств конечно. Множество, не являющееся конечным, называется бесконечным.

ТЕОРЕМА. Конечное множество неэквивалентно собственному подмножеству.

Доказательство. Пусть f – взаимнооднозначное отображение A в А, т. е. f(A)Ì A. Возьмем aÎA\f(A) и построим последовательность а0 = а, аi+1 = f(ai) при i ³ 0. Тогда ai ¹ aj при i ¹ j. Значит А содержит бесконечное подмножество {a0, a1, …}. ■

1.1.9. Счетные множества

Множество, эквивалентное множеству N0={0, 1, 2, ...}, называется счетным и его мощность обозначается w

ТЕОРЕМА. Бесконечное множеств содержит счетное подмножество.

Доказательство. Пусть А бесконечно, a0ÎА. Тогда А\{a0} тоже бесконечно. (Если предположить, что В=А\{a0} конечно, то и А=ВÈ{a0} также конечно). Следовательно, существует a1ÎА\{a0}, что А\{a0,a1} бесконечно, и т. д. Полoжим f(0) = a0, f(1) = a1,... Тогда f осуществляет взаимнооднозначное соответствие между множествами N0 и {a0,a1,...}. ■

ТЕОРЕМА. Множество бесконечно тогда и только тогда, когда оно эквивалентно некоторому собственному подмножеству.

Доказательство. Пусть А бесконечно, В = {b0, b1 , ...} – его счетное подмножество. Тогда А = (BÈ(A\B)) ~ (B\{b0})ÈА\B = A\{b0} Обратное очевидно. ■

ТЕОРЕМА. Подмножество счетного множества счетно или конечно.

Доказательство. Достаточно доказать для N0. Пусть IÌ N0 и I бесконечно. Построим f: N0 ®I. Возьмем в качестве f(0) наименьший элемент множества I, в качестве f(1) наименьший элемент множества I\{f(0)} и т. д.; f осуществляет взаимнооднозначное соответствие между N0 и I. ■

ТЕОРЕМА. Если А и В счетны, то AÈB счетно. ■

ТЕОРЕМА. Если А бесконечно, В – конечное или счетное множество, то AÈB ~ А. Если А бесконечно и несчетно, В конечно или счетно, то А\В ~ А.

Доказательство. Если А1 счетное подмножество множества А, то А1ÈВ ~ А1. Поэтому AÈB = (A\A1)È(A1\B) ~ (A\A1)ÈA1 = A. Здесь А\В бесконечно, поэтому (А\В)ÈВ ~ A\В. Отсюда А ~ (А\В). ■

Будем говорить, что card А £ card В, если А эквивалентно некоторому подмножеству множества В. Если card А £ card В, а А и В неэквивалентны, то будем писать card А < card В.

Упражнения

Докажите, что:

а) множество целых чисел Z счетно;

б) множество рациональных чисел Q счетно;

в) множество пар <х, у>, где х, у Î Q счетно;

г) множество многочленов от одной переменной с целыми коэффициентами счетно;

д) множество алгебраических чисел, т. е. являющихся корнями многочленов от одной переменной с целыми коэффициентами, счетно.

1.1.10. Метод полной математической индукции

Индукция – переход от частного к общему, дедукция – переход от общего к частному. Для конечного множества полная индукция – синоним полного перебора. Только совершив полный перебор элементов конечного множества, можно сделать общий вывод обладают ли каким-либо свойством элементы этого множества. Принцип математической индукции позволяет осуществить в некоторых случаях полный перебор элементов бесконечного множества.

Доказательство утверждения А(n) методом полной математической индукции заключается в следующем:

1) Проверяется справедливость утверждения для n = 1 (база индукции).

2) Предполагается справедливость этого утверждения для n = к, где кÎZ (гипотеза индукции).

3) С учетом этого предположения устанавливается справедливость его для n = к+1 (индукционный переход).

Доказательство методом неполной математической индукции некоторого утверждения, зависящего от n ³ р (р ³2), проводится следующим образом:

1) Устанавливается справедливость утверждения для n = р.

2) Предполагается справедливость утверждения для n = к ³ p.

3) Исходя из этого предположения, устанавливается его справедливость для n = к+1.

Пример. Докажите, что n5 – n делится на 30 для натурального числа n.

¨ Доказательство проведем методом полной математической индукции по числу n. При n =1 получаем 0 делится на 30. База индукции есть. Предположим, что при n = k утверждение верно, т. е. k5–k делится на 30. Пусть n = k+1. Тогда (k+1)5 – (k+1) = k5 +5 k4 +10 k3 + 10 k2 + 5 k + 1 –k –1 = ( k5 –k) + 5 k( k+1)( k2 +k +1). Первое из слагаемых делится на 30 по гипотезе индукции. Так как либо k, либо k+1, либо k2 +k +1 делится на 3, а произведение двух последовательных целых чисел k( k+1) делится на 2, то и второе слагаемое делится на 30. Утверждение доказано методом полной математической индукции.

Пример. Докажите, что

13 +23 +33 + … + n3 = n2 (n +1)2/4

¨ База индукции. При n = 1 выражения, записанные слева и справа, принимают значение 1. Это значит, что база индукции есть.

Гипотеза индукции. Предположим, что при n = k, где k ³ 1, имеет место равенство:

13 +23 +33 + … + k3 = k2 (k +1)2/4.

Право перехода. Пусть n = k+1. Тогда

13 +23 +33 + … + k3 +( k+1)3 = k2 ( k +1)2/ 4 + (k +1)3 =

= ( k+1)2( k2/ 4 +k+1) = ( k+1)2( k+2)2/ 4.

Получили значение выражения слева доказываемого равенства при n = k+1. Утверждение доказано методом полной математической индукции.

Пример. Для каждого b>1 и натурального n>1 верно неравенство Бернулли bn ³ 1+n(b-1).Докажите.

¨ n = 1; b ³ b. Верное неравенство. n = k, где k ³ 1; bk ³ 1+k(b-1).

n = k+1; bk+1 = bkb ³ b(1+k(b –1)) =b +kb –k = (k+1)(b -1) +1.

Упражнения

Докажите методом полной математической индукции:

1)  1 +2 +3 + … +n = n( n+1)/ 2;

2)  1 +3 +5 + … +(2n –1) = n2;

3)  12 +22 +32 + … +n2 = n(n +1)(2n +1)/ 6;

4)  14 +24 +34 + … +n4 = n2( n+1)2(2n+1)2/ 36;

5)  1/ 1×2 + 1/ 2×3 + 1/ 3×4 + … + 1/ n(n +1) = n/ (n+1);

6)  2 n > n;

7)  2 n > n2, n ³ 5;

8)  np – n делится на p, p – простое число;

9)  4 n + 15n – 1 делится на 9;

10)  если |Х| = m, то |Хn|=mn; (Х – множество, |Х| – число элементов);

11)  если Х1, ..., Хк – конечные попарно непересекающиеся множества, то |Х1È...ÈХк| = |Х1|+...+|Хк|.

1.2. Комбинаторика

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

Правило суммы. Если объект А может быть выбран m способами, а объект В другими n способами, то выбор "либо А, либо В" может быть осуществлен m+n способами.

Правило умножения. Если объект А может быть выбран m способами и после каждого из таких выборов объект В в свою очередь может быть выбран n способами, то выбор "А и В" в указанном порядке может быть осуществлен mn способами.

Т. е. союзам “и” и “или” в математике соответствуют знаки “х” и “+”, соответственно.

Примеры:

1)  Сколько существует трехзначных чисел?

Решение: Каждое трехзначное число – это выражение вида XYZ. Первую цифру мы можем выбрать 9 способами (всего цифр десять, но на первое место мы не имеем права ставить 0), вторую цифру – 10 способами, третью – тоже десятью. А так как мы выбираем и первую, и вторую, и третью, то между ними ставим знак “умножить”. Получаем: 9х10х10=900 трехзначных чисел.

2)  Сколько существует четырехзначных чисел, делящихся на 2?

Решение: Аналогично предыдущей задаче, первую цифру выбираем 9 способами, вторую – 10, третью – 10, а четвертую только 5 (так как число делится на 2, если у него последняя цифра четная, т. е. 0. 2. 4. 6, 8). Следовательно, получаем 9х10х10х5=4500 четырехзначных четных чисел.