Термин алгебра

Свободно генерируемая алгебраическая структура по заданной сигнатуре

В универсальной алгебре и математической логике термин алгебра — это свободно генерируемая алгебраическая структура над заданной сигнатурой . ^{[1] [2]} Например, в сигнатуре , состоящей из одной бинарной операции , термин алгебра над множеством X переменных — это в точности свободная магма, генерируемая X. Другие синонимы этого понятия включают абсолютно свободную алгебру и анархическую алгебру . ^[3]

С точки зрения теории категорий , терм алгебра является исходным объектом для категории всех X -порождённых алгебр той же сигнатуры , и этот объект, уникальный с точностью до изоморфизма , называется исходной алгеброй ; он порождает посредством гомоморфной проекции все алгебры в категории. ^{[4] [5]}

Аналогичное понятие есть у вселенной Эрбрана в логике , обычно используемой под этим названием в логическом программировании , ^[6] , которая (абсолютно свободно) определяется, начиная с набора констант и символов функций в наборе предложений . То есть, вселенная Эрбрана состоит из всех основных терминов : терминов, в которых нет переменных.

Атомная формула или атом обычно определяется как предикат , применяемый к кортежу терминов; тогда базовый атом — это предикат, в котором появляются только базовые термины. База Эрбрана — это набор всех базовых атомов, которые могут быть образованы из предикатных символов в исходном наборе предложений и терминов в его вселенной Эрбрана. ^{[7] [8]} Эти два понятия названы в честь Жака Эрбрана .

Алгебры терминов также играют роль в семантике абстрактных типов данных , где объявление абстрактного типа данных обеспечивает сигнатуру многосортной алгебраической структуры, а алгебра терминов является конкретной моделью объявления абстрактного типа.

Универсальная алгебра

Тип — это набор символов функций, каждый из которых имеет связанную арность (т.е. количество входов). Для любого неотрицательного целого числа пусть обозначает символы функций в арности . Константа — это символ функции арности 0. ${\displaystyle \tau }$ ${\displaystyle n}$ ${\displaystyle \tau _{n}}$ ${\displaystyle \tau }$ ${\displaystyle n}$

Пусть будет типом, и пусть будет непустым набором символов, представляющим переменные символы. (Для простоты предположим , что и не пересекаются.) Тогда набор терминов типа над — это набор всех правильно сформированных строк , которые могут быть построены с использованием переменных символов и констант и операций . Формально, — это наименьший набор такой, что: ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \tau }$ ${\displaystyle T(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \tau }$ ${\displaystyle T(X)}$

• ${\displaystyle X\cup \tau _{0}\subseteq T(X)}$   — каждый переменный символ из является термином в , и каждый постоянный символ из также является термином . ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle \tau _{0}}$
• Для всех и для всех функциональных символов и термов мы имеем строку   — данные термовы , применение к ним -арного функционального символа снова представляет собой термов. ${\displaystyle n\geq 1}$ ${\displaystyle f\in \tau _{n}}$ ${\displaystyle t_{1},...,t_{n}\in T(X)}$ ${\displaystyle f(t_{1},...,t_{n})\in T(X)}$ ${\displaystyle n}$ ${\displaystyle t_{1},...,t_{n}}$ ${\displaystyle n}$ ${\displaystyle f}$

Термин алгебра типа над , вкратце, является алгеброй типа , которая отображает каждое выражение в его строковое представление. Формально определяется следующим образом: ^[9] ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle \tau }$ ${\displaystyle {\mathcal {T}}(X)}$

• Домен — . ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle T(X)}$
• Для каждой нулевой функции в , определяется как строка . ${\displaystyle f}$ ${\displaystyle \tau _{0}}$ ${\displaystyle f^{{\mathcal {T}}(X)}()}$ ${\displaystyle f}$
• Для всех и для каждой n -арной функции в и элементах в области определяется как строка . ${\displaystyle n\geq 1}$ ${\displaystyle f}$ ${\displaystyle \tau }$ ${\displaystyle t_{1},...,t_{n}}$ ${\displaystyle f^{{\mathcal {T}}(X)}(t_{1},...,t_{n})}$ ${\displaystyle f(t_{1},...,t_{n})}$

Алгебра термов называется абсолютно свободной, потому что для любой алгебры типа и для любой функции , продолжается до единственного гомоморфизма , который просто оценивает каждый термин в его соответствующее значение . Формально, для каждого : ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \tau }$ ${\displaystyle g:X\to {\mathcal {A}}}$ ${\displaystyle g}$ ${\displaystyle g^{\ast }:{\mathcal {T}}(X)\to {\mathcal {A}}}$ ${\displaystyle t\in {\mathcal {T}}(X)}$ ${\displaystyle g^{\ast }(t)\in {\mathcal {A}}}$ ${\displaystyle t\in {\mathcal {T}}(X)}$

