Akhmetova_Vodopyanov_-_Kurs_matana

Теорема 2. Пусть Х и У два множества такие, что Х , У и в У не менее двух элементов. Тогда множество всех функций, действующих из Х в У является множеством, мощность которого больше мощности множества Х.

Доказательство. Обозначим множество функций, действующих из Х в У через УХ. Доказательство разобьем на две части. Сперва покажем, что существует инъекция множества Х на часть множества УХ. Пусть у1 У, у2 У, у1 у2 и х0 Х. Построим функцию f[х0] следую-

щим образом: f[х0](х0) = у1, а если х х0, то f[х0] (х) = у2. При таком построении различным элементам в Х соответствуют различные

функции. Например, если х1 х0, то f[х1](х0) = у2. Таким образом, по-
лучаем инъекцию из Х в УX.
Покажем теперь, что не существует биекции между Х и УX.
Предположим противное, что g является биекцией из Х		на УX и
g(x) = fx	УХ. Покажем, что существует f УХ такое, что f	fх для лю-
бого х	Х. Пусть х Х и fх УХ соответствующая функция. Определим
f(х) = а	У из условия а fх(x). Такой элемент а в У обязательно най-

дется, так как в У не менее двух элементов. Таким образом построенная функция f не будет совпадать ни с одной функцией f . Следовательно g не может быть биекцией.

Теорема 3. Множество всех подмножеств произвольного непустого множества Х имеет мощность большую, чем мощность множества Х.

Доказательство. Положим У = {0,1}. Рассмотрим множество

УХ. Если f УХ,	то f разбивает Х на два множества:
Х0(f) = {x X: f(x)=0} и Х1(f) = {x				X: f(x) = 1}.
Таким образом,	каждому f УX	соответствует множество Х1(f). На-
оборот, если Х1 – некоторое подмножество из Х, то полагая
	1,	если	х	Х1,
	f(x) = 0,	если х	Х	Х1 ,

получим f УХ. Этим мы построили биекцию между множеством всех подмножеств множества Х и множеством УХ. Следовательно они равномощны и по теореме 2 мощность множества Х меньше мощности множества всех подмножеств.

31

Задачи.

1. Пусть А и В произвольные конечные множества, card(А) = n,

card(В) = m. Доказать, что общее число отображений из А в В равно nm.

2. Пусть в условиях предыдущей задачи m n. Определить число биекций и инъекций из А в В.

8. Примеры равномощных множеств

Приведенные выше примеры и теоремы показывают, что установить равномощность различных множеств далеко не просто. В этом параграфе мы рассмотрим примеры построения биекции между различными множествами. Будут приведены примеры доказательств равномощности ряда множеств.

Пример 1. Установить биекцию между отрезком [0, 1] и отрезком [а, b].

Решение. Легко устанавливается биективность линейного отображения x = (b – a)t + a отрезка [0, 1] на отрезок [а, b].

Пример 2. Установить биекцию между интервалом (0, 1) и ин-

тервалом (– , +	).
Решение.	Легко устанавливается	биективность отображения
x = ctg( t) интервала (0, 1) на интервал (–		, + ).

Задача. Рассмотреть основные элементарные функции и найти промежутки, на которых они являются биективным отображением.

Пример 3. Построить биекцию между отрезком [0, 1] и интерва-

лом (0, 1).

Решение. Решение этой задачи основано на несчетности рассматриваемых множеств и теореме 4 из параграфа 6. Идея решения состоит в том, что из интервала (0, 1) выделяют некоторое счетное множество А. Затем к нему добавляют две точки {0} и {1}. Вновь полученное множество (обозначим его В [0, 1]), также является счетным. Следовательно, множества А и В равномощны и существует биекция f, отображающая B на A. Построим теперь биекцию отрезка [0, 1] на интервал (0, 1) следующим образом:

g( x) =	f(x), если	х В,
	х, если х	В.
32

Пример 4. Построить биекцию между окружностью единичного радиуса и отрезком [0, 1].

Схема решения. Легко устанавливается биекция между точкой окружности и углом, соответствующим этой точке. Этим получается биекция окружности и полуотрезка [0, 2 ). Затем по схеме примера 3 строится биекция полуотрезка [0, 2 ) на отрезок [0, 1].

Пример 5. Доказать, что множество всех окружностей на плоскости, радиусы которых рациональные числа и координаты центра которых ‒ рациональные числа, есть счетное множество.

