10 Множества и операции с ними. Функции. Мощности множеств. Множества на вещественной прямой. Вещественные числа.

Каждому такому отображению соответствует ровно одна (такое соответствие очевидно взаимно-однозначное) строчка длины Соответствие это строится следующим образом:

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

И вот, если то в этой строчке на ом месте будет стоять 0, а если то в этой строчке на ом месте будет стоять 1.

То есть, каждая функция - это просто набор из нулей и единиц длины

Причём же здесь множество всех поджмножеств множества ?
А притом, что любое подмножество множества можно задать так: сопоставить 0 тем элементам, которые в подмножество не входят, и 1 - тем элементам, которые в подмножество входят. Тогда различных подмножеств множества всего столько же, сколько строк длины составленных из нулей и единиц. То есть, ровно столько, сколько функций - как мы показали выше.

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

b) В данном случае композиция будет равна Наша функция определена только при тех при которых . То есть при тех что

a) Функция, устанавливающая биекцию между интервалами и задаётся формулой Поскольку эта функция представляет собой линейную функцию вида то она, очевидно, и инъективна (иначе бы какие-то две точки прямой склеились бы в одну), и сюръективна, поскольку в противном случае мы бы на выходе получили не всю прямую. В том числе, она инъективна и сюръективна на указанных множествах. Следовательно, - биекция.

b) Выберем для начала все рациональные точки на отрезке То есть, пусть - множество всех рациональных чисел на занумерованных произвольным образом, но с условием, что (их можно занумеровать, так как а, следовательно, и - cчётно).

Далее, пусть - произвольная нумерация рациональных чисел на интервале

Тогда биекцию построим вот так: и далее для любого рационального числа пускай при

То есть мы просто взяли и перегнали рациональные концы отрезка в какие-то две произвольные рациональные точки а между оставшимися рациональными числами отрезка и интервала устроили биекцию (оба множества счётные, поэтому такая биекция существует).

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

Для этого заметим для начала, что из таблицы истинности с очевидностью следует, что импликация вот так выражается через дизъюнкцию и отрицание:

Таким образом, отрицание импликации будет отрицанием дизъюнкции, и нам нужно будет воспользоваться для раскрытия скобок здесь законом де Моргана и законом снятия двойного отрицания:

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

Давайте для примера проверим c):

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

Вспомним определения наших операций объединения и пересечения. Допустим, с пересечением:

Видно, что объединение двух множеств определяется через логическую связку И. Но эта связка, очевидно, ассоциативна, когда у нас берется связка И от логических высказываний (). Аналогично, ассоциативна и связка ИЛИ. Следовательно, будут ассоциативными и теоретико-множественные операции, которые через них определяются.

a) поскольку ;

b) Эти три множества вложены друг в друга, поэтому их пересечение будет равно наименьшему из множеств ;

c) Поскольку то их объединение будет равно большему из множеств, то есть ;

d) Ясно, что ;

Далее, симметрическая разность будет равна

Ясно, что

e) в - это будут все те числа, что лежат в но не лежат в Это так называемое множество иррациональных чисел (обознач.: ;

f) Единственное простое и четное число одновременно - это 2. Таким образом, ;

g) По определению, декартово произведение - это множество пар

Таким образом, каждой фиксированной точке окружности будет соответствовать целый луч . Получается, что над каждой точкой окружности можно нарисовать такой луч - и получится в итоге поверхность кругового цилиндра, бесконечного в одну сторону (условно бесконечный вверх);
Действительно, любая пара точек

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

h) По определению, декартово произведение - это множество пар

Таким образом, каждой фиксированной точке вещественной прямой соответствовать целый отрезок . Получается, что над каждой точкой вещественной прямой можно нарисовать такой отрезок - и получится в итоге бесконечная (в обе стороны) полоса высоты 1;

i) По определению, декартово произведение - это множество троек

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

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

Давайте как раз найдем, сколько человек у нас будет в Хочется просто взять и сложить 128+126=254. Но тогда мы дважды посчитаем и тех, кто решил первую (как кусочек ) и тех, кто решил вторую (как кусочек ). Значит, чтобы этих людей учесть лишь однажды, нужно их отнять. Таким образом, (Запись означает пока что просто количество элементов в конечном множестве ).

Таким образом, ни одной задачи не решило

Ответ: 244

Это так называемая формула включений-исключений, которую можно обобщить и на большее количество множеств в объединении.

