The set of formulas that can be proved by a set P.

Question

Let $T(P)= \{φ/ P\vdashφ\}$ ,where $φ$'s are propositional formulas. We want to prove tha following equality: $$T(T(P))=T(P)$$ The inclusion $T(P)\subset T(T(P))$ is easy. I have a difficulty in the reverse inclusion. Any hint or advice would be great. Thank you in advance.

Answer 1

Well, yes, the first is trivial. Every fomula can be derived from itself. So any formula derived from $P$ may be derived from a formula derivable from $P$.

$$\forall\varphi\in\mathrm T(P)~.\varphi\in\mathrm T^2(P)$$

Conversely, I'd argue that any formula derivable from some subset of formulae derivable from $P$ must itself be derivable from $P$.

$$\big[~P\vdash \phi_1\quad\&\quad P\vdash \phi_2 \quad\&\quad\{\phi_1,\phi_2\}\vdash \psi~\big] \implies P\vdash\psi$$

Then by induction:

$$\forall\psi\in\mathrm T^2(P)~.\psi\in\mathrm T(P)$$

Answer 2

If $\varphi\in T(T(P))$ then it can be proved from some finite subset $\{\varphi_1,\ldots,\varphi_n\}\subset T(P).$ So we just string together a proof from $P$ of $\varphi_1$ and a proof from $P$ of $\varphi_2,$ and so on through $\varphi_n,$ and then a proof of $\varphi$ from $\{\varphi_1,\ldots,\varphi_n\}$ to get a proof of $\varphi$ from $P$.