PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] free Boolean algebra (Definition)

Let $ A$ be a Boolean algebra and $ X\subseteq A$ such that $ \langle X\rangle = A$. In other words, $ X$ is a set of generators of $ A$. $ A$ is said to be freely generated by $ X$, or that $ X$ is a free set of generators of $ A$, if $ \langle X\rangle =A$, and every function $ f$ from $ X$ to some Boolean algebra $ B$ can be extended to a Boolean algebra homomorphism $ g$ from $ A$ to $ B$, as illustrated by the commutative diagram below:

$ \xymatrix@R-=2pt{ X\ar[dr]^f\ar[dd]_i\ &B\ A\ar[ur]_g } $
where $ i: X\to A$ is the inclusion map. By extension of $ f$ to $ g$ we mean that $ g(x)=f(x)$ for every $ x\in X$. Any subset $ X\subseteq A$ containing 0 (or $ 1$) can never be a free generating set for any subalgebra of $ A$, for any function $ f:X\to B$ such that $ f(0)\ne 0$ can never be extended to a Boolean homomorphism.

A Boolean algebra is said to be free if it has a free set of generators. If $ A$ has $ X$ as a free set of generators, $ A$ is said to be free on $ X$. If $ A$ and $ B$ are both free on $ X$, then $ A$ and $ B$ are isomorphic. This means that free algebras are uniquely determined by its free generating set, up to isomorphisms.

A simple example of a free Boolean algebra is the one freely generated by one element. Let $ X$ be a singleton consisting of $ a$. Then the set $ A=\lbrace 0,a,a',1\rbrace$ is a Boolean algebra, with the obvious Boolean operations identified. Every function from $ X$ to a Boolean algebra $ B$ singles out an element $ b\in B$ corresponding to $ a$. Then the function $ g: A\to B$ given by $ g(a)=b$, $ g(a')=b'$, $ g(0)=0$, and $ g(1)=1$ is clearly Boolean.

The two-element algebra $ \lbrace 0,1\rbrace$ is also free, its free generating set being $ \varnothing$, the empty set, since the only function on $ \varnothing$ is $ \varnothing$, and thus can be extended to any function.

In general, if $ X$ is finite, then the Boolean algebra freely generated by $ X$ has cardinality $ 2^{2^{\vert X\vert}}$, where $ \vert X\vert$ is the cardinality of $ X$.



"free Boolean algebra" is owned by CWoo.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: cardinality, finite, empty set, algebra, operations, Boolean, obvious, singleton, simple, isomorphisms, free algebras, isomorphic, subalgebra, free generating set, subset, mean, extension, inclusion map, commutative diagram, Boolean algebra homomorphism, function, freely generated, generators, Boolean algebra
There is 1 reference to this entry.

This is version 8 of free Boolean algebra, born on 2008-04-24, modified 2008-04-28.
Object id is 10540, canonical name is FreeBooleanAlgebra.
Accessed 258 times total.

Classification:
AMS MSC: 03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures)
 06B20 (Order, lattices, ordered algebraic structures :: Lattices :: Varieties of lattices)
 03G05 (Mathematical logic and foundations :: Algebraic logic :: Boolean algebras)
 06E05 (Order, lattices, ordered algebraic structures :: Boolean algebras :: Structure theory)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)