Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What does $\mathrm{Cn}$ mean? – MJD May 2 '12 at 19:56
What is $\operatorname{Cn}$ in your system? – Brian M. Scott May 2 '12 at 19:57
Cn(A) are all the consequences of $A$. So all $a$ with $A \models a$. – jemnix May 2 '12 at 20:32
Do you know that $A\models a$ iff $A\vdash a$? – Brian M. Scott May 2 '12 at 20:58
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. – Apostolos May 2 '12 at 21:40

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.

share|cite|improve this answer

Your Answer


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.