Return to Answer

added 131 characters in body

Source Link

edited Apr 1, 2014 at 14:29

Given a Boolean algebra $B$, I shall construct a theory whose Lindenbaum-Tarski algebra is isomorphic to $B$. I do not know anything about intuitionistic logic, so I will answer this question just for first order logic and Boolean algebras.

Let $B$ be a Boolean algebra. Let $V$ be the variety consisting of all algebras $(A,(c_{a})_{a\in B})$ such that $A$ is a Boolean algebra and $c_{a}\wedge c_{b}=c_{a\wedge b},c_{a}\vee c_{b}=c_{a\vee b},c_{0}=0,c_{1}=1$ whenever $a,b\in A$. Then $V$ is a variety. Let $T$ be the theory of all algebras $\mathcal{A}=(A,(c^{\mathcal{A}}_{a})_{a\in B})\in V$ such that $|A|=2$. I claim that the mapping $L:B\rightarrow Sent(T)$ given by $L(b)=[c_{b}=1]$ is a Boolean algebra isomorphism.

Take note that $L(1)=[c_{1}=1]=1$ and $L(0)=[c_{0}=1]=0$. Furthermore, $$L(a)\wedge L(b)=[c_{a}=1]\wedge[c_{b}=1]=[c_{a}\wedge c_{b}=1]=[c_{a\wedge b}=1]=L(a\wedge b).$$ Furthermore, we have $L(a)\vee L(b)=[c_{a}=1]\vee[c_{b}=1]=[c_{a}\vee c_{b}=1]=[c_{a\vee b}=1]=L(a\vee b)$. Therefore $L$ is a Boolean algebra homomorphism. To show that $L$ is injective, suppose that $a\neq 1$. Then there is a Boolean algebra homomorphism $\phi:B\rightarrow 2$ with $\phi(a)=0$. In particular, if $\mathcal{A}=(2,(c^{\mathcal{A}}_{a})_{a\in B})$ and $c^{\mathcal{A}}_{b}=\phi(b)$ for $b\in B$, then $\mathcal{A}\models T$, but also $\mathcal{A}\models c_{a}\neq 1$. Therefore $L(a)=[c_{a}= 1]\neq 1$. We conclude that $L$ is an injective Boolean algebra since its kernel is trivial. Now assume that $\Phi$ is a sentence in $T$. It is easy to see that the theory of $T$ has quantifier elimination: We can simply replace a formula $\forall x\Phi(x)$ with $\Phi(0)\wedge\Phi(1)$ and $\exists x\Phi(x)$ with $\Phi(0)\vee\Phi(1)$. Therefore Therefore every sentence in the language of $T$ is equivalent to a quantifier free sentence. Furthermore, every quantifier free sentence in $T$ can easily be reduced to a sentence of the form $c_{a}= 1$. Therefore every sentence in the language of $T$ is equivalent modulo $T$ to a sentence of the form $c_{a}=1$. Therefore every element $[\Phi]$ in $Sent(T)$ is of the form $L(a)=[c_{a}=1]$ for some $a\in B$. In other words, the mapping $L$ is surjective. We conclude that $L$ is an isomorphism.

Take note that $L(1)=[c_{1}=1]=1$ and $L(0)=[c_{0}=1]=0$. Furthermore, $$L(a)\wedge L(b)=[c_{a}=1]\wedge[c_{b}=1]=[c_{a}\wedge c_{b}=1]=[c_{a\wedge b}=1]=L(a\wedge b).$$ Furthermore, we have $L(a)\vee L(b)=[c_{a}=1]\vee[c_{b}=1]=[c_{a}\vee c_{b}=1]=[c_{a\vee b}=1]=L(a\vee b)$. Therefore $L$ is a Boolean algebra homomorphism. To show that $L$ is injective, suppose that $a\neq 1$. Then there is a Boolean algebra homomorphism $\phi:B\rightarrow 2$ with $\phi(a)=0$. In particular, if $\mathcal{A}=(2,(c^{\mathcal{A}}_{a})_{a\in B})$ and $c^{\mathcal{A}}_{b}=\phi(b)$ for $b\in B$, then $\mathcal{A}\models T$, but also $\mathcal{A}\models c_{a}\neq 1$. Therefore $L(a)=[c_{a}= 1]\neq 1$. We conclude that $L$ is an injective Boolean algebra since its kernel is trivial. Now assume that $\Phi$ is a sentence in $T$. It is easy to see that the theory of $T$ has quantifier elimination. Therefore every sentence in the language of $T$ is equivalent to a quantifier free sentence. Furthermore, every quantifier free sentence in $T$ can easily be reduced to a sentence of the form $c_{a}= 1$. Therefore every sentence in the language of $T$ is equivalent modulo $T$ to a sentence of the form $c_{a}=1$. Therefore every element $[\Phi]$ in $Sent(T)$ is of the form $L(a)=[c_{a}=1]$ for some $a\in B$. In other words, the mapping $L$ is surjective. We conclude that $L$ is an isomorphism.

