What are techniques for proving undecidability or unprovability of a sentence?

Question

I asked a question the other day on how to form logical equivalence between a sentence $\phi$ and two other sentences $\psi$ and $\chi$, such that neither $\psi$ nor $\chi$ were on their own as 'strong' as $\phi$. Eventually the answer was provided in the form:

$\vdash\phi\leftrightarrow{(\psi\wedge\chi)}$, and $\not\vdash\chi\rightarrow{\phi}$ and $\not\vdash\psi\rightarrow{\phi}$

Now, I know how to prove provability of the first part semidecidably. I can prove $\vdash\phi\leftrightarrow{(\psi\wedge\chi)}$ by just following proof calculus if $\phi\leftrightarrow{(\psi\wedge\chi)}$ is a decidable sentence. I expect that $\not\vdash\chi\rightarrow{\phi}$ or generally $\not\vdash\phi$ can't be proved for the general case, because then it would seem that would solve the halting problem. But there are methods to prove $\not\vdash\phi$ for specific sentences $\phi$ (or in specific models of a specific theory?) or we wouldn't have independence proofs.

What are some techniques that are used to prove a sentence is undecidable and is there any way to prove $\vdash\phi\leftrightarrow{(\psi\wedge\chi)}$, $\not\vdash\chi\rightarrow{\phi}$ and $\not\vdash\psi\rightarrow{\phi}$ specifically, at least for some instances or models?

Answer 1

You use soundness: Let $L$ be a language and let $T$ be an $L$-theory. Now let $\theta$ be an $L$ sentence. Then;

$T\vdash{\theta}\rightarrow{\forall{M},(M\models{T}\implies{M\models{\theta}})}$

We use this idea:

If you trace through the example I gave here Can a statement in FOL be equivalent to two separate independent statements?; you can see these elements all playing apart.

Let $L=\{\cdot\}$. Let $T=\text{group axioms}\cup \text{there are only twelve distinct elements}$. Now Let $\phi$ say that "I'm is abelian and I'm not cyclic" (i.e. $\forall a,b, a\cdot b = b\cdot a$ and a fairly long sentence that says $\neg{\exists{x}\forall{b}, x=b \lor x^2=b \lor\ldots }$). Then let $\psi$ say that "I'm abelian" and let $\chi$ say that "I'm not cyclic".

Now as you say, $T\vdash\phi\leftrightarrow{(\psi\wedge\chi)}$. But how do we say that and $T\not\vdash\chi\rightarrow{\phi}$ or $T\not\vdash\psi\rightarrow{\phi}$? Well for the first one we would have to show that there is some abelian group with twelve elements that is cyclic, which is easily done by talking about $\mathbb{Z}_{12}$.

But how does this help us? Assume that $T\vdash\chi\rightarrow\phi$. Now all models of $T$ model $\chi\rightarrow\phi$ . However then $(\mathbb{Z}_{12},\cdot)$ models that it is not cyclic. This is a contradiction.

For the second staement we need to show the existence of a group with 12 elements that is not cyclic and is not abelian. For this we can use $A_{4}$.

Edit: To answer the second part of your question, forcing is probably one of the more well known tools for this. But it also has its roots in the above argument.