Jacobson Radical, Boolean Ring

Boolean Ring

A variable, or an operation, is boolean (biography) if it is either true or false, often represented by 1 and 0 respectively. Thus boolean logic involves variables that are true or false, and boolean circuitry, which drives your computer and mine, is based on solid state switches that are either on or off.

A ring R is boolean if every element is idempotent. We will see that such a ring actually consists of boolean vectors, arrays of boolean variables that are either true or false.

One direction is easy. Let R be the direct product of arbitrarily many copies of Z₂. Every element is idempotent, thus satisfying our definition of a boolean ring. The direct sum also gives a boolean ring, though an infinite direct sum does not contain 1. Bring 1 back in if you like; whence an element of R has almost all its components 0, or almost all its components 1. In fact any boolean ring without 1 can be enhanced in this way.

Now, without knowing the structure of R, let the elements of R be idempotent. Using the binomial theorem, x+x = (x+x)² = x²+2xx+x² = x+2x+x. Thus 2x = 0, and R has characteristic 2. Ad anything to itself and get 0; like a switch turning on and off.

Similarly, x+y = (x+y)² = x²+xy+yx+y² = x+xy+yx+y. Thus xy = yx, and R is commutative.

Since R is a Z₂ vector space, give it a basis, and it looks like an array of switches that can be on or off. Addition is implemented by the bitwise xor operator. In some cases multiplication is the & operator, although this may depend on the basis.

Ideals

If R has no zero divisors, let x and y be distinct nonzero elements, and write (x+y)*xy = 0. Since x ≠ y, xy = 0, which is a contradiction. The only boolean ring with no zero divisors is Z₂.

Mod out by any prime ideal, giving a quotient free of zero divisors, namely Z₂. Thus every prime ideal is maximal.

Let H be an ideal generated by x and y. Note that x+y+xy lies in H, and generates x and y, and H. Thus H is principal. Repeate this n times and every finitely generated ideal is principal.

Boolean implies Von Neumann

Since yyy = y, R is von neumann.

If R contains 1, and satisfies any of the chain conditions, it is semisimple. (This was discussed in the previous section.) A commutative semisimple ring is the finite direct product of fields. Let F be one of these fields, a boolean subring that is an integral domain. It has to be Z₂, hence R = Z₂ⁿ. This is the familiar ring of boolean vectors, and the only possible noetherian / artinian boolean ring.

A boolean ring that is finite, or a finite dimensional Z₂ vector space, is artinian, and isomorphic to Z₂ⁿ. To illustrate, adjoin x to Z₂ and mod out by the relation x² = x. Choose x and 1+x as an orthogonal basis.

Now adjoin y, and replace y² with y and xy with 0. This has the orthogonal basis x, y, and 1+x+y.

Finally, let xy be idempotent, giving a four dimensional vector space. This has the nonobvious orthogonal basis: xy+x, xy+y, xy, and 1+x+y+xy.

Power Set Ring

Let P be the power set of a fixed set F. Turn the elements of P, i.e. the subsets of F, into a boolean ring as follows.

Let ∅ = 0 and let F = 1. Let intersection become multiplication. Let symmetric difference, i.e. the union minus the intersection, become addition.

I'll prove one of the ring properties; the others are done similarly. Let's prove addition is associative. Let A B and C be subsets of F. An element x in F could be in none, 1, 2, or all 3 of these sets. For each of these 8 possibilities, evaluate (A+B)+C and A+(B+C). Show that x is in the former iff it is in the latter. For instance, let x lie in A and B, but not C. It is in the union and the intersection of A and B, hence x is not in A+B. Since x is not in C, it is not in (A+B)+C. On the other hand, x is in B, and not B∩C, hence x is in B+C. Now bring in A, which also contains x, and x drops out. The resulting subset of F is the same, and addition is associative.

Verify the other ring properties in this manner, and since B∩B = B, the result is a boolean ring.

