Цилиндрическая алгебра - Cylindric algebra - Wikipedia

Понятие цилиндрическая алгебра, изобретенный Альфред Тарский, естественно возникает в алгебраизация из логика первого порядка с равенством. Это сравнимо с ролью Булевы алгебры играть за логика высказываний. В самом деле, цилиндрические алгебры - это булевы алгебры, снабженные дополнительными операциями цилиндрификации, которые моделируют количественная оценка и равенство. Они отличаются от полиадические алгебры в том, что последние не моделируют равенство.

Определение цилиндрической алгебры

А цилиндрическая алгебра размерности ${ displaystyle alpha}$ (куда ${ displaystyle alpha}$ есть ли порядковый номер ) является алгебраической структурой ${ displaystyle (A, +, cdot, -, 0,1, c _ { kappa}, d _ { kappa lambda}) _ { kappa, lambda < alpha}}$ такой, что ${ Displaystyle (А, +, cdot, -, 0,1)}$ это Булева алгебра, ${ displaystyle c _ { kappa}}$ унарный оператор на ${ displaystyle A}$ для каждого ${ displaystyle kappa}$ (называется цилиндрификация), и ${ displaystyle d _ { kappa lambda}}$ выдающийся элемент ${ displaystyle A}$ для каждого ${ displaystyle kappa}$ и ${ displaystyle lambda}$ (называется диагональ) такие, что имеют место следующие условия:

(C1) ${ displaystyle c _ { kappa} 0 = 0}$

(C2) ${ Displaystyle х leq с _ { каппа} х}$

(C3) ${ displaystyle c _ { kappa} (x cdot c _ { kappa} y) = c _ { kappa} x cdot c _ { kappa} y}$

(C4) ${ displaystyle c _ { kappa} c _ { lambda} x = c _ { lambda} c _ { kappa} x}$

(C5) ${ Displaystyle д _ { каппа каппа} = 1}$

(C6) Если ${ displaystyle kappa notin { lambda, mu }}$, тогда ${ displaystyle d _ { lambda mu} = c _ { kappa} (d _ { lambda kappa} cdot d _ { kappa mu})}$

(C7) Если ${ displaystyle kappa neq lambda}$, тогда ${ displaystyle c _ { kappa} (d _ { kappa lambda} cdot x) cdot c _ { kappa} (d _ { kappa lambda} cdot -x) = 0}$

Предполагая представление логики первого порядка без функциональных символов, Оператор ${ displaystyle c _ { kappa} x}$ модели экзистенциальная количественная оценка сверх переменной ${ displaystyle kappa}$ в формуле ${ displaystyle x}$ в то время как оператор ${ displaystyle d _ { kappa lambda}}$ моделирует равенство переменных ${ displaystyle kappa}$ и ${ displaystyle lambda}$. Отныне, переформулированные с использованием стандартных логических обозначений, аксиомы читаются как

(C1) ${ Displaystyle существует каппа. { mathit {false}} iff { mathit {false}}}$

(C2) ${ Displaystyle х подразумевает существует kappa .x}$

(C3) ${ Displaystyle существует каппа. (х клин существует каппа. у) если и только если ( существует каппа. х) клин ( существует каппа. у)}$

(C4) ${ Displaystyle существует каппа существует лямбда. х если и только существует лямбда существует каппа. х}$

(C5) ${ Displaystyle каппа = каппа iff { mathit {истина}}}$

(C6) Если ${ displaystyle kappa}$ переменная отличается от обоих ${ displaystyle lambda}$ и ${ displaystyle mu}$, тогда ${ Displaystyle лямбда = му если существует каппа. ( лямбда = каппа клин каппа = му)}$

(C7) Если ${ displaystyle kappa}$ и ${ displaystyle lambda}$ - разные переменные, то ${ Displaystyle существует каппа. ( каппа = лямбда клин х) клин существует каппа. ( каппа = лямбда клин отр х) iff { mathit {false}}}$

Цилиндрические алгебры множеств

