Цилиндрическая алгебра

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

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

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

(С1) $c_{\kappa }0=0$

(С2) $x\leq c_{\kappa }x$

(С3) $c_{\kappa }(x\cdot c_{\kappa }y)=c_{\kappa }x\cdot c_{\kappa }y$

(С4) $c_{\kappa }c_{\lambda }x=c_{\lambda }c_{\kappa }x$

(С5) $d_{\kappa \kappa }=1$

(С6) Если $\kappa \notin \{\lambda ,\mu \}$, затем $d_{\lambda \mu }=c_{\kappa }(d_{\lambda \kappa }\cdot d_{\kappa \mu })$

(С7) Если $\kappa \neq \lambda$, затем $c_{\kappa }(d_{\kappa \lambda }\cdot x)\cdot c_{\kappa }(d_{\kappa \lambda }\cdot -x)=0$

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

(С1) $\exists \kappa .{\mathit {false}}\iff {\mathit {false}}$

(С2) $x\implies \exists \kappa .x$

(С3) $\exists \kappa .(x\wedge \exists \kappa .y)\iff (\exists \kappa .x)\wedge (\exists \kappa .y)$

(С4) $\exists \kappa \exists \lambda .x\iff \exists \lambda \exists \kappa .x$

(С5) $\kappa =\kappa \iff {\mathit {true}}$

(С6) Если $\kappa$ это переменная, отличная от обеих $\lambda$ и $\mu$, затем $\lambda =\mu \iff \exists \kappa .(\lambda =\kappa \wedge \kappa =\mu )$

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

Алгебры цилиндрических множеств

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

Представление цилиндрической алгебры — это изоморфизм этой алгебры алгебре цилиндрических множеств. Не каждая цилиндрическая алгебра имеет представление в виде алгебры цилиндрических множеств. Семантику логики предикатов первого порядка проще связать с алгеброй цилиндрических множеств. (Подробнее см. § Дополнительная литература .)

Обобщения

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

с монадической

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

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

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

$\exists (x+y)=\exists x+\exists y$

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

См. также

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

Ссылки

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

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

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

Внешние ссылки

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