В математике идея свободного объекта является одним из основных понятий абстрактной алгебры . Неформально, свободный объект над множеством A можно рассматривать как «общую» алгебраическую структуру над A : единственные уравнения, которые выполняются между элементами свободного объекта, - это те, которые следуют из определяющих аксиом алгебраической структуры. Примеры включают свободные группы , тензорные алгебры или свободные решетки .
Это понятие является частью универсальной алгебры в том смысле, что оно относится ко всем типам алгебраических структур (с финитными операциями). У него также есть формулировка в терминах теории категорий , хотя и в еще более абстрактных терминах.
Свободные объекты являются прямым обобщением на категории понятия базиса в векторном пространстве. Линейная функция u : E 1 → E 2 между векторными пространствами полностью определяется своими значениями на основе векторного пространства E 1 . Следующее определение переводит это в любую категорию.
Конкретная категория — это категория, снабженная точным функтором для Set , категории множеств . Пусть C — конкретная категория с точным функтором U : C → Set . Пусть X — набор (то есть объект в Set ), который будет основой определяемого свободного объекта. Свободный объект на X — это пара, состоящая из объекта в C и инъекции (называемой канонической инъекцией ), которая удовлетворяет следующему универсальному свойству :
Если в C существуют свободные объекты , универсальное свойство подразумевает, что каждое отображение между двумя множествами вызывает уникальный морфизм между построенными на них свободными объектами, и это определяет функтор . Отсюда следует, что если в C существуют свободные объекты , то функтор F , называемый свободным функтором , является левым сопряженным к точному функтору U ; то есть существует биекция
Создание свободных объектов происходит в два этапа. Для алгебр, которые подчиняются закону ассоциативности , первым шагом является рассмотрение совокупности всех возможных слов , образованных из алфавита . Затем к словам налагается набор отношений эквивалентности , где эти отношения являются определяющими отношениями рассматриваемого алгебраического объекта. Тогда свободный объект состоит из набора классов эквивалентности .
Рассмотрим, например, построение свободной группы в двух образующих . Начинается с алфавита, состоящего из пяти букв . На первом этапе «буквам» или ; еще не присвоено какое-либо значение ; они будут даны позже, на втором этапе. Таким образом, с таким же успехом можно было бы начать с алфавита из пяти букв, то есть . В этом примере набор всех слов или строк будет включать в себя такие строки, как aebecede и abdc и т. д., произвольной конечной длины, с буквами, расположенными во всех возможных порядках.
На следующем этапе вводится набор отношений эквивалентности. Отношения эквивалентности для группы — это умножение на единицу и умножение обратных чисел: . Применяя эти отношения к приведенным выше строкам, получаем
где было понятно, что является заменой , и является заменой , а является элементом идентичности. Аналогично, у человека есть
Обозначая отношение эквивалентности или конгруэнтность через , свободный объект представляет собой совокупность классов эквивалентности слов. Таким образом, в этом примере свободная группа в двух образующих — это фактор
Это часто записывается как где - набор всех слов и класс эквивалентности идентичности после того, как наложены отношения, определяющие группу.
Более простой пример — свободные моноиды . Свободный моноид на множестве X — это моноид всех конечных строк , использующих X в качестве алфавита, с операцией конкатенации строк. Идентичность – это пустая строка. По сути, свободный моноид — это просто набор всех слов без каких-либо наложенных отношений эквивалентности. Этот пример получил дальнейшее развитие в статье о звезде Клини .
В общем случае алгебраические отношения не обязательно должны быть ассоциативными, и в этом случае отправной точкой является не набор всех слов, а, скорее, строки, перемежающиеся круглыми скобками, которые используются для обозначения неассоциативных группировок букв. Такая строка может быть эквивалентно представлена двоичным деревом или свободной магмой ; листья дерева — это буквы алфавита.
Тогда алгебраические отношения могут быть общими арностями или финитными отношениями на листьях дерева. Вместо того, чтобы начинать со сбора всех возможных строк в скобках, может быть удобнее начать с вселенной Herbrand . Правильное описание или перечисление содержимого свободного объекта может быть простым или трудным, в зависимости от конкретного рассматриваемого алгебраического объекта. Например, легко описывается свободная группа в двух образующих. Напротив, о структуре свободных гейтинговых алгебр с более чем одним генератором известно мало или совсем ничего. [1] Проблема определения принадлежности двух разных строк одному и тому же классу эквивалентности известна как проблема слов .
Как показывают примеры, свободные объекты выглядят как конструкции из синтаксиса ; можно в некоторой степени изменить это мнение, сказав, что основные варианты использования синтаксиса можно объяснить и охарактеризовать как свободные объекты, причем таким образом, что кажущаяся тяжелая «пунктуация» становится объяснимой (и более запоминающейся). [ нужны разъяснения ]
Пусть — любое множество, и пусть — алгебраическая структура типа, порожденная . Пусть базовым набором этой алгебраической структуры , иногда называемой ее вселенной, будет , и пусть будет функция. Мы говорим, что (или неформально просто ) является свободной алгеброй (типа ) на множестве свободных образующих , если для каждой алгебры типа и каждой функции , где - универсум , существует уникальный гомоморфизм такой, что
Наиболее общая установка свободного объекта находится в теории категорий , где определяется функтор , свободный функтор , который является левым сопряженным к забывчивому функтору .
Рассмотрим категорию C алгебраических структур ; объекты можно рассматривать как множества плюс операции, подчиняющиеся некоторым законам. Эта категория имеет функтор , функтор забывчивости , который отображает объекты и функции в C в Set , категорию множеств . Функтор забывчивости очень прост: он просто игнорирует все операции.
Свободный функтор F , если он существует, является левым сопряженным к U. То есть переводит множества X в Set в соответствующие им свободные объекты F ( X ) в категории C. Множество X можно рассматривать как множество «генераторов» свободного объекта F ( X ).
Чтобы свободный функтор был левым сопряженным, необходимо также иметь Set -морфизм . Более явно, F с точностью до изоморфизмов в C характеризуется следующим универсальным свойством :
Конкретно, это отправляет набор в свободный объект этого набора; это «включение основы». Злоупотребление обозначениями (это злоупотребление обозначениями, поскольку X — множество, а F ( X ) — алгебра; правильно, это так ).
Естественное преобразование называется единицей ; вместе с единицей можно построить Т-алгебру и, следовательно, монаду .
Косвободный функтор является правым сопряженным функтору забывчивости.
Существуют общие теоремы существования, которые применимы; самый основной из них гарантирует, что
Здесь разнообразие является синонимом финитарной алгебраической категории , что подразумевает, что набор отношений является финитным и алгебраическим , поскольку он монадичен над Set .
Другие типы забывания также порождают объекты, подобные свободным объектам, в том смысле, что они остаются присоединенными к функтору забывания, а не обязательно к множествам.
Например, конструкция тензорной алгебры в векторном пространстве является левым сопряжением функтора на ассоциативных алгебрах , который игнорирует структуру алгебры. Поэтому ее часто еще называют свободной алгеброй . Аналогично симметрическая алгебра и внешняя алгебра являются свободными симметрическими и антисимметричными алгебрами в векторном пространстве.
К конкретным видам бесплатных объектов относятся: