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

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

Это попросту означает, что каждому будет соответствовать единственный
Коротко и формально это записывается вот как:

Посмотрим, что для нас это означает в данном случае. В пункте a) мы сопоставляем человекам стулья.

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

Напомним определение инъекции:
Опр. - инъективно, если если они разные, то есть то и их образы при отображении тоже разные, то есть

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

Напомним определение сюръекции:
Опр. - сюръективно, если такой, что То есть, мы при помощи нашего отображения можем попасть в любой элемент множества

Переведём это на язык нашей ситуации: это попросту означает, что все стулья заняты!

Напомним определение биекции:
Опр. - биективно, если одновременно и инъективно, и сюръективно.

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

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

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

Функциональность здесь означает, что каждому стулу соответствует ровно один человек, то есть что ни на каком стуле не сидит двое и больше людей (сравните с инъективностью из пункта a))
Инъективность будет означать, что разным стульям соответствуют разные люди, то есть что никакой человек не решил усидеть на двух стульях одновременно (сравните с функциональностью из пункта a)).
Сюръективность будет означать, что у нас каждый человек сел на какой-то стул, т.е. что не осталось ни одного человека, который не сидел бы на стуле. (Это зеркально напоминает ситуацию с сюръективностью ).
Биективность , вместе с функциональностью дают по смыслу то же самое, что и биективность и функциональность (вместе): то что стульев и людей поровну, т.е. каждый человек сидит ровно на одном стуле и все стулья заняты и все люди сидят.

Коль скоро - бесконечно, а - конечно то и - бесконечно (иначе, в противном случае, мы бы получили, что - конечно, как объединение двух конечных множеств ).

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

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

Осталось только задать
Итак, пусть устроена вот как:

То есть мы просто сдвинули все наши элементы на позиций, как в парадоксе Гильбертова отеля, когда учёных приехало в бесконечный отель, который был полностью заполнен гостями. Очевидно, что наша является биекцией, поскольку все элементы достижимы из каких-то элементов (а именно, элемент с номером (или ординалом, если их более чем счётно) приходит из элемента ). Элементы же приходят из первых иксов
То, что - инъекция видно по построению. Разные элементы множества переходят в разные элементы множества Значит, мы всё доказали.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

d) Ясно, что ;

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

Ясно, что

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

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

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

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

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

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

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

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

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

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

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

Ответ: 244

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

Любое подмножество множества может содержать или не содержать элементы множества Всего в три элемента и каждый можно "содержать" или "не содержать"

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

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

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

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

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

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

; b)

; c) Напомним, что функция называется инъекцией, если таких, что выполнено, что

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

; d) Соответственно, из предыдущего пункта понятно, что нам нужно нарушить, чтобы у нас не было инъекции:

e) Напомним, что функция называется сюръекцией, если такой, что То есть, мы при помощи нашего отображения можем попасть в любой элемент множества

f) Значит, нам нужно нарушить требование сюръективности, то есть "обделить" - не попасть в какой-то элемент

g) Функция является биекцией, если она одновременно инъективна и сюръективна. Подойдёт, например, вот такая картинка:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Давайте нарисуем левую часть равенства:

(жёлтым закрашено , красным закрашено пересечение с множеством - итого нам подходит обведенная зеленым часть)

Теперь нарисуем правую часть равенства

(синим закрашено , красным закрашено пересечение - итого нам подходит обведенная зеленым часть)

Видно, что и там и там зелёным обведена одна и та же часть - значит левая часть равенства равна правой части равенства.

Комментарий. Таким образом при помощи диаграмм Эйлера легко доказывать подобные формулы, связанные со свойствами операций с множествами.

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

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

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

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

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

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

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

c) Расположим все положительные рациональные числа в такую бесконечную таблицу

Она устроена по следующему принципу - в -ой строчке записаны все рациональные числа со знаменателями .

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

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

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

Значит, множество всех положительных дробей - счётно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и в то же время

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

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

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

Но тогда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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