Универсальная алгебра (иногда называемая общей алгеброй ) — это область математики , которая изучает сами алгебраические структуры , а не примеры («модели») алгебраических структур. Например, вместо того, чтобы рассматривать конкретные группы как объект изучения, в универсальной алгебре рассматривается класс групп как объект изучения.
В универсальной алгебре алгебра (или алгебраическая структура ) — это множество A вместе с набором операций над A.
n - арная операция над A — это функция , которая берет n элементов из A и возвращает один элемент из A. Таким образом, 0-арная операция (или нуль -арная операция ) может быть представлена просто как элемент A или константа , часто обозначаемая буквой, например , a . 1-арная операция (или унарная операция ) — это просто функция из A в A , часто обозначаемая символом, помещенным перед ее аргументом, например, ~ x . 2-арная операция (или бинарная операция ) часто обозначается символом, помещенным между ее аргументами (также называемым инфиксной записью ), например, x ∗ y . Операции более высокой или неопределенной арности обычно обозначаются символами функций, при этом аргументы заключаются в скобки и разделяются запятыми, например, f ( x , y , z ) или f ( x 1 ,..., x n ). Таким образом, один из способов говорить об алгебре — это ссылаться на нее как на алгебру определенного типа , где — упорядоченная последовательность натуральных чисел, представляющая арность операций алгебры. Однако некоторые исследователи также допускают бесконечные операции, например, где J — бесконечное множество индексов , что является операцией в алгебраической теории полных решеток .
После того, как операции были определены, природа алгебры далее определяется аксиомами , которые в универсальной алгебре часто принимают форму тождеств или эквациональных законов. Примером является ассоциативная аксиома для бинарной операции, которая задается уравнением x ∗ ( y ∗ z ) = ( x ∗ y ) ∗ z . Аксиома должна выполняться для всех элементов x , y и z множества A .
Совокупность алгебраических структур, определяемых тождествами, называется многообразием или эквациональным классом .
Ограничение исследования разновидностями исключает:
Изучение эквациональных классов можно рассматривать как особую ветвь теории моделей , обычно имеющую дело со структурами, имеющими только операции (т. е. тип может иметь символы для функций, но не для отношений, отличных от равенства), и в которой язык, используемый для описания этих структур, использует только уравнения.
Не все алгебраические структуры в более широком смысле попадают в эту область. Например, упорядоченные группы включают отношение упорядочения, поэтому не попадают в эту область.
Класс полей не является эквациональным классом, поскольку не существует типа (или «сигнатуры»), в котором все законы поля можно было бы записать в виде уравнений (обратные элементы определены для всех ненулевых элементов в поле, поэтому инверсия не может быть добавлена к типу).
Одним из преимуществ этого ограничения является то, что структуры, изучаемые в универсальной алгебре, могут быть определены в любой категории , которая имеет конечные произведения . Например, топологическая группа — это просто группа в категории топологических пространств .
Большинство обычных алгебраических систем математики являются примерами многообразий, но не всегда очевидным образом, поскольку обычные определения часто включают в себя квантификацию или неравенства.
В качестве примера рассмотрим определение группы . Обычно группа определяется в терминах одной бинарной операции ∗, подчиняющейся аксиомам:
(Некоторые авторы также используют аксиому « замыкания », согласно которой x ∗ y принадлежит A всякий раз, когда x и y принадлежат ему, но здесь это уже подразумевается, поскольку ∗ называется бинарной операцией.)
Это определение группы не сразу соответствует точке зрения универсальной алгебры, поскольку аксиомы элемента тождества и инверсии не сформулированы исключительно в терминах эквациональных законов, которые выполняются универсально «для всех ...» элементов, но также включают в себя экзистенциальный квантификатор «существует ...». Аксиомы группы можно сформулировать как универсально квантифицированные уравнения, указав, в дополнение к бинарной операции ∗, нулевую операцию e и унарную операцию ~, причем ~ x обычно записывается как x −1 . Аксиомы становятся:
Подводя итог, обычное определение звучит так:
в то время как определение универсальной алгебры имеет вид:
Ключевым моментом является то, что дополнительные операции не добавляют информацию, а однозначно следуют из обычного определения группы. Хотя обычное определение не указывает однозначно элемент идентичности e , простое упражнение показывает, что он уникален, как и обратный элемент каждого элемента.
Точка зрения универсальной алгебры хорошо адаптирована к теории категорий. Например, при определении группового объекта в теории категорий, где рассматриваемый объект может не быть множеством, необходимо использовать эквациональные законы (которые имеют смысл в общих категориях), а не квантифицированные законы (которые относятся к отдельным элементам). Кроме того, обратная и тождественная функции определяются как морфизмы в категории. Например, в топологической группе обратная функция должна не только существовать поэлементно, но и давать непрерывное отображение (морфизм). Некоторые авторы также требуют, чтобы тождественное отображение было замкнутым включением ( корасслоением ).
Большинство алгебраических структур являются примерами универсальных алгебр.
Примерами реляционных алгебр являются полурешетки , решетки и булевы алгебры .
Предположим, что тип, , зафиксирован. Тогда в универсальной алгебре есть три основные конструкции: гомоморфный образ, подалгебра и произведение.
Гомоморфизм между двумя алгебрами A и B — это функция h : A → B из множества A в множество B такая, что для каждой операции f A из A и соответствующей f B из B (арности, скажем, n ) h ( f A ( x 1 , ..., x n )) = f B ( h ( x 1 ), ..., h ( x n )). (Иногда индексы у f опускаются, когда из контекста ясно, из какой алгебры функция.) Например, если e — константа (нулевая операция), то h ( e A ) = e B . Если ~ — унарная операция, то h (~ x ) = ~ h ( x ). Если ∗ — бинарная операция, то h ( x ∗ y ) = h ( x ) ∗ h ( y ). И так далее. Несколько вещей, которые можно сделать с гомоморфизмами, а также определения некоторых специальных видов гомоморфизмов, перечислены в разделе Гомоморфизм . В частности, мы можем взять гомоморфный образ алгебры h ( A ).
Подалгебра A — это подмножество A , замкнутое относительно всех операций A. Произведение некоторого множества алгебраических структур — это декартово произведение множеств с операциями, определенными покоординатно.
В дополнение к своему объединяющему подходу универсальная алгебра также дает глубокие теоремы и важные примеры и контрпримеры. Она предоставляет полезную основу для тех, кто намерен начать изучение новых классов алгебр. Она может позволить использовать методы, изобретенные для некоторых конкретных классов алгебр, для других классов алгебр, переформулировав методы в терминах универсальной алгебры (если это возможно), а затем интерпретируя их применительно к другим классам. Она также предоставила концептуальное разъяснение; как выразился Дж. Д. Х. Смит, «То, что выглядит запутанным и сложным в конкретной структуре, может оказаться простым и очевидным в надлежащей общей».
В частности, универсальная алгебра может быть применена к изучению моноидов , колец и решеток . До появления универсальной алгебры многие теоремы (в частности, теоремы об изоморфизме ) были доказаны по отдельности во всех этих классах, но с помощью универсальной алгебры они могут быть доказаны раз и навсегда для любого вида алгебраической системы.
Статья Хиггинса 1956 года, на которую ссылаются ниже, была хорошо продолжена в плане ее структуры для ряда конкретных алгебраических систем, в то время как его статья 1963 года примечательна обсуждением алгебр с операциями, которые определены лишь частично, типичными примерами которых являются категории и группоиды. Это приводит к предмету многомерной алгебры , которую можно определить как изучение алгебраических теорий с частичными операциями, области определения которых определены при геометрических условиях. Известными примерами этого являются различные формы многомерных категорий и группоидов.
Универсальная алгебра предоставляет естественный язык для задачи удовлетворения ограничений (CSP) . CSP относится к важному классу вычислительных задач, где, имея реляционную алгебру A и экзистенциальное предложение над этой алгеброй, вопрос состоит в том, может ли быть удовлетворено в A. Алгебра A часто фиксирована, так что CSP A относится к задаче, экземпляром которой является только экзистенциальное предложение .
Доказано, что каждая вычислительная задача может быть сформулирована как CSP A для некоторой алгебры A. [1 ]
Например, задачу n- раскраски можно сформулировать как ЗСЗ алгебры ({0, 1, ..., n −1}, ≠) , т. е. алгебры с n элементами и одним соотношением — неравенством.
Гипотеза дихотомии (доказанная в апреле 2017 года) утверждает, что если A — конечная алгебра, то CSP A является либо P , либо NP-полной . [2]
Универсальная алгебра также изучалась с использованием методов теории категорий . В этом подходе вместо написания списка операций и уравнений, которым подчиняются эти операции, можно описать алгебраическую структуру, используя категории специального вида, известные как теории Ловера или, в более общем смысле, алгебраические теории . В качестве альтернативы, можно описать алгебраические структуры, используя монады . Эти два подхода тесно связаны, и каждый из них имеет свои преимущества. [3] В частности, каждая теория Ловера дает монаду в категории множеств, в то время как любая «финитарная» монада в категории множеств возникает из теории Ловера. Однако монада описывает алгебраические структуры в пределах одной конкретной категории (например, категории множеств), в то время как алгебраические теории описывают структуру в пределах любого большого класса категорий (а именно тех, которые имеют конечные произведения ).
Более недавнее развитие теории категорий — теория операд — операда — это набор операций, аналогичный универсальной алгебре, но ограниченный тем, что уравнения допускаются только между выражениями с переменными, без дублирования или пропуска переменных. Таким образом, кольца можно описать как так называемые «алгебры» некоторых операд, но не групп, поскольку закон gg −1 = 1 дублирует переменную g в левой части и опускает ее в правой части. Сначала это может показаться неудобным ограничением, но выигрыш в том, что операды имеют определенные преимущества: например, можно гибридизировать концепции кольца и векторного пространства, чтобы получить концепцию ассоциативной алгебры , но нельзя образовать подобный гибрид концепций группы и векторного пространства.
Другим развитием является частичная алгебра , где операторы могут быть частичными функциями . Некоторые частичные функции также могут обрабатываться обобщением теорий Ловера, известным как «по существу алгебраические теории». [4]
Другим обобщением универсальной алгебры является теория моделей , которую иногда называют «универсальной алгеброй + логикой». [5]
В книге Альфреда Норта Уайтхеда «Трактат об универсальной алгебре», опубликованной в 1898 году, термин «универсальная алгебра» имел по сути то же значение, что и сегодня. Уайтхед приписывает Уильяму Роуэну Гамильтону и Августу де Моргану основоположников предмета, а Джеймсу Джозефу Сильвестру — создание самого термина. [6] : v
В то время такие структуры, как алгебры Ли и гиперболические кватернионы, привлекли внимание к необходимости расширения алгебраических структур за пределы ассоциативно-мультипликативного класса. В обзоре Александр Макфарлейн писал: «Основная идея работы — не объединение нескольких методов и не обобщение обычной алгебры с целью их включения, а скорее сравнительное изучение их нескольких структур». [7] В то время алгебра логики Джорджа Буля составляла сильный контрапункт обычной числовой алгебре, поэтому термин «универсальный» служил для успокоения напряженных чувств.
Ранние работы Уайтхеда были направлены на объединение кватернионов (благодаря Гамильтону), Ausdehnungslehre Грассмана и алгебры логики Буля. Уайтхед писал в своей книге:
Однако Уайтхед не имел результатов общего характера. Работа по этой теме была минимальной до начала 1930-х годов, когда Гаррет Биркгофф и Эйстейн Оре начали публиковать работы по универсальным алгебрам. Развитие метаматематики и теории категорий в 1940-х и 1950-х годах способствовало развитию этой области, особенно работы Абрахама Робинсона , Альфреда Тарского , Анджея Мостовского и их учеников. [8]
В период между 1935 и 1950 годами большинство статей было написано в соответствии с направлениями, предложенными работами Биркгофа, и касалось свободных алгебр , решеток конгруэнции и подалгебр и теорем гомоморфизма. Хотя развитие математической логики сделало возможными приложения к алгебре, они появлялись медленно; результаты, опубликованные Анатолием Мальцевым в 1940-х годах, остались незамеченными из-за войны. Лекция Тарского на Международном конгрессе математиков в Кембридже в 1950 году ознаменовала новый период, в котором были разработаны аспекты теории моделей, в основном самим Тарским, а также CC Chang, Leon Henkin , Bjarni Jónsson , Roger Lyndon и другими.
В конце 1950-х годов Эдвард Марчевский [9] подчеркнул важность свободных алгебр, что привело к публикации более 50 статей по алгебраической теории свободных алгебр самим Марчевским совместно с Яном Мыцельским , Владиславом Наркевичем, Витольдом Нитка, Я. Плонкой, С. Сверчковским, К. Урбаником и другими.
Начиная с диссертации Уильяма Ловера в 1963 году, методы теории категорий стали играть важную роль в универсальной алгебре. [10]