Произвольное подмножество множества содержит или не содержит каждый из трёх элементов множества

Давайте будем кодировать все возможные подмножества множества последовательностями из нулей и единиц по следующему правилу: мы берем на ом месте, если -ый элемент множества НЕ входит в подмножество, и 1 на ом месте, если -ый элемент множества входит в подмножество.

Например, последовательность кодирует подмножество, в которое последние два элемента входят, а первый не входит, то есть подмножество

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

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

На первое место у нас два варианта, что можно поставить, на второе и на третье - тоже. Значит, всего вариантов будет

Действительно все эти подмножества можно перечислить явно:

Замечание. Ясно, что этим же способом можно доказать, что у любого конечного множества, состоящего из элементов, будет подмножеств.

a) Наша функция заведомо не будет сюръекцией, поскольку чтобы она была сюръекцией, синус должен был бы уметь давать на выходе любые числа из В то время как наоборот, всегда не превосходит по модулю 1, какие бы иксы мы в него ни подставляли.

Синус также не будет и инъекцией, поскольку он склеивает разные точки. Например, однако ;

b) Аналогично предыдущему пункту косинус не будет ни сюръекцией, ни инъекцией.

Сюръекцией он не будет по тем же самым причинам, а инъекцией, например, потому, что ;

c) Такая функция не будет сюръекцией, потому что она не умеет выдывать любые числа из на выходе. Действительно, для любого Значит, отрицательных чисел мы не получим.

В то же время, даже по графику легко увидеть, что у нас при функции разные точки переходят в разные. То есть, если то и Следовательно, в этом случае - инъекция;

d) Такая функция не будет сюръекцией, потому что она не умеет выдывать отрицательные числа из на выходе. Действительно, для любого Тем самым, - не сюръекция.

Далее, поскольку однако то разные точки переводит в одну и ту же. Следовательно, - не инъекция;

e) Мы здесь имеем дело с тождественной функцией (графиком её является прямая линия - биссектриса первого и третьего координатных квадрантов). То есть, функцией, которая на выход возвращает то же самое, что мы ей дали на вход.

Ясно, что при помощи такой можно получить любое число из - какое число мы хотим получить, такое и нужно в неё подставить. Значит, - сюръективна.

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

Тем самым, в данном примере - это и инъекция и сюръекция одновременно (а, значит, и биекция).

От противного.
Пусть, наоборот, существуют такие что И давайте договоримся, что дробь - несократима, то есть у и нет общих делителей (в противном случае её можно просто сократить, ведь дробь-то от этого не поменяется, и если раньше она была равна корню из 2, то и после сокращения - тоже).

Что дальше? Логично возвести равенство в квадрат. Тогда получится, что или

Далее, заметим, что правая часть равенства () делится на 2. Значит, и левая часть () - тоже. Но если квадрат какого-то числа делится на 2, то он, очевидно, должен делиться и на 4. Следовательно, левая часть равенства делится на 4. Но правая часть, равная тогда тоже должна делиться на 4. Следовательно, должен делиться хотя бы на 2. Но тогда, конечно, и должно делиться на 2.

Мы получили противоречие с тем, что дробь - несократима. Так как выше мы показали, что оба числа и делятся на 2.

Возьмём . Ясно, что - непусто (иначе бы состояло из одного элемента ). Тогда возьмём . Ясно, что - непусто (иначе бы состояло из двух элементов ). Тогда возьмём . И так далее...

На каждом шаге мы можем вытащить ещё один элемент из , иначе бы вообще было конечным. Таким образом, мы сможем вытащить из элемент с любым натуральным номером, то есть в заведомо содержится множество :

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

a) Давайте сделаем такую биекцию из в : отправим отрицательные числа из в нечётные числа в , а неотрицательные числа из в чётные числа в . То есть устроена так:

Ясно, что - это функция, поскольку каждое целое число отображается только в одно натуральное. Ясно, что это инъекция, потому что разные целые числа отображаются в разные натуральные. Ясно, что это сюръекция, поскольку при помощи мы можем попасть в любое натуральное число. Следовательно, - биекция, а, значит, - счётно.

b) Давайте сделаем такую биекцию из

Ясно, что - это функция, поскольку каждый полный квадрат отображается только в одно натуральное число. Ясно, что это инъекция, потому что разные полные квадраты отображаются в разные натуральные числа. Ясно, что это сюръекция, поскольку при помощи мы можем попасть в любое натуральное число. Следовательно, - биекция, а, значит, - счётно.

