"Duals" of Lindenbaum algebras - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T14:47:07Z http://mathoverflow.net/feeds/question/75646 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75646/duals-of-lindenbaum-algebras "Duals" of Lindenbaum algebras Hans Stricker 2011-09-16T22:53:06Z 2011-09-17T01:17:55Z <p>From <a href="http://en.wikipedia.org/wiki/Lindenbaum_algebra" rel="nofollow">Wikipedia</a> I learn: </p> <blockquote> <p><em>The Lindenbaum algebra A of a theory T consists of the equivalence classes of sentences of T. The operations in A are inherited from those in T.</em></p> </blockquote> <p>If there are disjunction, conjunction and negation, <em>A</em> is a Boolean algebra and can be seen as a poset: </p> <blockquote> <p>The objects of <em>A</em> are sentences $\phi$ modulo </p> <p>$$T \vdash \phi \leftrightarrow \phi'$$ </p> <p>There is a relation $\phi \leq \psi$ iff </p> <p>$$T \vdash \phi \rightarrow \psi$$</p> </blockquote> <p>Lindenbaum algebras are a bit boring since &mdash; for example &mdash; <a href="http://mathoverflow.net/questions/65851/lindenbaum-algebras-and-models/65853#65853" rel="nofollow">all complete theories <em>T</em> have the same two-element Lindenbaum algebra</a>.</p> <p>They might be a bit more interesting when relaxing the conditions:</p> <blockquote> <p>Objects $\phi$ modulo:</p> <p>$$\vdash \phi \leftrightarrow \phi'$$ </p> <p>Relation $\phi \leq \psi$: </p> <p>$$T \vdash \phi \rightarrow \psi$$</p> </blockquote> <p>I just want to know where I can learn more about this approach?</p> <p><em><strong>EDIT</strong>: I made two corrections due to Joel's answer.</em></p> <p><em><strong>EDIT</strong>: And a simplification.</em></p> http://mathoverflow.net/questions/75646/duals-of-lindenbaum-algebras/75648#75648 Answer by Joel David Hamkins for "Duals" of Lindenbaum algebras Joel David Hamkins 2011-09-16T23:13:29Z 2011-09-17T01:17:55Z <p>You seem to be missing a T on the left when defining the relation $\leq$ on the Lindenbaum algebra, an error which seems to undercut the premise of your question about duals. </p> <p>Namely, one wants to define that $\phi\leq\psi$ if and only if $T\vdash \phi\leftrightarrow\phi\wedge\psi$. This is the same as $T\vdash\phi\to\psi$. </p> <p>You need to include the theory $T$ in this definition, since otherwise the relation is not well-defined on your equivalence classes. For example, you won't even be able to prove that $\phi\leq\phi'$ when $\phi$ and $\phi'$ have been already identified by the first part of your definition. Thus, the way you have set things up, the relation $\leq$ will not be well-defined on the equivalence classes you have set up, but using the theory $T$ when defining the order does make things well-defined. </p> <p>The point of the Lindenbaum algebra is that the objects in the Lindenbaum algebra represent the possible assertions that you can make, having already committed yourself to the theory $T$. These form a Boolean algebra, and the order in that case is simply the usual order arising in any Boolean algebra. It is not a defect that the algebra has only two elements when $T$ is complete, since if you are committed to a complete theory, then every statement is either proved or refuted by the theory, and these are the two kinds of statements you can make. The way I would describe the situation is that the algebra is more interesting when the theory leaves matters unsettled, since the point of the algebra is to understand the nature of what is not yet settled by $T$. I think you can find an account of the Lindenbaum algebra in any of the standard logic texts, but I'd have to double check for a specific reference. </p> <p>But if we do consider the notion that you have set up, your objects are the Lindenbaum algebra of the underlying language with no theory, but you have a new relation, which is merely a pre-order, arising from the order as defined using theory $T$. Note that different objects $x$ and $y$ in your algebra can obey $x\leq y\leq x$ with $x\neq y$, so this is a pre-order rather than an order. But if we were to quotient by the corresponding equivalence relation, we would get exactly the Lindenbaum algebra arising from the theory $T$, since $\varphi\leq\psi\leq \varphi$ if and only if $\varphi$ and $\psi$ are equivalent in the Lindenbaum algebra of $T$. </p> http://mathoverflow.net/questions/75646/duals-of-lindenbaum-algebras/75654#75654 Answer by Vijay D for "Duals" of Lindenbaum algebras Vijay D 2011-09-17T01:09:45Z 2011-09-17T01:09:45Z <p>What you have defined is one way to go about this. There is <a href="http://mathoverflow.net/questions/65851/lindenbaum-algebras-and-models" rel="nofollow">another question</a> discussing Lindenbaum algebras and the answer by Andreas Blass discusses another possibility. Briefly, another possibility is to define an algebra over arbitrary formulas, including those containing free variables. Some people call this the Rasiowa-Sikorski approach. It is covered the the second half of the book</p> <blockquote> <p><em>The mathematics of metamathematics</em> by Helena Rasiowa and Roman Sikorski.</p> </blockquote> <p>The topic is briefly treated in the chapter on model theory in</p> <blockquote> <p><em>Mathematical Logic: A Course with Exercises Pt.2: Recursion Theory, Godel's Theorem, Set Theory and Model Theory</em>, by Rene Cori, Daniel Lascar.</p> </blockquote> <p>A tutorial style treatment that discusses some design decisions one can take in setting up an algebraic framework for studying logics is in these two articles (part 2 of the second).</p> <blockquote> <p><em><a href="http://www.math-inst.hu/pub/algebraic-logic/handbook.pdf" rel="nofollow">Algebraic logic</a></em> by Hajnal Andréka, István Németi and Ildikó Sain, and the article <em><a href="http://www.math-inst.hu/pub/algebraic-logic/meth.pdf" rel="nofollow">Applying Algebraic Logic; a General Methodology</a></em> by Hajnal Andréka, Ágnes Kurucz, István Németi and Ildikó Sain </p> </blockquote>