Free Boolean algebra

Free Boolean algebra

In abstract algebra, a branch of mathematics, a free Boolean algebra is a Boolean algebra 〈"B","F"〉, such that the set "B" (called the "carrier") has a subset whose elements are called generators. The generators satisfy the following properties:
*Each element of "B" that is not a generator can be expressed as a finite combination of generators, using the elements of "F", which are operations;
*The generators are as "independent" as possible, in that any equation holding for finite terms formed from the generators using the operations in "F", also holds for all elements of all possible Boolean algebras.

A simple example

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:
*John is tall, and Mary is rich;
*John is tall, and Mary is not rich;
*John is not tall, and Mary is rich;
*John is not tall, and Mary is not rich.

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 2"n" atoms, and therefore 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.

Category-theoretic definition

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 "i""X" 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 "FX" weren't sufficiently independent, then "f"′ wouldn't be well defined! It's easily shown that "FX" is unique (up to isomorphism), so this definition makes sense. It's also easily shown that a free Boolean algebra with generating set X, as defined originally, is isomorphic to "FX", so the two definitions agree.

One shortcoming of the above definition is that the diagram doesn't capture that "f"′ is a homomorphism; since it's a diagram in Set each arrow denotes a mere function. We can fix this by separating it into two diagrams, one in BA and one in Set. To relate the two, we introduce a functor "U" : BASet that "forgets" the algebraic structure, mapping algebras and homomorphisms to their underlying sets and functions.If we interpret the top arrow as a diagram in BA and the bottom triangle as a diagram in Set, then this diagram properly expresses that every function "f" : "X" → "B" extends to a unique Boolean algebra homomorphism "f"′ : "FX" → "B". The functor "U" can be thought of as a device to pull the homomorphism "f"′ back into Set so it can be related to "f".

The remarkable aspect of this is that the latter diagram is one of the various (equivalent) definitions of when two functors are adjoint. Our "F" easily extends to a functor SetBA, and our definition of "X" generating a free Boolean algebra "FX" is precisely that "U" has a left adjoint "F".

Topological realization

The free Boolean algebra with κ generators, where κ is a finite or infinite cardinal number, may be realized as the collection of all clopen subsets of {0,1}κ, given the product topology assuming that {0,1} has the discrete topology. For each α<κ, the α"th" generator is the set of all elements of {0,1}κ whose α"th" coordinate is 1. In particular, the free Boolean algebra with aleph_0 generators is the collection of all clopen subsets of a Cantor space. Surprisingly, this collection is countable. In fact, while the free Boolean algebra with "n" generators, "n" finite, has cardinality 2^{2^n}, the free Boolean algebra with aleph_0 generators has cardinality aleph_0.

For more on this topological approach to free Boolean algebra, see Stone's representation theorem for Boolean algebras.

ee also

* Boolean algebra
* Generating set

References

* Steve Awodey (2006) "Category Theory" (Oxford Logic Guides 49). Oxford University Press.
* Paul Halmos and Steven Givant (1998) "Logic as Algebra". Mathematical Association of America.
* Saunders Mac Lane (1998) "Categories for the Working Mathematician". 2nd ed. (Graduate Texts in Mathematics 5). Springer-Verlag.
* Saunders Mac Lane (1999) "Algebra", 3d. ed. American Mathematical Society. ISBN 0-821-81646-2.
* Robert R. Stoll, 1963. "Set Theory and Logic", chpt. 6.7. Dover reprint 1979.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Boolean algebra (introduction) — Boolean algebra, developed in 1854 by George Boole in his book An Investigation of the Laws of Thought , is a variant of ordinary algebra as taught in high school. Boolean algebra differs from ordinary algebra in three ways: in the values that… …   Wikipedia

  • Boolean algebra (structure) — For an introduction to the subject, see Boolean algebra#Boolean algebras. For the elementary syntax and axiomatics of the subject, see Boolean algebra (logic). For an alternative presentation, see Boolean algebras canonically defined. In abstract …   Wikipedia

  • Boolean algebra — This article discusses the subject referred to as Boolean algebra. For the mathematical objects, see Boolean algebra (structure). Boolean algebra, as developed in 1854 by George Boole in his book An Investigation of the Laws of Thought,[1] is a… …   Wikipedia

  • Complete Boolean algebra — This article is about a type of mathematical structure. For complete sets of Boolean operators, see Functional completeness. In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound) …   Wikipedia

  • List of Boolean algebra topics — This is a list of topics around Boolean algebra and propositional logic. Contents 1 Articles with a wide scope and introductions 2 Boolean functions and connectives 3 Examples of Boolean algebras …   Wikipedia

  • Boolean algebras canonically defined — Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the… …   Wikipedia

  • Free object — In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure (with finitary operations). It also has a clean… …   Wikipedia

  • Boolean-valued model — In mathematical logic, a Boolean valued model is a generalization of the ordinary Tarskian notion of structure or model, in which the truth values of propositions are not limited to true and false , but take values in some fixed complete Boolean… …   Wikipedia

  • Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… …   Wikipedia

  • Heyting algebra — In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras, named after Arend Heyting. Heyting algebras arise as models of intuitionistic logic, a logic in which the law of excluded… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”