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

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

В математике идея свободного объекта является одним из основных понятий абстрактной алгебры . Неформально, свободный объект над множеством 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 в качестве алфавита, с операцией конкатенации строк. Идентичность – это пустая строка. По сути, свободный моноид — это просто набор всех слов без каких-либо наложенных отношений эквивалентности. Этот пример получил дальнейшее развитие в статье о звезде Клини .

Общий случай

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

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

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

Бесплатные универсальные алгебры

Пусть — любое множество, и пусть — алгебраическая структура типа, порожденная . Пусть базовым набором этой алгебраической структуры , иногда называемой ее вселенной, будет , и пусть будет функция. Мы говорим, что (или неформально просто ) является свободной алгеброй (типа ) на множестве свободных образующих , если для каждой алгебры типа и каждой функции , где - универсум , существует уникальный гомоморфизм такой, что ${\displaystyle S}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \rho }$ ${\displaystyle S}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle A}$ ${\displaystyle \psi \colon S\to A}$ ${\displaystyle (A,\psi )}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \rho }$ ${\displaystyle S}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle \rho }$ ${\displaystyle \tau \colon S\to B}$ ${\displaystyle B}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle \sigma \colon A\to B}$ ${\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:X\to U(B)}$ ${\displaystyle f: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) Издательство Кембриджского университета, ISBN  0-521-23893-5 . (Рассмотрение одногенераторной свободной алгебры Гейтинга дано в главе 1, раздел 4.11)

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

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