1Множества, отображения и числа

1.1Множества

1.1.1Примеры множеств

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

Как бы определение 1. Множество — это набор каких-то элементов.

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

Пример 1. Определим множество , которое состоит из трёх элементов — чисел 1, 2 и 3. (Когда какой-то объект впервые определяется, мы часто будем использовать знак вместо обычного равно, чтобы подчеркнуть, что мы таким образом определяем значение того символа, который стоит со стороны двоеточия.) Чтобы задать множество, можно перечислить его элементы, заключив их в фигурные скобки. (Так, конечно, можно задать не все множества, а только конечные, в которых число элементов конечно; чуть позже мы столкнёмся с бесконечными множествами.) Важно отметить, что порядок следования элементов при перечислении не имеет значения: я мог бы написать или и получить ровно то же самое множество . Ещё одно важное замечание: каждый элемент либо входит в множество, либо не входит, нельзя «дважды входить» в множество. Если бы я написал , я бы получил то же множество из трёх элементов, что и выше: единица написана дважды, но входить в множество она может ровно один раз. (Именно так это будет интерпретировать, например, язык программирования Python, умеющий работать с множествами.)

Пример 2. Бывает пустое множество, которое обозначается (в другом стиле выглядит как ). Оно не содержит ни одного элемента: .

Утверждение «элемент входит в множество » кратко записывается таким образом:

То есть, например, справедливо сказать, что для множества , определенного в примере 1, а .

Определение 1. Пусть есть два множества, и . Говорят, что является подмножеством множества (пишут или ), если всякий элемент множества также является и элементом множества .

Например, множество является подмножеством множества из примера 1, а множество — не является.

Замечание 1. Пустое множество является подмножеством любого множества. Само множество также является подмножеством самого себя. Если подмножество некоторого множества не является пустым и не является всем множеством, говорят, что оно является собственным подмножеством.

Пример 3. Множества могут быть сами элементами множеств. Например, можно рассмотреть множество всех подмножеств множества : получится такое множество (обозначим его через ):

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

Вопрос 1. Кстати, а верно ли, что ?
  Верно

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

  Неверно

Верный ответ. Действительно, не является подмножеством множества : оно содержит это множество как элемент. Если вы хотите создать множество, единственным элементом которого является множество , оно будет записываться как .

Как мы видим из примера 3, множества могут содержать в себе другие множества. Тут может возникнуть соблазн рассмотреть «множество всех возможных множеств», однако это приводит к проблемам (подробнее можно посмотреть в статье про парадокс Рассела в Википедии). Таких проблем удаётся избегать, если мы разрешаем рассматривать лишь множества, которые понятным образом строятся из уже определенных ранее множеств. Так мы и будем поступать. Есть более аккуратные способы определения множеств путём ввода некоторой системы аксиом, но для всех практических целей нам будет достаточно «наивного» понятия о множествах, которое обсуждается здесь.

1.1.2Операции над множествами

Нам понадобятся некоторые известные операции с множествами.

Определение 2. Для произвольных множеств и , определим их пересечение, то есть новое множество (обозначается ), которое состоит из всех элементов, которые есть одновременно и в , и в .

Два пересекающихся овала, левый X, правый Y, закрашено их пересечение.
Рис. 1.1: Пересечение множеств.

Определение 3. Для произвольных множеств и , определим их объединение, то есть новое множество (обозначается ), которое состоит из всех элементов, которые есть хотя бы в одном из множеств , или в (или в обоих).

Два пересекающихся овала, левый X, правый Y, равномерно закрашены
оба овала.
Рис. 1.2: Объединение множеств.

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

Два пересекающихся овала, левый X, правый Y, закрашена часть X, не
пересекающаяся с Y.
Рис. 1.3: Разность множеств.

1.2Отображения

Вы наверняка встречались с понятием функции. В математике есть два набора терминов, которые описывают одно и то же — в одних случаях используется слово «функция», в других — «отображение». Слово «отображение» выглядит чуть более универсальным термином. Его можно было бы определить формально, опираясь только на понятие множества, но мы ограничимся неформальным описанием.

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

