Monadyczna algebra Boole'a

Monadyczna algebra Boole'a – algebra Boole'a z dodatkowym działaniem jednoargumentowym $\exists$, które spełnia pewne warunki naśladujące własności kwantyfikatora egzystencjalnego.

Definicja

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

• $(B, \lor, \land, 0, 1, ')$ jest algebrą Boole'a,
• funkcja $\exists\colon B \to B$ spełnia następujące warunki dla wszystkich $p, q\in B$:

1. $\exists 0 = 0$
2. $p \leqslant \exists p$
3. $\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 $\exists$ jest idempotentna: dla każdego $p \in B$ zachodzi $\exists\exists p = \exists p$, ponieważ $\exists\exists p = \exists(\exists p \land \exists p) = \exists\exists p \land \exists p = \exists p$.

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

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

Przykłady

∃p = 1

Niech $\mathbb B$ będzie algebrą Boole'a. Funkcja $\exists\colon B \to B$ zdefiniowana wzorem

$\exists p = 1$ dla każdego $p \in B\setminus \lbrace 0\rbrace$

umożliwia określenie monadycznej algebry Boole'a $(\mathbb B, \exists)$.

∃p = p

Niech $\mathbb B$ będzie algebrą Boole'a. Funkcja $\exists\colon B \to B$ zdana wzorem

$\exists p = p$ dla każdego $p\in B$

tworzy wraz $\mathbb B$ monadyczną algebrę Boole'a $(\mathbb B, \exists)$.

Funkcyjne monadyczne algebry Boole'a

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

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

Uogólnienie 

Niech $C$ będzie dowolną algebrą Boole'a, a $I$ dowolnym zbiorem niepustym. Niech $B$ będzie podzbiorem zbioru $C^I$ wszystkich funkcji $p$ takim, że spełnione są następujące warunki:

• $B$ (z działaniami określonymi punktowo) jest algebrą Boole'a (w szczególności funkcje stałe $0$ i $1$ należą do $B$);
• dla każdej funkcji $p \in B$ istnieje kres górny zbioru $\left\lbrace p(i)\colon i \in I \right\rbrace$;
• jeśli $p \in C$ i $p^\ast = \sup \left\lbrace p(i)\colon i\in I \right\rbrace$, to również funkcja stała o wartości $p^\ast$ należy do zbioru $C$. Funkcję tę oznacza się $\exists p$.

Wówczas $(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$).

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.

Źródła

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