Бесплатный объект - Free object

В математика, идея свободный объект одна из основных концепций абстрактная алгебра. Это часть универсальная алгебра, в том смысле, что он относится ко всем типам алгебраических структур (с финишный операции). Он также имеет формулировку с точки зрения теория категорий, хотя это еще более абстрактно. Примеры включают бесплатные группы, тензорные алгебры, или же свободные решетки. Неформально свободный объект над множеством А можно рассматривать как «общую» алгебраическую структуру над А: единственные уравнения, которые выполняются между элементами свободного объекта, - это те, которые следуют из определяющих аксиом алгебраической структуры.

Определение

Бесплатные объекты являются прямым обобщением категории понятия основа в векторном пространстве. Линейная функция ты : E₁ → E₂ между векторными пространствами полностью определяется своими значениями на основе векторного пространства E₁. Следующее определение переводит это на любую категорию.

А конкретная категория категория, которая оснащена верный функтор к Набор, то категория наборов. Позволять C конкретная категория с точным функтором F : C → Набор. Позволять Икс быть объектом в Набор (то есть, Икс это набор, здесь называемый основа), позволять А быть объектом в C, и разреши я : Икс → F(А) быть инъективным отображением между множествами Икс и F(А) (называется каноническая вставка). потом А считается бесплатный объект на Икс (относительно я) тогда и только тогда, когда он удовлетворяет следующему универсальная собственность:

для любого объекта B в C и любая карта между наборами ж : Икс → F(B), существует единственный морфизм грамм : А → B в C такой, что ж = F(грамм) ∘ я. То есть следующие диаграмма коммутирует:

{ displaystyle { begin {array} {c} X { xrightarrow { quad i quad}} F (A) {} _ {f} seekrow quad swarrow {} _ {F (g) } F (B) quad end {array}}}

Таким образом, бесплатный функтор, который строит бесплатный объект А из набора Икс становится левый смежный к забывчивый функтор.

Примеры

Создание бесплатных объектов происходит в два этапа. Для алгебр, соответствующих ассоциативный закон, первым делом нужно рассмотреть набор всех возможных слова сформированный из алфавит. Затем накладывают набор отношения эквивалентности на словах, где отношения являются определяющими отношениями рассматриваемого алгебраического объекта. Тогда свободный объект состоит из набора классы эквивалентности.

Рассмотрим, например, построение свободной группы из двух образующих. Каждый начинается с алфавита, состоящего из пяти букв ${ Displaystyle {е, а, Ь, а ^ {- 1}, Ь ^ {- 1} }}$ . На первом этапе «буквам» еще не присвоено какое-либо значение. ${ displaystyle a ^ {- 1}}$ или же ${ displaystyle b ^ {- 1}}$ ; они будут даны позже, на втором этапе. Таким образом, можно с равным успехом начать с алфавита из пяти букв, ${ Displaystyle S = {a, b, c, d, e }}$ . В этом примере набор всех слов или строк ${ Displaystyle W (S)}$ будет включать такие строки, как aebecede и abdcи т. д. произвольной конечной длины с расположением букв во всевозможном порядке.

На следующем этапе вводится набор отношений эквивалентности. Отношения эквивалентности для группа умножение на единицу, ${ displaystyle ge = eg = g}$ , и умножение обратных: ${ displaystyle gg ^ {- 1} = g ^ {- 1} g = e}$ . Применяя эти отношения к приведенным выше строкам, получаем

{ displaystyle aebecede = aba ^ {- 1} b ^ {- 1},}

где было понято, что ${ displaystyle c}$ заменяет ${ displaystyle a ^ {- 1}}$ , и ${ displaystyle d}$ заменяет ${ displaystyle b ^ {- 1}}$ , пока ${ displaystyle e}$ является элементом идентичности. Точно так же

{ displaystyle abdc = abb ^ {- 1} a ^ {- 1} = e.}

Обозначая отношение эквивалентности или соответствие к ${ displaystyle sim}$ , тогда свободный объект представляет собой набор классы эквивалентности слов. Таким образом, в этом примере свободная группа в двух образующих - это частное

{ Displaystyle F_ {2} = W (S) / sim.}

Это часто записывается как ${ Displaystyle F_ {2} = W (S) / E}$ куда ${ Displaystyle W (S) = {a_ {1} a_ {2} ldots a_ {n} , vert ; a_ {k} in S ,; , n in mathbb {N} }}$ это набор всех слов, и ${ Displaystyle E = {a_ {1} a_ {2} ldots a_ {n} , vert ; e = a_ {1} a_ {2} ldots a_ {n} ,; , a_ { k} in S ,; , n in mathbb {N} }}$ является классом эквивалентности единицы после того, как наложены отношения, определяющие группу.

Более простой пример - бесплатные моноиды. Бесплатный моноид на множестве Икс, является моноидом всех конечных струны с помощью Икс как алфавит, с операцией конкатенация струн. Идентификатор - это пустая строка. По сути, свободный моноид - это просто набор всех слов без каких-либо отношений эквивалентности. Этот пример более подробно рассматривается в статье о Клини звезда.

Общий случай

В общем случае алгебраические отношения не обязательно должны быть ассоциативными, и в этом случае отправной точкой является не набор всех слов, а, скорее, строки, разделенные круглыми скобками, которые используются для обозначения неассоциативных группировок букв. Такая строка может быть эквивалентно представлена двоичное дерево или свободная магма; листья дерева - это буквы алфавита.

