Algebra Heytinga – Wikipedia, wolna encyklopedia

Algebra Heytinga – pewien typ struktury algebraicznej, rodzaj algebry ogólnej, uogólnienie pojęcia algebry Boole’a polegające na odrzuceniu z systemu aksjomatów prawa wyłączonego środka ${\displaystyle p\vee \lnot p=1,}$ odrzuceniu prawa podwójnej negacji ${\displaystyle \lnot \lnot p=p}$ oraz na odrzuceniu pierwszego prawa de Morgana ${\displaystyle \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^[a].

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[edytuj | edytuj kod]

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

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

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

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

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

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

Własności algebr Heytinga[edytuj | edytuj kod]

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

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

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

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

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

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

${\displaystyle 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 ${\displaystyle \lnot (p\vee q)=\lnot p\wedge \lnot q,}$ pierwsze zaś prawo ma znacznie słabszą postać:

${\displaystyle \lnot (p\wedge q)=\lnot \lnot (\lnot p\vee \lnot q).}$

Algebra Heytinga ${\displaystyle L}$ jest algebrą Boole’a wtedy i tylko wtedy, gdy zachodzi w niej prawo podwójnej negacji ${\displaystyle \lnot \lnot p=p,}$ a także wtedy i tylko wtedy, gdy zachodzi prawo wyłączonego środka ${\displaystyle 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 ${\displaystyle p\to q}$ zdefiniowanym jako ${\displaystyle \lnot p\vee q.}$ Jednakże równość ${\displaystyle p\to q=\lnot p\vee q}$ nie jest na ogół spełniona w algebrach Heytinga, bowiem zawsze ${\displaystyle p\to p=1,}$ a ${\displaystyle \lnot p\vee p}$ może nie być równe 1.

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

Algebra Heytinga zbiorów otwartych przestrzeni topologicznej[edytuj | edytuj kod]

 Osobny artykuł: Topologiczna algebra Heytinga.

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

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

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

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

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

Reprezentacja algebr Heytinga w topologicznych algebrach Boole’a[edytuj | edytuj kod]

 Osobny artykuł: Twierdzenie o reprezentacji algebr Heytinga.

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

${\displaystyle \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 ${\displaystyle A,B\in {\mathfrak {A}}.}$ Jest to uogólnienie operacji wnętrza ${\displaystyle \mathrm {Int} }$ w przestrzeni topologicznej^[6][5]. Element ${\displaystyle A\in {\mathfrak {A}}}$ nazywa się otwartym, jeżeli ${\displaystyle \mathbf {I} (A)=A,}$ jego dopełnienie nazywa się domknięte, a operator domknięcia ${\displaystyle \mathbf {C} \colon {\mathfrak {A}}\to {\mathfrak {A}}}$ zdefiniowany jako ${\displaystyle \mathbf {C} (A)=1\setminus \mathbf {I} (1\setminus A)}$ spełnia warunki analogiczne do aksjomatów Kuratowskiego^[6] przestrzeni topologicznej:

${\displaystyle \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 ${\displaystyle \mathrm {Int} }$ bądź z aksjomatów domknięcia Kuratowskiego bez używania pojęcia elementu ${\displaystyle 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^[7][8].

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

Algebry Heytinga w teorii kategorii[edytuj | edytuj kod]

Każda krata ${\displaystyle L}$ jest zbiorem częściowo uporządkowanym, może więc być traktowana jako kategoria. W tym ujęciu krata ${\displaystyle 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 ${\displaystyle a\in L}$ funktor ${\displaystyle \Phi _{a}}$ z ${\displaystyle L}$ w ${\displaystyle L}$ o przyporządkowaniu obiektowym ${\displaystyle \Phi _{a}(b)=a\wedge b}$ jest lewym sprzężonym funktora ${\displaystyle \Psi _{a}}$ o przyporządkowaniu obiektowym ${\displaystyle \Psi _{a}(b)=a\to b.}$ Warunek (H), tzn. równoważność nierówności ${\displaystyle p\wedge q\leqslant r}$ i ${\displaystyle 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^[2][10].

Uwagi[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

• 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].