How does one prove atoms in propositional logic

logicpropositional-calculus

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?

Best Answer

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

Related Question