# How does one prove atoms in propositional logic?

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?

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

• how do you prove an atom if its not in the theory/model/assumptions $\Sigma$? – Pinocchio Oct 11 '18 at 22:58
• 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. – symplectomorphic Oct 11 '18 at 23:01
• I think something that is crucially confusing me is that if $\Sigma \not \vdash a$, if that means that $\Sigma \vdash \neg a$ – Pinocchio Oct 11 '18 at 23:09
• 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. – symplectomorphic Oct 11 '18 at 23:11
• 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. – Graham Kemp Oct 11 '18 at 23:41