2
$\begingroup$

In my logic class, we were given the following definition for a set of sentences being consistent in first order logic:

Let $\Gamma$ be a set of sentences in some underlying language $L$. The set $\Gamma$ is inconsistent if $\Gamma \vdash \varphi$ for all $L$ sentences $\varphi$. The set $\Gamma$ is consistent if it is not inconsistent.

We were then given several equivalent definitions. In particular, we were told that

$\Gamma \cup \{\gamma\}$ is inconsistent if and only if $\Gamma \vdash \neg \gamma$.

I am trying to verify this on my own, and can easily show that if $\Gamma \vdash \neg \gamma$ then $\Gamma \cup \{\gamma\}$ is inconsistent, but I am having more trouble with the other direction. I feel like it should be relatively simple, but I do not have much experience with formal logic.

All of my attempts run into a wall where I feel like I need to prove the following: if $\Sigma \cup \{\sigma\} \vdash \neg \sigma$ then $\Sigma \vdash \neg \sigma$, which makes intuitive sense, but which I cannot formalize.

$\endgroup$
  • $\begingroup$ I don't think the statement about $\Gamma \cup \{\gamma\}$ is a definition. $\endgroup$ – Mike Nov 13 '14 at 5:49
  • $\begingroup$ Does $\vdash$ have a semantic meaning (to do with models) or a syntactic meaning (to do with formal proofs)? $\endgroup$ – Mike Nov 13 '14 at 5:51
  • $\begingroup$ If it is the syntactic meaning, this might help you. en.wikipedia.org/wiki/Deduction_theorem $\endgroup$ – Mike Nov 13 '14 at 5:58
  • $\begingroup$ Essentially, it's a duplicate of math.stackexchange.com/questions/1018833/… $\endgroup$ – Asaf Karagila Nov 13 '14 at 8:15
2
$\begingroup$

We just need to use the deduction theorem and remember some useful definitions:

Claim: If $\Gamma \cup \{\gamma\}$ is inconsistent then $\Gamma \vdash \neg \gamma$

Proof: Suppose that $\Gamma \cup \{\gamma\}$ is inconsistent. Then, by the definition of an inconsistent set above, $\Gamma \cup \{\gamma\} \vdash \varphi$ for all $L$ sentences $\varphi$. Hence, $\Gamma \cup \{\gamma\} \vdash \bot$ and, by deduction theorem, $\Gamma \vdash \gamma \to \bot$. Now, by the usual definition of $\neg$, it means that $\Gamma \vdash \neg \gamma$.

Hope this helps!

$\endgroup$
2
$\begingroup$

The above definitions of consistency are expressed in terms of the derivability relation : $\vdash$.

Thus, in order to study their properties, we need the rules of the proof system.

Your definition of consistency is one of the two "natural" definition of consistency, the other being :

$\Gamma$ is consistent if there is no formula $\varphi$ such that both : $\Gamma \vdash \varphi$ and $\Gamma \vdash \lnot \varphi$.

Alternatively, if the language has the symbol $\bot$ (the falsum), we can state it as :

$\Gamma$ is consistent if $\Gamma \nvdash \bot$.

In any case, we can prove :

The following conditions are equivalent:

(i) $\Gamma \nvdash \bot$

(ii) For no $\varphi$, $\Gamma \vdash \varphi$ and $\Gamma \vdash \lnot \varphi$,

(iii) There is at least one formula $\varphi$ such that $\Gamma \vdash \varphi$.

Finally, we can prove :

(a) if $\Gamma \cup \{ \lnot \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$,

(b) if $\Gamma \cup \{ \varphi \}$ is inconsistent, then $\Gamma \vdash \lnot \varphi$.

To prove it, we will use as proof system the Natural Deduction one; in it we have $\bot$ as primitive and the definition of $\lnot \varphi$ as $\varphi \rightarrow \bot$.

We have also the rules for $\lnot$ :

$$\frac {\bot } \varphi \quad \text{(EFQ)}$$

$$\frac {\lnot \varphi \vdash \bot} \varphi \quad \text{(RAA)}$$

We have to use also the rules for managing $\rightarrow$ :

$$\frac {\varphi \rightarrow \psi \quad \varphi } \psi \quad \text{($\rightarrow$-E)}$$

$$\frac {\varphi \vdash \psi } {\varphi \rightarrow \psi} \quad \text{($\rightarrow$-I)}$$

If we apply the $\rightarrow$-E rule with $\bot$ in place of $\psi$, due to the fact that $\varphi \rightarrow \bot$ is $\lnot \varphi$, we can derive a new rule for $\lnot$ :

$$\frac {\lnot \varphi \quad \varphi } \bot \quad \text{($\lnot$-I)}$$


We assume the following definition : $\Gamma$ is inconsistent if $\Gamma \vdash \bot$.

Thus, form the assumption that $\Gamma \cup \{ \lnot \varphi \}$ is inconsistent, we have :

$\Gamma \cup \{ \lnot \varphi \} \vdash \bot$;

then, applying RAA rule we have :

$\Gamma \vdash \varphi$.

If we assume that $\Gamma \cup \{ \varphi \}$ is inconsistent, we have :

$\Gamma \cup \{ \varphi \} \vdash \bot$;

then, applying $\rightarrow$-I rule we have :

$\Gamma \vdash \lnot \varphi$.



Note

This proof can be adapted to others proof systems.

For an Hilbert-style one, we can use the definition :

$\Gamma$ is inconsistent if for every formula $\varphi$ : $\Gamma \vdash \varphi$.

We need some preliminary Lemmas; we have to prove that :

$\lnot \varphi → \varphi \vdash \varphi$

[see this post for a proof].

With this result we can prove :

if $\Gamma \cup \{ \lnot \varphi \} \vdash \psi$ and $\Gamma \cup \{ \lnot \varphi \} \vdash \lnot \psi$, then $\Gamma \vdash \varphi$

and finally apply it to prove :

if $\Gamma \cup \{ \lnot \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.