Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mmonline.ru/forum/read/7/26978/
Дата изменения: Mon Apr 11 15:55:42 2016
Дата индексирования: Mon Apr 11 15:55:42 2016
Кодировка: Windows-1251
MMOnline | Форумы | Разное | Алгебраистам

Алгебраистам

Автор темы Finder 
30.01.2003 15:06
Finder
Алгебраистам
Привет! Кто-нибудь работал с множествами, на которых задана ассоциативная, коммутативная и идемпотентная операция? То есть для всех А, В из множества верно, что

A*B = B*A,
A*(B*C) = (A*B)*C,
A*A = A

Обратного элемента нет, никаких других свойств, вообще говоря, тоже.
Подскажите, есть ли теория подобных структур? Как они называются? Где о них можно прочитать?
31.01.2003 01:29
Мои получасовые рассуждения.
Если количество порожадющих, конечно, то поо-моему, так. Для каждого N есть свободная такая полугруппа. Состоящая из 2^N - 1 элементов. Пусть x_1, ... , x_N - его порождающие, тогда есть 0 = x_1*....*x_n. И все элементы есть вида x_i_1*...*x_i_k, для некоторого k. Это должно быть понятно. Основная гипотеза состтоит в том, что любая подобная структура (уже несвободная, но также с конечным числом порождающих M) - изоморфна некоторй свободной с числом порождающих N<=M. надо проверить, конечно, но по-моему, так оно и будет. Для бесконечного числа порождающих сразу навскидку трудно сказать.
Теперь вопрос, где они оказались нужны?
31.01.2003 13:59
Finder
По-моему, неверно
Два других примера

1) Рассмотрим произвольное дерево. Узлы дерева будут элементами множества. Результат операции (назовем ее "объединение") A*B - первый общий "предок" для А и В.

2) N (натуральные числа), или произвольное подмножество N. Операция A*B = max(A,B). Обобщается на N^k и на R^n.

По-моему, все это не изоморфно тому, что ты сказал.

Оказались нужны в базах знаний. Собственно, дальше должна определяться факторизация по инвариантной группе преобразований и на этой основе производиться сжатие информации.
31.01.2003 16:24
Игорь Абрамов
напоминает ...
Вроде это похоже на полурешетку.
Там м.б. еще единица нужна.

Часто есть дополнительная операция, превращающая это все в решетку.

Часто возникают в связи с отношениями порядка.

Про решетки есть книжка Биркгофа.
По-немногу написано много где.
Бурбаки (Теор Мн-в), Биркгоф и Барти (Современная
прикладная алгебра)
31.01.2003 17:31
Он же
Да неверно конечно же...(-)
Да неверно конечно же...(-)
31.01.2003 17:56
Finder
Большое спасибо за информацию
Кстати, единица - это A*1 = A?
Если да, то ее всегда можно добавить, не нарушив этих соотношений, даже если ее там изначально не было.
02.02.2003 12:23
В коммутативном случае да
В коммутативном случае да
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти