I am trying to prove Unique readability for propositional logic. I have read several proofs around the internet, but I was wondering whether this particular proof I came up with is valid or not and if so, why?
I have defined formulas as follows:
A $\textit{formula}$ is the last element of an ordered $n$-tuple of strings $\langle \epsilon_1,...,\epsilon_n \rangle$ known as construction sequence, such that for each $i \leq n$:
- $\epsilon_i$ is a propositional variable;
- or $\epsilon_i$ is $(\neg \epsilon_j)$ for some $j < i$;
- or $\epsilon_i$ is $(\epsilon_j \rightarrow \epsilon_k)$ for some $j,k < i$.
I have derived an induction principle:
Let $S$ be a set of formulas of $\mathcal{L}$. Consider the following properties:
- $S$ contains all the propositional variables of $\mathcal{L}$.
- If $\phi \in S$, then $(\neg \phi) \in S$.
- If $\phi \in S$ and $\psi \in S$, then $(\phi \rightarrow \psi) \in S$.
If $S$ satisfies all these, then $S$ is the set of all formulas of $\mathcal{L}$.
Can I now prove unique readability as follows:
Let $S$ be the set of formulas that can be constructed in 1 way only; i.e., formulas whose construction sequences differs only in order. All propositional variables have unique construction sequences. Thus, they all belong to $S$. If $\phi$ can be constructed in $1$ way only, then there is only one way to construct $(\neg \phi)$, namely option 2 in definition of formulas. If $\phi$ and $\psi$ can be constructed in one way only, then there is only one way to construct $(\phi \rightarrow \psi)$, namely option 3 in definition of formulas. By the induction principle, $S$ is the set of all formulas.
I suspect that a flaw might be found in the step: "if $\phi$ can be constructed in only one way, then there is only one way to construct $\neg\phi$" and similar. Should I still check that $\neg\phi$ could not be constructed by $\psi \rightarrow \chi$ for instance?