3. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ

3.1. Множества и подмножества

Любое понятие дискретной математики можно определить с помощью понятия множества.

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

Объекты, которые образуют множество, называют элементами множества и обозначают, как правило, малыми буквами латинского алфавита. Принадлежность элемента а множеству М обозначается а М («а принадлежит М»); непринадлежность а множеству М обозначается а M.

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

Пример 3.1.

1. M₁ – множество всех натуральных чисел: 1, 2, 3... В дальнейшем будем обозначать его N, элементы N – натуральные числа. N = {1, 2, 3, …}.Часто 0 также считают натуральным числом; множество, полученное добавлением 0 к N, будем обозначать N₀= {0, 1, 2, 3,…}.

2. M₂ – множество всех натуральных чисел, не превосходящих 100.

3. М₃ – множество всех решений уравнения sin x = 1; элементы M₃ – числа, являющиеся решениями этого уравнения.

4. M₄ – множество всех чисел вида p/2±kp, где k N₀ .

5. M₅ – множество всех действительных чисел (в дальнейшем R).

Множество А называется подмножеством множества В (обозначение
A Í B; знак Í называется знаком включения), если всякий элемент А является элементом В. При этом говорят, что В содержит или покрывает A. Множества А и В равны, если их элементы совпадают, иначе говоря, если А Í В и
B Í A. Второй вариант определения равенства множеств указывает и на наиболее типичный метод доказательства того, что данные множества равны, заключающийся в доказательстве сначала утверждения A Í B («в одну сторону»), а затем B Í A («в другую сторону»). Форму утверждения о равенстве двух множеств имеют многие математические теоремы. Пример – тригонометрическая теорема M₃ = M₄, состоящая из двух утверждений: а) всякое решение уравнения sin x = 1 имеет вид p/2±kp (M₃ Í M₄ ); б) всякое число вида p/2±kp является решением уравнения sin x = 1 (M₄ Í M₃ ).

Если A Í B и A ¹ В, то A часто называется собственным, строгим или истинным подмножеством В (обозначение а Ì в; знак Ì называется знаком строгого включения).

Множества могут быть конечными (т. е. состоящими из конечного числа элементов) и бесконечными. Число элементов в конечном множестве М называется мощностью М и часто обозначается |М|. Множество мощности 0,
т. е. не содержащее элементов, называется пустым и обозначается Æ. Принято считать, что пустое множество является подмножеством любого множества. Пустое множество введено в математике для удобства и единообразия языка. Например, если исследуется множество объектов, обладающих каким-либо свойством, и впоследствии выясняется, что таких объектов не существует, то гораздо удобнее сказать, что исследуемое множество пусто, чем объявлять его несуществующим. Утверждение «множество М непусто» является более компактной формулировкой равносильного ему утверждения «существуют элементы, принадлежащие М».

3.2. Способы задания множеств

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

Списком можно задавать лишь конечные множества. Задание типа
N = 1, 2, З... – это не список, а условное обозначение, допустимое лишь тогда, когда оно заведомо не вызывает разночтений. Список обычно заключается в фигурные скобки. Например, А={а, Ь, d, h} означает, что множество A состоит из четырех элементов а, Ь, d и h.

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

Примером служит описание множества М₄, где исходными объектами для построения являются натуральные числа, а порождающей процедурой – вычисление, описанное формулой p/2±kp. Другой пример – множество M₂n = 1, 2, 4, 8, 16..., порождающая процедура для которого определяется следующими двумя правилами: 1) 1 Ï M₂n; 2) если m Ï M₂n, то 2m Ï M₂n. Правила, описанные таким образом, называются индуктивными или рекурсивными. Третий пример – множество М_p , заданное следующим образом. Пусть имеется процедура вычисления цифр разложения числа p в бесконечную десятичную дробь: p = 3,1415926536... По мере вычисления будем образовывать из последовательно стоящих цифр трехразрядные числа: 314, 159, 265 и т.д. Множество всех таких чисел обозначим M_p .

Задание множества описанием свойств его элементов, пожалуй, наиболее обычно: так заданы множества М₂, M₃, M₅; да и задание M₄ можно интерпретировать как описание свойства его элементов, заключающегося в возможности представить их в виде p/2±kp. Множество М₂n можно задать фразой «М₂n – множество всех целых чисел, являющихся степенями числа два». В случае, когда свойство элементов М может быть описано коротким выражением Р(х), означающим «х обладает свойством Р», М задается при помощи обозначения М={х|Р(х)}, которое читается так: «M – это множество х, обладающих свойством Р». Например, M₂n={x|x=2^k, где kÏN_o}, M₄={x|x=p/2±kp, где kÏN_o}. К описанию свойств естественно предъявить требование точности и недвусмысленности. Например, множество всех хороших видеофильмов 1999 г. разные люди зададут разными списками (быть может, пустыми); сами критерии, по которым производится отбор, при этом будут различны. Такое множество нельзя считать строго заданным. Надежным способом точно описать свойство элементов данного множества служит задание распознающей (или, как говорят в математике, разрешающей) процедуры, которая для любого объекта устанавливает, обладает он данным свойством и, следовательно, является элементом данного множества или нет. Например, для M₂n, т. е. для свойства «быть степенью двойки», разрешающей процедурой может служить любой метод разложения целых чисел на простые множители.

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

Множество также часто задают графически с помощью диаграмм Эйлера. Например, задание множества {{a,b, с}, {b, d, е}} в пространстве A = {а, b, с, d, е} приведено на рис.3.1, где замкнутая линия, называемая кругом Эйлера, соответствует одному из рассматриваемых множеств и ограничивает его элементы, при этом рамка, в верхнем правом углу которой стоит A, ограничивает элементы пространства.

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

В чем трудности вопроса о задании множеств? Одна из основных трудностей заключается в том, что даже из множеств, точность описания которых не вызывает сомнений, с помощью, казалось бы, вполне законных средств можно сконструировать описания множеств, которые приводят к противоречиям – «парадоксам теории множеств», хорошо известным в истории математики.

Примером является «множество всех множеств». По смыслу своего описания оно должно содержать все мыслимые множества. Однако оно само содержится в множестве своих подмножеств в качестве элемента. Более точный комментарий этого примера должен опираться на понятие мощности бесконечного множества.

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