Алгебраическая Система

Множество с определенными на нем операциями и отношениями. А. с. принадлежат к числу основных математич. структур и имеют глубоко разработанную общую теорию, сформировавшуюся в начале 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. Д. М. Смирнов.