Free Boolean algebra

In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called generators, such that: In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called generators, such that: The generators of a free Boolean algebra can represent independent propositions. Consider, for example, the propositions 'John is tall' and 'Mary is rich'. These generate a Boolean algebra with four atoms, namely: Other elements of the Boolean algebra are then logical disjunctions of the atoms, such as 'John is tall and Mary is not rich, or John is not tall and Mary is rich'. In addition there is one more element, FALSE, which can be thought of as the empty disjunction; that is, the disjunction of no atoms. This example yields a Boolean algebra with 16 elements; in general, for finite n, the free Boolean algebra with n generators has 2n atoms, and therefore 2 2 n {displaystyle 2^{2^{n}}} elements. If there are infinitely many generators, a similar situation prevails except that now there are no atoms. Each element of the Boolean algebra is a combination of finitely many of the generating propositions, with two such elements deemed identical if they are logically equivalent. Another way to see why the free Boolean algebra on an n-element set has 2 2 n {displaystyle 2^{2^{n}}} elements is to note that each element is a function from n bits to one. There are 2 n {displaystyle 2^{n}} possible inputs to such a function and the function will choose 0 or 1 to output for each input, so there are 2 2 n {displaystyle 2^{2^{n}}} possible functions. In the language of category theory, free Boolean algebras can be defined simply in terms of an adjunction between the category of sets and functions, Set, and the category of Boolean algebras and Boolean algebra homomorphisms, BA. In fact, this approach generalizes to any algebraic structure definable in the framework of universal algebra. Above, we said that a free Boolean algebra is a Boolean algebra with a set of generators that behave a certain way; alternatively, one might start with a set and ask which algebra it generates. Every set X generates a free Boolean algebra FX defined as the algebra such that for every algebra B and function f : X → B, there is a unique Boolean algebra homomorphism f′ : FX → B that extends f. Diagrammatically, where iX is the inclusion, and the dashed arrow denotes uniqueness. The idea is that once one chooses where to send the elements of X, the laws for Boolean algebra homomorphisms determine where to send everything else in the free algebra FX. If FX contained elements inexpressible as combinations of elements of X, then f′ wouldn't be unique, and if the elements of X weren't sufficiently independent, then f′ wouldn't be well defined! It is easily shown that FX is unique (up to isomorphism), so this definition makes sense. It is also easily shown that a free Boolean algebra with generating set X, as defined originally, is isomorphic to FX, so the two definitions agree.