Take note that $L(1)=[c_{1}=1]=1$ and $L(0)=[c_{0}=1]=0$. Furthermore, $$L(a)\wedge L(b)=[c_{a}=1]\wedge[c_{b}=1]=[c_{a}\wedge c_{b}=1]=[c_{a\wedge b}=1]=L(a\wedge b).$$ Furthermore, we have $L(a)\vee L(b)=[c_{a}=1]\vee[c_{b}=1]=[c_{a}\vee c_{b}=1]=[c_{a\vee b}=1]=L(a\vee b)$. Therefore $L$ is a Boolean algebra homomorphism. To show that $L$ is injective, suppose that $a\neq 1$. Then there is a Boolean algebra homomorphism $\phi:B\rightarrow 2$ with $\phi(a)=0$. In particular, if $\mathcal{A}=(2,(c^{\mathcal{A}}_{a})_{a\in B})$ and $c^{\mathcal{A}}_{b}=\phi(b)$ for $b\in B$, then $\mathcal{A}\models T$, but also $\mathcal{A}\models c_{a}\neq 1$. Therefore $L(a)=[c_{a}= 1]\neq 1$. We conclude that $L$ is an injective Boolean algebra since its kernel is trivial. Now assume that $\Phi$ is a sentence in $T$. It is easy to see that the theory of $T$ has quantifier elimination: We can simply replace a formula $\forall x\Phi(x)$ with $\Phi(0)\wedge\Phi(1)$ and $\exists x\Phi(x)$ with $\Phi(0)\vee\Phi(1)$. Therefore every sentence in the language of $T$ is equivalent to a quantifier free sentence. Furthermore, every quantifier free sentence in $T$ can easily be reduced to a sentence of the form $c_{a}= 1$. Therefore every sentence in the language of $T$ is equivalent modulo $T$ to a sentence of the form $c_{a}=1$. Therefore every element $[\Phi]$ in $Sent(T)$ is of the form $L(a)=[c_{a}=1]$ for some $a\in B$. In other words, the mapping $L$ is surjective. We conclude that $L$ is an isomorphism.

Source Link

created Apr 1, 2014 at 5:32

Joseph Van Name

Take note that $L(1)=[c_{1}=1]=1$ and $L(0)=[c_{0}=1]=0$. Furthermore, $$L(a)\wedge L(b)=[c_{a}=1]\wedge[c_{b}=1]=[c_{a}\wedge c_{b}=1]=[c_{a\wedge b}=1]=L(a\wedge b).$$ Furthermore, we have $L(a)\vee L(b)=[c_{a}=1]\vee[c_{b}=1]=[c_{a}\vee c_{b}=1]=[c_{a\vee b}=1]=L(a\vee b)$. Therefore $L$ is a Boolean algebra homomorphism. To show that $L$ is injective, suppose that $a\neq 1$. Then there is a Boolean algebra homomorphism $\phi:B\rightarrow 2$ with $\phi(a)=0$. In particular, if $\mathcal{A}=(2,(c^{\mathcal{A}}_{a})_{a\in B})$ and $c^{\mathcal{A}}_{b}=\phi(b)$ for $b\in B$, then $\mathcal{A}\models T$, but also $\mathcal{A}\models c_{a}\neq 1$. Therefore $L(a)=[c_{a}= 1]\neq 1$. We conclude that $L$ is an injective Boolean algebra since its kernel is trivial. Now assume that $\Phi$ is a sentence in $T$. It is easy to see that the theory of $T$ has quantifier elimination. Therefore every sentence in the language of $T$ is equivalent to a quantifier free sentence. Furthermore, every quantifier free sentence in $T$ can easily be reduced to a sentence of the form $c_{a}= 1$. Therefore every sentence in the language of $T$ is equivalent modulo $T$ to a sentence of the form $c_{a}=1$. Therefore every element $[\Phi]$ in $Sent(T)$ is of the form $L(a)=[c_{a}=1]$ for some $a\in B$. In other words, the mapping $L$ is surjective. We conclude that $L$ is an isomorphism.