|
There are several different signatures and conventions used for Boolean algebras: The signature has 2 constants, 0 and 1, and two binary functions ∧ and ∨ ("and" and "or"), and one unary function ¬ ("not"). This is a little confusing as the functions use the same symbols as the propositional functions of first-order logic. In set theory, a common convention is that the language has 2 constants, 0 and 1, and two binary functions · and +, and one unary function −. The three functions have the same interpretation as the functions in the first convention. Unfortunately, this convention clashes badly with the next convention: In algebra, the usual convention is that the language has 2 constants, 0 and 1, and two binary functions · and +. The function · has the same meaning as ∧, but a+b means a∨b∧¬(a∧b). The reason for this is that the axioms for a Boolean algebra are then just the axioms for a ring with 1 plus ∀x x2 = x. Unfortunately this clashes with the standard convention in set theory given above. The axioms are: The axioms for a distributive lattice (see above) ∀a∀b a∧¬a = 0, ∀a∀b a∨¬a = 1 (properties of negation) Some authors add the extra axiom ¬0=1, to exclude the trivial algebra with one element. Tarski proved that the theory of Boolean algebras is decidable. We write x ≤ y as an abbreviation for x ∧ y = x, and atom(x) as an abbreviation for ¬x = 0 ∧ ∀y y≤x → y = 0 ∨ y = x, read as "x is an atom", in other words a non-zero element with nothing between it and 0. Here are some first-order properties of Boolean algebras: Atomic: ∀x x=0 ∨ ∃y y≤x ∧ atom(y) Atomless: ∀x ¬atom(x) The theory of atomless Boolean algebras is ω-categorical and complete. For any Boolean algebra B, there are several invariants defined as follows. the ideal I(B) consists of elements that are the sum of an atomic and an atomless element. The quotient algebras Bi of B are defined inductively by B0=B, Bk+1 = Bk/I(Bk). The invariant m(B) is the smallest integer such that Bm+1 is trivial, or ∞ if no such integer exists. If m(B) is finite, the invariant n(B) is the number of atoms of Bm(B) if this number is finite, or ∞ if this number is infinite. The invariant l(B) is 0 if Bm(B) is atomic or if m(B) is ∞, and 1 otherwise. Then two Boolean algebras are elementarily equivalent if and only if their invariants l, m, and n are the same. In other words, the values of these invariants classify the possible completions of the theory of Boolean algebras. So the possible complete theories are: The trivial algebra (if this is allowed; sometimes 0≠1 is included as an axiom.) The theory with m=∞ The theories with m a natural number, n a natural number or ∞, and l = 0 or 1 (with l = 0 if n=0) |
About us|Jobs|Help|Disclaimer|Advertising services|Contact us|Sign in|Website map|Search|
GMT+8, 2015-9-11 22:04 , Processed in 0.151514 second(s), 16 queries .
