Unique readability of propositional sentences
An early theorem of mathematical logic is that every sentence has unique readability. I suspect that the point of the theorem, as fundamental as it is to the subject, is possibly confusing. So the point of this post is to try to articulate the point of the unique readability theorem.
But you'll need a background in symbolic logic, and at least a little familiarity with the first few pages of a standard mathematical logic textbook, to understand what follows. One will also need at least a little familiarity with coding in Python.
For the purposes of this post I'll write sentences in prefix notation, so that for instance \(\land p q\) represents the conjunction of p and q. In prefix notation there is no need for parentheses so that \(\land p \neg q \) is unambiguously intended to mean the conjunction of p on the one hand and \( \neg q\) on the other.
I emphasize that it is our intention to interpret the "expression" as a sentence, but the intention is not yet realized. (An "expression" is any sequence of symbols in the language. One with a more computer science background can think of this as a "string".) The entire point of the unique readability theorem is to guarantee that every expression has a unique way to read it as a particular sentence sturcture.
The unique readability theorem states: If \(\phi\) is any sentence then precisely one of the following conditions holds.
(1) \(\phi\) is atomic
(2) \(\phi = \neg\psi\) for some sentence \(\psi\)
(3) \(\phi = \bullet\psi\chi\) for some binary connective \(\bullet\) and sentences \(\psi,\chi\).
Further the unique readability asserts that if (2) holds then subsentence \(\psi\) is uniquely determined, and if (3) holds then \(\bullet,\psi,\chi\) are each uniquely determined.
I won't discuss the proof. The reason why I think just the statement of the theorem is confusing, is that when I first read the statement I thought "Well yeah obviously. Is this even a theorem or is it just obvious? Why do we need this theorem?"
Of course after further reflection and applying this theorem as a step in the proofs of other theorems, it's clearer to me just what this means and why it's important. Hence the blog post, to try to contribute to making this clear to others, if they perhaps had the same confusion that I did.
In particular I'll try to demonstrate the meaning of this theorem, in a computer simulation of propositional logic. See the Python program below. (I will walk the reader through the code in the remainder of the blog post.)
# phi is the sentence (and)(p1)(not p2)
phi = ['and', 'p1', 'not', 'p2']
# psi is the sentence (iff)(not p1)(not p2)
psi = ['iff', 'not', 'p1', 'not', 'p2']
# tva_example is the truth-value assignment based on p1->True and p2->True
tva_example = [True, True]
binary_connectives = ['and','or','if','iff']
def find_end_sent(p):
'''Input an expression which is a concatenated list of sentences. Output the index after the end of the first sentence.'''
needed = 1
index = 0
while True:
if p[index] in binary_connectives:
needed += 1
elif p[index] == 'not':
pass
else:
needed -= 1
index += 1
if needed < 1:
return index
class Sentence:
'''Object representation of a sentence. Fields: expression, main_connective, subsent1, subsent2'''
def __init__(self, p):
self.expression = p
self.main_connective = None
self.subsent1 = None
self.subsent2 = None
if p[0] == 'not':
self.main_connective = 'not'
self.subsent1 = Sentence(p[1:])
if p[0] in binary_connectives:
self.main_connective = p[0]
i = find_end_sent(p[1:])
self.subsent1 = Sentence(p[1:i+1])
self.subsent2 = Sentence(p[i+1:])
phi = Sentence(phi)
psi = Sentence(psi)
def eval(p, t):
if p.main_connective == None:
atom = p.expression[0]
index = int(atom[1:])-1
return t[index]
if p.main_connective == 'not':
return not eval(p.subsent1, t)
left = eval(p.subsent1, t)
right = eval(p.subsent2, t)
if p.main_connective == 'and':
return left and right
if p.main_connective == 'or':
return left or right
if p.main_connective == 'if':
return (not left) or right
return left == right
print(eval(phi,tva_example))
print(eval(psi,tva_example))The code starts with a representation of expressions as lists of symbols. The symbols are themselves represented in Python as strings, such as ‘and’ and ‘p1’ where ‘p1’ is understood to be the atomic sentence \( p_1\). As such these are unstructured, which is to say, it is not immediately obvious what are its subsentences.
This is particularly a problem if we would like to evaluate the sentence using an atomic truth assignment. For instance, we can represent an atomic truth assignment by a list of truth-values. This positionally corresponds to the corresponding atomic sentence. For instance, in this example [True, True] is the atomic truth-value assignment. Because the first element is True this positionally corresponds to the truth value we are assigning to \( p_1\). Because the second element is True, positionally we are assigning it to \( p_2\).
How do we then determine the truth-value of the sentence phi when it is unstructured? We cannot easily scrape out the subsentences to find their values and then apply the rule for the appropriate connective.
The unique readability theorem says that every sentence has a unique structure determined by its connective and subsentences, if there are any. The Python class Sentence represents that in the code by taking an expression and finding its main connective, then scraping for its first subsentence, and then determining the second subsentence, if these exist. The object so constructed is then a structured object—structured as a sentence is, with these components.
In this way, every sentence will have precisely one main connective, corresponding to the unique readability’s claim that every sentence satisfies precisely one of the three conditions enumerated earlier.
Similarly, if a sentence is of type (2) in the unique readability theorem, then its subsentence is uniquely determined. In the Sentence object corresponds to the fact that this.subsent1 will have a determined value when the main connective is not. We can of course also make similar remarks about what happens when the sentence is of type (3).
Having done all that, it is now possible to assign truth-value to the sentence, by means of an atomic truth assignment. This is done recursively, in the eval function, and practically just reiterates the very semantics of the connectives.