RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1999, том 38, номер 6, страницы 643–666 (Mi al2485)

Сложность булевых алгебр и их ранг Скотта

П. Е. Алаев

Институт математики СО РАН, г. Новосибирск

Аннотация: Рассматриваются вопросы, связанные с рангом Скотта булевых алгебр. Его можно рассматривать как некоторую меру сложности алгебраической системы. Строится и обосновывается конструкция, позволяющая по произвольной счетной булевой алгебре построить другую булеву алгебру малого ранга Скотта, по своей естественной алгебраической сложности эквивалентную первой. Тем самым показывается, в частности, что ранг Скотта не может служить во всех отношениях хорошей мерой сложности на классе булевых алгебр. Рассматривается также вопрос о возможности выделения в булевой алгебре с большим рангом Скотта прямых слагаемых с промежуточными рангами. Строятся примеры счетных булевых алгебр со сколь угодно большим счетным рангом Скотта, в которых прямые слагаемые имеют либо тот же ранг, либо фиксированно малый, слагаемые промежуточных рангов отсутствуют. Эта серия примеров показывает, в частности, что нельзя получить нетривиальные взаимные оценки между рангами Скотта и Фреше на классе счетных булевых алгебр.

УДК: 510.6

Поступило: 20.04.1998


 Англоязычная версия: DOI: 10.1007/BF02671732

Реферативные базы данных:


© МИАН, 2024