1

The following is from Kenneth Kunen: Set theory - an introduction to independence proofs

$S$ is consistent iff for no $\phi$ does $S \vdash \phi$ and $S \vdash \neg \phi.$ If $S$ is inconsistent, then $S \vdash \psi$ for all $\psi$ and $S$ is thus of no interest. By formalizing reductio ad absurdum, one proves for any sentence $\phi$ that $S \vdash \phi$ iff $S \cup \{\neg \phi\}$ is inconsistent and $S \vdash \neg \phi$ iff $S \cup \{\phi\}$ is inconsistent.

I just wanted to justify the last statement.

If for any sentence $\phi,$ $S \vdash \phi$ then $S \nvdash \neg\phi.$ If $\phi_1$ is any sentence from $S,$ then $\phi_1 \wedge \neg\phi \rightarrow \psi$ for any $\psi.$ Thus if we define $S' = S \cup \{\neg \phi\},$ then $S' \vdash \psi$ for any $\psi.$ This means that $S'$ is inconsistent.

By a similar argument, I can prove the other claim - Am I right on this?

Hanul Jeon
  • 27,376
Bijesh K.S
  • 2,604
  • It's not necessarily true for any sentence from $S$ that $\phi_1 \land \lnot \phi \rightarrow \psi$. You need a fragment of $S$ that's big enough to prove $\phi$ for that to be necessarily true. – Robert Shore Sep 01 '21 at 17:15

2 Answers2

2

The statement "For all statements $\phi$, if $S \vdash \phi$ then $S \nvdash \neg \phi$" is exactly the statement that $S$ is consistent.

If you use propositional logic with $\bot$ as a propositional constant ($\bot$ meaning "false"), then it's even easier to state what it means for $S$ to be inconsistent. $S$ is inconsistent if and only if $S \vdash \bot$, and $S$ is consistent if and only if $S \nvdash \bot$. We will use this definition, but it's simple to show that the two statements are equivalent.

If you don't like the thought of adding in a new logical symbol $\bot$ (although I can't think of any reason not to like it), you can substitute $\exists x (x \neq x)$ for $\bot$.

The statement "$S \cup \{\phi\}$ is inconsistent" is exactly the statement $S \cup \{\phi\} \vdash \bot$. This in turn is equivalent to the statement that $S \vdash \phi \implies \bot$. But $\phi \implies \bot$ is logically equivalent to $\neg \phi$, so $S \vdash \phi \implies \bot$ is in turn equivalent to the statement $S \vdash \neg \phi$. So we see that $S \vdash \neg \phi$ if, and only if, $S \cup \{\phi\}$ is inconsistent.

Substituting in $\neg \phi$ for $\phi$ gives us that $S \vdash \neg \neg \phi$ if and only if $S \cup \{\neg \phi\}$ is inconsistent. In classical logic, $\neg \neg \phi$ is logically equivalent to $\phi$, so we see that $S \vdash \phi$ if and only if $S \cup \{\neg \phi\}$ is inconsistent.

Mark Saving
  • 31,855
  • Could you please explain the bit " This in turn is equivalent to the statement that $S \vdash \phi \implies \bot$." ? – Bijesh K.S Sep 02 '21 at 09:20
  • 1
    @BijeshK.S The way we prove an implication $P \implies Q$ is by assuming $P$ and proving $Q$. So to prove $\phi \implies \bot$, we need to assume $\phi$ and prove $\bot$. That is, to prove that $S \vdash \phi \implies \bot$, it is enough to prove $S \cup {\phi} \vdash \bot$. This is how implication works. – Mark Saving Sep 02 '21 at 16:40
1

Here your book's consistent definition using turnstile is purely syntactical, so to prove

for any sentence $\phi$ that $S \vdash \phi$ iff $S \cup \{\neg \phi\}$ is inconsistent

from right to left side, first by definition $S \cup \{\neg \phi\}$ is inconsistent means $S \cup \{\neg \phi\} \vdash \bot$, then per reductio ad absurdum (RAA) natural deduction rule, since $S$ is consistent you can discharge $\neg \phi$ and arrive at $S \vdash \phi$. To prove from left to right side, it's direct from your above textbook definition.

By the way, there's also a concept of semantically consistent as referenced here:

The semantic definition states that a theory is consistent if it has a model, i.e., there exists an interpretation under which all formulas in the theory are true.

It turns out in sentential and first order logic every syntactically consistent set of formulas has a model, a result many textbooks use to prove the completeness theorem of the usual sentential and predicate logic.

cinch
  • 1,648
  • 1
  • 4
  • 12