Треп о математике 2.2

Sergei Nickolaev написал(а) к All в Apr 23 15:10:22 по местному времени:

Привет, All!

В этом разделе задачки будут интереснее :-)

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

Множество называется счётным, если оно равномощно множеству N натуральных чисел, то есть, если его можно представить в виде {x0, x1, x2, . . . } (здесь xi - элемент, соответствующий числу i; соответствие взаимно однозначно, так что все xi различны).
Например, множество целых чисел Z счётно, так как целые числа можно расположить в последовательность 0, 1, -1, 2, -2, 3, -3, . . .

Несколько утверждений:
1. Подмножество счётного множества конечно или счётно.
Пусть B - подмножество счётного множества A. Представим множество A как {a0, a1, a2, . . . }. Выбросим из последовательности a0, a1, . . . те члены, которые не принадлежат B (сохраняя порядок оставшихся). Тогда оставшиеся члены образуют либо конечную последовательность (и тогда B конечно), либо бесконечную (и тогда
B счётно).

2. Всякое бесконечное множество содержит счётное подмножество.
Пусть A бесконечно. Тогда оно непусто и содержит некоторый элемент b0. Будучи бесконечным, множество A не исчерпывается элементом b0 - возьмём какой-нибудь другой элемент b1, и т. д.
Получится последовательность b0, b1, . . . ; построение не прервётся ни на каком шаге, поскольку A бесконечно. Теперь множество B = {b0, b1, . . . } и будет искомым счётным подмножеством. (Заметим, что B вовсе не обязано совпадать с A, даже если A счётно.)

3. Объединение конечного или счётного числа конечных или счётных множеств конечно или счётно.
Пусть имеется счётное число счётных множеств A1,A2, . . .
Расположив элементы каждого из них слева направо в последовательность (Ai = {ai0, ai1, . . . }) и поместив эти последовательности друг под другом, получим таблицу
a00 a01 a02 a03 . . .
a10 a11 a12 a13 . . .
a20 a21 a22 a23 . . .
a30 a31 a32 a33 . . .
. . . . . . . . . . . . . . .
Теперь эту таблицу можно развернуть в последовательность, например, проходя по очереди диагонали:
a00, a01, a10, a02, a11, a20, a03, a12, a21, a30, . . .
Если множества Ai не пересекались, то мы получили искомое представление для их объединения. Если пересекались, то из построенной последовательности надо выбросить повторения.
Если множеств конечное число или какие-то из множеств конечны, то в этой конструкции части членов не будет - и останется либо конечное, либо счётное множество.

Задачка 1:
Описанный проход по диагоналям задаёт взаимно однозначное соответствие между множеством всех пар натуральных чисел (которое обозначается N x N) и N.
Это соответствие задается простой формулой: многочленом второй степени с рациональными коэффициентами). Найдите этот многочлен.

Ещё несколько примеров счётных множеств:
1. Множество Q рациональных чисел счётно. В самом деле, рациональные числа представляются несократимыми дробями с целым числителем и знаменателем. Множество дробей с данным знаменателем счётно, поэтому Q представимо в виде объединения счётного числа счётных множеств.
2. Множество N^k, элементами которого являются наборы из k натуральных чисел, счётно. Это легко доказать индукцией по k.
Задачка 2: докажите :-)
3. По тем же причинам произведение двух счётных множеств A x B (множество пар, в которых 1-й элемент из A, 2-й элемент - из B) - счетно. Это же относится к произведению конечного количества счетных множеств (это произведение - упорядоченные наборы, в которых очередной элемент принадлежит очередному множеству).
4. Множество всех конечных последовательностей натуральных чисел счётно. В самом деле, множество всех последовательностей данной длины счётно (как мы только что видели), так что интересующее нас множество разбивается на счётное число счётных множеств.
5. В предыдущем примере не обязательно говорить о натуральных числах - можно взять любое счётное (или конечное) множество. Например, множество всех текстов, использующих русский алфавит (такой текст можно считать конечной последова-
тельностью букв, пробелов, знаков препинания и т. п.), счётно; то же самое можно сказать о множестве (всех мыслимых) компьютерных программ и т. д.
6. Число называют алгебраическим, если оно является корнем ненулевого многочлена с целыми коэффициентами. Множество алгебраических чисел счётно, так как многочленов счётное число (многочлен задаётся конечной последовательностью целых чисел - его коэффициентов), а каждый многочлен имеет конечное число корней (не более n для многочленов степени n).
7. Множество периодических дробей счётно. В самом деле, такая дробь может быть записана как конечная последовательность символов из конечного множества (запятая, цифры, скобки); например, дробь 0,16666. . . можно записать как 0,1(6). А таких последовательностей счётное множество.
8. Любое семейство непересекающихся интервалов на прямой конечно или счётно. Это утверждение опирается на то, что множество рациональных чисел всюду плотно в множестве вещественных чисел. Означает, что сколь угодно близко к любому вещественному числу можно найти рациональное число. Доказывать строго не буду, нестрого - если в бесконечной десятичной записи вещественного числа отбросить "хвост", получим рациональное число. Чем дальше начинается "хвост", тем ближе рациональное число к исходному вещественному.
Теперь берем середину интервала и находим рациональное число на расстоянии меньше половины длины интервала. Поскольку по условию интервалы не пересекаются, получаем взаимно-однозначное соответствие между множеством интервалов и некоторым множеством рациональных чисел. Последнее может быть только счетным или конечным.

Задачки:
3. Докажите, что любое множество непересекающихся восьмёрок на плоскости конечно или счётно. (Под "восьмеркой" будем понимать пару касающихся внешним образом окружностей, именно линий, а не плоских фигур, "восьмерка" полностью лежащая внутри одной из окружностей другой "восьмерки" без касания - не пересекается).
4. То же для непересекающихся букв "Т". (Пара перпендикулярных отрезков, конец одного из них расположен внутри другого отрезка).
5. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счётно. (Строгий локальный максимум - точка, в некоторой окрестности которой значения функции строго меньше, чем в этой точке).

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)