Ініціальна алгебра - Велика Енциклопедія Нафти та Газа, стаття 1

Ініціальна алгебра

Ініціальна алгебра ізоморфна алгебри слів. [1]

Проте ініціальна алгебра який завжди є найбільш природною моделлю типу даних. Прикладом тому є теорія множини натуральних чисел, для якої, як сказано в розд. [2]

Алгебра / називається ініціальною алгеброю теорії, якщо для будь-якої алгебри А цієї теорії існує єдиний гомоморфізм /: / - - А. [3]

Ми позначаємо складові частини ініціальної алгебри FQ / - T як (fa, Т) - алгебру. [4]

Кожному класу еквівалентності в ініціальній алгебрі зіставляється окремий елемент носія, внаслідок чого ініціальна алгебра має найбільший носій серед усіх алгебр цієї теорії. У цьому сенсі ініціальна алгебра є найбільш марнотратною щодо витрати ресурсів пам'яті. [5]

Дуальним поняттям щодо ініціальної алгебри є термінальна (фінальна) алгебра. [6]

Ми можемо тепер визначити поняття, аналогічні ініціальній і термінальній алгебрі, по відношенню до всіх алгебр даної теорії. [7]

За відсутності рівностей терми s і empty j s в алгебрі слів даної сигнатури розглядалися б як різні, у зв'язку з чим будь-яка ініціальна алгебра повинна була б мати різні елементи для цих виразів, а термінальна - один і той самий елемент. Наявність даної системи рівностей змушує вважати алгебрами теорії рядок тільки такі алгебри, у яких терми,подібні s і empty/s, відображаються в один і той самий елемент носія. Таким чином, завдання системи рівностей дозволяє сформувати класи еквівалентності виразів і тим самим визначити як ініціальні та термінальні реальніші алгебри, що відповідають тому, що розробник алгебри мав на увазі. [9]

Оскільки про будь-які два базисних терми цієї теорії ми можемо винести певне судження, чи позначають вони одне й те саме значення чи ні, ініціальна алгебра цієї теорії є також термінальної. [10]

Тому термінальні алгебри не можуть використовуватися як реальні моделі даної теорії. У той самий час ініціальні алгебри також рідко є ідеальними моделями. Наприклад, ініціальна алгебра наведеної вище теорії множин буде вважати різними множини з елементами, що повторюються, або з різним порядком їх розташування, тоді як на практиці такі множини зазвичай вважаються однаковими. [12]

Абстрактний тип setofnat розширює теорію natbool до теорії, скажімо, setnatbool. Алгебри, що відповідають цій теорії,можуть будуватися розширенням алгебр теорії natbool. Як зазначалося вище, ініціальною алгеброю даної теорії по відношенню до основи setofnat буде така алгебра, в якій множини з повторюваними елементами або з різним порядком їх розташування вважаються різними. [14]