Two-Valued Functions form Boolean Algebra
Theorem
Let $\mathbf 2$ be the Boolean algebra two, and let $X$ be a set.
Let $\mathbf 2^X$ be the set of all mappings $p: X \to \mathbf 2$.
Define the operations $\vee$, $\wedge$ and $\neg$ on $\mathbf 2^X$ in pointwise fashion thus:
- $\vee: \mathbf 2^X \times \mathbf 2^X \to \mathbf 2^X, \left({p \vee q}\right) (x) := p (x) \vee q (x)$
- $\wedge: \mathbf 2^X \times \mathbf 2^X \to \mathbf 2^X, \left({p \wedge q}\right) (x) := p (x) \wedge q (x)$
- $\neg: \mathbf 2^X \to \mathbf 2^X, \left({\neg p}\right) (x) := \neg p (x)$
Furthermore, write $\bot$ and $\top$ for the constant mappings with these values, viz:
- $\bot: X \to \mathbf 2, \bot (x) := \bot$
- $\top: X \to \mathbf 2, \top (x) := \top$
Then $\left({\mathbf 2^X, \vee, \wedge, \neg}\right)$ is a Boolean algebra, with $\bot$ and $\top$ as identities for $\vee$ and $\wedge$, respectively.
Proof
Let us verify the axioms for a Boolean algebra in turn.
$(BA \ 0)$: Closure
Follows from Induced Operations Preserve Closure.
$\Box$
$(BA \ 1)$: Commutativity
Follows from Induced Operations Preserve Commutativity.
$\Box$
$(BA \ 2)$: Distributivity
Follows from Induced Operations Preserve Distributivity.
$\Box$
$(BA \ 3)$: Identities
Follows from Identity for Induced Operation.
$\Box$
$(BA \ 4)$: Complements
Follows from Induced Operations Preserve Identities.
$\Box$
Having verified all the axioms, we conclude $\mathbf 2^X$ is a Boolean algebra.
$\blacksquare$
Sources
- 2008: Paul Halmos and Steven Givant: Introduction to Boolean Algebras ... (previous): $\S 2$: Exercise $4$