Тогда алгебраические соотношения могут быть общими. арности или же финансовые отношения на листьях дерева. Вместо того, чтобы начинать со сбора всех возможных строк в скобках, может быть удобнее начать с Вселенная Herbrand. Правильное описание или перечисление содержимого свободного объекта может быть простым или трудным, в зависимости от конкретного рассматриваемого алгебраического объекта. Например, легко описывается свободная группа в двух образующих. Напротив, мало или совсем ничего известно о структуре бесплатные алгебры Гейтинга в более чем одном генераторе.^[1] Проблема определения того, принадлежат ли две разные строки к одному и тому же классу эквивалентности, известна как проблема со словом.

Как показывают примеры, свободные объекты выглядят как конструкции из синтаксис; можно до некоторой степени это изменить, сказав, что основные виды использования синтаксиса можно объяснить и охарактеризовать как свободные объекты таким образом, чтобы сделать явно тяжелую «пунктуацию» объяснимой (и более запоминающейся).^{[требуется разъяснение ]}

Свободные универсальные алгебры

Позволять ${ displaystyle S}$ быть любым набором, и пусть ${ displaystyle mathbf {A}}$ быть алгебраическая структура типа ${ displaystyle rho}$ создано ${ displaystyle S}$ . Пусть основной набор этой алгебраической структуры ${ displaystyle mathbf {A}}$ , иногда называемый своей вселенной, будь ${ displaystyle A}$ , и разреши ${ displaystyle psi: S to A}$ быть функцией. Мы говорим что ${ displaystyle (A, psi)}$ (или неформально просто ${ displaystyle mathbf {A}}$ ) это свободная алгебра (типа ${ displaystyle rho}$ ) на множестве ${ displaystyle S}$ из бесплатные генераторы если для каждой алгебры ${ displaystyle mathbf {B}}$ типа ${ displaystyle rho}$ и каждая функция ${ Displaystyle тау: от S до B}$ , куда ${ displaystyle B}$ это вселенная ${ displaystyle mathbf {B}}$ существует единственный гомоморфизм ${ displaystyle sigma: от A до B}$ такой, что ${ Displaystyle sigma circ psi = tau.}$

Свободный функтор

Самая общая настройка бесплатного объекта - в теория категорий, где определяется функтор, то свободный функтор, это левый смежный к забывчивый функтор.

Рассмотрим категорию C из алгебраические структуры; их можно рассматривать как наборы плюс операции, подчиняющиеся некоторым законам. У этой категории есть функтор, ${ Displaystyle U: mathbf {C} to mathbf {Set}}$ , то забывчивый функтор, который отображает объекты и функции в C к Набор, то категория наборов. Функтор забывчивости очень прост: он просто игнорирует все операции.

Свободный функтор F, когда он существует, является левым, сопряженным с U. То есть, ${ displaystyle F: mathbf {Set} to mathbf {C}}$ берет наборы Икс в Набор к их соответствующим бесплатным объектам F(Икс) в категории C. Набор Икс можно рассматривать как набор «генераторов» свободного объекта F(Икс).

Для того чтобы свободный функтор был сопряженным слева, необходимо также наличие Набор-морфизм ${ Displaystyle eta: X к U (F (X)) , !}$ . Более конкретно, F есть, с точностью до изоморфизмов в C, характеризующийся следующими универсальная собственность:

В любое время А это алгебра в C, и грамм : Икс → U(А) - функция (морфизм в категории множеств), то существует единственное C-морфизм час : F(Икс) → А такой, что U(час) ∘ η = грамм.

Конкретно, это отправляет набор в свободный объект на этом наборе; это «включение основы». Злоупотребление обозначениями, ${ Displaystyle X к F (X)}$ (это злоупотребление обозначениями, потому что Икс это набор, а F(Икс) - алгебра; правильно, это ${ Displaystyle X к U (F (X))}$ ).

В естественная трансформация ${ displaystyle eta: operatorname {id} _ { mathbf {Set}} to UF}$ называется единица измерения; вместе с графство ${ displaystyle varepsilon: FU to operatorname {id} _ { mathbf {C}}}$ можно построить Т-алгебра, и так монада.

В cofree функтор это правый смежный забывчивому функтору.

Существование

Существуют общие теоремы существования, которые применимы; самые основные из них гарантируют, что

В любое время C это разнообразие, то для каждого набора Икс есть бесплатный объект F(Икс) в C.

Здесь разнообразие является синонимом финитарная алгебраическая категория, таким образом подразумевая, что набор отношений финишный, и алгебраический потому что это так монадический над Набор.

Общий случай

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

Например, тензорная алгебра строительство на векторное пространство является левым сопряженным к функтору на ассоциативные алгебры который игнорирует структуру алгебры. Поэтому его часто также называют свободная алгебра. Аналогичным образом симметрическая алгебра и внешняя алгебра являются свободными симметричными и антисимметрическими алгебрами в векторном пространстве.

Список бесплатных объектов

Конкретные виды бесплатных объектов включают:

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

Генераторная установка

Примечания

^ Питер Т. Джонстон, Каменные Пространства, (1982) Издательство Кембриджского университета, ISBN 0-521-23893-5. (Рассмотрение алгебры Гейтинга без одного генератора дано в главе 1, раздел 4.11)

[1] Питер Т. Джонстон, Каменные Пространства, (1982) Издательство Кембриджского университета, ISBN 0-521-23893-5. (Рассмотрение алгебры Гейтинга без одного генератора дано в главе 1, раздел 4.11)

[1]