Комментарии 8
«Легко доказать известный результат [62] о том, что любую конечную нижнюю полурешетку с наибольшим элементом можно превратить в решетку.»
1) Не задана операция упорядочивания, чтобы говорить о максимальном элементе.
2) Что такое решётка?
Хорошо, давайте я попробую объяснить:
1) Нижняя полурешетка — это множество X с идемпотентной x^x=x, коммутативной x^y=y^x и ассоциативной x^(y^z)=(x^y)^z бинарной операцией ^:XxX->X. Можете думать о ней как об операции пересечения (или даже лучше, о побитовом умножении на битовых строках фиксированной длины). Тогда она задает порядок x<=y <=> x^y=x ("Меньшее, пересечённое с большим, есть меньшее.").
Поэтому наибольший элемент (обычно обозначается 1) таков, что 1^x=x.
2) Решетка — это пара полурешеток на одном множестве, связанных тождествами поглощения (чтобы порядки, задаваемые разными полурешетками, совпадали). Второй порядок задается правилом: "Меньшее, объединенное с большим, есть большее.".
3) Утверждение на странице 16 действительно легкое: чтобы получить объединение (вторую операцию) для элементов a и b, нужно пересечь все элементы x, содержащие каждое из объединяемых элементов (a<=x)&(b<=x). Так как полурешетка конечна, то это пересечение можно вычислить в некотором (на самом деле, безразлично каком) порядке.
Подробности есть на Википедии. К моему сожалению, я не знаю, какую книжку Вам рекомендовать: если читаете по-английски, то найдите Davey&Priestley (там все с картинками). Русские (и переведенные на русский) книги слишком сложны для первоначального обучения. Успехов!
Решетки — фундаментальное понятие в универсальной алгебре (более общее, чем алгебры или кольца). Возникло в трудах Кронекера как средство описания структуры подпространств векторных пространств над полями. Нижние полурешетки возникают как подалгебры некоторой алгебры (подгруппы в группе, подкольца в кольце, подполя в поле) с естественной операцией пересечения. Конструкция пересечения всех надалгебр для 2 подалгебр (описанная в моем предыдущем ответе) задает операцию порождения минимальной подалгебры, порожденной этими двумя слагаемыми. Например, для 2 прямых в многомерном пространстве — это плоскость, натянутая на эти прямые. Как Вы понимаете, простым объединением здесь не обойтись.
Существует класс полных решеток, использованный Д.Скоттом для описания денотационной семантики алгоритмов. Там возникает трансфинитная индукция. Но у меня все решетки конечны, так как я работаю с данными. загруженными в память компьютера.
Последние Ваши вопросы я несовсем понимаю.
1) Есть специальные классы решеток: модулярные и дистрибутивные. Для них Кронекером и Биркгофом найдены конструктивные критерии (немодулярная решетка должна содержать пентагон N5, а недистрибутивная — или пентагон, или диамант M3).
2) Для многих классов решеток есть теоремы представления:
a) для Булевых алгебр — теорема Стоуна, что любая Б.А. изоморфна подалгебре множества всех подмножеств.
b) для дистрибутивных решеток — теорема Биркгофа, что она изоморна множеству идеалов в упорядоченном множестве.
c) для общих решеток — теорема Вилле, что она изоморфна решетки всех кандидатов.
Я не могу гарантировать, что у меня данные порождают какую-то специальную решетку, поэтому использую теорию Вилле (Анализ формальных понятий).
Спасибо за ответы.
Исторически Вы правы, но на современном этапе я смотрю на вопрос о смысле алгебры более широко: есть класс функциональных моделей, задаваемых тождествами и квазитождествами (группа, кольцо, модуль, поле, ассоциативная алгебра, алгебра Ли и т.п.), нужно понять, каким образом построить все эти модели с помощью теоретико-категорных конструкций (прямые и обратные пределы, в частности, декартовы произведения, подмодели и гомоморфизмы) из простейших. Так возникают задача классификации конечных простых групп, структурная теория алгебр Ли и восстановление по алгебре соответствующей группы Ли.
Обратная задача — найти тождества (еще лучше, базис тождеств) для некоторого квазимногообразия функциональных моделей.
Например, системы полиномиальных уравнений после А.Гротендика заменяются на идеалы, для решения обратной задачи — нахождения базиса полиномиального идеала — применяется техника базисов Грёбнера.
Для дистрибутивных решеток можно добавить тождество дистрибутивности, для модулярных — квазитождество модулярности (впрочем, можно написать и некоторое эквивалентное ему тождество). Для дистрибутивных решеток есть теорема представления Биркгофа, как я писал раньше. Но замечательный факт — то, что можно дать конструкцию для любой решетки, причем она снабжает нас идеальным (с точки зрения современных процессоров) способом манипулирования с данными. Это и есть основное открытие проф. Рудольфа Вилле.
Представление объектов для машинного обучения, основанного на теории решеток