Решение. Нетрудно видеть, что каждый элемент рассматриваемого множества может быть отождествлен с тройкой чисел (х, у, r), где (х, у) – координаты центра окружности, а r – ее радиус. Этим между множеством указанных окружностей и множеством Q Q Q устанавливается биекция. Но произведение счетных множеств счетно (см. задачу в 6 параграфе) и, следовательно, наше множество также счетно.

Пример 6. Доказать, что множество точек разрыва монотонной функции, заданной на отрезке [а, b], конечно или счетно.

Решение. Предположим, что рассматриваемая функция f(х) является возрастающей. Пусть хточка разрыва этой функции. В силу монотонности функции и ее ограниченности ( f(а) < f(х) < f(b) ) в точ-

ке	х будет	существовать как предел слева, так и предел справа:
lim	f (x) A	B lim f (x) Таким образом, множество точек разрыва
x x		x x

{х } может быть отождествлено с множеством отрезков{[A, B ]}. При этом необходимо заметить, получаемые отрезки могут пересекаться лишь на концах и все они лежат на отрезке [f(а), f(b)]. Поставим каждому отрезку [А , В ] в соответствие рациональное число у , выбрав в качестве такового произвольное рациональное число из интервала (А , В ) (наличие такое числа гарантируется аксиомой непрерывности действительных чисел и тем, что А В ). В силу отмеченного выше, построенное соответствие будет являться инъекцией. Следовательно, мы построили инъекцию множества точек разрыва монотонной функции на отрезке [а, b] в счетное множество рациональных точек отрезка [f(а), f(b)]. Это означает, что рассмотренное множество точек разрыва не более чем счетно.

33

Задачи.

1. Существует ли функция вида		a0	a1 x+...+an xn
	f(x) =	b0	b1 x+...+bn xn (где ко-

эффициенты a0, a1, ..., an; b0, b1, ..., bn – целые числа), обладающая следующим свойством: для любого рационального числа r найдется такое целое число k, что f(k) = r.

2. Найти биекцию числовой прямой на интервал (а, b).

3. Найти биекцию полуотрезка [0, 1) на полуось [0, ).

4.Построить биекцию отрезка [0, 1] на всю числовую ось.

5.Существует ли непрерывная функция, являющаяся биекцией отрезка [а, b] на всю числовую ось?

6.Существует ли непрерывная функция, являющаяся биекцией отрезка [а, b] на интервал (с, d)?

7.Установить биекцию между открытым и замкнутым единичным кругом.

8.Какова мощность множества всех треугольников на плоскости, вершины которых имеют рациональные координаты?

9.Какова мощность множества всех рациональных функций с целыми коэффициентами в числителе и знаменателе?

10.Доказать, что множество точек разрыва монотонной функции, определенной на всей числовой прямой, не более чем счетно.

11.Пусть Е – счетное множество точек на прямой. Можно ли так

сдвинуть это множество на величину а (т.е. заменить все точки х Е точками х + а), чтобы получившееся в результате сдвига множество Еa не пересекалось с Е?

12.Пусть Е – счетное множество точек на окружности. Можно ли повернуть окружность вокруг центра на некоторый угол так, чтобы множество Е , получившееся из Е в результате поворота, не пересекалось с Е?

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

14.Какова мощность множества всех строго возрастающих последовательностей натуральных чисел?

15.Какова мощность множества всех последовательностей натуральных чисел, не содержащих число 7?

34

16.Какова мощность множества всех многочленов (с произвольными вещественными коэффициентами)?

17.Какова мощность множества всех отрезков на числовой пря-

мой?

18.На числовой прямой задано множество попарно непересекающихся отрезков. Какова его мощность?

19.Какова мощность множества всех строго возрастающих непрерывных функций на отрезке [а, b]?

20.Доказать, что если А – В равномощно В – А, то А и В равно-

мощны.

21.Доказать, что если А В и А равномощно А С, то В равномощно В С.

22.Верно или нет утверждение: “Если А равномощно С, В рав-

номощно D, причем А В, С D, то А – В равномощно С – D”?

23.Доказать, что множество всех конечных подмножеств счетного множества – счетно.

24.Какова мощность множества всех конечных и счетных подмножеств множества Е, если Е имеет мощность континуума?

9. Отношение порядка

Определение. Отношение r в множестве Х, удовлетворяющее условиям:

1) хrх для х Х (рефлексивность);

2)из хrу и уrх следует, что х = у (антисимметрия);

3)из хrу и уrz следует, что хrz (транзитивность).

называется частичным порядком на Х.