• Если , то . ${\displaystyle t\in X}$ ${\displaystyle g^{\ast }(t)=g(t)}$
• Если , то . ${\displaystyle t=f\in \tau _{0}}$ ${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}()}$
• Если где и , то . ${\displaystyle t=f(t_{1},...,t_{n})}$ ${\displaystyle f\in \tau _{n}}$ ${\displaystyle n\geq 1}$ ${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}(g^{\ast }(t_{1}),...,g^{\ast }(t_{n}))}$

Пример

В качестве примера тип, вдохновленный целочисленной арифметикой, может быть определен как , , , и для каждого . ${\displaystyle \tau _{0}=\{0,1\}}$ ${\displaystyle \tau _{1}=\{\}}$ ${\displaystyle \tau _{2}=\{+,*\}}$ ${\displaystyle \tau _{i}=\{\}}$ ${\displaystyle i>2}$

Самая известная алгебра типа имеет в качестве своей области натуральные числа и интерпретирует , , , и обычным образом; мы называем ее . ${\displaystyle \tau }$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle +}$ ${\displaystyle *}$ ${\displaystyle {\mathcal {A}}_{nat}}$

Для примера набора переменных мы собираемся исследовать термин алгебра типа над . ${\displaystyle X=\{x,y\}}$ ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$

