Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский

емент другого множества. Античные математики использовали различные таблицы, например астрономические таблицы Птолемея, но эти таблицы понимались как соотношения между конечными дискретными множествами постоянных величин и предназначались только для вычисления числовых значений. В многочисленных трудах греческих математиков, включая и Архимеда, не используется идея функциональной зависимости. Эта идея сформировалась лишь в начале XVII в., когда научились представлять функциональные зависимости с помощью формул. В работах Декарта, Ньютона, Лейбница, Эйлера для записи различных зависимостей стали использовать не громоздкие таблицы, а компактные алгебраические выражения. Эти работы привели к значительным успехам в математике и благодаря им в XVIII в. главным объектом становится не число, а функция.

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

      1.1. Множество и его элементы

      Понятие множества не имеет строгого определения. Оно выведено из понятия совокупности, образованной из конечного числа предметов, которые необходимо рассмотреть как единое целое. Например, можно говорить о множестве различных студентов, которых объединяет то, что они учатся в одной учебной группе, или о множестве граждан одной страны, или о множестве всех точек, лежащих на одной прямой. При этом, чтобы выделить эти предметы, необходимо указать свойства, которыми они обладают, а также указать признаки, по которым можно будет отличить предметы одной совокупности от другой. В 1872 г. Кантор определил множество как «объединение в одно целое объектов, хорошо различимых нашей интуицией». В книге Бурбаки «Теория множеств», изданной в 1939 г., имеется такое определение: «множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств».

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

      Множество однозначно задано, если определены его элементы.

      Для обозначения множеств обычно используются большие латинские буквы A, B, С, X, Y,…, а элементы обозначаются строчными буквами a, b, с, x, y,… Утверждение «x является элементом A», или «x принадлежит A» записывается как x ∈ A.

      Если x не является элементом A, тогда пишут x ∉ A.

      Определение. Два множества А и Вравны, если они состоят из одних и тех же элементов.

      Запись A = B означает, что множество А равно множеству В, а запись A ≠ B означает, что они не равны. Каждый элемент в одном множестве является элементом только один раз, даже если он и повторяется в записи множества многократно. Элементы одного множества принято заключать в круглые скобки. Например, множество букв {ТЕОРИЯ МНОЖЕСТВ} и множество букв {ВИНЕР МОНЖ СМИТ ЯН} равны, поскольку они задают одно и то же множество букв {В Е Ж И М Н О Р С Т Я}, однако если рассматривать в качестве элементов не буквы а слова, тогда это будет два различных множества. Очень часто в приложениях используются числовые множества, для обозначения которых выделены специальные символы:

      N = {1, 2, 3,}, множество натуральных чисел;

      Z = {…, – 2, – 1, 0, 1, 2…}, множество целых чисел;

      Q = {множество рациональных чисел};

      R = {множество вещественных чисел};

      С = {множество комплексных чисел}.

      Чтобы задать множество, можно просто перечислить все его элементы, однако на практике составить такой список обычно довольно сложно. Например, если мы хотим составить список всех, живущих в данном городе, рост которых превышает 2 метра, то теоретически это вполне возможно, но в реальности получение списка для такого множества вызовет непреодолимые проблемы. Список можно применять, когда число элементов сравнительно небольшое. Еще один способ задания множества основан на так называемом принципе абстракции, который формулируется следующим образом:

      для любого множества Х и любого свойства Р имеется множество А, такое что элементы А являются элементами Х и обладают свойством Р.

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

      Пример 1.1

      (а) М = {x: x – нечетное целое число и x > 1}.

      Здесь М является множеством, состоящим из положительных целых чисел, которые больше 1 и нечетные.

      (в) А = {x: x – гласная буква английского алфавита}.

      Здесь,