Notice that subsets can be represented by arrays of 1's and 0's, where the i^th bit indicates whether the element x_i belongs to that particular subset. Now multiplication, or intersection, performs a bitwise and operation, and addition looks like an xor operation, as one would expect from a ring with characteristic 2. The power set ring has become a classic boolean ring, based on boolean vectors and bitwise operators.

Given such a ring, the or operation can be reproduced as B+C+bc. If x ∈ F is in B, or C, or both, it will wind up in B+C+bc.

Although it is not the standard convention, you can stand on your head and build the inverted power set ring, where F = 0 and ∅ = 1, and union is multiplication. (Symmetric difference is addition, as it was before.) The original ring and the inverted ring are isomorphic, by flipping all the bits in the arrays.

Boolean Lattice

A boolean lattice is a lattice, with an absolute minimum 0 and an absolute maximum 1, and a unique complement for each element. That is, each x has a y, such that 1 is x join y, and 0 is x meet y. Furthermore, the lattice is distributive, so that meet distributes over join, and join distributes over meet.

A boolean ring can always be turned into such a lattice. Declare x ≤ y if xy = x, and verify the following steps.

x ≤ x (x = x*x) … reflexive.
x ≤ y and y ≤ x implies x = y (xy equals both x and y) … antisymmetric.
xy = x and yz = y implies xz =(xy)z = x(yz) = xy = x … transitive.
0 ≤ x for every x.
x ≤ 1 for every x.
xy is a lower bound for x and y, and x+y+xy is an upper bound for x and y.
If z is another lower bound then z(xy) = (zx)y = xy, hence xy is the meet.
If z is another upper bound then (x+y+xy)z = xz+yz+xyz = x+y+xy, and x+y+xy is the join.
1+x is a complement for x.
If y is a complement for x then xy = 0 and x+y+xy = 1, whence y = 1+x, hence the complement is unique.
Rewrite z*(x+y+xy) as zx+zy+zzxy, the join of zx and zy. Similarly, z+xy+zxy equals (z+x+zx)*(z+y+zy). The lattice is distributive.
The boolean ring has become a boolean lattice.

If R is a power set ring, x ≤ y means x is a subset of y. The meet of the lattice is set intersection, and the join is union. The power set ring produces a subset lattice.

Conversely, every boolean lattice can be turned back into a boolean ring. These are inverse transformations, hence boolean rings and boolean lattices correspond.

In the following proof, I will use | for join, & for meet, and ~ for complement. This notation is concise, and it reflects the bitwise operations that are typical of a boolean lattice. C programmers should feel right at home.

Let x*y equal x&y, i.e. the greatest lower bound of x and y. Let x+y = (x|y)&~(xy). Verify the following steps.

+ and * are commutative.
Every element is idempotent.
0*x = 0&x = 0
1*x = 1&x = x
1|x = 1
x satisfies the conditions of ~(~x), and complement is unique, thus x = ~~x.
0 = ~1, or if you prefer, 1 = ~0.
x * ~x = 0
x | ~x = x + ~x = 1
x + x = x * ~x = 0
(x*y)*z is the greatest lower bound of x y and z. It is a lower bound, and if w is another lower bound it is below x and y, and xy. Thus w is below xy and z, and is below (xy)z.
x*(y*z) is the greatest lower bound of x y and z (by symmetry).
Multiplication, synonymous with meet, is associative. A similar proof shows join is associative.
Use the distributive law to expand (x|y)|(~x&~y) to get 1&1, or 1. Similarly, (x|y)&(~x&~y) drops to 0. Therefore x|y and ~x&~y are complement. Replace x with ~x and y with ~y to show x&y and ~x|~y are complement. These are demorgan's laws.
Convert x+y to conjunctive normal form: x&~y|y&~x. Apply this formula recursively to (x+y)+z, and convert to normal form, giving xyz|x~y~z|y~x~z|z~x~y. This is symmetric in x y and z, hence addition is associative.
Convert xz+yz to normal form, giving xz~y|yz~x. This is the same as x~y|y~x times z. Therefore multiplication distributes over addition.
The boolean lattice has become a boolean ring.