I really do not understand the Unique Readability Theorem proof (in Enderton's book). The proof essentially goes that we have wffs $\alpha, \beta, \gamma, \delta$, and that if we assume $(\alpha \wedge \beta) = (\gamma \wedge \delta)$ then by deleting the first parenthesis on both sides of the equality, i.e. $\alpha \wedge \beta) = \gamma \wedge \delta)$, that this forces $\alpha = \gamma$, because otherwise $\alpha$ might be a proper initial segment of $\gamma$. But isn't it possible that $\alpha$ is something completely different from $\gamma$, i.e. $\alpha = (X), \gamma = (Y)$, so why is $\alpha$ forced to equal $\gamma$? I must be missing something, but I don't really get what.
EDIT: In fact, couldn't we let $\alpha = (X), \beta = (Y), \gamma = (Y), \delta = (X)$ and have the equality still hold?
1 Answer
See Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001).
The Unique Readibility Theorem [page 40] says that for any formula $\varphi$, its immediate predecessors (that are well-formed formulae !) are uniquely determined.
This means that each formula, written without "colloquialisms" : e.g. as $(\alpha \land \beta)$ and not $\alpha \land \beta$, is "built-up from the set of sentence symbols by the five operations in a unique way.
Consider the formula $\varphi$ and assume that we can decompose it in two different way :
$\varphi := (\alpha \land \beta)$ and $\varphi := (\gamma \land \delta)$, where either $\alpha$ and $\gamma$ are different strings, or $\beta$ and $\delta$ are different strings, or both.
Consider the cases :
(i) $\alpha$ and $\gamma$ are different.
Both $\alpha$ and $\gamma$ are proper initial segments of $\varphi$ (i.e. initial substrings of $\varphi$); thus, one must be a proper initial segment of the other.
Then, say, $\alpha$ is a proper initial segment of $\gamma$ (of course, $\alpha$ is nonempty : otherwise our $\varphi$ is $(\land \beta)$, that it is not well-formed).
By Lemma 13B [page 30], being a proper initial segment of the wff $\gamma$, $\alpha$ has more left brackets than right ones; but $\alpha$ is also a wff and thus, by Lemma 13A [page 30], it has the same number of left and right brackets. Impossible!
The other case, $\gamma$ being a proper initial segment of $\alpha$ instead, is equally impossible.
(ii) If $\alpha$ and $\gamma$ match, this forces $\beta$ and $\delta$ to be the same string, since the strings $(\alpha \land \beta)$ and $(\gamma \land \delta)$ are the same, and it's okay again.
Having answered "no" in all cases, we are done.
