of integers and the symmetric group Sn of permutations of n objects, there are also basic examples of Boolean algebras such as the following.
Unlike groups of finite order, which exhibit complexity and diversity and whose first-order theory is decidable only in special cases, all finite Boolean algebras share the same theorems and have a decidable first-order theory.
These bases impart respectively a logical, an arithmetical, and a parsimonious character to the subject.
The ring basis has instead the arithmetic operation x⊕y of addition (the symbol ⊕ is used in preference to + because the latter is sometimes given the Boolean reading of join).
These tables continue at higher arities, with 2n rows at arity n, each row giving a valuation or binding of the n variables x0,...xn−1 and each column headed nfi giving the value nfi(x0,...,xn−1) of the i-th n-ary operation at that valuation.
As a minor detail important more for its form than its content, the operations of an algebra are traditionally organized as a list.
This permits organizing the set of all Boolean operations in the traditional list format.
A program can therefore represent for example the operation x∧(y∨z) in these languages as x&(y|z), having previously set x = 0xaa, y = 0xcc, and z = 0xf0 (the "0x" indicates that the following constant is to be read in hexadecimal or base 16), either by assignment to variables or defined as macros.
This technique is almost universally used in raster graphics hardware to provide a flexible variety of ways of combining and masking images, the typical operations being ternary and acting simultaneously on source, destination, and mask bits.
The direct product of any family Bi of Boolean algebras where i ranges over some index set I (not necessarily finite or even countable) is a Boolean algebra consisting of all I-tuples (...xi,...) whose i-th element is taken from Bi.
[11] Hence the cardinality (number of elements) of a finite Boolean algebra is a power of 2, namely one of 1,2,4,8,...,2n,...
It is convenient when talking about a set X of natural numbers to view it as a sequence x0,x1,x2,... of bits, with xi = 1 if and only if i ∈ X.
Example 6, and hence Example 5, constitutes the free Boolean algebra on countably many generators, meaning the Boolean algebra of all finitary operations on a countably infinite set of generators or variables.
The direct product of a Periodic Sequence (Example 5) with any finite but nontrivial Boolean algebra.
In principle it is desirable to have finitely many axioms; however as a practical matter it is not necessary since it is just as effective to have a finite axiom schema having infinitely many instances each of which when used in a proof can readily be verified to be a legal instance, the approach we follow here.
The following axiom schema and three inference rules axiomatize the Boolean algebra of n-ary terms.
Then to prove s = t in the general case when t may be an application, use the fact that if s = t is an identity then s and t must evaluate to the same atom, call it u.
So first prove s = u and t = u as above, that is, evaluate s and t using A1, R1, and R3, and then invoke R2 to infer s = t. In A1, if we view the number nm as the function type m→n, and mn as the application m(n), we can reinterpret the numbers i, j, ĵ, and ioĵ as functions of type i: (m→2)→2, j: m→((n→2)→2), ĵ: (n→2)→(m→2), and ioĵ: (n→2)→2.
This composition is the one in Lawvere's previously mentioned category of power sets and their functions.
This provides an alternative definition of a Boolean algebra, namely as any complemented distributive lattice.
These form the basis for nonstandard analysis, providing representations for such classically inconsistent objects as infinitesimals and delta functions.
Recall the definition of sup and inf from the section above on the underlying partial order of a Boolean algebra.
Gaifman [1964] and Hales [1964] independently showed that infinite free complete Boolean algebras do not exist.
One benefit of the latter approach is that it simplifies the definition of homomorphism between CABAs of different cardinality.)
This neatly rescues infinitary Boolean logic from the fate the Gaifman–Hales result seemed to consign it to.
Things are not so simple for the category Bool of Boolean algebras and their homomorphisms, which Marshall Stone showed in effect (though he lacked both the language and the conceptual framework to make the duality explicit) to be dual to the category of totally disconnected compact Hausdorff spaces, subsequently called Stone spaces.
This is defined analogously to complete Boolean algebras, but with sups and infs limited to countable arity.
Because the sups and infs are of bounded cardinality, unlike the situation with complete Boolean algebras, the Gaifman-Hales result does not apply and free sigma-algebras do exist.
Thus when generalizing finite algebras (of any kind, not just Boolean) to infinite ones, "discrete" and "compact" part company, and one must choose which one to retain.
Between these two extremes, there are many intermediate infinite Boolean algebras whose topology is neither discrete nor compact.