- АЛГЕБРАИЧЕСКАЯ СИСТЕМА
- множество с определенными на нем операциями и отношениями. А. с. принадлежат к числу основных математич. структур и имеют глубоко разработанную общую теорию, сформировавшуюся в начале 50-х гг. 20 в. на грани между алгеброй и математич. логикой.
Основные понятия. Алгебраической системой наз. объект
состоящий из непустого множества А, семейства О алгебраических операций о i:
и семейства R отношений
заданных на множестве А. Показатели
рассматриваемых декартовых степеней множества Апредполагаются целыми неотрицательными числами и наз. арностями соответствующих операций и отношений. Множество Аназ. носителем, или основным множеством, А. с.
, а его элементы - элементами этой системы. Мощность
множества Аназ. мощностью, или порядком, А. с.
. Образ
элемента при отображении
наз. значением операции
в точке
Аналогично, если
то говорят, что элементы
из Анаходятся в отношении
и пишут
Операции
и отношения
в отличие от других операций и отношений, к-рые могут быть определены на множестве А, наз. основными, или главными.
Пара семейств
наз. типом А. с.
Две А. с.
однотипны, если
для всех
Основные операции
и основные отношения
однотипных А. с.
имеющих одинаковые индексы в I, J соответственно, наз. одноименными.
А. с.
наз. конечной, если множество
конечно, иконечного типа, если множество
конечно, А. с. А конечного типа записывают в виде А=(A;o1,...,os, r1,...,rt).
А. с. А=(A, O, R) наз. универсальной алгеброй, или алгеброй, если множество R основных отношений ее является пустым, в моделью, или реляционной системой, если множество Оосновных операций ее пустое. Классическими А. с. являются группы, кольца, линейные пространства, линейные алгебры, линейно упорядоченные множества, линейно упорядоченные группы, линейно упорядоченные кольца, решетки и т. д.
Непустое подмножество Восновного множества АА. с. А=бA, O, Rс наз. замкнутым, если для любых элементов
из Взначение
каждой основной операции
также принадлежит множеству В. Рассматривая операции из О и отношения из R на замкнутом подмножестве В, Мы получим А. с.
однотипную данной и наз. подсистемой
Подсистемы алгебр наз. подалгебрами, а подсистемы моделей -подмоделям и. Понятие подалгебры существенно зависит от множества основных операций рассматриваемой алгебры. Напр., группоид
есть алгебра типа (2), т. е. алгебра с одной основной операцией
Группоид
с выделенной единицей еесть алгебра типа
выделенный элемент к-рой обладает по отношению к основной операции о:
. свойством
для всех
Поэтому всякий подгруппоид группоида
с выделенной единицей
содержит
тогда как подгруппоид группоида
не обязан содержать элемент
В отличие от алгебр, любое непустое подмножество модели может рассматриваться как подмодель.
изоморфна однотипной
если существует такое взаимно однозначное отображение
множества
что
для всех
из Аи для всех
Отображение
с этими свойствами наз. изоморфизмом. Под классом алгебраич. систем понимается в дальнейшем только абстрактный класс, т. е. такой класс однотипных А. с., к-рый содержит с каждой системой
и все изоморфные ей системы. При рассмотрении того или иного класса
А. с. все системы из этого класса записывают обычно в определенной сигнатуре следующим образом. Пусть класс
имеет тип
Каждому
сопоставляют нек-рый символ
наз. функциональным, а каждому
- символ
наз. предикатным. Если А. с. А принадлежит классу
- основная операция в ней, то элемент
из Азаписывают в виде
Аналогично, если
- основное отношение в Аи элемент
то пишут
(истинно) или просто
Если же
то пишут
(ложно) или
Пусть
- отображение объединения
в множество натуральных чисел
определяемое формулами:
Объект
наз. сигнатурой класса
Конечную сигнатуру записывают в виде строки
или короче
записанная в сигнатуре
и обозначается
Условия (1), (2) изоморфизма однотипных систем
упрощаются, если эти системы рассматривать в одной сигнатуре
Так, если сигнатурными символами будут
то (1), (2) примут вид
Гомоморфизмом
-системы
в
-систему
наз. всякое отображение
удовлетворяющее условию (3) и условию
для всех
и для всех
из А. Гомоморфизм
наз. сильным, если для любых элементов
из
и для любого предикатного символа
соотношение Pj(b1,...,bmj)=И влечет существование в Атаких прообразов
элементов
для к-рых
Понятия гомоморфизма и сильного гомоморфизма алгебр совпадают. Для моделей существуют гомоморфизмы, к-рые не являются сильными, и взаимно однозначные гомоморфизмы, к-рые не являются изоморфизмами. При гомоморфизме
образами в
подсистем из
и непустыми полными прообразами в
подсистем из
являются подсистемы.
Эквивалентность
паз. конгруэнцией
если
для всех
из Аи для всех
Для каждого гомоморфизма
бинарное отношение
истинное тогда и только тогда, когда
является конгруэнцией в
, к-рая наз. ядерной. Для произвольной конгруэнции
системы
и для каждого элемента
множество
наз. смежным классом
по
конгруэнции
Полагая для каждых
и
тогда и только тогда, когда существуют такие элементы в
, что
и
мы получим А. с.
однотипную данной
и наз. факторсистемой А. с.
по конгруэнции
. Для каждой конгруэнции
А. с.
канонич. отображение
является гомоморфизмом А. с.
на факторсистему
для которого данная конгруэнция
ядерная. Если
есть гомоморфизм А. с.
на А. с.
и
- ядерная конгруэнция для
то отображение
является гомоморфизмом факторсистемы
на
Если при этом гомоморфизм
сильный, то
есть изоморфизм.
Декартовым произведением
-систем
наз.
-система
в к-рой Dесть декартово произведение основных множеств
а основные операции и основные отношения на Dзадаются условиями:
есть элемент
с координатами
тогда и только тогда, когда
для всех
Язык 1-й ступени. Основным формальным языком теории А. с. является язык 1-й ступени L, к-рый строится следующим образом. Алфавит языка Lв заданной сигнатуре
состоит из предметных переменных
функциональных символов
предикатных символов
символов логич. связок:
кванторов:
- "для каждого элемента
",
- "существует такой элемент
"
и вспомогательных символов: скобок и запятых. Для выражения свойств (1-Й ступени) Q-систем употребляются конечные последовательности алфавитных символов, или слова, составленные по определенным правилам и наз. термами и формулами. Индуктивно полагают, что каждое слово вида
при
есть терм; если
- термы и
то
- также терм.
Если
есть
-система и
- терм сигнатуры
содержащий предметные переменные
то, заменяя
к.-н. элементами
из Аи выполняя над последними операции в
соответствующие входящим в терм символам из
получают элемент
из А , называемый значением терма
при
Если
- гомоморфизм
-системы
в
-систему
, то
Понятие формулы сигнатуры Q, свободных и связанных предметных переменных в ней определяется также индуктивно:
1) Если
- какой-нибудь предикатный символ из
или знак равенства
или 2 соответственно, а
- произвольные термы сигнатуры
то слово
есть формула, в к-рой все предметные переменные свободны.
2) Если
- формула, то
- также формула. Свободные (связанные) предметные переменные в формуле
те и только те, к-рые являются свободными (связанными) в
3) Если
- формулы и предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то слова
- также формулы.
Предметные переменные, свободные (связанные) хотя бы в одной из формул
наз. свободными (связанными) и в формулах (6).
4) Если предметное переменное
входил свободно в формулу
то слова
снова являются формулами, в к-рых переменное
связанное, а все остальные предметные переменные, входящие в формулу
свободно или связанно, остаются такими же и в формулах
Если заданы
-система
и формула
сигнатуры
, то придавая всем свободным предметным переменным
какие-нибудь значения
из
и интерпретируя функциональные и предикатные символы, входящие в
как соответствующие основные операции и основные отношения в
мы получим конкретное высказывание, к-рое будет истинным или ложным. В соответствии с этим формуле
приписывают значение
при
обозначаемое
Если
- изоморфное отображение
-системы
на
-систему
, то
для всех
из А.
Формула
наз. замкнутой, если она не содержит свободных предметных переменных. Для любой замкнутой формулы
сигнатуры
и произвольной
-системы
можно говорить об истинности или ложности
Совокупность
замкнутых формул данной сигнатуры И наз. выполнимой, или совместной, если существует Q-система, в к-рой истинны все формулы из
Теорема компактности или локальная теорема Гёделя - Мальцева. Если выполнима каждая конечная часть бесконечной совокупности
замкнутых формул какой-то сигнатуры
то выполнима и вся совокупность
Аксиоматизируемые классы. Пусть S - некоторая совокупность замкнутых формул сигнатуры
Класс всех
-систем, в к-рых истинны все формулы из S, будет обозначаться KS. Совокупность
всех замкнутых формул сигнатуры
истинных во всех
системах из заданного класса
наз. элементарной теорией класса
В частности, если
- класс
-систем, изоморфных данной
-системе
, то
наз. элементарной теорией
-системы
и обозначается просто
Класс
-систем наз. аксиоматизируемы м, если
Класс
-систем аксиоматизируем тогда и только тогда, когда существует такая совокупность
замкнутых формул сигнатуры
что
Наряду с общим понятием аксиоматизируемости рассматривают аксиоматизируемость при помощи формул 1-й ступени специального вида. Наиболее важными в алгебре специальными формулами заданной сигнатуры
являются:
Тождества - формулы вида
где Р - к.-л. предикатный символ из Q или знак равенства
- термы сигнатуры
от
Квазитождества - формулы вида
где
- нек-рые предикатные символы из или знаки равенства, а
- термы сигнатуры
Универсальные формулы- формулы вида
где
- формула сигнатуры
не содержащая кванторов.
Если задано множество Sтождеств (квазитождеств или универсальных формул) сигнатуры
, то класс
наз. многообразием (квазимногообразием или универсальным классом)
-систем.
Теорема Биркгофа. Непустой класс
-систем является многообразием тогда и только тогда, когда он замкнут относительно подсистем, декартовых произведений и гомоморфных образов.
Если
- некоторая
-система, то, заменяя каждый функциональный символ
предикатным символом
и полагая для элементов
мы получим модель
для которой =
Подмодели модели
наз.
подмоделями
-системы
Для любых непустых конечных подмножеств
наз. конечным обеднением конечной подмодели
-системы
.
-система
наз. локально вложимой в класс
-систем, если для каждого конечного обеднения
любой конечной подмодели
-системы
существует в классе
такая
-система
(зависящая от выбранного конечного обеднения
), что модель
изоморфна модели
для подходящего подмножества
Подкласс
класса
-систем наз. универсальным (или универсально аксиоматизируемым) в
если существует такая совокупность
универсальных формул сигнатуры
что
Теорема Тарского - Лося. Подкласс
класса
-систем универсален в
тогда и только тогда, когда
содержит все системы из
локально вложимые в
Фильтрованные произведения. Пусть
- декартово произведение
-систем
и
- некоторый фильтр над
Отношение
есть эквивалентность на основном множестве
системы
Для каждого элемента
пусть
есть смежный класс по этой эквивалентности 1 и
=
Полагая
можно получить
-систему
которая наз. фильтрованным по фильтру Ф произведением
-систем
-системы
наз. сомножителями этого произведения. Если
- ультрафильтр над Л, то фильтрованное произведение
наз. ультрапроизведением
-систем
Теорема об ультрапроизведениях. Если
-ультрапроизведение
-систем
и
- произвольная формула сигнатуры
, в к-рой свободными предметными переменными являются
то для любых элементов
В частности, замкнутая формуласигнатуры
истинна в ультрапроизведении
-систем
тогда и только тогда, когда множество номеров сомножителей, в к-рых формула
истинна, принадлежит ультрафильтру Ф. Поэтому всякий аксиоматизируемый класс
-систем замкнут относительно ультрапроиз-ведеиий.
Класс
-систем универсально аксиоматизируем тогда и только тогда, когда он замкнут относительно подсистем и ультрапроизведений.
-система
наз. единичной, если ее основное множество состоит из одного элемента, скажем е, и
для всех
.
Теорема Мальцева. Класс"
-систем является квазимногообразием тогда и только тогда, когда он содержит единичную Q-систему и замкнут относительно подсистем и фильтрованных (по произвольному фильтру) произведений.
Полнота и категоричность. Непустой класс
-систем наз. категоричным, если все
-системы из
изоморфны между собой. Всякий категоричный аксиоматизируемый класс
-систем состоит из одной (с точностью до изоморфизма) конечной
-системы.
Класс
-систем наз. категоричным в мощности
, если он содержит
-систему мощности
и все
-системы из
, имеющие мощность т, изоморфны между собой. Напр., класс алгебраически замкнутых полей фиксированной характеристики категоричен в любой несчетной бесконечной мощности. Непустой класс
-систем наз. полным, если для любых
-систем
из
имеет место равенство
Теорема Воота. Если аксиоматизируемый класс
-систем категоричен в нек-рой мощности
и все
-системы из
бесконечны, то
- полный класс.
В частности, класс всех алгебраически замкнутых полей фиксированной характеристики является полным.
См. также Алгебраической системы автоморфизм, Алгебраических систем квазимногообразие, Алгебраических систем класс, Алгебраических систем многообразие.
Лит.:Г1] Мальцев А. И., Алгебраические системы, М., 1970; [2] Кон П., Универсальная алгебра, пер. с англ., М., 1968; [3] GrStzer G., Uneversal algebra, Princeton, 1968; [4] Ве11 J. L., S1оmsоn A. B., Models and ultra-products, Amst.-L., 1969; [5] Сhang C.C., Keisler H. J., Model theory, Amst. - N.Y., 1973. Д. М. Смирнов.
Математическая энциклопедия. — М.: Советская энциклопедия. И. М. Виноградов. 1977—1985.