Two-Valued Functions form Boolean Algebra

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Two-Valued_Functions_form_Boolean_Algebra&oldid=128578"