other exercises: 20241205_DiskMat_Serie11.pdf

11.4 b)

We know that $\mathrm{\Sigma }=(S.P.\tau ,\varphi )$ is a complete and sound proof system.
Let $s_1,s_2,s_3\in S$, $p_1,p_2,p_3\in P$ be arbitrary.
Let ${\mathrm{\Sigma }}^{\prime }=(S^{\prime },P^{\prime },{\tau }^{\prime },{\varphi }^{\prime })$ be a proof system where

We will now show that ${\mathrm{\Sigma }}^{\prime }$ is sound and complete.

soundness
Let $s^{\prime }=(s_1,s_2,s_3),s\in S\times S\times S$ and $p^{\prime }=(p_1,p_2,p_3),p^{\prime }\in P\times P\times P$ be arbitrary.
For any statement $s^{\prime }$ where ${\varphi }^{\prime }(s^{\prime },p^{\prime })=1$, at least two of $\varphi (s_1,p_1),\varphi (s_2,p_2),\varphi (s_3,p_3)$ are equal to $1$ (def ${\varphi }^{\prime }$). Since $\mathrm{\Sigma }$ is sound, this implies that for each $i\in \{1,2,3\}$ where $\varphi (s_i,p_i)=1$, $\tau (s_i)=1$ (def soundness). Thus, at least two of $\tau (s_1),\tau (s_2),\tau (s_3)$ are equal to $1$. This implies ${\tau }^{\prime }(s^{\prime })=1$ (def ${\tau }^{\prime }$). Therefore, ${\mathrm{\Sigma }}^{\prime }$ is sound.

completeness
Let $s^{\prime }=(s_1,s_2,s_3)\in S^{\prime }$ be any statement where ${\tau }^{\prime }(s^{\prime })=1$. This means that at least two of $\tau (s_1),\tau (s_2),\tau (s_3)$ are equal to $1$ (def ${\tau }^{\prime }$). Since $\mathrm{\Sigma }$ is complete, for at least two $i\in \{1,2,3\}$ where $\tau (s_i)=1$, there exists $p_i\in P$ such that $\varphi (s_i,p_i)=1$ (def. completeness). Choose $p^{\prime }=(p_1,p_2,p_3)\in P^{\prime }$. Thus, ${\varphi }^{\prime }(s^{\prime },p^{\prime })=1$ (def ${\varphi }^{\prime }$), and ${\mathrm{\Sigma }}^{\prime }$ is complete (def completeness).

11.4 b)

We know that $\mathrm{\Sigma }=(S.P.\tau ,\varphi )$ is a complete and sound proof system.
Let $s\in S,p\in P$ be arbitrary.
Let ${\mathrm{\Sigma }}^{\ast }=(S,P^{\ast },{\tau }^{\ast },{\varphi }^{\ast })$ be a proof system where

Since $p\in P$, also $p\in P^{\ast }$.
We will now show that ${\mathrm{\Sigma }}^{\ast }$ is sound and complete.

soundness
For any statement $s$ where ${\varphi }^{\ast }(s,p)=1$, $\varphi (s,p)=0$ (def ${\varphi }^{\ast }$). Since $\mathrm{\Sigma }$ is complete, this implies that $\tau (s)=0$ (def soundness). Thus ${\tau }^{\ast }(s)=1$ (def ${\tau }^{\ast }$), proving that ${\mathrm{\Sigma }}^{\ast }$ is sound (def soundness).

completeness
For any statement $s$ where ${\tau }^{\ast }(s)=1$, $\tau (s)=0$ (def ${\tau }^{\ast }$). Since $\mathrm{\Sigma }$ is sound, $\varphi (s,p)=0$ for any $p\in P$ . (def soundness). Thus, ${\varphi }^{\ast }(s,p)=1$ (def ${\varphi }^{\ast }$), thus proving that ${\mathrm{\Sigma }}^{\ast }$ is complete (def completeness).