Cтраница 1
Инициальная алгебра изоморфна алгебре слов. [1]
Однако инициальная алгебра не всегда является наиболее естественной моделью типа данных. Примером тому является теория множества натуральных чисел, для которой, как сказано в разд. [2]
Алгебра / называется инициальной алгеброй теории, если для любой алгебры А этой теории существует единственный гомоморфизм /: / - - А. [3]
Мы обозначаем составные части инициальной алгебры FQ / - T как ( fa, Т) - алгебру. [4]
Каждому классу эквивалентности в инициальной алгебре сопоставляется отдельный элемент носителя, вследствие чего инициальная алгебра имеет наибольший носитель среди всех алгебр данной теории. В этом смысле инициальная алгебра является наиболее расточительной в отношении расхода ресурсов памяти. [5]
Дуальным понятием по отношению к инициальной алгебре является терминальная ( финальная) алгебра. [6]
Мы можем теперь определить понятия, аналогичные инициальной алгебре и терминальной алгебре, по отношению ко всем алгебрам данной теории. [7]
Каждому классу эквивалентности в инициальной алгебре сопоставляется отдельный элемент носителя, вследствие чего инициальная алгебра имеет наибольший носитель среди всех алгебр данной теории. В этом смысле инициальная алгебра является наиболее расточительной в отношении расхода ресурсов памяти. [8]
При отсутствии равенств термы s и empty j s в алгебре слов данной сигнатуры рассматривались бы как различные, в связи с чем любая инициальная алгебра должна была бы иметь разные элементы для этих выражений, а терминальная - один и тот же элемент. Наличие данной системы равенств заставляет считать алгебрами теории строка только такие алгебры, у которых термы, подобные s и empty / s, отображаются в один и тот же элемент носителя. Таким образом, задание системы равенств позволяет сформировать классы эквивалентности выражений и тем самым определить в качестве инициальных и терминальных более реальные алгебры, отвечающие тому, что разработчик алгебры имел в виду. [9]
Поскольку о любых двух базисных термах этой теории мы можем вынести определенное суждение, обозначают ли они одно и то же значение или нет, инициальная алгебра данной теории является также и терминальной. [10]
Каждому классу эквивалентности в инициальной алгебре сопоставляется отдельный элемент носителя, вследствие чего инициальная алгебра имеет наибольший носитель среди всех алгебр данной теории. В этом смысле инициальная алгебра является наиболее расточительной в отношении расхода ресурсов памяти. [11]
По этой причине терминальные алгебры не могут использоваться как реальные модели данной теории. В то же время инициальные алгебры также редко являются идеальными моделями. Например, инициальная алгебра приведенной выше теории множеств будет считать различными множества с повторяющимися элементами или с разным порядком их расположения, тогда как на практике такие множества обычно считаются одинаковыми. [12]
По этой причине терминальные алгебры не могут использоваться как реальные модели данной теории. В то же время инициальные алгебры также редко являются идеальными моделями. Например, инициальная алгебра приведенной выше теории множеств будет считать различными множества с повторяющимися элементами или с разным порядком их расположения, тогда как на практике такие множества обычно считаются одинаковыми. [13]
Абстрактный тип setofnat расширяет теорию natbool до теории, скажем, setnatbool. Алгебры, соответствующие этой теории, могут строиться расширением алгебр теории natbool. Как указывалось выше, инициальной алгеброй данной теории по отношению к основе setofnat будет такая алгебра, в которой множества с повторяющимися элементами или с разным порядком их расположения считаются различными. [14]