Свободный объект

Левый сопряженный к забывающему функтору множеств

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

Понятие является частью универсальной алгебры , в том смысле, что оно относится ко всем типам алгебраической структуры (с финитными операциями). Оно также имеет формулировку в терминах теории категорий , хотя это еще более абстрактные термины.

Определение

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

Конкретная категория — это категория, которая снабжена точным функтором для Set , категории множеств . Пусть C — конкретная категория с точным функтором U  : C → Set . Пусть X — множество (то есть объект в Set ), которое будет основой свободного объекта, который будет определен. Свободный объект на X — это пара, состоящая из объекта в C и инъекции (называемой канонической инъекцией ), которая удовлетворяет следующему универсальному свойству : ${\displaystyle A}$ ${\displaystyle i:X\to U(A)}$

Для любого объекта B в C и любого отображения между множествами существует единственный морфизм в C такой, что . То есть, следующая диаграмма коммутирует: ${\displaystyle g:X\to U(B)}$ ${\displaystyle f:A\to B}$ ${\displaystyle g=U(f)\circ i}$

х

Если в C существуют свободные объекты , универсальное свойство подразумевает, что каждое отображение между двумя множествами индуцирует уникальный морфизм между свободными объектами, построенными на них, и это определяет функтор . Отсюда следует, что если в C существуют свободные объекты , функтор F , называемый свободным функтором , является левым сопряженным к верному функтору U ; то есть существует биекция ${\displaystyle F:\mathbf {Set} \to \mathbf {C} }$

${\displaystyle \operatorname {Hom} _{\mathbf {Set} }(X,U(B))\cong \operatorname {Hom} _{\mathbf {C} }(F(X),B).}$

Примеры

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

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

На следующем этапе накладывается набор отношений эквивалентности. Отношения эквивалентности для группы — это отношения умножения на тождество, , и умножения обратных чисел: . Применяя эти отношения к строкам выше, получаем ${\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} \}}$

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

Общий случай

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

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

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

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

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

Для каждой алгебры типа и каждой функции , где — универсум , существует единственный гомоморфизм, такой что следующая диаграмма коммутирует: ${\displaystyle B}$ ${\displaystyle \rho }$ ${\displaystyle \tau :S\to B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle \sigma :A\to B}$

${\displaystyle {\begin{array}{ccc}S&\xrightarrow {\psi } &A\\&\searrow _{\tau }&\downarrow ^{\sigma }\\&&B\ \end{array}}}$

Это означает, что . ${\displaystyle \sigma \circ \psi =\tau }$

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

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

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

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

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

Если B — алгебра в C , а — функция (морфизм в категории множеств), то существует единственный C -морфизм, такой что . ${\displaystyle g\colon X\to U(B)}$ ${\displaystyle f\colon F(X)\to B}$ ${\displaystyle g=U(f)\circ \eta _{X}}$

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

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

Функтор косвободы является правым сопряженным к функтору забывания.

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

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

Если C является многообразием , то для каждого множества X существует свободный объект F ( X ) в C.

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

Общий случай

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

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

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

К особым видам свободных объектов относятся:

• свободная алгебра
  • свободная ассоциативная алгебра
  • свободная коммутативная алгебра
• свободная категория
  • свободная строгая моноидальная категория
• бесплатная группа
  • свободная абелева группа
  • свободная частично коммутативная группа
• свободная алгебра Клини
• свободная решетка
  • свободная булева алгебра
  • свободная распределительная решетка
  • свободная алгебра Гейтинга
  • свободная модульная решетка
• свободная алгебра Ли
• свободная магма
• свободный модуль , и в частности, векторное пространство
• свободный моноид
  • свободный коммутативный моноид
  • свободный частично коммутативный моноид
• бесплатное кольцо
• свободная полугруппа
• свободное полукольцо
  • свободное коммутативное полукольцо
• свободная теория
• термин алгебра
• дискретное пространство

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

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

Примечания

1. Питер Т. Джонстон, Stone Spaces , (1982) Cambridge University Press, ISBN  0-521-23893-5 . (Трактовка свободной алгебры Гейтинга с одним генератором приведена в главе 1, разделе 4.11)

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

• В nLab : свободный функтор, свободный объект, векторное пространство