0

$\def\True{\top}\def\False{\bot}$ In Kaye's math logic, $X$ is a set of propositional letters, and $BT(X)$ is the set of Boolean terms over $X$. There is a theorem about its valuation on the binary Boolean algebra $\{\True, \False \}$:

enter image description here

  1. Why is it named "completeness theorem"? I think it is not about "completeness" but about "soundness", because completeness is from $\Sigma \vDash \True$ to $\Sigma \vdash \True$, while soundness is from $\Sigma \vdash \True$ to $\Sigma \vDash \True$:

    enter image description here

    enter image description here

  2. In particular, I am not sure if "$\Sigma_0$ is consistent" means $\Sigma_0 \vdash \True$.

Thanks.

Community
  • 1
Tim
  • 47,382
  • Regarding consistency [see also your previous post], the answer is : NO. See page 65 : "we will say that $Σ$ is inconsistent if $Σ \vdash ⊥$, and consistent otherwise." Thus (properties of negation) : $\Sigma$ is consistent iff it does not prove "the false", i.e. iff $\Sigma \nvdash \bot$. – Mauro ALLEGRANZA Jul 25 '14 at 06:46
  • Regarding Completeness Th, see page 89 : "Theorem 7.13 (Completeness Theorem, second form) : Let $X$ be a set, and suppose that $Σ ⊆ BT(X), τ ∈ BT(X)$ with $Σ \vDash τ$. Then $Σ \vdash τ$, i.e. there is a formal derivation of $τ$ from $Σ$", which is exactly what you expected. It is proved as a corollary of the first form of the Completeness Theorem. – Mauro ALLEGRANZA Jul 25 '14 at 08:10

1 Answers1

4

Kaye's theorem is that if a set of sentences is syntactically consistent, there is a valuation which makes the sentences all true together.

That trivially implies that if some sentences $\Gamma, \neg\phi$ can't all be true together, then $\Gamma, \neg\phi$ aren't consistent.

In other words, if $\Gamma \vDash \phi$ [= no valuation makes all $\Gamma$ true and $\neg\phi$ true as well] then $\Gamma \vdash \phi$ [for if $\Gamma, \neg\phi$ are inconsistent, then by reductio $\Gamma \vdash \phi$].

So yes, Kaye's result is indeed a version of the completeness theorem.

I should add -- as you are asking a vast number of questions here -- that this is entirely routine, and is explained in any number of books. For the standard Henkin-style proof of completeness goes precisely via showing that any any consistent set of sentences has a model. Perhaps you should try putting your brain into gear, and consulting more than one text when you hit something you find difficult, before troubling math.se quite so often.

Peter Smith
  • 54,743
  • Thanks. How do you like Kaye's book? What level would you classify it into, with what similar books? – Tim Jul 25 '14 at 06:27