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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .