# Different definitions for consistent set of sentences

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.

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

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!

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$.