Пример. 1) Обычное отношение (или ) на множестве всех чисел;

2)х является целым кратным у, где х и у из N;

3)отношение включения для множеств на множестве всех подмножеств.

Определение. Отношение r на Х, удовлетворяющее условиям:

1)	хrх для х Х;
2)	из хrу и уrz следует хrz.

называется предпорядком.

35

Пример. На некотором множестве людей отношением предпорядка являются: а) рост одного человека больше или равен росту другого; б) вес одного человека больше или равен весу другого.

Если на множестве Х задано отношение предпорядка r, то полагая, что хsу, если хrу и уrх, получим отношение эквивалентности s на Х (проверить самостоятельно). Эквивалентность s разбивает Х на классы эквивалентности [x]. Обозначим через [X] – множество всех классов эквивалентности в Х. На [X] предпорядок r порождает отношение частичного порядка t по правилу [x]t[y], если х1 [x] и

у1 [y]: x1rу1. Если х2 [x], то х2sх1, т.е. х2rх1 и х1rу1, следовательно, х2rу1. Последнее означает, что [x]t[y] тогда и только тогда, когда для

х [x] и у [y] выполняется хrу. Проверьте самостоятельно, что t является отношением частичного порядка на [X].

Определение. Отношение r в Х называется строгим порядком, если это отношение обладает свойствами^

1)отношение хrх не верно ни для одного х Х (иррефлексив-

ность);

2)из хrу и уrz следует хrz.

Если на множестве Х задан частичный порядок r, то он порождает на Х отношение строгого порядка t по правилу: хtу тогда и только тогда, когда хrу и х у. Верно и обратное: отношение строгого порядка порождает отношение частичного порядка (каким образом?).

Таким образом, наличие одного из порядков, частичного или строгого, автоматически порождает на том же множестве наличие и другого порядка. Следовательно, можно говорить лишь о наличии порядка на множестве, имея ввиду, что тогда на этом множестве есть и частичный, и строгий порядки.

Множество Х, на котором введено отношение частичного порядка r, называется линейно упорядоченным (или цепью), если для

х, у Х выполнено одно из отношений: либо хrу, либо уrх.

Пусть Х – множество с частичным порядком r, а М Х. Тогда у Х называется левой гранью множества М, если уrх для х М.

Если же z Х и хrz для х М,		то z называют правой гранью множе-
ства М.
Определение. Элемент у		Х называется точной левой гранью
множества М	Х, если
1) уrх для	х М;
36

2) zrу для	z Х: zrх.
Определение. Элемент у Х называется точной правой гранью
множества М	Х, если:
1) хrу для	х	М;
2) уrz для	z	Х: zrх.

Определение. Элемент у М называется правым экстремальным (левым) элементом множества М Х, если: хrу (соответственно, уrх) для х М.

Задачи.

1.Показать, что если r является отношением частичного порядка, то r-1 также есть частичный порядок.

2.На множестве всех непрерывных функций на отрезке [а, b]

введем отношение f = О(g) по определению: для всех х [а, b] выполняется неравенство f(х) Мg(х) для некоторого М. Показать, что введенное таким образом отношение является предпорядком.

3. Доказать, что отношение m n, если n делится на m, является отношением порядка на N. Проверить, что для всякого конечного множества А N в этом упорядочении существует точная грань.

	10. Элементы комбинаторики
	Пусть есть некоторое конечное множество		элементов
U = {a1, a2, ..., an}. Рассмотрим набор элементов a		, a	, ..., a , , где
	i1	i2	i
			r
a	U, j = 1, 2, ..., r. Этот набор называется выборкой объема r из n
i j

элементов. Любое подмножество U является выборкой, но не всякая выборка является подмножеством U, так как в выборку один и тот же элемент может входить несколько раз (в отличие от подмножества).

Комбинаторные задачи связаны с подсчетом числа выборок объема r из n элементов, где выборки подчиняются определенным условиям, т.е. выбор производится по какому-нибудь принципу. Подсчет числа выборок основывается на двух правилах теории множеств.

Принцип суммы: если card A = m, card B = n и A B = , то card A B = m + n. На комбинаторном языке это означает: если объект A можно выбрать m способами, объект B другими n способами и

37

их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m + n способами.

Принцип произведения: если card A = m, card B = n, то card

(A B) = m n. На комбинаторном языке это означает: если объект A может быть выбран m способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен m n способами.

Пример 1. A = {10 различных шоколадок}, B = {5 различных пачек печенья}. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в этом случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.

