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?

  • $\begingroup$ Equal does not mean equivalent. The fact that $p\land q$ is equivalent to $q\land p$ does not mean that the two strings are equal. $\endgroup$
    – Asaf Karagila
    Apr 8 '14 at 7:40
  • $\begingroup$ Wait, so why does $(\alpha \wedge \beta) = (\gamma \wedge \delta)$ not immediately imply $\alpha = \gamma$, and why do we have to remove the first parenthesis? $\endgroup$
    – user124577
    Apr 8 '14 at 7:48
  • $\begingroup$ You know that for strings shorter than $(\alpha\land\beta)$ the readability is unique; now you want to prove that for $(\alpha\land\beta)$. So suppose that you could write it as a decomposition $(\gamma\land\delta)$. Now remove the first parenthesis and the strings are still equal, so $\alpha$ is an initial segment of $\delta$, but it can't be a proper initial segment of $\delta$. So they must be equal. $\endgroup$
    – Asaf Karagila
    Apr 8 '14 at 7:51
  • 1
    $\begingroup$ This theorem, much like the pigeonhole principle, or "subsets of a finite set is finite" are theorems of the form "What is there to prove, and why are we wasting time on this?" but in fact these theorems teach us a great deal of respect to the fine details. By not overlooking the fine points, you learn to recognize at later steps where you use the statement that you want to prove within your proof, or where you might be lying to yourself. $\endgroup$
    – Asaf Karagila
    Apr 8 '14 at 7:53
  • $\begingroup$ Thank you for your help! So, the spirit of the proof is essentially an induction. Just to clarify, when you said "so α is an initial segment of δ...", you meant to say γ instead of δ, right? $\endgroup$
    – user124577
    Apr 8 '14 at 7:55

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.

  • $\begingroup$ Why couldn't $\gamma$ be a subformula of $\alpha$? $\endgroup$ Sep 26 '14 at 18:08
  • $\begingroup$ @alessandro - the proof says : "If α and γ are different, then, say [that means : for example], α is a proper initial segment of γ ...". For "The other case, γ being a proper initial segment of α instead" we have the same argument, exchanging the roles of α and γ. $\endgroup$ Sep 26 '14 at 18:56
  • $\begingroup$ We assume that $\gamma$ is different from $\alpha$ and then we say that one as to be the proper initial segment of the other or vice versa. As far as a proper initial segment is not a wff it contradicts the assumption we made at the beginning that so we drop. I don't understand why if $\gamma$ and $\alpha$ are different they must be one the proper initial segment of the other. Why can't they be one the subformula of the other. If so we can't use the fact that a proper initial segment is not a wff, for a subformula being a wff. $\endgroup$ Sep 27 '14 at 16:10
  • $\begingroup$ @alessandro - what you are missing is that we are parsing strings. The theorem aims to prove the (obvious) fact that a formula $\varphi$ cannot e decomposed (correctly) into two different ways. Let $\varphi$ be $(α∧β)$ and $(γ∧δ)$; remove the outer parentheses and we are left with $α∧β and γ∧δ$, that are equal strings. Is it possible that the formula $\varphi$ has two occurrences of $\land$ ? Of course : yes. Is it possible that we can decompose it according to the two different occurrences of $\land$ ? Of course : no. 1/2 $\endgroup$ Sep 27 '14 at 16:36
  • $\begingroup$ The "impossible" case must be : $\varphi := (\sigma_1 \land (\sigma_2 \land \sigma_3))$ with $\alpha := \sigma_1$ and $\beta := (\sigma_2 \land \sigma_3)$. The other possibility must be $\gamma := \sigma_1 \land (\sigma_2$ and $\delta := \sigma_3)$. This is the case where α is a proper initial segment of γ. And now apply the two Lemmas, obtaining a contradiction. 2/2 $\endgroup$ Sep 27 '14 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.