Monadyczna algebra Boole’a

Monadyczna algebra Boole’aalgebra Boole’a z dodatkowym działaniem jednoargumentowym , {\displaystyle \exists ,} które spełnia pewne warunki naśladujące własności kwantyfikatora egzystencjalnego.

Definicja

Monadyczna algebra Boole’a to struktura algebraiczna B = ( B , , , 0 , 1 , , ) {\displaystyle \mathbb {B} =(B,\lor ,\land ,0,1,',\exists )} taka, że:

  • ( B , , , 0 , 1 , ) {\displaystyle (B,\lor ,\land ,0,1,')} jest algebrą Boole’a,
  • funkcja : B B {\displaystyle \exists \colon B\to B} spełnia następujące warunki dla wszystkich p , q B : {\displaystyle p,q\in B{:}}
    1. 0 = 0 {\displaystyle \exists 0=0}
    2. p p {\displaystyle p\leqslant \exists p}
    3. ( p q ) = ( p ) ( q ) {\displaystyle \exists (p\land \exists q)=(\exists p)\land (\exists q)}

Pojęcie monadycznych algebr Boole’a pierwszy wprowadził Paul Halmos. Według niego motywacją do badań tych algebr było pragnienie lepszego rozumienia pewnych aspektów logiki matematycznej.

Elementy domknięte

Operacja {\displaystyle \exists } jest idempotentna: dla każdego p B {\displaystyle p\in B} zachodzi p = p , {\displaystyle \exists \exists p=\exists p,} ponieważ p = ( p p ) = p p = p . {\displaystyle \exists \exists p=\exists (\exists p\land \exists p)=\exists \exists p\land \exists p=\exists p.}

Elementy p {\displaystyle p} spełniające p = p {\displaystyle \exists p=p} (innymi słowy wartości funkcji {\displaystyle \exists } ) nazywa się elementami domkniętymi. Zbiór elementów domkniętych jest podalgebrą Boole’a algebry B . {\displaystyle \mathbb {B} .}

Zbiór elementów domkniętych zawiera pełną informację o funkcji , {\displaystyle \exists ,} dlatego możliwe jest jej odtworzenie na podstawie tego zbioru: niech Z = { q : q B } , {\displaystyle Z=\left\{\exists q\colon q\in B\right\},} wtedy p = min { q Z : p q } . {\displaystyle \exists p=\min \left\{q\in Z\colon p\leqslant q\right\}.}

Przykłady

p = 1

Niech B {\displaystyle \mathbb {B} } będzie algebrą Boole’a. Funkcja : B B {\displaystyle \exists \colon B\to B} zdefiniowana wzorem

p = 1 {\displaystyle \exists p=1} dla każdego p B { 0 } {\displaystyle p\in B\setminus \{0\}}

umożliwia określenie monadycznej algebry Boole’a ( B , ) . {\displaystyle (\mathbb {B} ,\exists ).}

p = p

Niech B {\displaystyle \mathbb {B} } będzie algebrą Boole’a. Funkcja : B B {\displaystyle \exists \colon B\to B} zdana wzorem

p = p {\displaystyle \exists p=p} dla każdego p B {\displaystyle p\in B}

tworzy wraz z B {\displaystyle \mathbb {B} } monadyczną algebrę Boole’a ( B , ) . {\displaystyle (\mathbb {B} ,\exists ).}

Funkcyjne monadyczne algebry Boole’a

Niech C {\displaystyle C} będzie zupełną algebrą Boole’a i niech I {\displaystyle I} będzie dowolnym zbiorem niepustym. Rodzina C I {\displaystyle C^{I}} wszystkich funkcji p : I C {\displaystyle p\colon I\to C} z działaniami określonymi punktowo jest również zupełną algebrą Boole’a.

Dla każdego p C I {\displaystyle p\in C^{I}} istnieje p = sup { p ( i ) : i I } . {\displaystyle p^{*}=\sup \left\{p(i)\colon i\in I\right\}.} Niech p {\displaystyle \exists p} oznacza funkcję stałą o wartości p . {\displaystyle p^{*}.} Wtedy C I {\displaystyle C^{I}} z powyższym działaniem {\displaystyle \exists } jest zupełną monadyczną algebrą Boole’a.

Uogólnienie
Niech C {\displaystyle C} będzie dowolną algebrą Boole’a, a I {\displaystyle I} dowolnym zbiorem niepustym. Niech B {\displaystyle B} będzie podzbiorem zbioru C I {\displaystyle C^{I}} wszystkich funkcji p {\displaystyle p} takim, że spełnione są następujące warunki:
    • B {\displaystyle B} (z działaniami określonymi punktowo) jest algebrą Boole’a (w szczególności funkcje stałe 0 {\displaystyle 0} i 1 {\displaystyle 1} należą do B {\displaystyle B} );
    • dla każdej funkcji p B {\displaystyle p\in B} istnieje kres górny zbioru { p ( i ) : i I } ; {\displaystyle \left\{p(i)\colon i\in I\right\};}
    • jeśli p C {\displaystyle p\in C} i p = sup { p ( i ) : i I } , {\displaystyle p^{*}=\sup \left\{p(i)\colon i\in I\right\},} to również funkcja stała o wartości p {\displaystyle p^{*}} należy do zbioru C . {\displaystyle C.} Funkcję tę oznacza się p . {\displaystyle \exists p.}
Wówczas ( C , ) {\displaystyle (C,\exists )} jest monadyczną algebrą Boole’a. Takie monadyczne algebry Boole’a nazywa się funkcyjnymi monadycznymi algebrami Boole’a (określonymi na I o wartościach w zbiorze C {\displaystyle C} ).

Twierdzenie Halmosa o reprezentacji monadycznych algebr Boole’a

Paul Halmos udowodnił, że każda monadyczna algebra Boole’a jest izomorficzna z funkcyjną monadyczną algebrą Boole’a.

Bibliografia

  • Paul Halmos, Algebraic Logic. Chelsea Publishing Co., New York 1962.