Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 at 6: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 at 8:10

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks. How do you like Kaye's book? What level would you classify it into, with what similar books? –  Tim Jul 25 at 6:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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