24

Глава 1. Теоретико–множественное введение

1.1. Множества: основные понятия

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

Принадлежность элемента a множеству A (объект a есть элемент множества A) обозначается a A; непринадлежность элемента a множеству A обозначается a A. Символ “” называется знаком принадлежности.

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

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

R, N, Z – множества действительных, натуральных и целых чисел;

[a,b], (a,b) – множества действительных чисел, принадлежащих соответственно отрезку и интервалу числовой оси.

Числовое множество Х называется ограниченным, если существуют действительные числа a,b такие, что для любого (каждого, всякого) элемента x из множества Х будет выполняться a ≤ x ≤ b. Коротко с помощью логической символики сформулированное условие можно записать следующим образом

 a,b  R  x X: a ≤ x ≤ b,

где символ  - квантор существования, а символ  - квантор всеобщности. Числа a,b называются нижней и верхней гранями множества X, а наибольшая из всех нижних граней (наименьшая из всех верхних граней) - точной нижней (точной верхней) гранью множества и обозначается inf X ( sup X ).

Если точные грани принадлежат множеству Х, т.е. являются его элементами, то числа

m = inf X, M = sup X

есть не что иное, как минимальный (наименьший) и максимальный (наибольший) элементы рассматриваемого множества. Эти элементы обычно обозначают min X и max X. Так, например, для множеств

X = [a,b], Y = (a,b) , H = (a,b]

будет справедливо:

min X = a, max X = b, inf X = a, sup X = b;

min Y и max Y – не существуют, inf Y = a, sup Y = b;

min H – не существует, max H = b, inf H = a, sup H = b.

Замечание. Если множество Х не ограничено сверху (снизу), то для обозначения его точной верхней (точной нижней) грани используют символ “ + ∞ ” ( “- ∞ ” ), читаемый “плюс (минус) бесконечность“, т.е. записывают sup X = + ∞ ( inf X = - ∞ ). В частности, для указанных выше множеств с общепринятыми обозначениями R , Z будет иметь место

sup R = sup Z = + ∞, inf R = inf Z = - ∞ .

Подмножество: множество A называется подмножеством множества B, если любой элемент множества A принадлежит множеству B, т.е.  a A : a B . При этом говорят, что множество В содержит (покрывает) А и пишут А  В. Символ  называется знаком включения (знаком нестрогого включения). В соответствии с определением всякое множество является своим подмножеством. Так, например, для множеств

N, Z, R, [0,1], (-1,2], [-1,3), [a,b], (a,b)

будут справедливы отношения

N  Z, Z  R, [0,1]  (-1,2]  [-1,3), [a,b]  R, (a,b)  [a,b]  [a,b].

Равные множества: два множества A и B называются равными (что соответствует записи A = B), если A и B содержат одни и те же элементы, т.е. (с учетом определения подмножества) удовлетворяют условию:  В и В  А. Из определения, в частности, вытекает – множество определяется только составом входящих в него элементов (порядок элементов безразличен). Так, если множество A = {прямая, кривая, эллипс, парабола, плоскость, поверхность, гиперболоид}, то множество В = { прямая, плоскость, кривая, поверхность, эллипс, парабола, гиперболоид }, отличающееся от А только порядком элементов, будет совпадать с А, т.е. В = А .

Правильная часть множества: множество A называется правильной частью (собственным подмножеством) множества В, если А  В и  b B : b A . При этом пишут А  В (символ “” называется знаком строгого включения). В качестве примера собственного подмножества множества Z целых чисел можно назвать множество целых чисел, делящихся без остатка на некоторое целое натуральное число n > 1. В то же время множество, полученное при n = 1, будет, очевидно, равно Z, т.е. в соответствии с определениями оно будет просто подмножеством множества Z, но не его правильной частью.

Разбиение множества: система множеств S = {A,B,C,…,G} называется разбиением множества U, а сами множества системы S - классами разбиения, если выполняются два условия:

1) любое множество системы S является собственным подмножеством множества U, т.е.  M S : M  U;

2) любой элемент множества U принадлежит одному (и только одному) из множеств системы S, т.е.

 u U ! M S : u M (! – знак единственности).

С разбиениями множеств (в том числе с построением разбиений изучаемого множества) приходится сталкиваться постоянно в повседневной деятельности. Среди примеров такого рода разбиений можно назвать:

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

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

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

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

1. Множество определяется перечислением (списком) всех своих элементов, заключенным в фигурные скобки. Например, множество десятичных цифр можно записать в виде A = { 0,1,2,3,4,5,6,7,8,9 }, а множество решений кубического уравнения - в виде В = { 1,2,4 }.

2. Множество определяется посредством описания свойств его элементов. В этом случае используется обозначение А = { x X |  (x) }, где запись  (x) означает – элемент x обладает свойством  . Например, множество С = [ a,b ] точек отрезка числовой оси можно записать в виде С = { x \ x [a,b] }, а указанное выше множество В решений кубического уравнения - в виде В = { x R | }.

3. Множество определяется с помощью порождающей его функции.

В данном случае используется обозначение А = { f ( x ) | x X }. Элементами множества А служат значения порождающей функции f ( x ) с областью определения X. Так, например, множество квадратов натуральных чисел можно записать в виде М = { x | x N }, а множество точек синусоиды – в виде Y = { sin x | x R }.

Ясно, что довольно часто одно и то же множество может быть описано разными способами. Это подтверждается как вышеизложенным, так и примером 1.1.

Замечание. В теории рядов формула общего члена как функция натурального аргумента фактически выполняет роль порождающей функции для бесконечной последовательности членов (слагаемых) ряда. При этом элементы последовательности, соответствующие разным значениям натурального аргумента, могут совпадать. Например, бесконечная числовая последовательность {Xn} c формулой общего члена (порождающей функцией) Xn = 1 - cos nπ ( n є N ) может быть посредством перечисления элементов записана следующим образом

{ Xn } = { 2,0,2,0,2,0, … }. В отличие от последовательности, множество не может содержать одинаковые элементы (объекты, предметы). Таким образом, задание (описание) последовательности и множества, составленного из элементов этой последовательности, - в общем случае две разные задачи. В частности, множество Х, объектами которого служат элементы указанной выше последовательности { Xn }, можно (после исключения повторяющихся объектов) записать в виде X = { 0,2 }.