Алгебра Гейтинга: различия между версиями

Интерактивная навигация по истории

[отпатрулированная версия]

← Предыдущая правка

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Текущая версия от 16:29, 16 июля 2024

Алгебра Гейтинга (псевдобулева алгебра) — импликативная решётка с наименьшим элементом $0$ .

Наряду с другими подклассами импликативных решёток впервые отмечены Скулемом в 1919 году^[1]; широкое применение получили после того, как Гейтинг в 1930 году предложил их как модель интуиционистского исчисления высказываний (так же, как булева алгебра является моделью классического исчисления высказываний). С точки зрения логики высказываний, относительное псевдодополнение $a\rightarrow b$ в решётке Гейтинга — слабейшее высказывание, для которого имеет правило вывода modus ponens (то есть $(a\land (a\rightarrow b))\leqslant b$ .

Как и во всякой импликативной решётке в алгебре Гейтинга однозначно вводятся наибольший элемент:

1:=a\rightarrow a

,

и унарная операция абсолютного псевдодополнения:

\neg a:=a\rightarrow 0

.

Булева алгебра — алгебра Гейтинга, в которой абсолютное псевдодополнение является абсолютным дополнением: $a\lor \neg a=1$ (исключённое третье) или, что эквивалентно, $\neg \neg a=a$ (двойное отрицание).

Класс алгебр Гейтинга может быть задан как многообразие алгебраических систем типа $\langle L;0,\land ,\lor ,\rightarrow \rangle$ (с сигнатурой $\langle 0,2,2,2\rangle$ ) конечным числом тождеств.

Пример алгебры Гейтинга — единичный отрезок $[0,1]$ с $\lor =\max$ и $\land =\min$ и относительным псевдодополнением, определяемым следующим образом: $a\rightarrow b=1$ , если $a\leqslant b$ и $a\rightarrow b=b$ в ином случае. Другой важный пример — семейство подмножеств заданного множества $M$ , упорядоченное по включению, оно образует полную алгебру Гейтинга; всякая её подалгебра будет топологией на $M$ , кроме того, всякая топология на $M$ образует полную алгебру Гейтинга, в связи с этим полные алгебры Гейтинга играют ключевую роль в бесточечной топологии^[англ.].

Внутренняя логика элементарного топоса основана на гейтинговой алгебре подобъектов терминального объекта $1$ , упорядоченных по включению (или, эквивалентно, алгебре морфизмов из $1$ в классификатор подобъектов).

Свойства

В алгебрах Гейтинга выполняется свойство бесконечной дистрибутивности:

a\land \bigvee B=\bigvee \{a\land b\mid b\in B\}

,

где $B$ — подмножество носителя алгебры, имеющее верхнюю грань. Если дистрибутивная решётка полна (то есть верхняя грань $B$ существует), то из выполнения свойства бесконечной дистрибутивности следует, что она является алгеброй Гейтинга. Каждая конечная дистрибутивная решётка полна, таким образом, является алгеброй Гейтинга.

Если в алгебре Гейтинга верхняя грань $\bigvee A$ существует, то выполняется тождество:

\neg \bigvee A=\bigwedge \neg A

.

Также имеет место соотношение:

\neg \bigwedge A\leqslant \bigwedge \neg A

при условии, что соответствующие грани существуют.

В алгебрах Гейтинга действует закон тройного отрицания: $\neg \neg \neg a=\neg a$ . Элемент, для которого снимается двойное отрицание ( $\neg \neg a=a$ ) называется регулярным; соответственно, алгебра Гейтинга, все элементы которой регулярны — булева.

В гейтинговых алгебрах имеет место один закон де Моргана:

\neg (a\lor b)=\neg a\land \neg b

,

вместо второго закона де Моргана выполняется более слабое соотношение:

\neg (a\land b)=\neg \neg (\neg a\lor \neg b)

.

Алгебра Гейтинга, в которой выполняются оба закона де Моргана, моделирует логику Янкова — логику из класса промежуточных логик^[англ.].

Подрешётка $H_{g}$ алгебры Гейтинга $H$ , образованная всеми элементами, предшествующими $g$ ( $H_{g}=\{a\mid a\leqslant g\}$ ) является алгеброй Гейтинга с абсолютным псведодополнением $\neg _{g}a=g\land \neg a$ и относительным псевдодополнением $a\rightarrow _{g}b=g\land (a\rightarrow b)$ ; $a\mapsto g\land a$ является гомоморфизмом из $H\rightarrow H_{g}$ , сохраняющим верхние и нижние грани (в том числе для бесконечных подмножеств).

Для всякой гейтинговой алгебры $H$ существует изоморфная ей полная алгебра Гейтинга $H^{\star }$ .

Примечания

↑ Thoralf Skolem, Jens Erik Fenstad. Selected works in logic. — Oslo: Universitetsforlaget, 1970. — 732 p. — ISBN 9788200061274.

Литература

Псевдобулева алгебра — статья из Математической энциклопедии. Гришин В. Н.
Драгалин А. Г. Математический интуиционизм. Введение в теорию доказательств. — М.: Наука, 1979. — 256 с. — (Математическая логика и основания математики).
Плиско В. Е., Хаханян В. Х. Интуиционистская логика. — М.: Мехмат МГУ, 2009. — 159 с.
Расёва Е., Сикорский Р. IV. Псевдобулевы алгебры // Математика метаматематики. — М.: Наука, 1972. — С. 147—170.

[1] Thoralf Skolem, Jens Erik Fenstad. Selected works in logic. — Oslo: Universitetsforlaget, 1970. — 732 p. — ISBN 9788200061274.

[1]

@@ Строка 1: / Строка 1: @@
+'''Алгебра Гейтинга''' (''псевдобулева алгебра'') — [[импликативная решётка]] с наименьшим элементом <math>0</math>.
-[[Файл:Join and meet.svg|мини|Д[[Диаграмма Хассе|иаграмма Хассе]], состоящая из 4 элементов: '''a''' и '''b''', максимального элемента '''a ∨ b''', минимального элемента '''a ∧ b''']]
-'''Алгебра Гейтинга''', также известная как '''псевдобулева алгебра'''<ref>[https://www.encyclopediaofmath.org/index.php/Pseudo-Boolean_algebra "Pseudo-Boolean algebra - Encyclopedia of Mathematics".]</ref> '''—''' ограниченная [[Решётка (алгебра)|решётка]] (с операциями [[Операция соединения (реляционная алгебра)|соединения]] (англ.яз ''join)'' и встречи (англ.яз ''meet''), записываемые как <math>\lor</math> и <math>\land</math>, с наименьшим элементом <math>0</math> и наибольшим элементом <math>1</math>) с [[Бинарная операция|бинарной операцией]] <math>a \rightarrow b</math> [[Импликация|импликации]], такой, что <math>(c \land a) \leq b</math> [[Отношение эквивалентности|эквивалентно]] <math>c \leq (a \rightarrow b)</math>. С логической точки зрения, <math>A \rightarrow B</math> — это, согласно этому определению, самая слабая пропозиция, для которой действует [[modus ponens]], [[правило вывода]] <math>A \rightarrow B</math>, <math>A \vdash B</math>. Как и [[Булева алгебра|булевы алгебры]], алгебры Гейтинга образуют аксиоматизируемое многообразие с конечным числом уравнений. Алгебры Гейтинга были введены [[Аренд Гейтинг|Арендом Гейтингом]] (1930) для формализации [[Интуиционистская логика|интуиционистской логики]].
+Наряду с другими подклассами импликативных решёток впервые отмечены [[Скулем, Туральф|Скулемом]] в [[1919 год в науке|1919 году]]<ref>{{книга
-Алгебры Гейтинга — это [[Дистрибутивная решётка (алгебра)|дистрибутивные решётки]]. Каждая булева алгебра является алгеброй Гейтинга, когда <math>a \rightarrow b</math> определяется как <math>\neg a \lor b</math>'','' как и каждая полная дистрибутивная решётка, удовлетворяющая одностороннему бесконечному дистрибутивному закону, когда <math>a \rightarrow b</math> принимается за [[Максимальный элемент|максимум]] множества всех <math>c</math>, для которых <math>c \land a \leq b</math>. В конечномерном случае каждая непустая дистрибутивная решётка, в частности, каждая непустая конечная цепочка, автоматически является полной и полностью дистрибутивной, а значит, алгеброй Гейтинга.
+ | автор         = Thoralf Skolem, Jens Erik Fenstad
+ | заглавие      = Selected works in logic
+ | ссылка       = https://archive.org/details/selectedworksinl0000thsk
+ | место         = Oslo
+ | издательство  = Universitetsforlaget
+ | год           = 1970
+ | allpages      = 732
+ | isbn          = 9788200061274
+}}</ref>; широкое применение получили после того, как [[Гейтинг, Аренд|Гейтинг]] в [[1930 год в науке|1930 году]] предложил их как модель [[Интуиционистская логика|интуиционистского исчисления высказываний]] (так же, как [[булева алгебра]] является моделью классического исчисления высказываний). С точки зрения логики высказываний, [[относительное псевдодополнение]] <math>a \rightarrow b</math> в решётке Гейтинга — слабейшее высказывание, для которого имеет правило вывода [[modus ponens]] (то есть <math>(a \and (a \rightarrow b)) \leqslant b</math>.
+Как и во всякой импликативной решётке в алгебре Гейтинга однозначно вводятся наибольший элемент:
-Из определения следует, что <math>1 \leq 0 \rightarrow a</math>, что соответствует интуиции, согласно которой из любого предложения а следует противоречие <math>0</math>. Хотя операция отрицания <math>\neg a</math> не входит в определение, её можно определить как <math>a \rightarrow 0</math>. Интуитивное содержание <math>\neg a</math> состоит в том, что предположение <math>a</math> приводит к противоречию. Определение подразумевает, что <math>a \land \neg a = 0</math>. Далее можно показать, что <math>a \leq \neg\neg a</math>, в общем случае не верно, то есть устранение двойного отрицания в алгебре Гейтинга вообще не выполняется.
+: <math>1 := a \rightarrow a</math>,
+и унарная операция [[абсолютное псевдодополнение|абсолютного псевдодополнения]]:
+: <math>\neg a := a \rightarrow 0</math>.
+[[Булева алгебра]] — алгебра Гейтинга, в которой абсолютное псевдодополнение является [[абсолютное дополнение|абсолютным дополнением]]: <math>a \or \neg a = 1</math> ([[Закон исключённого третьего|исключённое третье]]) или, что эквивалентно, <math>\neg \neg a = a</math> ([[двойное отрицание]]).
+Класс алгебр Гейтинга может быть задан как [[многообразие алгебраических систем]] типа <math>\langle L; 0, \and, \or, \rightarrow \rangle</math> (с [[Сигнатура (математическая логика)|сигнатурой]] <math>\langle 0, 2, 2, 2 \rangle</math>) конечным числом тождеств.
-Алгебры Гейтинга обобщают булевы алгебры в том смысле, что булевы алгебры — это именно алгебры Гейтинга, удовлетворяющие <math>a \lor \neg a = 1</math> ([[Закон исключённого третьего|исключённое третье]]), что эквивалентно <math>\neg\neg a = a</math>. Элементы алгебры Гейтинга <math>H</math> вида <math>\neg a</math> составляют булеву решётку, но в общем случае она не является подалгеброй <math>H</math> (см. ниже).
+Пример алгебры Гейтинга — единичный отрезок <math>[0,1]</math> с <math>\or = \max</math> и <math>\and = \min</math> и относительным псевдодополнением, определяемым следующим образом: <math>a \rightarrow b = 1</math>, если <math>a \leqslant b</math> и <math>a \rightarrow b = b</math> в ином случае. Другой важный пример — семейство подмножеств заданного множества <math>M</math>, упорядоченное по включению, оно образует [[Полная решётка|полную]] алгебру Гейтинга; всякая её подалгебра будет [[открытая топология|топологией]] на <math>M</math>, кроме того, всякая топология на <math>M</math> образует полную алгебру Гейтинга, в связи с этим полные алгебры Гейтинга играют ключевую роль в {{iw|бесточечная топология|бесточечной топологии|en|pointless topology}}.
-Алгебры Гейтинга служат алгебраическими моделями пропозициональной интуиционистской логики так же, как булевы алгебры моделируют пропозициональную классическую логику. Внутренняя логика [[Элементарный топос|элементарного топоса]] основана на алгебре Гейтинга подобъектов [[Начальный объект|терминального объекта]] <math>1</math>, упорядоченных по включению, эквивалентно [[Морфизм|морфизмам]] от <math>1</math> к [[Классификатор подобъектов|классификатору подобъектов]] <math>\Omega</math>.
+Внутренняя логика [[Элементарный топос|элементарного топоса]] основана на гейтинговой алгебре подобъектов [[Терминальный объект|терминального объекта]] <math>1</math>, упорядоченных по включению (или, эквивалентно, алгебре [[морфизм]]ов из <math>1</math> в [[классификатор подобъектов]]).
-[[Открытое множество|Открытые множества]] любого [[Топологическое пространство|топологического пространства]] образуют полную алгебру Гейтинга. Таким образом, полные алгебры Гейтинга становятся центральным объектом изучения в бессмысленной топологии (англ.яз [[:en:Pointless_topology|pointless topology.]]  или же point-free topology).
+== Свойства ==
-Каждая алгебра Гейтинга, множество не самых не самых больших элементов которой имеет самый большой элемент (и образует другую алгебру Гейтинга), является подпрямо (англ.яз ''subdirectly'') несводимой, а значит, каждую алгебру Гейтинга можно сделать подпрямо несводимой, присоединив к ней новый самый большой элемент. Отсюда следует, что даже среди конечных алгебр Гейтинга существует бесконечно много подпрямо несводимых, причем никакие две из них не имеют одинаковой теории уравнений. Следовательно, никакое конечное множество конечных алгебр Гейтинга не может дать все контрпримеры к не-законам алгебры Гейтинга. Это резко отличается от булевых алгебр, единственной подпрямо несводимой из которых является двухэлементная, которая сама по себе, следовательно, достаточна для всех контрпримеров к не-законам булевой алгебры, что является основой для простого метода решения с помощью [[Таблица истинности|таблицы истинности]]. Тем не менее, можно [[Алгоритмическая разрешимость|решить]], справедливо ли уравнения для всех алгебр Гейтинга<ref>Kripke, S. A.: 1965, 'Semantical analysis of intuitionistic logic I'. In: J. N. Crossley and M. A. E. Dummett (eds.): Formal Systems and Recursive Functions. Amsterdam: North-Holland, pp. 92–130.</ref>.
+В алгебрах Гейтинга выполняется свойство бесконечной дистрибутивности:
+: <math>a \and \bigvee B = \bigvee \{a \and b \mid b \in B\}</math>,
+где <math>B</math> — подмножество носителя алгебры, имеющее верхнюю грань. Если [[Дистрибутивная решётка|дистрибутивная]] решётка [[полная решётка|полна]] (то есть верхняя грань <math>B</math> существует), то из выполнения свойства бесконечной дистрибутивности следует, что она является алгеброй Гейтинга. Каждая конечная дистрибутивная решётка полна, таким образом, является алгеброй Гейтинга.
+Если в алгебре Гейтинга верхняя грань <math>\bigvee A</math> существует, то выполняется тождество:
-Реже алгебры Гейтинга называют псевдобулевыми алгебрами или даже решетками Брувера, хотя последний термин может обозначать двойственное определение или иметь несколько более общее значение<ref>Helena Rasiowa; Roman Sikorski (1963). ''The Mathematics of Metamathematics''. Państwowe Wydawnictwo Naukowe (PWN). pp. 54–62, 93–95, 123–130.</ref><ref>A. G. Kusraev; Samson Semenovich Kutateladze (1999). ''Boolean valued analysis''. Springer. p. 12. ISBN <bdi>978-0-7923-5921-0</bdi>.</ref><ref>Yankov, V.A. (2001) [1994], "Brouwer lattice", ''Encyclopedia of Mathematics'', EMS Press</ref><ref>Thomas Scott Blyth (2005). ''Lattices and ordered algebraic structures''. Springer. p. 151. ISBN <bdi>978-1-85233-905-0</bdi>.</ref>.
+: <math>\neg \bigvee A = \bigwedge \neg A</math>.
+Также имеет место соотношение:
+: <math>\neg \bigwedge A \leqslant \bigwedge \neg A</math>
+при условии, что соответствующие грани существуют.
+В алгебрах Гейтинга действует [[закон тройного отрицания]]: <math>\neg \neg \neg a = \neg a</math>.
-== Формальное определение ==
+{{якорь|Регулярный элемент алгебры Гейтинга}}Элемент, для которого снимается двойное отрицание (<math>\neg \neg a = a</math>) называется ''регулярным''; соответственно, алгебра Гейтинга, все элементы которой регулярны — булева.
-Алгебра Гейтинга <math>H</math> — это ограниченная решётка, такая, что для всех <math>a</math> и <math>b</math> в <math>H</math> существует наибольший элемент <math>x</math> из <math>H</math>, такой, что <math display="block">a \land x \leq b</math>Этот элемент является '''относительным псевдодополнением''' <math>a</math> относительно <math>b</math> и обозначается <math>a \rightarrow b</math>. Мы пишем 1 и 0 для самого большого и самого маленького элемента <math>H</math>, соответственно.
+В гейтинговых алгебрах имеет место один [[Законы де Моргана|закон де Моргана]]:
-В любой алгебре Гейтинга можно определить [[псевдодополнение]] <math>\neg a</math> любого элемента <math>a</math>, задав <math>\neg a = (a \rightarrow 0)</math>. По определению, <math>a \land \neg a = 0</math> и <math>\neg a</math> — наибольший элемент, обладающий этим свойством. Однако в общем случае неверно, что <math>a \lor \neg a = 1</math>, поэтому <math>\neg</math> является лишь псевдодополнением, а не истинным дополнением, как это было бы в булевой алгебре.
+: <math>\neg (a \or b) = \neg a \and \neg  b</math>,
+вместо второго закона де Моргана выполняется более слабое соотношение:
+: <math>\neg (a \and b) = \neg \neg (\neg a \or \neg b)</math>.
+Алгебра Гейтинга, в которой выполняются оба закона де Моргана, моделирует [[логика Янкова|логику Янкова]] — логику из класса {{iw|промежуточная логика|промежуточных логик|en|intermediate logic}}.
+[[Подрешётка]] <math>H_g</math> алгебры Гейтинга <math>H</math>, образованная всеми элементами, предшествующими <math>g</math> (<math>H_g = \{a \mid a \leqslant g\}</math>) является алгеброй Гейтинга с абсолютным псведодополнением <math>\neg_g a = g \and \neg a</math> и относительным псевдодополнением <math>a \rightarrow_g b = g \and (a \rightarrow b)</math>; <math>a \mapsto g \and a</math> является [[гомоморфизм]]ом из <math>H \rightarrow H_g</math>, сохраняющим верхние и нижние грани (в том числе для бесконечных подмножеств).
-Полная алгебра Гейтинга — это алгебра Гейтинга, которая является полной решёткой.
+Для всякой гейтинговой алгебры <math>H</math> существует [[Изоморфизм|изоморфная]] ей полная алгебра Гейтинга <math>H^\star</math>.
-'''Подалгеброй''' алгебры Гейтинга <math>H</math> называется подмножество <math>H_1</math> из <math>H</math>, содержащее 0 и 1, и замкнутое по операциям <math>\land</math>, <math>\lor</math> и <math>\rightarrow</math>. Отсюда следует, что оно также замкнуто под <math>\neg</math>. Подалгебра преобразуется в алгебру Гейтинга с помощью индуцированных операций.
+<!--
+Каждая алгебра Гейтинга, множество не самых больших элементов которой имеет наибольший элемент (и образует другую алгебру Гейтинга), является подпрямо несводимой, а значит, каждую алгебру Гейтинга можно сделать подпрямо несводимой, присоединив к ней новый самый большой элемент. Отсюда следует, что даже среди конечных алгебр Гейтинга существует бесконечно много подпрямо несводимых, причём никакие две из них не имеют одинаковой теории уравнений. Следовательно, никакое конечное множество конечных алгебр Гейтинга не может дать все контрпримеры к не-законам алгебры Гейтинга. Это резко отличается от булевых алгебр, единственной подпрямо несводимой из которых является двухэлементная, которая сама по себе, следовательно, достаточна для всех контрпримеров к не-законам булевой алгебры, что является основой для простого метода решения с помощью [[Таблица истинности|таблицы истинности]]. Тем не менее, можно [[Алгоритмическая разрешимость|решить]], справедливо ли уравнения для всех алгебр Гейтинга<ref>Kripke, S. A.: 1965, 'Semantical analysis of intuitionistic logic I'. In: J. N. Crossley and M. A. E. Dummett (eds.): Formal Systems and Recursive Functions. Amsterdam: North-Holland, pp. 92—130.</ref>.
+-->
 == Примечания ==
+{{примечания}}
-<references />
+== Литература ==
+* {{Из|МЭ|заглавие=Псевдобулева алгебра|автор = Гришин В. Н.}}
+* {{книга
+ | автор         = Драгалин А. Г.
+ | заглавие      = Математический интуиционизм. Введение в теорию доказательств
+ | место         = М.
+ | издательство  = [[Наука (издательство)|Наука]]
+ | год           = 1979
+ | страниц       = 256
+ | серия         = Математическая логика и основания математики
+ | ref           = Драгалин
+}}
+* {{книга
+ |автор          = Плиско В. Е., Хаханян В. Х.
+ |заглавие       = Интуиционистская логика
+ |ссылка         = http://lpcs.math.msu.su/~plisko/intlog.pdf
+ |место          = М.
+ |издательство   = Мехмат МГУ
+ |год            = 2009
+ |страниц        = 159
+}}
+* {{книга | автор = Расёва Е., Сикорский Р. | заглавие = Математика метаматематики  | часть = IV. Псевдобулевы алгебры | место = М. | издательство = Наука | год = 1972 | страницы = 147—170}}
+{{ВС}}
 [[Категория:Математика]]

Ссылки на внешние ресурсы
Тематические сайты	MathWorld nLab
В библиографических каталогах	J9U: 987007572533605171 LCCN: sh2010014322

Алгебра Гейтинга: различия между версиями

Текущая версия от 16:29, 16 июля 2024

Свойства

Примечания

Литература

Навигация

Поиск