Algebra Heytinga

Algebra Heytinga

Algebra Heytinga to rodzaj struktury algebraicznej, będący rozszerzeniem algebry Boole’a, które polega na odrzuceniu trzech aksjomatów:

• prawa wyłączonego środka:
  p ∨ ¬p = 1;
• prawa podwójnej negacji:
  ¬¬p = p;
• pierwszego prawa de Morgana:
  ¬(p ∧ q) = ¬p ∨ ¬q.

Typ algebr został wprowadzony przez Arenda Heytinga w 1930 roku jako formalne narzędzie dla logiki intuicjonistycznej, opracowanej przez holenderską szkołę logików inspirowaną przez L.E.J. Brouwera. Jednak sam Brouwer był przeciwny formalizacji jego idei intuicjonizmu, w tym korzystania z narzędzi, które proponował jego uczeń Heyting. Odrzucenie prawa wyłączonego środka oraz podwójnej negacji wynikało z ogólnych założeń filozoficznych Brouwera dotyczących matematyki i rodzaju dopuszczalnych rozumowań.

Obecnie większość badań nad algebrami Heytinga nie jest związana z logiką i intuicjonizmem. Zamiast tego traktuje się je jako typ struktur matematycznych, część algebry lub dział teorii kategorii. Różnorodne równoważne podejścia do teorii algebr Heytinga mogą być formułowane w ramach teorii częściowego porządku, algebry ogólnej (znanej również jako algebra uniwersalna), topologii ogólnej oraz w kontekście funktorów sprzężonych w pewnych specjalnych kategoriach. W tych teoriach rozumowania dotyczące algebr Heytinga bazują na logice klasycznej (z prawem wyłączonego środka, nieintuicjonistycznej).

Definicje

Algebra Heytinga (znana także jako algebra pseudoboolowska) w kontekście teorii częściowego porządku to krata dystrybutywna, która ma element najmniejszy 0 i element największy 1, w której dodatkowo zdefiniowane jest dwuargumentowe działanie implikacji (→), które spełnia następujący warunek:

(H) Nierówność
p ∧ q ⩽ r
jest równoważna nierówności
p ⩽ q → r.

W tym kontekście symbol p → q nie oznacza zdania (które mogłoby być prawdziwe lub fałszywe), lecz pewien element zbioru L, podobnie jak elementy p ∧ q i p ∨ r. Symbol → oznacza więc funkcję z L × L w L.

W interpretacji zapisów takich jak p ∧ q ⩽ r, symbol p ∧ q można traktować jako koniunkcję, a s ⩽ r jako powszechnie rozumiane: s pociąga r (przez analogię z relacją zawierania: S ⊆ R).

Negację (nazywaną także pseudodopełnieniem) definiuje się wzorem: ¬p = p → 0.

Algebrę Heytinga można również zdefiniować jako kratę L z elementami 0 i 1, spełniającą warunek: dla dowolnych p, r ∈ L istnieje element największy w zbiorze tych q, dla których p ∧ q ⩽ r; ten największy element q nazywa się relatywnym pseudodopełnieniem elementu p względem r i oznacza się symbolem p → r.

W języku algebr ogólnych algebra Heytinga jest strukturą A = ⟨L, ∨, ∧, →, 0, 1⟩ z trzema dwuargumentowymi działaniami: ∨, ∧, → oraz L × L w L, w której A = ⟨L, ∨, ∧, 0, 1⟩ jest kratą dystrybutywną z elementami 0, 1, z uporządkowaniem x ⩽ y zdefiniowanym w terminach pierwotnych przez warunek x ∨ y = y, a działanie → spełnia warunek (H). Dodatkowo dla dowolnych elementów x, y nierówność x ⩽ y zachodzi wtedy i tylko wtedy, gdy x → 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 w formie równości.

Własności algebr Heytinga

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

• ¬0 = 1;
• ¬1 = 0;
• ¬(p ∨ q) ⩽ ¬p;
• p ∧ ¬p = 0;
• ¬¬p ⩾ p;
• ¬¬¬p = ¬p;
• ¬¬(p ∨ ¬p) = 1.

Działanie dwuargumentowe → spełnia następujące warunki:

• p → q ⩽ p → (q ∨ r);
• (p ∨ r) → q ⩽ p → q;
• p → p = 1;
• p ∧ (p → q) = p ∧ q;
• p → (q ∧ r) = (p → q) ∧ (p → r);
• q ⩽ p → q.

W algebrze Heytinga tylko drugie prawo de Morgana jest prawdziwe w postaci równości ¬(p ∨ q) = ¬p ∧ ¬q; pierwsze zaś prawo ma znacznie słabszą postać: ¬(p ∧ q) = ¬¬(¬p ∨ ¬q).

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

Każda algebra Boole’a (w tym każde ciało zbiorów) jest algebrą Heytinga z działaniem p → q zdefiniowanym jako ¬p ∨ q. Niemniej jednak równość p → q = ¬p ∨ q nie jest na ogół spełniona w algebrze Heytinga, bowiem zawsze p → p = 1, a ¬p ∨ p może nie być równe 1.

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

Algebra Heytinga zbiorów otwartych przestrzeni topologicznej

Podobnie jak typowym przykładem algebry Boole’a jest ciało podzbiorów dowolnego ustalonego zbioru X z częściowym porządkiem wyznaczonym przez relację inkluzji ⊆ oraz działaniami na zbiorach ∪, ∩, ∖, tak typowym przykładem algebry Heytinga jest krata O wszystkich podzbiorów otwartych przestrzeni topologicznej X (oznaczanej w tej algebrze symbolem 1) ze zwykłymi działaniami ∪, ∩ oraz działaniami →, ¬ zdefiniowanymi jako:

• A → B = Int[(1 ∖ A) ∪ B]
• ¬A = Int(1 ∖ A)

gdzie A, B ∈ O, a Int(A) = 1 ∖ (1 ∖ A) oznacza wnętrze zbioru A, a E̅ oznacza domknięcie zbioru E. To, że w takiej algebrze Heytinga ¬(¬A) może być różne od A, ilustruje następujący przykład. Niech X oznacza płaszczyznę kartezjańską R² i niech A = {(x, y) ∈ R² | 0 < x² + y² < 1} oznacza otwarte koło bez środka. Wówczas dopełnieniem zbioru A jest zbiór E = {(x, y) | x² + y² ≥ 1} z dołączonym punktem izolowanym (0, 0), dlatego ¬A = Int(E) = {(x, y) | x² + y² > 1}, skąd wynika, że ¬(¬A) = {(x, y) | x² + y² < 1} ≠ A.

Każdy element A algebry Heytinga O spełnia warunek A ⊆ ¬¬A, równość zachodzi wtedy i tylko wtedy, gdy A jest dziedziną otwartą (zbiór A nazywa się dziedziną otwartą, gdy spełnia warunek A = Int(A̅)).

Algebra Heytinga O jest algebrą Boole’a wtedy i tylko wtedy, gdy topologia O jest dyskretna, co oznacza, że O jest rodziną 2^X wszystkich podzbiorów zbioru X.

Reprezentacja algebr Heytinga w topologicznych algebrach Boole’a

Topologiczna algebra Boole’a to algebra Boole’a A wraz z dodatkową strukturą operatora wnętrza I:

I: A → A

określoną aksjomatycznie przez następujące warunki:

• I(A ∩ B) = I(A) ∩ I(B);
• I(A) ⊆ A;
• I(1) = 1;
• I(I(A)) = I(A);

dla A, B ∈ A. Jest to uogólnienie operacji wnętrza Int w przestrzeni topologicznej. Element A ∈ A nazywa się otwartym, jeżeli I(A) = A; jego dopełnienie nazywa się domknięte, a operator domknięcia C:

C: A → A

zdefiniowany jako:

C(A) = 1 ∖ I(1 ∖ A)

spełnia warunki analogiczne do aksjomatów Kuratowskiego przestrzeni topologicznej:

• C(A ∪ B) = C(A) ∪ C(B);
• A ⊆ C(A);
• C(∅) = ∅;
• C(C(A)) = C(A);

W topologicznych algebrze Boole’a prawdziwe są wszystkie zdania o przestrzeniach topologicznych, które można wyprowadzić z aksjomatów wnętrza Int lub z aksjomatów domknięcia Kuratowskiego bez używania pojęcia elementu x ∈ 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 O(A) wszystkich elementów otwartych w topologicznej algebrze Boole’a A jest algebrą Heytinga. Z drugiej strony, prawdziwe jest twierdzenie o reprezentacji McKinseya i Tarskiego: dla każdej algebry Heytinga L istnieje topologiczna algebra Boole’a A, taka że L jest izomorficzna z algebrą O(A).

Algebry Heytinga w teorii kategorii

Każda krata L jest zbiorem częściowo uporządkowanym, co pozwala na traktowanie jej jako kategorii. 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 zdefiniowana struktura kategorii kartezjańsko zamkniętej, tzn. dla każdego a ∈ L funktor Φ_a z L w L o przyporządkowaniu obiektowym Φ_a(b) = a ∧ b jest lewym sprzężonym funktora Ψ_a o przyporządkowaniu obiektowym Ψ_a(b) = a → b. Warunek (H), czyli równoważność nierówności p ∧ q ⩽ r i p ⩽ q → r, przekłada się bezpośrednio na warunek sprzężoności tych funktorów. Wymienione tożsamości i nierówności dla algebr Heytinga można wyprowadzić z ogólnych własności funktorów sprzężonych.

Uwagi

Przypisy

Linki zewnętrzne

RamonR. Jansana, 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].