Algebra Heytinga

Algebra Heytinga – typ struktury algebraicznej, uogólnienie algebry Boole’a polegające na odrzuceniu trzech aksjomatów:

• prawa wyłączonego środka $p\vee \lnot p=1;$
• prawa podwójnej negacji $\lnot \lnot p=p;$
• pierwszego prawa de Morgana $\lnot (p\wedge q)=\lnot p\vee \lnot q.$

Ten typ algebr wprowadził Arend Heyting (1930) w celu zbudowania formalnego narzędzia dla logiki intuicjonistycznej, którą stworzyła holenderska szkoła logików inspirowana przez L.E.J. Brouwera. Jednakże sam Brouwer był przeciwny wszelkiej formalizacji jego idei intuicjonizmu, w szczególności używania takich narzędzi, jakie proponował jego uczeń Heyting. Zakwestionowanie prawa wyłączonego środka i prawa podwójnej negacji wynikało z ogólnych założeń filozoficznych Brouwera dotyczących tego, czym jest matematyka i jakiego typu rozumowania są w niej dopuszczalne.

Obecnie większość badań dotyczących algebr Heytinga nie jest związana z logiką i intuicjonizmem. Traktuje się je jako pewien typ struktur matematycznych, część algebry lub dział teorii kategorii. Rozmaite, równoważne podejścia do teorii algebr Heytinga mogą być sformułowane w ramach teorii częściowego porządku, algebry ogólnej (zwanej też algebrą uniwersalną), topologii ogólnej oraz w języku funktorów sprzężonych w pewnych specjalnych kategoriach. W teoriach tych rozumowania dotyczące algebr Heytinga są oparte na logice klasycznej (z prawem wyłączonego środka, nieintuicjonistycznej).

Definicje

Algebra Heytinga (zwana też algebrą pseudoboolowską) zdefiniowana w języku częściowego porządku to krata dystrybutywna mająca element najmniejszy 0, element największy 1, w której jest dodatkowo dane działanie dwuargumentowe implikacji $\to$ spełniające następujący warunek:

(H)     nierówność $p\wedge q\leqslant r$ jest równoważna nierówności      $p\leqslant q\to r.$

Tutaj symbol typu $p\to q$ nie oznacza zdania (które mogłoby być prawdziwe lub fałszywe), lecz pewien element zbioru $L,$ podobnie jak elementy $p\wedge q$ i $p\vee r.$ Symbol $\to$ oznacza więc pewną funkcję z $L\times L$ w $L.$ Przy interpretowaniu napisów takich jak $p\land q\leqslant r,$ symbol $p\land q$ można traktować jako koniunkcję, a symbol $s\leqslant r$ jako potocznie rozumiane: $s$ pociąga $r$ (przez analogię z relacją zawierania: $S\subseteq R$).

Negację (zwaną też pseudodopełnieniem) określa się wzorem: $\lnot p=p\to 0.$

Można też zdefiniować algebrę Heytinga jako kratę $L$ z elementami 0 i 1, spełniającą warunek: dla dowolnych $p,r\in L$ istnieje element największy w zbiorze tych $q,$ dla których $p\wedge q\leqslant r;$ ten największy element $q$ jest zwany relatywnym pseudodopełnieniem elementu $p$ względem $r$ i jest oznaczany symbolem $p\to r$.

W języku algebr ogólnych algebra Heytinga jest strukturą $A=\langle L,\vee ,\wedge ,\to ,0,1\rangle$ z trzema działaniami dwuargumentowymi $\vee ,\wedge ,\to$ z $L\times L$ w $L,$ w której $A=\langle L,\vee ,\wedge ,0,1\rangle$ jest kratą dystrybutywną z elementami $0,1,$ z uporządkowaniem $x\leqslant y$ zdefiniowanym w terminach pierwotnych przez warunek $x\vee y=y,$ a działanie $\to$ spełnia warunek (H). Ponadto dla dowolnych elementów $x,y$ nierówność $x\leqslant y$ zachodzi wtedy i tylko wtedy, gdy $x\to y=1.$

Algebry Heytinga tworzą klasę algebr definiowalnych równościowo – ich system aksjomatów, w tym warunek (H), da się zapisać w postaci skończonej liczby aksjomatów mających postać równości.

Własności algebr Heytinga

W każdej algebrze Heytinga dla dowolnych $p,q,r\in L$ oprócz warunku (H) spełnione są następujące warunki:

$\lnot 0=1,\qquad \lnot 1=0,\qquad \lnot (p\vee q)\leqslant \lnot p,\qquad p\wedge \lnot p=0,$

