2 proofs on consistency

64 Views Asked by At

Could anyone check if my proof for the following is correct please? In particular, I am not feeling very comfortable about my inference from $Γ \vdash φ$ to $Γ ∪ \{¬φ\} \vdash φ$.

Let $Γ$ be a set of formulas and $φ$ a formula.

a). $Γ ∪ \{¬φ\}$ is inconsistent if and only if $Γ \vdash φ$.

b). Suppose that $Γ$ is consistent and $Γ \vdash φ$. Then $Γ∪ \{φ\}$ is consistent.

a). The $\rightarrow$ has already been provided in the book, so I will only prove $\leftarrow$.

Suppose $Γ \vdash φ$. We need to prove that $Γ ∪ \{¬φ\} \vdash \phi$ and $Γ ∪ \{¬φ\} \vdash \lnot\phi$.

Since $Γ \vdash φ$, and $Γ$ is a member of the broader set of assumptions $Γ ∪ \{¬φ\}$, that must mean there is also a proof from this broader set to $φ$, ie. $Γ ∪ \{¬φ\} \vdash φ$.

$\lnot φ$ is itself already a member of the set of assumption $Γ ∪ \{¬φ\}$, so $Γ ∪ \{¬φ\} \vdash \lnot φ$.

Since from $Γ ∪ \{¬φ\}$ one can derive both $\lnot φ$ and $φ$, this set is inconsistent.

b). Suppose that $Γ$ is consistent and $Γ \vdash φ$. If $Γ∪ \{φ\}$ is not consistent, then that means $Γ∪ \{φ\} \vdash\psi $ and $Γ∪ \{φ\} \vdash \lnot\psi $. $\{φ\}$ on its own cannot derive $\lnot φ$, so IF this is possible it must be from $Γ$.

But we know that $Γ$ is consistent and $Γ \vdash φ$, so it is impossible for $Γ \vdash \lnot φ$ as well. So to conclude it is impossible for $Γ∪ \{φ\} \vdash \lnot\psi $ and hence $Γ∪ \{φ\}$ is consistent.

1

There are 1 best solutions below

1
On BEST ANSWER

Could anyone check if my proof for the following is correct please?

It reads clear and is correct. It is a good proof.

In particular, I am not feeling very comfortable about my inference from $Γ \vdash φ$ to $Γ ∪ \{¬φ\} \vdash φ$.

If you can derive $\varphi$ from (some of the) assumptions in set $\Gamma$, then you can derive $\varphi$ from (some of the) assumptions in any superset of $\Gamma$; including inconsistent ones.