The Language $\mathcal{L_0}$: Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in \mathbb{N}$ satisfying the following properties:

(1) For each propositional symbol $A_n$ with $n\in\mathbb{N}$, \begin{multline} A_n \in L. \end{multline}

(2) For each pair of finite sequences $s$ and $t$, if $s$ and $t$ belong to $L$, then \begin{multline} (\neg s) \in L \end{multline} and \begin{multline} (s \to t) \in L. \end{multline}

Readability for $\mathcal{L_0}$: Suppose that $\phi$ is a formula in $\mathcal{L_0}$. Then exactly one of the following conditions applies.
(1) There is an $n$ such that $\phi = A_n.$
(2) There is a $\psi \in \mathcal{L_0}$ such that $\phi = (\neg\psi)$.
(3) There are $\psi_1$ and $\psi_2$ in $\mathcal{L_0}$ such that $\phi = (\psi_1 \to \psi_2)$

Unique Readability for $\mathcal{L_0}$: Same conditions as Readability, but in (2) and (3), the formulas $\psi$, $\psi_1$, and $\psi_2$ are unique, respectively.

Problem (Polish Notation): Let $\mathcal{P_0}$ be the smallest set of sequences $P$ such that the following conditions hold.
a) For each $n$, $A_n \in P$.
b) If $\psi_1$ and $\psi_2$ belong to $P$, then so do $\neg\psi_1$ and $\to\psi_1\psi_2 = \langle \to \rangle + \psi_1 + \psi_2$.

State and prove the unique readability theorem for $\mathcal{P_0}$

  • $\begingroup$ On readability, there is a typo on (2), the LHS is supposed to be $\phi$. On (1), as in another question, I don't agree with $\langle \rangle$ enclosing the propositional symbols. The set $P$ is a set of sequences of what? I must be reading something very wrong because it looks to me like $\mathcal P_0=\mathcal L_0$. $\endgroup$ – Git Gud Oct 14 '14 at 23:37
  • $\begingroup$ "I'm a little confused on this language. It says If $\psi_1$ and $\psi_2$ belong to $P$, then so do $(\neg\psi_1)$ and $(\psi_1 \to \psi_2)$. Are they at all implying that $(\neg\psi_2)$ not exist?" $\endgroup$ – Git Gud Oct 14 '14 at 23:42
  • 1
    $\begingroup$ It's not all implying that $(\neg \psi _2)$ doesn't exist, in fact it's saying it exists. One has $\forall \psi_1, \psi_2((\neg \psi_1)\in P\land (\psi_1\to \psi_2)\in P)$ which is equivalent to $\forall \psi_1, \psi_2((\neg \psi_1)\in P)\land \forall \psi_1, \psi_2((\psi_1\to \psi_2)\in P)$ which in turn implies $\forall \psi_1, \psi_2((\neg \psi_1)\in P)$ from where one gets $\forall \psi_1((\neg \psi_1)\in P)$ and finally as it is a dummy variable one gets $\forall \psi_2((\neg \psi_2)\in P)$. $\endgroup$ – Git Gud Oct 14 '14 at 23:43
  • $\begingroup$ Is 'induction on the complexity of formulas' available to you yet? $\endgroup$ – Git Gud Oct 14 '14 at 23:46
  • $\begingroup$ Induction on length, but I'll look into induction on the complexity of formulas. $\endgroup$ – Kevin Carroll Oct 14 '14 at 23:52

Suppose $\phi$ is a formula in $\mathcal{P_0}$. Then $\phi$ is one and only one of these forms:
(1) There is an $n$ such that $\phi =A_n$.
(2) There is a $\psi$ in $\mathcal{P_0}$ such that $\phi = \neg\psi$.
(3) There are $\psi_1$ and $\psi_2$ in $\mathcal{P_0}$ such that $\phi = \to\psi_1\psi_2$.
Further, the $\psi_i$ in (2) and (3) are uniquely determined.

It is absolutely clear these are mutually exclusive in polish notation. All that remains is to show that in (2) and (3), these $\psi_i$ are unique:

For (2), suppose $\neg\psi_a$ = $\neg\psi_b \implies \psi_a=\psi_b \implies$ uniqueness.
For (3), suppose $\to\psi_1\psi_2=\to\psi_3\psi_4 \implies \psi_1\psi_2=\psi_3\psi_4 \implies$ one of $\psi_1,\psi_3$ is an initial segment of one another, which we know is not possible:

Let $w$ be the weight of the symbols:
$w(A_n) = 1, w(\neg)=0, w(\to) = -1$.

Then for any polish-formula $\psi = s_1\dots s_n$ of length $n$, The sum of the weights of its symbols, $\sum_{i=1}^{n}w(s_i) =1$ by induction.

Any terminal segment of a polish-formula is a concatenation of polish-formulas. So suppose $\psi'$ is a proper initial segment polish-formula of the polish-formula $\psi$, and $\psi''$ is the terminal segment of $\psi$ that makes $\psi=\psi'\psi''$.

If $\psi=\psi'\psi''$ then $w(\psi) = w(\psi')+w(\psi'')$. But $\psi''$ is a terminating segment of a polish-formula so its weight is greater than or equal to $1$. Contradiction.

  • $\begingroup$ "an initial segment of one another, which we know is not possible" I bet, that had to be proved as a lemma, ah? $\endgroup$ – carlosayam Oct 16 '14 at 23:52
  • $\begingroup$ In my text it was proved prior, but I suppose not technically in Polish notation $\endgroup$ – Kevin Carroll Oct 16 '14 at 23:57
  • $\begingroup$ I included proof of the lemma $\endgroup$ – Kevin Carroll Oct 17 '14 at 0:33

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.