Пример 2. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков ?

Пусть m – число возможностей для выпадения четного числа на одной кости, n – число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, равно как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных или двух нечетных чисел будет 18.

Рассмотрим основные способы формирования выборок. Определение. Выборка называется упорядоченной, если в ней

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

Из определения следует, две упорядоченные выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, являются различными.

Перестановки. Упорядоченные выборки объемом n из n элементов, где все элементы различны, называются перестановками из n элементов. Число перестановок из n элементов обозначается Pn.

Теорема 1. Pn = n!

Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P1 = 1!. Пусть для n = k теорема верна и Pk = k !, покажем, что она тогда верна и для n = k + 1. Рассмотрим (k + 1)-й элемент, будем считать его объектом A, который можно выбрать k+1 способами. Тогда объект B – упорядоченная выборка из ос-

38

A mn .

A mn .

тавшихся k элементов по k. B соответствии с индуктивным предположением объект B можно выбрать k! способами. По принципу произведения выбор “A и B” можно осуществить k! (k + 1) = (k + 1)! способами. А совместный выбор “A и B” есть упорядоченная выборка из k + 1 элементов по k + 1.

Пример 3. Сколько существует способов, чтобы расположить на полке 10 различных книг? Ответ: 10!

Можно рассуждать иначе. Выбираем первый элемент, это можно сделать n способами. Затем выбираем второй элемент, это можно сделать (n 1) способами. По правилу произведения упорядоченный выбор двух элементов можно осуществить n (n 1) способами. Затем выбираем третий элемент, для его выбора останется n 2 возможности, последний элемент можно выбрать единственным способом. Мы вновь приходим к формуле: n(n 1)( n r) ... 1.

Размещения. Упорядоченные выборки объемом m из n элементов (m n), где все элементы различны, называются размещениями. Число размещений из n элементов по m обозначается

	Теорема 2. A nm =	n!		.
		(n - m)!

Доказательство. Обозначим x = A mn . Тогда оставшиеся (n – m) элементов можно упорядочить (n - m)! способами. По принципу произведения, если объект A можно выбрать x способами, объект B (n – m)! способами, то совместный выбор “A и B” можно осуществить x (n – m)! способами, но выбор “A и B” есть перестановка и Pn = n!

n! Отсюда x = A mn = (n - m)! .

Рассуждая иначе: первый элемент выбираем n способами, второй – (n – 1) способами и т.д. , m-й элемент выбираем (n – m + 1) способом. По принципу произведения вновь имеем: n(n – 1)...(n – m +1), что совпадает с

Пример 4. Группа из 15 человек выиграла 3 различные книги. Сколькими способами можно распределить эти книги среди группы?

	Имеем A153	15!
				= 15 14 13 = 2730.
		12!

39

Сочетания. Неупорядоченные выборки объемом m из n элементов (m n) называются сочетаниями. Их число обозначается Cmn .

		Cnm	n!			.
	Теорема 3.
			m!(n	m)!

Доказательство. Очевидно, Amn = Cmn m!. Действительно, объект A - неупорядоченная выборка из n элементов по m, их число C mn . После того, как эти m элементов отобраны, их можно упорядочить m! способами (в роли объекта B выступает “ порядок “ в выборке). Совместный выбор “A и B“ – упорядоченная выборка.

Пример 5. Группа из 15 человек выиграла 3 одинаковые книги. Сколькими способами можно распределить эти книги?

	C153	15!		15	14	13	455.
		3!12!		1	2	3

Сочетания, размещения и перестановки являлись подмножествами исходного множества. Рассмотрим выборки, которые не являются подмножествами.

Размещения с повторениями. Упорядоченные выборки объемом m из n элементов, где элементы могут повторяться, называются

размещениями с повторениями. Их число обозначается A mn (n).

Теорема 4. A mn (n) = nm.

Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m-й элемент также может быть выбран n способами. По принципу произведения получаем nm .

Пример 6. Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций?

Здесь n = 10, m = 4 и ответом будет 104.

Пример 7. Рассмотрим вектор длины m, каждая координата которого может принимать всего 2 значения: 0 или 1. Сколько будет таких векторов ?

Это есть выборка объемом m из двух элементов. Ответ : 2m

Перестановки с повторениями. Пусть имеется n элементов,

среди которых k1 элементов первого типа, k2 элементов второго типа и т.д., ks элементов s-го типа, причем k1 + k2 + ... + ks = n. Упорядоченные выборки из таких n элементов по n называются перестановками

40