3
$\begingroup$

Sorry for this question out of the blue (especially if its answer should be trivial, obvious, or folklore):

(When and how) can we construct models of a consistent first order theory $T$ from its Lindenbaum algebra?

More specifically: Is there an algebraic theory which its Lindenbaum algebra is a model of?

$\endgroup$

2 Answers 2

9
$\begingroup$

The Lindenbaum algebra of a (classical) first-order theory is a Boolean algebra. (And, conversely, every Boolean algebra is a Lindenbaum algebra of some classical theory, even a propositional one.) Since there are not that many different Boolean algebras, it usually encodes very little information about the theory or its models. The most common examples you can encounter in practice are:

  • Countable essentially undecidable theories (e.g., consistent extensions of Robinson arithmetic): they all have the same Lindenbaum algebra, viz the unique countable atomless Boolean algebra.

  • Complete theories (e.g., real-closed fields): their Lindenbaum algebra is the two-element Boolean algebra.

  • Theories $T$ with a unique complete extension not finitely axiomatizable over $T$ (e.g., algebraically closed fields, or euclidean geometry without a dimension axiom): their Lindenbaum algebra is isomorphic to the algebra of finite and cofinite subsets of $\omega$.

$\endgroup$
7
  • $\begingroup$ @Emil: I take "there are not that many different Boolean algebras" as the essence of your answer. Thank you! (What about my side question? Do you have an example?) $\endgroup$ Commented May 24, 2011 at 14:41
  • $\begingroup$ Which question is the side question? $\endgroup$ Commented May 24, 2011 at 14:47
  • $\begingroup$ Is there an algebraic theory which its Lindenbaum algebra is a model of? (I am not quite sure whether this is correct English;-) $\endgroup$ Commented May 24, 2011 at 15:02
  • 1
    $\begingroup$ You mean $T$ such that the Lindenbaum algebra of $T$ is a model of $T$ itself? Clearly, the theory of Boolean algebras does the job. Some of its proper extensions also work. For example, if $T$ is the theory of nontrivial Boolean algebras of size at most $2^n$, then its Lindenbaum algebra has indeed size $2^n$. $\endgroup$ Commented May 24, 2011 at 15:13
  • 3
    $\begingroup$ How could it be far away from Boolean algebras? Every Lindenbaum algebra is a Boolean algebra. $\endgroup$ Commented May 24, 2011 at 15:29
9
$\begingroup$

Emil's answer covers the interpretation of the question in which the Lindenbaum algebra is considered abstractly, i.e., up to isomorphism. Another possible interpretation would take "Lindenbaum algebra" to mean the specific algebra consisting of equivalence classes of formulas, where equivalence of $\phi$ and $\psi$ means that $T$ proves $(\phi\iff\psi)$. (The Boolean operations are given by the propositional connectives, so the equivalence class $[\phi]$ of $\phi$ will be $\leq[\psi]$ iff $T$ proves $(\phi\implies\psi)$.) With this interpretation, one can obtain a model from the Lindenbaum algebra, provided the vocabulary of $T$ is countable. This is called the Rasiowa-Sikorski construction (it's in their book "The Mathematics of Metamathematics"), and it goes as follows. Work, as usual, with a countably infinite set of variables, so if the vocabulary of $T$ is countable, the Lindenbaum algebra $A$ is also countable. For each formula of the form $\forall x\,\phi(x)$, its equivalence class is the greatest lower bound (the Boolean meet) of all the instances $[\phi(y)]$, where $y$ ranges over all the variables (and substituting $y$ for $x$ in $\phi(x)$ is understood to include renaming any bound variables in $\phi(x)$ to avoid clashes). There are ultrafilters $U$ in $A$ that respect these particular meets; that is, $[\forall x\,\phi(x)]\in U$ iff, for each $y$, $[\phi(y)]\in U$. (Quite generally, any countably many prescribed meets are respected by some ultrafilter. This theorem of Rasiowa and Sikorski is essentially the Baire category theorem applied to the Stone space of $A$.) Fix such an ultrafilter $U$ and form a structure as follows: Its universe is obtained by taking the set of all terms in the vocabulary of $T$ and dividing by the equivalence relation that identifies $t$ with $t'$ iff $[t=t']\in U$. Function symbols are interpreted in the obvious way, and a relation symbol $R$ is interpreted as holding of those tuples of equivalence classes of terms $t_1,\dots,t_n$ for which $[R(t_1,\dots,t_n)]\in U$. One checks that these definitions make sense (i.e., don't depend on the choices of terms from equivalence classes), so that one obtains a structure $M$, and that the formulas that hold in $M$ are exactly those whose equivalence classes (in $A$) are in $U$. In particular, for any theorem $\theta$ of $T$, the equivalence class is $[\theta]=1\in U$, so $M$ is a model of $T$.

$\endgroup$
1
  • 4
    $\begingroup$ In order not to confuse the OP: we are each talking about a different Lindenbaum algebra. The Rasiowa–Sikorski construction needs the algebra of arbitrary formulas, whereas I was discussing the algebra of sentences. $\endgroup$ Commented May 24, 2011 at 18:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .