1

In a logic system, a set $\Sigma$ of formulas is said to be inconsistent if $\Sigma \vdash \bot$, and consistent otherwise.

Does it mean that $\Sigma$ is consistent if and only if $\Sigma \vdash \top$? Thanks.

MJD
  • 65,394
  • 39
  • 298
  • 580
Tim
  • 47,382
  • 1
    Think about it. If a set of formulas is inconsistent, does it mean it doesn't imply True? – hardmath Jul 24 '14 at 22:29
  • 2
    What kind of logic would not have $\Sigma \vdash \text{ True}$? Specifically, what about $\emptyset \vdash \text{ True}$? – DanielV Jul 24 '14 at 23:33

2 Answers2

4

Every set of first-order sentences proves $\mbox{True},$ even the empty set; so, you're not negating correctly. If done correctly, you will see that 'consistent' equals 'does not prove false.' Lets just spell out the definitions to make this as clear as possible.

Definition 0. $\Sigma$ is inconsistent iff $\Sigma \vdash \mbox{False}.$

Definition 1. $\Sigma$ is consistent iff not ($\Sigma$ is inconsistent.)

Therefore, $\Sigma$ is consistent iff not ($\Sigma \vdash \mbox{False}.$)

goblin GONE
  • 67,744
2

Nope. We actually have something weirder at first glance. A set of sentences (in a language $L$), $\Sigma$ in FOL is consistent iff there exists a $\phi$ in $L$ such that $\Sigma \not \vdash \phi$. Odd, right?

This follows from the fact that if $\Sigma$ is inconsistent, then for all $\phi$ in $L$, $\Sigma \vdash \phi$. How does this work? Well, first you need to show that if $\Sigma$ is inconsistent, then $\Sigma \vdash \psi \wedge \neg \psi$ for some $\psi$ in $L$ (This is actually an 'iff' statement, and I will leave this portion for you).

Since $\Sigma \vdash \psi \wedge \neg \psi$, we have that: $$\Sigma \vdash \psi \implies \Sigma \vdash \psi \vee \sigma \implies \Sigma \vdash (\psi \vee \sigma) \wedge \neg \psi \implies \Sigma \vdash \sigma $$

Hence, if $\Sigma$ is inconsistent, then $\Sigma$ proves every sentences in the language.

Now, we show that $\Sigma$ is consistent iff there exists a $\phi$ in $L$ such that $\Sigma \not \vdash \phi$. One direction is trivial.

Suppose that there exists $\phi$ in $L$ such that $\Sigma \not \vdash \phi$. Then $\Sigma$ cannot prove anything of the form $\phi \wedge \neg \phi$ (by the proof above). Since if it did, then we could prove everything (including $\phi$). Hence, $\Sigma$ does not prove any contradiction and therefore, by definition, is consistent.

$\mathbf{Edit}$ Note that if $\Sigma$ is an set of sentences, then $\Sigma$ proves all valid sentences.

Kyle Gannon
  • 6,363