Сначала рассматривается множество терминов типа over . Мы используем красный цвет для обозначения его членов, которые в противном случае было бы трудно распознать из-за их необычной синтаксической формы. Например, у нас есть ${\displaystyle T(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$

• ${\displaystyle {\color {red}x}\in T(X)}$, так как — переменный символ; ${\displaystyle x\in X}$
• ${\displaystyle {\color {red}1}\in T(X)}$, так как является постоянным символом; следовательно, ${\displaystyle 1\in \tau _{0}}$
• ${\displaystyle {\color {red}+x1}\in T(X)}$, так как является 2-арным функциональным символом; следовательно, в свою очередь, ${\displaystyle +}$
• ${\displaystyle {\color {red}*+x1x}\in T(X)}$поскольку является 2-арным функциональным символом. ${\displaystyle *}$

В более общем смысле, каждая строка в соответствует математическому выражению, построенному из принятых символов и записанному в польской префиксной нотации ; например, термин соответствует выражению в обычной инфиксной нотации . Скобки не нужны, чтобы избежать двусмысленности в польской нотации; например, инфиксное выражение соответствует термину . ${\displaystyle T(X)}$ ${\displaystyle {\color {red}*+x1x}}$ ${\displaystyle (x+1)*x}$ ${\displaystyle x+(1*x)}$ ${\displaystyle {\color {red}+x*1x}}$

Чтобы привести некоторые контрпримеры, у нас есть, например,

• ${\displaystyle {\color {red}z}\not \in T(X)}$, поскольку не является ни допустимым переменным символом, ни допустимым постоянным символом; ${\displaystyle z}$
• ${\displaystyle {\color {red}3}\not \in T(X)}$, по той же причине,
• ${\displaystyle {\color {red}+1}\not \in T(X)}$, поскольку является символом 2-арной функции, но здесь используется только с одним аргументом term (а именно ). ${\displaystyle +}$ ${\displaystyle {\color {red}1}}$

Теперь, когда множество терминов установлено, рассмотрим алгебру терминов типа над . Эта алгебра использует в качестве своей области, на которой должны быть определены сложение и умножение. Функция сложения принимает два термина и и возвращает термин ; аналогично, функция умножения отображает заданные термины и в термин . Например, вычисляется как термин . Неформально, операции и являются «ленивцами», поскольку они просто записывают, какие вычисления должны быть выполнены, а не выполняют их. ${\displaystyle T(X)}$ ${\displaystyle {\mathcal {T}}(X)}$ ${\displaystyle \tau }$ ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle +^{{\mathcal {T}}(X)}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle {\color {red}+}pq}$ ${\displaystyle *^{{\mathcal {T}}(X)}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle {\color {red}*}pq}$ ${\displaystyle *^{{\mathcal {T}}(X)}({\color {red}+x1},{\color {red}x})}$ ${\displaystyle {\color {red}*+x1x}}$ ${\displaystyle +^{{\mathcal {T}}(X)}}$ ${\displaystyle *^{{\mathcal {T}}(X)}}$

В качестве примера уникальной расширяемости гомоморфизма рассмотрим определенный с помощью и . Неформально, определяет присвоение значений переменным символам, и как только это сделано, каждый член из может быть оценен уникальным образом в . Например, ${\displaystyle g:X\to {\mathcal {A}}_{nat}}$ ${\displaystyle g(x)=7}$ ${\displaystyle g(y)=3}$ ${\displaystyle g}$ ${\displaystyle T(X)}$ ${\displaystyle {\mathcal {A}}_{nat}}$

${\displaystyle {\begin{array}{lll}&g^{*}({\color {red}+x1})\\=&g^{*}({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&g({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ coincides on }}X{\text{ with }}g\\=&7+g^{*}({\color {red}1})&{\text{ by definition of }}g\\=&7+1&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&8&{\text{ according to the well-known arithmetical rules in }}{\mathcal {A}}_{nat}\\\end{array}}}$

Аналогичным образом получается . ${\displaystyle g^{*}({\color {red}*+x1x})=...=8*g({\color {red}x})=...=56}$

база Herbrand

Сигнатура σ языка — это тройка < O , F  , P  > , состоящая из алфавита констант O , функциональных символов F и предикатов P . База Эрбрана ^[10] сигнатуры σ состоит из всех основных атомов σ : всех формул вида R ( t ₁ , ...,  t _n ), где t ₁ , ...,  t _n — термины, не содержащие переменных (т. е. элементы универсума Эрбрана), а R — символ n -арного отношения ( т. е. предикат ). В случае логики с равенством она также содержит все уравнения вида t ₁  =  t ₂ , где t ₁ и t ₂ не содержат переменных.

Разрешимость

Алгебры терминов можно показать разрешимыми с помощью исключения квантификаторов . Сложность проблемы принятия решения заключается в НЕЭЛЕМЕНТАРНОСТИ , поскольку бинарные конструкторы являются инъективными и, таким образом, спаривают функции. ^[11]

Смотрите также

• Программирование набора ответов
• Клон (алгебра)
• Область дискурса / Вселенная (математика)
• Теорема Рабина о дереве (монадическая теория бесконечного полного двоичного дерева разрешима)
• Начальная алгебра
• Абстрактный тип данных
• Система переписывания терминов

Ссылки

1. Уилфрид Ходжес (1997). Теория более короткой модели . Cambridge University Press . С. 14. ISBN 0-521-58713-1.
2. Франц Баадер ; Тобиас Нипков (1998). Переписывание терминов и все такое. Cambridge University Press . стр. 49. ISBN 0-521-77920-0.
3. Клаус Денеке; Шелли Л. Висмат (2009). Универсальная алгебра и коалгебра. World Scientific . стр. 21–23. ISBN 978-981-283-745-5.
4. TH Tse (2010). Унифицированная структура для структурного анализа и моделей проектирования: подход с использованием начальной алгебраической семантики и теории категорий . Cambridge University Press . стр. 46–47. doi :10.1017/CBO9780511569890. ISBN 978-0-511-56989-0.
5. Жан-Ив Безьяу (1999). "Математическая структура логического синтаксиса". В Carnielli, Walter Alexandre; D'Ottaviano, Itala ML (ред.). Достижения в современной логике и информатике: Труды одиннадцатой бразильской конференции по математической логике, 6-10 мая 1996 г., Сальвадор, Баия, Бразилия . Американское математическое общество . стр. 9. ISBN 978-0-8218-1364-5. Получено 18 апреля 2011 г.
6. Дирк ван Дален (2004). Логика и структура. Спрингер . п. 108. ИСБН 978-3-540-20879-2.
7. М. Бен-Ари (2001). Математическая логика для компьютерных наук. Springer . С. 148–150. ISBN 978-1-85233-319-5.
8. Monroe Newborn (2001). Автоматизированное доказательство теорем: теория и практика. Springer . стр. 43. ISBN 978-0-387-95075-4.
9. Стэнли Беррис; HP Sankappanavar (1981). Курс универсальной алгебры. Springer. стр. 68–69, 71. ISBN 978-1-4613-8132-7.{{cite book}}: CS1 maint: multiple names: authors list (link)
10. Рохелио Давила. Обзор программирования набора ответов.
11. Жанна Ферранте; Чарльз В. Ракофф (1979). Вычислительная сложность логических теорий . Springer , Глава 8, Теорема 1.2.

Дальнейшее чтение

• Джоэл Берман (2005). «Структура свободных алгебр». В Structural Theory of Automata, Semigroups, and Universal Algebra . Springer . стр. 47–76. MR 2210125.

Внешние ссылки

• Вайсштейн, Эрик В. «Вселенная Эрбрана». Математический мир .