a) Биекция задаётся линейной функцией ;

b) При помощи биекции из пункта a) отобразим наш интервал в интервал . Далее, интервал на всю прямую можно биективно отобразить при помощи отображения . Таким образом, получаем композицию биективных отображений:

Эта композиция будет осуществлять биекцию между интервалом и ;

c) Давайте занумеруем все рациональные числа интервала : . Теперь, чтобы построить биекцию , давайте сделаем так:

то есть мы первое рациональное число из интервала отправляем в ноль отрезка, второе рациональное число из интервала отправляем в единицу отрезка, а дальше рациональные числа из интервала отправляем в рациональные числа отрезка со сдвигом на два номера.

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

Таким образом, получаем взаимно-однозначное отображение из в .

a) Пусть в есть два нуля , оба из которых удовлетворяют аксиоме A1.

Тогда с одной стороны

ведь для любого выполнено, что

(мы просто воспользовались A1 в применении к ).

Теперь же, с другой стороны,

ведь для любого выполнено, что

(мы просто воспользовались A1 в применении к ).

Таким образом, получаем, что

и в то же время

Следовательно,

То есть эти два нуля обязаны совпадать. Что и требовалось.

b) Пусть для какого-то имеется два обратных ему , то есть

Но тогда

То есть мы получили, что , что и требовалось доказать.

Отметим, что в процессе нам нужно было еще воспользоваться аксиомой A3, гарантирующей нам возможность расставлять в сумме скобки как мы хотим.

c) Действительно:

Пока мы воспользовались только тем, что - это очевидно и потом воспользовались A9 для раскрытия скобок.

Далее, мы получили, если обратить внимание только на первый и на последний член равенства, следующее:

Обозначим . То есть у нас имеется равенство

У этой обязан быть обратный по сложению ( это гарантирует A2 ). Прибавим к обеим частям последнего равенства этот самый обратный к , то есть прибавим к обеим частям :

Левая часть этого равенства равна нулю по A2, а в правой части разность тоже равна нулю.

Следовательно, получили

Что и требовалось.

1. То, что вещественных чисел в интервале бесконечно много - очевидно.

2. Почему их несчётно?

Будем доказывать от противного. Пусть, напротив, множество - счётно, то есть существует биекция

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

И из того, что - биекция следует, что в этой таблице встретится каждое вещественное число, причем каждое встретится ровно один раз.

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

И, таким образом, ясно, что любое вещественное число из интервала является десятичной дробью вида

Тогда нашу таблицу можно переписать в виде

То есть - это -ая цифра десятичной дроби, расположенной в ой строчке нашей таблицы.

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

Действительно, в этой таблице нет числа, устроенного следующим образом:

Где - любая цифра, отличающаяся от , - любая цифра, отличающаяся от , ..., - любая цифра, отличающаяся от , и так далее.
Например, если было цифрой 5, то в качестве возьмем любую цифру, кроме 5. И так на каждой позиции.

Ну и что же у нас получается? А получается, что построенная таким образом бесконечная десятичная дробь

очевидно лежит в интервале .

Но её не было в нашей таблице. Ведь она отличается от каждой десятичной дроби в таблице. А именно, она отличается от -го числа как минимум в -ом (а, быть может и в каких-то других тоже) разряде.

Противоречие, ведь мы предположили, что в нашей исходной таблице

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

Следовательно, раз мы получили противоречие, то такой биекции вообще не может существовать. Поэтому множество - несчётно.

Давайте наглядно продемонстрируем метод с кругами Эйлера. Он состоит в том, что мы на диаграмме Эйлера рисуем левую часть равенства, правую часть равенства, и убеждаемся в том, что они задают одно и то же.

Правую часть, понятное дело, нарисовать здесь будет совсем нетрудно:

А как нарисовать левую? Давайте вначале нарисуем то, что в скобках. То есть

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

А этот пример давайте докажем рассуждениями. Итак, нам нужно доказать равенство множеств:

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

Докажем вначале, что . Итак, пусть , то есть . Это означает, что , и при этом . Есть два случая.

1 случай. . Тогда получается, что , значит, , значит, конечно,

таким образом, .
2 случай. . Тогда получается, что , значит, , значит, конечно,

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

Это будет множество всевозможных пар: один элемент из множества , другой - из множества . Получается всего 6 элементов:

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