I was going through the completeness theorem for propositional logic from these notes (on page 23 Lemma 2.2.12). Before the proof they give a crucial definition:

$$ t_{\Sigma}(a) = \left\{ \begin{array}{ll} 1 & \mbox{if } \Sigma \vdash a \\ 0 & \mbox{if } \Sigma \not \vdash a \end{array} \right. $$

which felt like a rather unsatisfactory definition of a truth function and I wanted to figure out why. I think the pain reason I thought it was odd was because in my head one can't "prove the atoms". The atoms are just statements, say about the world like a="The clouds are white" which are considered of length 1 and that are either true of false. What I mean they are true or false is that if we had $n$ atoms then setting them to true or false would correspond to one row of a truth table, namely $\{ 0,1\}^n$. Thus a truth function $t:A \to \{0,1\}$ can be thought as a row of the truth table (that then induces truths on propositions). However, here we are defining truth w.r.t. to provability which seems odd to me. So my questions are:

  1. what does it mean to "prove an atom"? I know what formal proof means, its a sequence of statements that are either propositional axioms, are in $\Sigma$ or arrived via Modus Ponens (MP). However, how can one arrive at any atom $a$? Wouldn't that be possible IFF the atoms were already included in $\Sigma$?
  2. $\Sigma \not \vdash a$ seems even harder to show is true. i.e. how do we show there is no smart way of combining the logical rules to never arrive at $a$? My intuition tells me that this can be showed for atoms IFF they are not in $a$ in which $\Sigma \vdash a$ is just a short hand for inclusion of sets.

So is this function $t_{\Sigma}(a)$ just an indicator function if the current atom (statement) is in our set of assumptions $\Sigma$? I guess that would make sense as a way to define truth, we only consider things true if they are in our set of assumptions. Is this correct? Or am I missing something?


1 Answer 1


How can one arrive at any atom $a$? Wouldn't that be possible IFF the atoms were already included in Σ?

No. The set $\Sigma$, which is an arbitrary subset of $\text{Prop}(A)$, might well include $a\land b$ but not $a$; nevertheless $\Sigma\vdash a$.

Added. Here's some more context. The set $\Sigma$ here stands for a propositional "theory": it models (I mean the word in an informal sense, not the technical logical sense) a set of assumptions or axioms (in the informal sense, not the axioms that go into your axiomatic proof system) you'd like to make about a domain of discourse.

Some books define a theory to be not just a subset of well-formed formulas in the grammar of propositional or predicate logic, but the syntactic closure of a set of well-formed formulas. If you only allow yourself to write $T\vdash p$ where $T$ is a theory in the second, stronger sense, then $p\in T$ after all. But if you allow yourself to write $T\vdash p$ where $T$ is a theory in the first, weaker sense, it does not follow that $p\in T$.

  • $\begingroup$ how do you prove an atom if its not in the theory/model/assumptions $\Sigma$? $\endgroup$ Oct 11, 2018 at 22:58
  • 1
    $\begingroup$ I just gave you an example: did you not read the top of my answer? Suppose $\Sigma$ contains only $a\land b$. Then you can prove $a$ using axiom schema 4 in your notes, together with modus ponens. $\endgroup$ Oct 11, 2018 at 23:01
  • $\begingroup$ I think something that is crucially confusing me is that if $\Sigma \not \vdash a$, if that means that $\Sigma \vdash \neg a$ $\endgroup$ Oct 11, 2018 at 23:09
  • 1
    $\begingroup$ Certainly not. If $\Sigma$ is the empty set, then $\Sigma$ proves neither $a$ nor $\lnot a$. Only theories that are “negation complete” have the property you described. $\endgroup$ Oct 11, 2018 at 23:11
  • 2
    $\begingroup$ It is possible that both $\Sigma\nvdash a$ and $\Sigma\nvdash\neg a$. In such a case then $t_\Sigma(\neg a)=0$ and $t_\Sigma(a)=0$ and so $t_\Sigma(\neg a)\neq 1-t_\Sigma(a)$. Likewise if $\Sigma$ is inconsistent, then $\Sigma\vdash a$ and $\Sigma\vdash\neg a$ so $t_\Sigma(\neg a)=1$, $t_\Sigma(a)=1$ and so $t_\Sigma(\neg a)\neq 1-t_\Sigma(a)$ too. $\endgroup$ Oct 11, 2018 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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