{"id":28683,"date":"2013-05-21T16:58:05","date_gmt":"2013-05-21T11:28:05","guid":{"rendered":"http:\/\/www.kopykitab.com\/blog\/?p=28683"},"modified":"2013-05-21T16:58:05","modified_gmt":"2013-05-21T11:28:05","slug":"definition-and-properties-of-boolean-algebra-notes","status":"publish","type":"post","link":"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/","title":{"rendered":"Definition and Properties of Boolean Algebra Notes"},"content":{"rendered":"<h1 style=\"text-align: center;\">Definition and Properties of Boolean Algebra Notes<\/h1>\n<p>Boolean algebra is the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation. The rigorous concept is that of a certain kind of algebra, analogous to the mathematical notion of a group. This concept has roots and applications in logic (Lindenbaum-Tarski algebras and model theory), set theory (fields of sets), topology (totally disconnected compact Hausdorff spaces), foundations of set theory (Boolean-valued models), measure theory (measure algebras), functional analysis (algebras of projections), and ring theory (Boolean rings).\u00a0 The study of Boolean algebras has several aspects: structure theory, model theory of Boolean algebras, decidability and undecidability questions for the class of Boolean algebras, and the indicated applications. In addition, although not explained here, there are connections to other logics, subsumption as a part of special kinds of algebraic logic, finite Boolean algebras and switching circuit theory,\u00a0 and Boolean matrices.<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_47_1 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"ez-toc-toggle-icon-1\"><label for=\"item-69fbebfa70ac4\" aria-label=\"Table of Content\"><span style=\"display: flex;align-items: center;width: 35px;height: 30px;justify-content: center;direction:ltr;\"><svg style=\"fill: #000000;color:#000000\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #000000;color:#000000\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/label><input  type=\"checkbox\" id=\"item-69fbebfa70ac4\"><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 eztoc-visibility-hide-by-default' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/#1-definition-and-simple-properties\" title=\"1. Definition and simple properties\">1. Definition and simple properties<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/#2-the-elementary-algebraic-theory\" title=\"2. The elementary algebraic theory\">2. The elementary algebraic theory<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/#3-special-classes-of-boolean-algebras\" title=\"3. Special classes of Boolean algebras\">3. Special classes of Boolean algebras<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/#4-structure-theory-and-cardinal-functions-on-boolean-algebras\" title=\"4. Structure theory and cardinal functions on Boolean algebras\">4. Structure theory and cardinal functions on Boolean algebras<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/#5-decidability-and-undecidability-questions\" title=\"5. Decidability and undecidability questions\">5. Decidability and undecidability questions<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/#6-lindenbaum-tarski-algebras\" title=\"6. Lindenbaum-Tarski algebras\">6. Lindenbaum-Tarski algebras<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/#7-boolean-valued-models\" title=\"7. Boolean-valued models\">7. Boolean-valued models<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"1-definition-and-simple-properties\"><\/span><a name=\"def\"><\/a>1. Definition and simple properties<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>A Boolean algebra (BA) is a set\u00a0<em>A<\/em>\u00a0together with binary operations + and \u00b7 and a unary operation \u2212, and elements 0, 1 of\u00a0<em>A<\/em>\u00a0such that the following laws hold: commutative and associative laws for addition and multiplication, distributive laws both for multiplication over addition and for addition over multiplication, and the following special laws:<\/p>\n<blockquote><p>x + (x \u00b7 y) = x<br \/>\nx \u00b7 (x + y) = x<br \/>\nx + (\u2212x) = 1<br \/>\nx \u00b7 (\u2212x) = 0<\/p><\/blockquote>\n<p>These laws are better understood in terms of the basic example of a BA, consisting of a collection\u00a0<em>A<\/em>\u00a0of subsets of a set\u00a0<em>X<\/em>\u00a0closed under the operations of union, intersection, complementation with respect to\u00a0<em>X<\/em>, with members \u2205 and\u00a0<em>X<\/em>. One can easily derive many elementary laws from these axioms, keeping in mind this example for motivation. Any BA has a natural partial order \u2264 defined upon it by saying that\u00a0<em>x<\/em>\u00a0\u2264\u00a0<em>y<\/em>\u00a0if and only if\u00a0<em>x<\/em>\u00a0+\u00a0<em>y<\/em>\u00a0=\u00a0<em>y<\/em>. This corresponds in our main example to \u2286. Of special importance is the two-element BA, formed by taking the set\u00a0<em>X<\/em>\u00a0to have just one element. The two-element BA shows the direct connection with elementary logic. The two members, 0 and 1, correspond to falsity and truth respectively. The Boolean operations then express the ordinary truth tables for disjunction (with +), conjunction (with \u00b7) and negation (with \u2212). An important elementary result is that an equation holds in all BAs if and only if it holds in the two-element BA. Next, we define\u00a0<em>x<\/em>\u00a0\u2295\u00a0<em>y<\/em>\u00a0= (<em>x<\/em>\u00a0\u00b7 \u2212<em>y<\/em>) + (<em>y<\/em>\u00a0\u00b7 \u2212<em>x<\/em>). Then\u00a0<em>A<\/em>\u00a0together with \u2295 and \u00b7, along with 0 and 1, forms a ring with identity in which every element is idempotent. Conversely, given such a ring, with addition \u2295 and multiplication, define\u00a0<em>x<\/em>\u00a0+\u00a0<em>y<\/em>\u00a0=\u00a0<em>x<\/em>\u00a0\u2295\u00a0<em>y<\/em>\u00a0\u2295 (<em>x<\/em>\u00a0\u00b7\u00a0<em>y<\/em>) and \u2212<em>x<\/em>\u00a0= 1 \u2295\u00a0<em>x<\/em>. This makes the ring into a BA. These two processes are inverses of one another, and show that the theory of Boolean algebras and of rings with identity in which every element is idempotent are definitionally equivalent. This puts the theory of BAs into a standard object of research in algebra. An atom in a BA is a nonzero element\u00a0<em>a<\/em>\u00a0such that there is no element\u00a0<em>b<\/em>\u00a0with 0 &lt;\u00a0<em>b<\/em>\u00a0&lt;\u00a0<em>a<\/em>. A BA is atomic if every nonzero element of the BA is above an atom. Finite BAs are atomic, but so are many infinite BAs. Under the partial order \u2264 above,\u00a0<em>x<\/em>+\u00a0<em>y<\/em>\u00a0is the least upper bound of\u00a0<em>x<\/em>\u00a0and\u00a0<em>y<\/em>, and\u00a0<em>x<\/em>\u00a0\u00b7\u00a0<em>y<\/em>\u00a0is the greatest lower bound of\u00a0<em>x<\/em>\u00a0and\u00a0<em>y<\/em>. We can generalize this: \u03a3<em>X<\/em>\u00a0is the least upper bound of a set\u00a0<em>X<\/em>\u00a0of elements, and \u03a0<em>X<\/em>\u00a0is the greatest lower bound of a set\u00a0<em>X<\/em>\u00a0of elements. These do not exist for all sets in all Boolean algebras; if they do always exist, the Boolean algebra is said to be complete.<\/p>\n<h2><span class=\"ez-toc-section\" id=\"2-the-elementary-algebraic-theory\"><\/span><a name=\"elem\"><\/a>2. The elementary algebraic theory<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Several algebraic constructions have obvious definitions and simple properties for BAs: subalgebras, homomorphisms, isomorphisms, and direct products (even of infinitely many algebras). Some other standard algebraic constructions are more peculiar to BAs. An ideal in a BA is a subset\u00a0<em>I<\/em>\u00a0closed under +, with 0 as a member, and such that if\u00a0<em>a<\/em>\u00a0\u2264\u00a0<em>b<\/em>\u00a0\u2208\u00a0<em>I<\/em>, then also\u00a0<em>a<\/em>\u00a0\u2208\u00a0<em>I<\/em>. Although not immediately obvious, this is the same as the ring-theoretic concept. There is a dual notion of a filter (with no counterpart in rings in general). A filter is a subset\u00a0<em>F<\/em>\u00a0closed under \u00b7 , having 1 as a member, and such that if\u00a0<em>a<\/em>\u00a0\u2265\u00a0<em>b<\/em>\u00a0\u2208\u00a0<em>F<\/em>, then also\u00a0<em>a<\/em>\u00a0\u2208\u00a0<em>F<\/em>. An ultrafilter on\u00a0<em>A<\/em>\u00a0is a filter\u00a0<em>F<\/em>\u00a0with the following properties: 0 \u2209\u00a0<em>F<\/em>, and for any\u00a0<em>a<\/em>\u00a0\u2208\u00a0<em>A<\/em>, either\u00a0<em>a<\/em>\u00a0\u2208\u00a0<em>F<\/em>\u00a0or \u2212<em>a<\/em>\u00a0\u2208\u00a0<em>F<\/em>. For any\u00a0<em>a<\/em>\u00a0\u2208\u00a0<em>A<\/em>, let\u00a0<em>S<\/em>(<em>a<\/em>)= {<em>F<\/em>\u00a0:\u00a0<em>F<\/em>\u00a0is an ultrafilter on\u00a0<em>A<\/em>\u00a0and\u00a0<em>a<\/em>\u00a0\u2208\u00a0<em>F<\/em>}. Then\u00a0<em>S<\/em>\u00a0is an isomorphism onto a BA of subsets of the set\u00a0<em>X<\/em>\u00a0of all ultrafilters on<em>A<\/em>. This establishes the basic Stone representation theorem, and clarifies the origin of BAs as concrete algebras of sets. Moreover, the sets\u00a0<em>S<\/em>(<em>a<\/em>) can be declared to be a base for a topology on\u00a0<em>X<\/em>, and this turns\u00a0<em>X<\/em>\u00a0into a totally disconnected compact Hausdorff space. This establishes a one-one correspondence between the class of BAs and the class of such spaces. As a consequence, used very much in the theory of BAs, many topological theorems and concepts have consequences for BAs. If\u00a0<em>x<\/em>\u00a0is an element of a BA, we let 0<em>x<\/em>\u00a0= \u2212<em>x<\/em>\u00a0and 1<em>x<\/em>\u00a0=\u00a0<em>x<\/em>. If (<em>x<\/em>(0), \u2026\u00a0<em>x<\/em>(<em>m<\/em>\u00a0\u2212 1)) is a finite sequence of elements of a BA\u00a0<em>A<\/em>, then every element of the subalgebra of\u00a0<em>A<\/em>generated by {<em>x<\/em>(0), \u2026\u00a0,\u00a0<em>x<\/em>(<em>m<\/em>\u00a0\u2212 1)} can be written as a sum of monomials\u00a0<em>e<\/em>(0)<em>x<\/em>(0) \u00b7 \u2026\u00a0\u00b7\u00a0<em>e<\/em>(<em>m<\/em>\u00a0\u2212 1)<em>x<\/em>(<em>m<\/em>\u00a0\u2212 1) for\u00a0<em>e<\/em>\u00a0in some set of functions mapping\u00a0<em>m<\/em>\u00a0= {0, \u2026\u00a0,\u00a0<em>m<\/em>\u00a0\u2212 1} into 2 = {0, 1}. This is an algebraic expression of the disjunctive normal form theorem of sentential logic. A function\u00a0<em>f<\/em>\u00a0from a set\u00a0<em>X<\/em>\u00a0of generators of a BA\u00a0<em>A<\/em>\u00a0into a BA\u00a0<em>B<\/em>\u00a0can be extended to a homomorphism if and only if\u00a0<em>e<\/em>(0)<em>x<\/em>(0) \u00b7 \u2026\u00a0\u00b7\u00a0<em>e<\/em>(<em>m<\/em>\u00a0\u2212 1)<em>x<\/em>(<em>m<\/em>\u00a0\u2212 1) = 0 always implies that<em>e<\/em>(0)<em>f<\/em>(<em>x<\/em>(0)) \u00b7 \u2026 \u00b7\u00a0<em>e<\/em>(<em>m<\/em>\u00a0\u2212 1)<em>f<\/em>(<em>x<\/em>(<em>m<\/em>\u00a0\u2212 1)) = 0. This is Sikorski&#8217;s extension criterion. Every BA\u00a0<em>A<\/em>\u00a0can be embedded in a complete BA\u00a0<em>B<\/em>\u00a0in such a way that every element of\u00a0<em>B<\/em>\u00a0is the least upper bound of a set of elements of\u00a0<em>A<\/em>.\u00a0<em>B<\/em>is unique up to\u00a0<em>A<\/em>-isomorphism, and is called the completion of\u00a0<em>A<\/em>. If\u00a0<em>f<\/em>\u00a0is a homomorphism from a BA\u00a0<em>A<\/em>\u00a0into a complete BA\u00a0<em>B<\/em>, and if\u00a0<em>A<\/em>\u00a0is a subalgebra of\u00a0<em>C<\/em>, then\u00a0<em>f<\/em>\u00a0can be extended to a homomorphism of\u00a0<em>C<\/em>\u00a0into\u00a0<em>B<\/em>. This is Sikorski&#8217;s extension theorem. Another general algebraic notion which applies to Boolean algebras is the notion of a free algebra. This can be concretely constructed for BAs. Namely, the free BA on \u03ba is the BA of closed-open subsets of the two element discrete space raised to the \u03ba power.<\/p>\n<h2><span class=\"ez-toc-section\" id=\"3-special-classes-of-boolean-algebras\"><\/span><a name=\"spec\"><\/a>3. Special classes of Boolean algebras<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>There are many special classes of Boolean algebra which are important both for the intrinsic theory of BAs and for applications:<\/p>\n<ul>\n<li>Atomic BAs, already mentioned above.<\/li>\n<li>Atomless BAs, which are defined to be BAs without any atoms. For example, any infinite free BA is atomless.<\/li>\n<li>Complete BAs, defined above. These are specially important in the foundations of set theory.<\/li>\n<li>Interval algebras. These are derived from linearly ordered sets (<em>L<\/em>, &lt;) with a first element as follows. One takes the smallest algebra of subsets of\u00a0<em>L<\/em>\u00a0containing all of the half-open intervals [<em>a<\/em>,\u00a0<em>b<\/em>) with\u00a0<em>a<\/em>\u00a0in\u00a0<em>L<\/em>\u00a0and\u00a0<em>b<\/em>\u00a0in\u00a0<em>L<\/em>\u00a0or equal to \u221e. These BAs are useful in the study of Lindenbaum-Tarski algebras. Every countable BA is isomorphic to an interval algebra, and thus a countable BA can be described by indicating an ordered set such that it is isomorphic to the corresponding interval algebra.<\/li>\n<li>Tree algebras. A tree is a partially ordered set (<em>T<\/em>, &lt;) in which the set of predecessors of any element is well-ordered. Given such a tree, one considers the algebra of subsets of\u00a0<em>T<\/em>\u00a0generated by all sets of the form {<em>b<\/em>\u00a0:\u00a0<em>a<\/em>\u2264\u00a0<em>b<\/em>} for some\u00a0<em>a<\/em>\u00a0in\u00a0<em>T<\/em>.<\/li>\n<li>Superatomic BAs. These are BAs which are not only atomic, but are such that each subalgebra and homomorphic image is atomic.<\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"4-structure-theory-and-cardinal-functions-on-boolean-algebras\"><\/span><a name=\"card\"><\/a>4. Structure theory and cardinal functions on Boolean algebras<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Much of the deeper theory of Boolean algebras, telling about their structure and classification, can be formulated in terms of certain functions defined for all Boolean algebras, with infinite cardinals as values. We define some of the more important of these cardinal functions, and state some of the known structural facts, mostly formulated in terms of them<\/p>\n<ol>\n<li>The cellularity\u00a0<em>c<\/em>(<em>A<\/em>) of a BA is the supremum of the cardinalities of sets of pairwise disjoint elements of\u00a0<em>A<\/em>.<\/li>\n<li>A subset\u00a0<em>X<\/em>\u00a0of a BA\u00a0<em>A<\/em>\u00a0is independent if\u00a0<em>X<\/em>\u00a0is a set of free generators of the subalgebra that it generates. The independence of\u00a0<em>A<\/em>\u00a0is the supremum of cardinalities of independent subsets of\u00a0<em>A<\/em>.<\/li>\n<li>A subset\u00a0<em>X<\/em>\u00a0of a BA\u00a0<em>A<\/em>\u00a0is dense in\u00a0<em>A<\/em>\u00a0if every nonzero element of\u00a0<em>A<\/em>\u00a0is \u2265 a nonzero element of\u00a0<em>X<\/em>. The \u03c0-weight of\u00a0<em>A<\/em>\u00a0is the smallest cardinality of a dense subset of\u00a0<em>A<\/em>.<\/li>\n<li>Two elements\u00a0<em>x<\/em>,\u00a0<em>y<\/em>\u00a0of\u00a0<em>A<\/em>\u00a0are incomparable if neither one is \u2264 the other. The supremum of cardinalities of subset\u00a0<em>X<\/em>\u00a0of\u00a0<em>A<\/em>\u00a0consisting of pairwise incomparable elements is the incomparability of\u00a0<em>A<\/em>.<\/li>\n<li>A subset\u00a0<em>X<\/em>\u00a0of\u00a0<em>A<\/em>\u00a0is irredundant if no element of\u00a0<em>X<\/em>\u00a0is in the subalgebra generated by the others.<\/li>\n<\/ol>\n<p>An important fact concerning cellularity is the Erdos-Tarski theorem: if the cellularity of a BA is a singular cardinal, then there actually is a set of disjoint elements of that size; for cellularity regular limit (inaccessible), there are counterexamples. Every infinite complete BA has an independent subset of the same size as the algebra. Every infinite BA\u00a0<em>A<\/em>\u00a0has an irredundant incomparable subset whose size is the \u03c0-weight of\u00a0<em>A<\/em>. Every interval algebra has countable independence. A superatomic algebra does not even have an infinite independent subset. Every tree algebra can be embedded in an interval algebra. A BA with only the identity automorphism is called rigid. There exist rigid complete BAs, also rigid interval algebras and rigid tree algebras.<\/p>\n<h2><span class=\"ez-toc-section\" id=\"5-decidability-and-undecidability-questions\"><\/span><a name=\"decid\"><\/a>5. Decidability and undecidability questions<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>A basic result of Tarski is that the elementary theory of Boolean algebras is decidable. Even the theory of Boolean algebras with a distinguished ideal is decidable. On the other hand, the theory of a Boolean algebra with a distinguished subalgebra is undecidable. Both the decidability results and undecidablity results extend in various ways to Boolean algebras in extensions of first-order logic.<\/p>\n<h2><span class=\"ez-toc-section\" id=\"6-lindenbaum-tarski-algebras\"><\/span><a name=\"lind\"><\/a>6. Lindenbaum-Tarski algebras<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>A very important construction, which carries over to many logics and many algebras other than Boolean algebras, is the construction of a Boolean algebra associated with the sentences in some logic. The simplest case is sentential logic. Here there are sentence symbols, and common connectives building up longer sentences from them: disjunction, conjunction, and negation. Given a set\u00a0<em>A<\/em>\u00a0of sentences in this language, two sentences\u00a0<em>s<\/em>\u00a0and\u00a0<em>t<\/em>\u00a0are equivalent modulo\u00a0<em>A<\/em>\u00a0if and only if the biconditional between them is a logical consequence of\u00a0<em>A<\/em>. The equivalence classes can be made into a BA such that + corresponds to disjunction, \u00b7 to conjunction, and \u2212 to negation. Any BA is isomorphic to one of this form. One can do something similar for a first-order theory. Let\u00a0<em>T<\/em>\u00a0be a first-order theory in a first-order language\u00a0<em>L<\/em>. We call formulas \u03c6 and \u03c8 equivalent provided that\u00a0<em>T<\/em>\u00a0\u22a2 \u03c6 \u2194 \u03c8. The equivalence class of a sentence \u03c6 is denoted by [\u03c6]. Let\u00a0<em>A<\/em>\u00a0be the collection of all equivalence classes under this equivalence relation. We can make\u00a0<em>A<\/em>\u00a0into a BA by the following definitions, which are easily justified:<\/p>\n<blockquote>\n<table>\n<tbody>\n<tr>\n<td>[\u03c6] + [\u03c8]<\/td>\n<td>=<\/td>\n<td>[\u03c6 \u2228 \u03c8]<\/td>\n<\/tr>\n<tr>\n<td>[\u03c6] \u00b7 [\u03c8]<\/td>\n<td>=<\/td>\n<td>[\u03c6 \u2227 \u03c8]<\/td>\n<\/tr>\n<tr>\n<td align=\"right\">\u2212[\u03c6]<\/td>\n<td>=<\/td>\n<td>[\u00ac\u03c6]<\/td>\n<\/tr>\n<tr>\n<td align=\"right\">0<\/td>\n<td>=<\/td>\n<td>[F]<\/td>\n<\/tr>\n<tr>\n<td align=\"right\">1<\/td>\n<td>=<\/td>\n<td>[T]<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/blockquote>\n<p>Every BA is isomorphic to a Lindenbaum-Tarski algebra. However, one of the most important uses of these classical Lindenbaum-Tarski algebras is to describe them for important theories (usually decidable theories). For countable languages this can be done by describing their isomorphic interval algebras. Generally this gives a thorough knowledge of the theory. Some examples are:<\/p>\n<blockquote>\n<table>\n<tbody>\n<tr>\n<td><\/td>\n<td><strong>Theory<\/strong><\/td>\n<td><strong>Isomorphic to interval algebra on<\/strong><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">(1)<\/td>\n<td valign=\"top\">essentially undecidable theory<\/td>\n<td valign=\"top\"><strong>Q<\/strong>, the rationals<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">(2)<\/td>\n<td valign=\"top\">BAs<\/td>\n<td valign=\"top\"><img alt=\"Natural\" src=\"http:\/\/plato.stanford.edu\/entries\/boolalg-math\/Num.gif\" \/>\u00a0\u00d7\u00a0<img alt=\"Naturals\" src=\"http:\/\/plato.stanford.edu\/entries\/boolalg-math\/Num.gif\" \/>, square of the positive integers, ordered lexicographically<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">(3)<\/td>\n<td valign=\"top\">linear orders<\/td>\n<td valign=\"top\"><strong>A<\/strong>\u00a0\u00d7\u00a0<strong>Q<\/strong>\u00a0ordered antilexicographically, where\u00a0<strong>A<\/strong>\u00a0is\u00a0<img alt=\"Naturals\" src=\"http:\/\/plato.stanford.edu\/entries\/boolalg-math\/Num.gif\" \/>\u00a0to the\u00a0<img alt=\"Naturals\" src=\"http:\/\/plato.stanford.edu\/entries\/boolalg-math\/Num.gif\" \/>\u00a0power in its usual order<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">(4)<\/td>\n<td valign=\"top\">abelian groups<\/td>\n<td valign=\"top\">(<strong>Q<\/strong>\u00a0+\u00a0<strong>A<\/strong>) \u00d7\u00a0<strong>Q<\/strong><\/p>\n<p>&nbsp;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"7-boolean-valued-models\"><\/span><a name=\"bv\"><\/a>7. Boolean-valued models<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>In model theory, one can take values in any complete BA rather than the two-element BA. This Boolean-valued model theory was developed around 1950&#8211;1970, but has not been worked on much since. But a special case, Boolean-valued models for set theory, is very much at the forefront of current research in set theory. It actually forms an equivalent way of looking at the forcing construction of Cohen, and has some technical advantages and disadvantages. Philosophically it seems more satisfactory than the forcing concept. We describe this set theory case here; it will then become evident why only compete BAs are considered. Let B be a complete BA. First we define the Boolean valued universe\u00a0<em>V<\/em>(<em>B<\/em>). The ordinary set-theoretic universe can be identified with\u00a0<em>V<\/em>(2), where 2 is the 2-element BA. The definition is by transfinite recursion, where \u03b1, \u03b2 are ordinals and \u03bb is a limit ordinal:<\/p>\n<blockquote>\n<table>\n<tbody>\n<tr>\n<td align=\"right\"><em>V<\/em>(<em>B<\/em>, 0)<\/td>\n<td>=<\/td>\n<td>\u2205<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\"><em>V<\/em>(<em>B<\/em>,\u00a0\u03b1\u00a0+\u00a01)<\/td>\n<td valign=\"top\">=<\/td>\n<td valign=\"top\">the set of all functions\u00a0<em>f<\/em>\u00a0such that the domain of\u00a0<em>f<\/em>\u00a0is a subset of\u00a0<em>V<\/em>(<em>B<\/em>, \u03b1) and the range of\u00a0<em>f<\/em>\u00a0is a subset of\u00a0<em>B<\/em><\/td>\n<\/tr>\n<tr>\n<td align=\"right\"><em>V<\/em>(<em>B<\/em>, \u03bb)<\/td>\n<td>=<\/td>\n<td>the union of all\u00a0<em>V<\/em>(<em>B<\/em>, \u03b2) for \u03b2 &lt; \u03bb.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/blockquote>\n<p>The\u00a0<em>B<\/em>-valued universe is the proper class\u00a0<em>V<\/em>(<em>B<\/em>) which is the union of all of these\u00a0<em>V<\/em>s. Next, one defines by a rather complicated transfinite recursion over well-founded sets the value of a set-theoretic formula with elements of the Boolean valued universe assigned to its free variables<\/p>\n<blockquote>\n<table>\n<tbody>\n<tr>\n<td align=\"right\">||<em>x<\/em>\u00a0\u2208\u00a0<em>y<\/em>||<\/td>\n<td>=<\/td>\n<td>\u03a3{(||<em>x<\/em>\u00a0=<em>t<\/em>|| \u00b7\u00a0<em>y<\/em>(<em>t<\/em>)) :\u00a0<em>t<\/em>\u00a0\u2208 domain(<em>y<\/em>)}<\/td>\n<\/tr>\n<tr>\n<td align=\"right\">||<em>x<\/em>\u00a0\u2286\u00a0<em>y<\/em>||<\/td>\n<td>=<\/td>\n<td>\u03a0{\u2212<em>x<\/em>(<em>t<\/em>) + ||<em>t<\/em>\u00a0\u2208\u00a0<em>y<\/em>|| :\u00a0<em>t<\/em>\u00a0\u2208 domain(<em>x<\/em>)}<\/td>\n<\/tr>\n<tr>\n<td align=\"right\">||<em>x<\/em>\u00a0=\u00a0<em>y<\/em>||<\/td>\n<td>=<\/td>\n<td>||<em>x<\/em>\u00a0\u2286\u00a0<em>y<\/em>|| \u00b7 ||<em>y<\/em>\u00a0\u2286\u00a0<em>x<\/em>||<\/td>\n<\/tr>\n<tr>\n<td align=\"right\">||\u00ac\u03c6||<\/td>\n<td>=<\/td>\n<td>\u2212|| \u03c6 ||<\/td>\n<\/tr>\n<tr>\n<td align=\"right\">|| \u03c6 \u2228 \u03c8 ||<\/td>\n<td>=<\/td>\n<td>|| \u03c6 || + || \u03c8 ||<\/td>\n<\/tr>\n<tr>\n<td>||\u2203<em>x<\/em>\u03c6 (<em>x<\/em>)||<\/td>\n<td>=<\/td>\n<td>\u03a3{||\u03c6(<em>a<\/em>)|| :\u00a0<em>a<\/em>\u00a0\u2208\u00a0<em>V<\/em>(<em>B<\/em>)}<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/blockquote>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Definition and Properties of Boolean Algebra Notes Boolean algebra is the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation. The rigorous concept is that of a certain kind of algebra, analogous to the mathematical notion of a group. This concept has roots and applications in &#8230; <a title=\"Definition and Properties of Boolean Algebra Notes\" class=\"read-more\" href=\"https:\/\/www.kopykitab.com\/blog\/definition-and-properties-of-boolean-algebra-notes\/\" aria-label=\"More on Definition and Properties of Boolean Algebra Notes\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":""},"categories":[4773],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts\/28683"}],"collection":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/comments?post=28683"}],"version-history":[{"count":0,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts\/28683\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/media?parent=28683"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/categories?post=28683"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/tags?post=28683"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}