|
Алгебра и логика, 1999, том 38, номер 6, страницы 643–666
(Mi al2485)
|
|
|
|
Сложность булевых алгебр и их ранг Скотта
П. Е. Алаев Институт математики СО РАН, г. Новосибирск
Аннотация:
Рассматриваются вопросы, связанные с рангом Скотта булевых алгебр. Его можно рассматривать как некоторую меру сложности алгебраической системы. Строится и обосновывается конструкция, позволяющая по произвольной счетной булевой алгебре построить другую булеву алгебру малого ранга Скотта, по своей естественной алгебраической сложности эквивалентную первой. Тем самым показывается, в частности, что ранг Скотта не может служить во всех отношениях хорошей мерой сложности на классе булевых алгебр. Рассматривается также вопрос о возможности выделения в булевой алгебре с большим рангом Скотта прямых слагаемых с промежуточными рангами. Строятся примеры счетных булевых алгебр со сколь угодно большим счетным рангом Скотта, в которых прямые слагаемые имеют либо тот же ранг, либо фиксированно малый, слагаемые промежуточных рангов отсутствуют. Эта серия примеров показывает, в частности, что нельзя получить нетривиальные взаимные оценки между рангами Скотта и Фреше на классе счетных булевых алгебр.
Поступило: 20.04.1998
Образец цитирования:
П. Е. Алаев, “Сложность булевых алгебр и их ранг Скотта”, Алгебра и логика, 38:6 (1999), 643–666
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2485 https://www.mathnet.ru/rus/al/v38/i6/p643
|
Статистика просмотров: |
Страница аннотации: | 31 | PDF полного текста: | 15 |
|