Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following is a continuation of this question.

I would like to prove that the Lindenbaum algebra is a free algebra. Hopefully I would like to hear hints on how to proceed in the 'right' direction.

Let $X$ be a set of propositional variables, $M$ the set of all boolean expressions over $X$ and $L = M/_{\sim}$ the partition of $M$ into logically equivalent sentences.

The claim is that $L$ is free over $X$ with respect to the map $e:X \mapsto L$ defined as $e(x) = [x]$ where $[x]$ denotes the equivalence class of $x \in X.$

Let $B$ be any boolean algebra and $f:X\mapsto B$ any function. We want to argue that there is precisely one homomorphism $\overline{f}:L\mapsto B$ so that $\overline{f}\circ e = f.$ The only choice I see is to extend the map defined as $$\overline{f}([a]) = f(x) \; \hbox{if} \; x \in X \; \hbox{and} \; [x] = [a]$$

to a homomorphism in the natural way (if $[a]$ is not the equivalence class of propositional element then apply $\overline{f}$ to recursively to the subterms of a compound element in $[a]$)

The following seems like the wrong way to do it since then one has many technicalities to show.

  1. $\overline{f}$ is well defined.

  2. That $\overline{f}$ is indeed the only possible homomorphism. Is it valid to use an inductive argument to show that if $\overline{g}$ is another such homomorphism then it has to be that $\overline{f} = \overline{g}$ since $f,g$ agree for all elements that are equivalence classes of propositional variables and any other element in $L$ is a finite expression of these?

As said I believe I haven't defined $\overline{f}$ in a convenient way to allow me to prove the necessary conditions.

Is there a better way to approach this?

share|improve this question
    
how does this question relate to model theory? also, what's not obvious about 2.? –  tomasz Jun 18 '12 at 20:50
    
Lindenbaum algebra is usually a model for propositional logic. –  Jernej Jun 18 '12 at 20:53
1  
Well, the reals are usually a model for a real closed field, and that doesn't mean that anything related to them is model-theoretic. I don't mean to be rude, I was just curious as to whether there was something I missed about it (since at first I thought it was the Lindenbaum algebra of actual formulas, which is much more common in model theory afaik). –  tomasz Jun 18 '12 at 20:56
add comment

1 Answer

up vote 2 down vote accepted

What you’re doing is fine: you want to define $\bar f$ by structural recursion on formulas of $L$. The base of it is what you already have: $\bar f\big([x]\big)=f(x)$ for $x\in X$. Now if $\varphi,\psi\in L$ and $\bar f\big([\varphi]\big)$ and $\bar f\big([\psi]\big)$ have been defined, let

$$\begin{align*} &\bar f\big([\varphi\lor\psi]\big)=\bar f\big([\varphi]\big)\lor\bar f\big([\psi]\big),\\ &\bar f\big([\varphi\land\psi]\big)=\bar f\big([\varphi]\big)\land\bar f\big([\psi]\big),\text{ and }\\ &\bar f\big([\lnot\varphi]\big)=\lnot\bar f\big([\varphi]\big)\;. \end{align*}$$

You know that if $\varphi\equiv\varphi'$ and $\psi\equiv\psi'$, then $\varphi\lor\psi\equiv\varphi'\lor\psi'$, $\varphi\land\psi\equiv\varphi'\land\psi'$, and $\lnot\varphi\equiv\lnot\varphi'$, so $\bar f$ is well-defined. To show that $\bar f$ is unique, just do what you sketched in (2): show by structural induction (parallel to the structural recursion defining $\bar f$) that if $g:L\to B$ is a homomorphism such that $g\!\upharpoonright\! X=f$, then $g=\bar f$.

share|improve this answer
    
Thank you! $ \; \; $ –  Jernej Jun 19 '12 at 12:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.