$\lnot \lnot p\geqslant p,\qquad \lnot \lnot \lnot p=\lnot p,\qquad \lnot \lnot (p\vee \lnot p)=1.$

Działanie dwuargumentowe $\to$ spełnia następujące warunki:

$p\to q\leqslant p\to (q\vee r),\qquad (p\vee r)\to q\leqslant p\to q,$

$p\to p=1,\qquad p\wedge (p\to q)=p\wedge q,$

$p\to (q\wedge r)=(p\to q)\wedge (p\to r),\qquad q\leqslant p\to q.$

W algebrach Heytinga prawdziwe jest tylko drugie prawo de Morgana w postaci równości $\lnot (p\vee q)=\lnot p\wedge \lnot q,$ pierwsze zaś prawo ma znacznie słabszą postać:

$\lnot (p\wedge q)=\lnot \lnot (\lnot p\vee \lnot q).$

Algebra Heytinga $L$ jest algebrą Boole’a wtedy i tylko wtedy, gdy zachodzi w niej prawo podwójnej negacji $\lnot \lnot p=p,$ a także wtedy i tylko wtedy, gdy zachodzi prawo wyłączonego środka $p\vee \lnot p=1.$

Każda algebra Boole’a (w szczególności każde ciało zbiorów) jest algebrą Heytinga z działaniem $p\to q$ zdefiniowanym jako $\lnot p\vee q.$ Jednakże równość $p\to q=\lnot p\vee q$ nie jest na ogół spełniona w algebrach Heytinga, bowiem zawsze $p\to p=1,$ a $\lnot p\vee p$ może nie być równe 1.

Jeżeli $L$ jest kratą z największym elementem 1 i z uporządkowaniem całkowitym (zwanym również liniowym, tzn. $L$ jest zarazem łańcuchem, w którym każde dwa elementy $p,q$ są porównywalne), to $L$ staje się algebrą Heytinga, gdy $p\to q$ określimy jako równe 1 w przypadku $p\leqslant q$ i jako $q$ w przypadku przeciwnym $p>q$.

Algebra Heytinga zbiorów otwartych przestrzeni topologicznej

Tak jak typowym przykładem algebry Boole’a jest ciało podzbiorów dowolnego ustalonego zbioru $X$ wraz z częściowym porządkiem wyznaczonym przez relację inkluzji $\subseteq$ i z działaniami na zbiorach $\cup ,\cap ,\setminus$ jako operacjami algebraicznymi, tak typowym przykładem algebry Heytinga jest krata ${\mathcal {O}}$ wszystkich podzbiorów otwartych przestrzeni topologicznej $X$ (oznaczanej w tej algebrze symbolem $1$) ze zwykłymi działaniami $\cup ,\cap$ oraz z działaniami $\to ,\neg$ zdefiniowanymi jako

$A\to B={\mathrm {Int} }[(1\setminus A)\cup B]$ oraz $\neg A={\mathrm {Int} }(1\setminus A)$ dla $A,B\in {\mathcal {O}},$

gdzie $\mathrm {Int} (A)=1\setminus {\overline {(1\setminus A)}}$ oznacza wnętrze zbioru $A,$ a ${\overline {E}}$ oznacza domknięcie zbioru $E.$ To, że w takiej algebrze Heytinga $\neg (\neg A)$ może być różne od $A,$ pokazuje następujący przykład. Niech $X$ oznacza płaszczyznę kartezjańską $\mathbb {R} ^{2}$ i niech $A=\{(x,y)\in \mathbb {R} ^{2}|0<x^{2}+y^{2}<1\}$ oznacza koło otwarte bez środka. Wówczas dopełnieniem zbioru $A$ jest zbiór $E=\{(x,y)|x^{2}+y^{2}\geqslant 1\}$ z dołączonym punktem izolowanym $(0,0),$ zatem $\neg A={\mathrm {Int} }(E)=\{(x,y)|x^{2}+y^{2}>1\},$ skąd wynika, że $\neg (\neg A)=\{(x,y)|x^{2}+y^{2}<1\}\neq A.$

Każdy element $A$ algebry Heytinga ${\mathcal {O}}$ spełnia warunek $A\subseteq \neg \neg A,$ równość zaś zachodzi wtedy i tylko wtedy, gdy $A$ jest dziedziną otwartą (zbiór $A$ nazywa się dziedziną otwartą, gdy spełnia warunek $A={\mathrm {Int} }({\overline {A}})$).

Algebra Heytinga ${\mathcal {O}}$ jest algebrą Boole’a wtedy i tylko wtedy, gdy topologia ${\mathcal {O}}$ jest dyskretna, tzn. ${\mathcal {O}}$ jest rodziną $\mathbf {2} ^{X}$ wszystkich podzbiorów zbioru $X.$

Reprezentacja algebr Heytinga w topologicznych algebrach Boole’a

Topologiczna algebra Boole’a to algebra Boole’a ${\mathfrak {A}}$ wraz z dodatkową strukturą operatora wnętrza $\mathbf {I} \colon {\mathfrak {A}}\to {\mathfrak {A}}$ określoną aksjomatycznie przez następujące warunki:

$\mathbf {I} (A\cap B)=\mathbf {I} (A)\cap \mathbf {I} (B),\quad \mathbf {I} (A)\subseteq A,\quad \mathbf {I} (1)=1,\quad \mathbf {I} (\mathbf {I} (A))=\mathbf {I} (A)$

dla $A,B\in {\mathfrak {A}}.$ Jest to uogólnienie operacji wnętrza $\mathrm {Int}$ w przestrzeni topologicznej. Element $A\in {\mathfrak {A}}$ nazywa się otwartym, jeżeli $\mathbf {I} (A)=A,$ jego dopełnienie nazywa się domknięte, a operator domknięcia $\mathbf {C} \colon {\mathfrak {A}}\to {\mathfrak {A}}$ zdefiniowany jako $\mathbf {C} (A)=1\setminus \mathbf {I} (1\setminus A)$ spełnia warunki analogiczne do aksjomatów Kuratowskiego przestrzeni topologicznej:

$\mathbf {C} (A\cup B)=\mathbf {C} A\cup \mathbf {C} B,\quad A\subseteq \mathbf {C} A,\quad \mathbf {C} (\emptyset )=\emptyset ,\quad \mathbf {C} (\mathbf {C} (A))=\mathbf {C} (A).$

W topologicznych algebrach Boole’a prawdziwe są te wszystkie zdania o przestrzeniach topologicznych, które dadzą się wywieść z aksjomatów wnętrza $\mathrm {Int}$ bądź z aksjomatów domknięcia Kuratowskiego bez używania pojęcia elementu $x\in A.$

Topologiczne algebry Boole’a można zaliczyć do szerszej dziedziny topologii bezpunktowej, do której należą różnorakie obiekty matematyczne, rozpatrywane w nieprzekładalnych wzajemnie bezpośrednio ujęciach różnych teorii.

Krata ${\mathcal {O}}({\mathfrak {A}})$ wszystkich elementów otwartych w topologicznej algebrze Boole’a ${\mathfrak {A}}$ jest algebrą Heytinga. Odwrotnie, prawdziwe jest następujące twierdzenie o reprezentacji McKinseya i Tarskiego: dla każdej algebry Heytinga $L$ istnieje topologiczna algebra Boole’a ${\mathfrak {A}}$ taka, że $L$ jest izomorficzna z algebrą ${\mathcal {O}}({\mathfrak {A}})$.

Algebry Heytinga w teorii kategorii

Każda krata $L$ jest zbiorem częściowo uporządkowanym, może więc być traktowana jako kategoria. W tym ujęciu krata $L$ jest algebrą Heytinga, jeśli istnieje w niej obiekt początkowy 0, obiekt końcowy 1 i jest na niej określona struktura kategorii kartezjańsko zamkniętej, tzn. dla każdego $a\in L$ funktor $\Phi _{a}$ z $L$ w $L$ o przyporządkowaniu obiektowym $\Phi _{a}(b)=a\wedge b$ jest lewym sprzężonym funktora $\Psi _{a}$ o przyporządkowaniu obiektowym $\Psi _{a}(b)=a\to b.$ Warunek (H), tzn. równoważność nierówności $p\wedge q\leqslant r$ i $p\leqslant q\to r,$ tłumaczy się bezpośrednio na warunek sprzężoności tych funktorów. Wymienione wyżej tożsamości i nierówności dla algebr Heytinga mogą być wyprowadzone z ogólnych własności funktorów sprzężonych.

Linki zewnętrzne

• RamonR. Jansana RamonR., Algebraic Propositional Logic, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 12 grudnia 2016, ISSN 1095-5054 [dostęp 2018-01-10]  (ang.).
• Chapter 3. Algebras for Logic, [w:] Handouts – Autumn 2003-04 [online], 2003 [dostęp 2018-04-25] .
• autorzy nLab, Heyting algebra in nLab [online] [dostęp 2018-01-11] .
• Pseudo-Boolean algebra (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].