Пример 4. Рассмотрим отображение из множества в множество (здесь , , и — не переменные, а просто буквы английского алфавита — множества ведь могут содержать не только числа), заданное следующим образом (см. рис 1.4: числу поставили в соответствие букву , числу — букву и числу — букву . Таким образом мы задали отображение из в . Это отображение можно обозначить какой-нибудь буквой, например, буквой . Тогда можно записать: , и . Говорят также, что под действием отображения , число переходит в букву и т.д. Также можно сказать, что буква является образом числа под действием отображения , и наоборот, число является одним из прообразов буквы .

Два овала, в левом отмечены точки 1, 2, 3, он подписан A, в правом точки
a, b, c, d, он подписан L. Есть стрелочки от 1 к b, от 2 к c и от 3 к b.
Рис. 1.4: Пример отображения.
Если задано отображение из множества в множество , пишут:
Можно представить себе отображение как такую картинку, в которой из каждого элемента множества выходит стрелочка, которая ведёт к какому-то элементу множества . При этом стрелочки обязаны выходить из всех элементов , но не обязаны входить во все элементы . Важно также, что из каждого элемента выходит ровно одна стрелочка, то есть каждый элемент множества отображается ровно в один элемент множества .

Определение 5. Отображение называется инъективным (или просто инъекцией), если оно «не склеивает точки», то есть не переводит две разные точки в одну и ту же. Если представлять отображение в виде картинки со стрелочками, это соответствует тому, что нет двух стрелочек, ведущих в одну и ту же точку.

Две картинки. Слева два овала, в левом точки 1, 2, 3. В правом точки
a, b, c, d. Есть стрелочки от 1 к a, от 2 и 3 к b. Подпись: не
инъективное. Справа тоже два овала с такими же точками. Стрелочки из
1 в b, из 2 в с, из 3 в a. Подпись: инъективное.
Рис. 1.5: Не инъективное (слева) и инъективное (справа) отображения.

Определение 6. Отображение называется сюръективным (или просто сюръекцией), если в любую точку множества что-то переходит. Иными словами, у любой точки множества есть хотя бы один прообраз под действием . Если представлять отображение в виде картинки со стрелочками, это соответствует тому, что в каждую точку ведёт хотя бы одна стрелочка.

Две картинки. Слева два овала, в левом точки 1, 2, 3, 4, 5. В правом точки
a, b, c, d. Есть стрелочки от 1 к a, от 2 и 3 к c, от 5 к b. Подпись: не
сюръективное. Справа тоже два овала с такими же точками. Стрелочки из
1 в a, из 2 и 3 в с, из 4 в d, из 5 в b. Подпись: сюръективное.
Рис. 1.6: Не сюръективное (слева) и сюръективное (справа) отображения.

Определение 7. Отображение называется биективным (или биекцией, или взаимно однозначным отображением), если оно одновременно является инъективным и сюръективным. В этом случае не только каждому элементу множества поставлен в соответствие ровно один элемент (как всегда бывает, когда отображение задано), но и наоборот, каждому элементу множества поставлен в соответствие ровно один элемент множества — тот, который в него переходит под действием отображения. Он существует (потому что отображение сюръективно) и единственный (потому что инъективно).

Два овала, в левом точки 1, 2, 3, в правом точки
a, b, c. Есть стрелочки от 1 к b, от 2  к c, от 3 к a.
Рис. 1.7: Биективное отображение.

Замечание 2. Для конечных множеств и существование биективного отображение из в означает, что число элементов в этих двух множествах равно. Вероятно, идея взаимно однозначного соответствия могла предшествовать идее числа: чтобы понять, сколько стульев нужно принести в комнату, чтобы все могли сесть, можно пересчитать гостей, а можно просто установить взаимно однозначное соответствие: этот стул для Кати, этот стул для Коли и т.д.

Определение 8. Множества, между которыми существует взаимно однозначное соответствие, называются равномощными. Очевидно, если два множества равномощны, у них одинаковая мощность. Но что такое эта мощность? Для конечных множеств, мощность определяется просто как число элементов. Для бесконечных всё сложнее, мы поговорим об этом позже.

1.3Числа

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

1.3.1Натуральные числа

Множество натуральных чисел обозначается буквой . Единственный камень преткновения: считать ли ноль натуральным числом. Как правило, натуральные числа «определяются» как «числа, используемые при счёте предметов». В этом случае среди натуральных чисел нет нуля, и это соответствует распространённому в России соглашению. Есть другой подход — сказать, что натуральные числа — это «мощности конечных множеств» (см. определение 8). В этом случае ноль следовало бы считать натуральным, потому что это мощность пустого множества. Такое соглашение принято, например, во Франции. Мы будем использовать соглашение, принятое в России, и не будем считать 0 натуральным числом.

1.3.2Целые числа

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

Каких чисел больше: натуральных или целых? Казалось бы, отрицательных целых чисел «столько же», сколько положительных, то есть натуральные числа входит в число целых дважды, да ещё остаётся ноль. То есть целых должно быть вдвое больше, чем натуральных (и ещё чуть-чуть больше). На самом деле, для бесконечных множеств такая логика не работает: легко придумать взаимно однозначное соответствие между натуральными и целыми числами (например, можно воспользоваться тем, как эти множества записаны выше: отобразить в , в , в , в , в и т.д.), так что с тем же успехом можно сказать, что их «поровну». Аккуратное утверждение состоит в том, что множества целых и натуральных чисел равномощны.

1.3.3Рациональные числа

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

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

Целые числа входят в множество рациональных чисел — это в точности рациональные числа со знаменателем .

Определение 9. Целые числа и называются взаимно простыми, если они не имеют общих натуральных делителей, кроме 1.

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

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

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

1.3.4Вещественные числа

С вещественными (действительными) числами всё сложно. Интуитивно, вещественные числа — это длины отрезков, площади фигур и т.д. Но чтобы аккуратно их ввести в математику, человечество потратило несколько тысяч лет: тот факт, что длины отрезков могут не выражаться рациональными числами, был известен ещё Древним Грекам за несколько сотен лет до нашей эры, но аккуратно вещественные числа были введены в математику только в XIX веке.

В рамках лекций мы будем следовать «школьному» определению: вещественное число — это бесконечная десятичная дробь, то есть бесконечная вправо последовательность цифр, у которой на каком-то месте стоит десятичная запятая (в англоязычной традиции — десятичная точка). Множество вещественных чисел обозначается буквой (от слова real, действительный).

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

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

Определение 10. Вещественные числа, не являющиеся рациональными, называются иррациональными. Специального обозначения для иррациональных чисел нет, обычно просто пишут .

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

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

Теорема 2. Число не является рациональным.

Доказательство. Докажем от противного. Пусть является, то есть существует такая несократимая дробь , которая равна . По определению, это такое число, которое при возведении в квадрат даёт . Значит, Из этого следует, что — четное число. Если бы было нечётным, оно бы представлялось в виде и его квадрат был бы нечётным: . Значит, обязательно чётно. Пусть . Имеем: Из таких же рассуждений получаем, что должно быть чётным. Но по предположению, дробь несократима, и значит её числитель и знаменатель не могут быть одновременно чётными. Противоречие.