§6. Частично упорядоченные множества. Булевы алгебры.

Определение 1: Пусть - отношение порядка на множестве. Элементназываетсянаименьшим (наибольшим) элементом множества , если выполнено условие:

(для наименьшего элемента);

(для наибольшего элемента).

Определение 2: Пусть - отношение порядка на множестве. Элементназываетсяминимальным (максимальным) элементом множества , если выполнено условие:

(для минимального элемента);

(для максимального элемента).

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

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

Пример:

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

2) Множество всех подмножеств некоторого множества обладает единственным минимальным элементом - пустым множеством. Во множестве всех непустых подмножеств некоторого произвольного множества минимальными элементами являются все одноэлементные подмножества. Наконец, если множество бесконечное, то множество всех его бесконечных подмножеств вообще не имеет минимальных элементов.

По определению, элемент частично упорядоченного множества будет наименьшим, если он меньше всех элементов. Ясно, что если наименьший элемент существует, то он единственный. Аналогично определяется наибольший элемент.

Рассмотрим класс частично упорядоченных множеств, удовлетворяющих следующим эквивалентным между собой условиям:

1) Условие минимальности. Всякое непустое подмножество частично упорядоченного множестваобладает хотя бы одним минимальным во множествеэлементом.

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

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

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

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

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

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

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

Определение 4: Решетка называется дистрибутивной, если операции исвязаны дистрибутивными законами, т.е. выполнены соотношения:

,

.

Замечание: Указанные соотношения называются двойственными. Отметим, что в решетке одно из этих соотношений является следствием другого.

Определение 5: Нулем и единицей решетки называются его наименьший и наибольший элементы, если они существуют.

Определение 6: В решетке можно определить следующим образом дополнение: является дополнением для(а- дополнением для), если одновременнои.

Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.

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

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

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

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

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

Аксиома: Если дано множество , то существует функция, сопоставляющая каждому непустому подмножествуопределенный элементэтого подмножества.

Другими словами, функция отмечает по одному элементу в каждом из непустых подмножеств множества.

Вопрос о логических основах этой аксиомы и о законности ее использования относится к числу самых трудных и спорных вопросов обоснования теории множеств. Многие из теорем, доказанные с помощью аксиомы выбора совершенно противоречили наглядности. Поэтому один из видных математиков XX века Бертран Рассел так высказался об этой аксиоме: «Сначала она кажется очевидной; но чем больше вдумываешься в нее, тем более странными кажутся выводы из этой аксиомы; под конец же перестаешь понимать, что же она означает».

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

Теорема Цериело: Всякое множество можно вполне упорядочить.

Теорема Хауздорфа: Всякая цепь частично упорядоченного множества содержится в некоторой максимальной цепи.