А цилиндрическая алгебра множеств размерности ${ displaystyle alpha}$ является алгебраической структурой ${ displaystyle (A, чашка, cap, -, emptyset, X ^ { alpha}, c _ { kappa}, d _ { kappa lambda}) _ { kappa, lambda < alpha}}$ такой, что ${ displaystyle langle X ^ { alpha}, A rangle}$ это поле наборов, ${ displaystyle c _ { kappa} S}$ дан кем-то ${ Displaystyle {Y в Икс ^ { альфа} середина существует х в S forall beta neq kappa у ( бета) = х ( бета) }}$, и ${ displaystyle d _ { kappa lambda}}$ дан кем-то ${ Displaystyle {х ин Икс ^ { альфа} середина х ( каппа) = х ( лямбда) }}$.^[1] Это обязательно подтверждает аксиомы C1 – C7 цилиндрической алгебры с ${ Displaystyle чашка}$ вместо ${ displaystyle +}$, ${ displaystyle cap}$ вместо ${ displaystyle cdot}$, установить дополнение для дополнения, пусто установить как 0, ${ displaystyle X ^ { alpha}}$ как единица, и ${ displaystyle substeq}$ вместо ${ displaystyle leq}$. Набор Икс называется основание.

Не всякая цилиндрическая алгебра имеет представление как цилиндрическая алгебра множеств.^{[нужна цитата ][пример необходим ]} Легче связать семантику логики предикатов первого порядка с цилиндрической алгеброй множеств. (Подробнее см. дальнейшее чтение раздел.)

Обобщения

Цилиндрические алгебры обобщены на случай разносторонняя логика (Caleiro and Gonçalves 2006), что позволяет лучше моделировать двойственность между формулами и терминами первого порядка.

Связь с монадической булевой алгеброй

Когда ${ Displaystyle альфа = 1}$ и ${ displaystyle kappa, lambda}$ ограничены значением только 0, то ${ displaystyle c _ { kappa}}$ становится ${ Displaystyle существует}$, диагонали можно опустить, и следующая теорема цилиндрической алгебры (Пинтер, 1973):

${ Displaystyle с _ { каппа} (х + у) = с _ { каппа} х + с _ { каппа} у}$

превращается в аксиому

${ Displaystyle существует (х + у) = существует х + существует у}$

из монадическая булева алгебра. Аксиома (C4) выпадает. Таким образом, монадическую булеву алгебру можно рассматривать как ограничение цилиндрической алгебры на случай одной переменной.

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

• Абстрактная алгебраическая логика
• Лямбда-исчисление и Комбинаторная логика —Другие подходы к моделированию количественной оценки и исключения переменных
• Гипердоктрины площадь категоричный формулировка цилиндрических алгебр
• Алгебры отношений (РА)
• Полиадическая алгебра

Примечания

Рекомендации

• Чарльз Пинтер (1973). «Простая алгебра логики первого порядка». Журнал формальной логики Нотр-Дам. XIV: 361–366.
• Леон Хенкин, Монк, Д.Д., и Альфред Тарский (1971) Цилиндрические алгебры, часть I. Северная Голландия. ISBN  978-0-7204-2043-2.
• Леон Хенкин, Монк, Джей Ди, и Альфред Тарски (1985) Цилиндрические алгебры, часть II.. Северная Голландия.
• Робин Хирш и Ян Ходкинсон (2002) Алгебры отношений по играм Исследования по логике и основам математики, Северная Голландия
• Карлос Калейро, Рикардо Гонсалвеш (2006). «Об алгебраизации многомерных логик» (PDF). В J. Fiadeiro и P.-Y. Schobbens (ред.). Proc. 18 инт. конф. о последних тенденциях в методах алгебраического развития (WADT). LNCS. 4409. Springer. С. 21–36. ISBN  978-3-540-71997-7.

дальнейшее чтение

• Имелиньски, Т.; Липски, В. (1984). «Реляционная модель данных и цилиндрические алгебры». Журнал компьютерных и системных наук. 28: 80–102. Дои:10.1016/0022-0000(84)90077-1.

внешняя ссылка

• пример цилиндрической алгебры автор: CWoo на сайте planetmath.org