3
$\begingroup$

How to show in propositional logic, that $\mathrm{Cn}(\mathrm{Cn}(A)) = \mathrm{Cn}(A)$?

I thought of first showing $\mathrm{Cn}(\mathrm{Cn}(A)) \subseteq \mathrm{Cn}(A)$ and then $\mathrm{Cn}(\mathrm{Cn}(A)) \supseteq \mathrm{Cn}(A)$. I managed to show the second but don't exactly know how to show the first inclusion.

  • 0
    Given $\phi$ such that $Cn(A)\models\phi$ you want $A\models\phi$. To show this you just need to show that for all models of $A$ satisfy $\phi$. Take an arbitrary model of $A$, let's call it $M$. Then by the definition of $Cn(A)$ we have that $M$ is also$a$model of $Cn(A)$. Since we assume that $Cn(A)\models\phi$ we get that $M$ satisfies $\phi$, which is what we wanted.2012-05-02

1 Answers 1

2

Let me write one way of concluding this. Your mileage may vary depending how many of the theorems stated below you may use. $\newcommand{cn}{\operatorname{Cn}}$

First note that $A\subseteq\cn(A)$, since $A\models a$ for all $a\in A$. This gives us an immediate inclusion that $\cn(A)\subseteq\cn(\cn(A))$.

The other direction is slightly more complicated. Note that if $A\models\sigma$ then there is a finite subset $A_\sigma\subseteq A$ such that $A_\sigma\models\sigma$. Now suppose that $\cn(A)\models\sigma$. Let $\widehat A_\sigma\subseteq\cn(A)$ be a finite set such that $\widehat A_\sigma\models\sigma$. For every $\phi\in\widehat A_\sigma$ let $A_\phi$ be a finite subset of $A$ such that $A_\phi\models\phi$. Let $A_\sigma$ be the union of the finitely many $A_\phi$'s. We have that $\widehat A_\sigma\subseteq\cn(A_\phi)$.

Fact: for two statements $\alpha,\beta$ we have $\alpha\models\beta$ if and only if $\alpha\rightarrow\beta$ is a tautology.

Let $\alpha$ be the conjuction of all the statements in $A_\phi$ and $\varphi$ the conjuction of all $\phi$'s in $\widehat A_\sigma$, then $\alpha\models\varphi$ and $\alpha\land\varphi\models\sigma$, therefore $\alpha\models\varphi\rightarrow\sigma$ and therefore $\alpha\models\sigma$ as wanted.