(This construction is not to be confused with an algebra of complex numbers.)

Most algebraic constructions we come across in model theory and mathematical logic have their operations or relations defined on the elements of some set. As an example we can take a look at the group <N, +, 0> formed by the natural numbers, denoted N, with the operation + (addition) interpreted in the standard way, e.g.

1 + 1 = 2
4 + 0 = 4
5 + 6 = 11.

But how about adding sets of numbers, how would that be done? I.e. if we take elements of P(N) (the power set of N) how would we interpret the operation +. Well the natural solution turns out to be the best, I'll give a few examples of what I mean by the "natural solution"
{1} + {3} = {1+3} = {4},
{1, 2} + {3, 4} = {1+3, 1+4, 2+3, 2+4} = {4, 5, 6},

where {x, y, z} denotes the set containing the elements x, y and z. Formally we define + for two subsets X and Y of N to be
X + Y = { x+y : with x an element of X and y an element of Y}.

This is all very interesting, but I haven't told you what a complex algebra is yet... Sorry, before we can get there I need to make a few remarks on P(X) (the set of subsets of X). Between two sets we can define the intersection `^' and union `v' of these sets or the complement `~' of a set. However these operations function in much the same way as the and, or and not logical connectives of propositional logic, in fact <P(X), ^, v, ~, 0> forms a Boolean algebra (where `0' is just my way of writing the emptyset).

So here's the definition of a complex algebra: Let M = <M, F, R> be some mathematical model, we define the complex algebra of M to be the algebra Cm(M) = <P(M), ^, v, ~, 0, FI, RI>, where the interpretation function I is defined as follows. For an element f of F with arity n we define

fI(X1,...,Xn) = { f(x1, ..., xn) | where xi is an element of Xi}

and for an element r of R with arity n we define
rI(X1,...,Xn-1) = { xn : where r(x1, ..., xn) and each xi is an elements of Xi}
These new interpretations of `f' and `r' over sets is sometimes referred to as the lifting of operations to sets.

The name complex, in this context, comes from a subset of a group being historically referred to as a complex. The study of these lifted operations on groups was then referred to as a calculus of complexes. (The particular example I presented above was used by Frobenius to define the coset of a group.) My favorite way of looking at complex algebras is as a form of meta-algebraic structure, i.e. these complex algebras talk about the algebras they were originally defined from.

This construction has proven very important in algebraic logic since it gives us a way of turning a Kripke model, or for that matter any relational structure, into an algebra.
