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

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

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

А цилиндрическая алгебра размерности ${\displaystyle \alpha }$ (куда ${\displaystyle \alpha }$ есть ли порядковый номер ) является алгебраической структурой ${\displaystyle (A,+,\cdot ,-,0,1,c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }}$ такой, что ${\displaystyle (A,+,\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 x\leq c_{\kappa }x}$

(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 d_{\kappa \kappa }=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 \exists \kappa .{\mathit {false}}\iff {\mathit {false}}}$

(C2) ${\displaystyle x\implies \exists \kappa .x}$

(C3) ${\displaystyle \exists \kappa .(x\wedge \exists \kappa .y)\iff (\exists \kappa .x)\wedge (\exists \kappa .y)}$

(C4) ${\displaystyle \exists \kappa \exists \lambda .x\iff \exists \lambda \exists \kappa .x}$

(C5) ${\displaystyle \kappa =\kappa \iff {\mathit {true}}}$

(C6) Если ${\displaystyle \kappa }$ переменная отличается от обоих ${\displaystyle \lambda }$ и ${\displaystyle \mu }$, тогда ${\displaystyle \lambda =\mu \iff \exists \kappa .(\lambda =\kappa \wedge \kappa =\mu )}$

(C7) Если ${\displaystyle \kappa }$ и ${\displaystyle \lambda }$ - разные переменные, то ${\displaystyle \exists \kappa .(\kappa =\lambda \wedge x)\wedge \exists \kappa .(\kappa =\lambda \wedge \neg x)\iff {\mathit {false}}}$

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

А цилиндрическая алгебра множеств размерности ${\displaystyle \alpha }$ является алгебраической структурой ${\displaystyle (A,\cup ,\cap ,-,\emptyset ,X^{\alpha },c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }}$ такой, что ${\displaystyle \langle X^{\alpha },A\rangle }$ это поле наборов, ${\displaystyle c_{\kappa }S}$ дан кем-то ${\displaystyle \{y\in X^{\alpha }\mid \exists x\in S\ \forall \beta \neq \kappa \ y(\beta )=x(\beta )\}}$, и ${\displaystyle d_{\kappa \lambda }}$ дан кем-то ${\displaystyle \{x\in X^{\alpha }\mid x(\kappa )=x(\lambda )\}}$.^[1] Это обязательно подтверждает аксиомы C1 – C7 цилиндрической алгебры с ${\displaystyle \cup }$ вместо ${\displaystyle +}$, ${\displaystyle \cap }$ вместо ${\displaystyle \cdot }$, установить дополнение для дополнения, пусто установить как 0, ${\displaystyle X^{\alpha }}$ как единица, и ${\displaystyle \subseteq }$ вместо ${\displaystyle \leq }$. Набор Икс называется основание.

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

Обобщения

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

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

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

${\displaystyle c_{\kappa }(x+y)=c_{\kappa }x+c_{\kappa }y}$

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

${\displaystyle \exists (x+y)=\exists x+\exists y}$

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

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

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

Примечания

1. Хирш и Ходкинсон с. 167, определение 5.16.

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

• Чарльз Пинтер (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