1
$\begingroup$

Usually when we prove some properties of propositional formulas, we use induction on the complexity of propositional formulas, but instead, we can just use induction on the number of occurrence of connections? (Because, I think we need unique readability to define the complexity of formulas. And I want to avoid it.)

$\endgroup$
  • $\begingroup$ Why would you want to avoid unique readability? $\endgroup$ – lemontree Apr 17 at 14:09
  • $\begingroup$ @MauroALLEGRANZA Thank you. But I think we need unique readability to define the $\text {rank} (\varphi)$. And why do we need Polish notation to use the induction on number of occurrences of connectives? $\endgroup$ – amoogae Apr 17 at 14:26
  • $\begingroup$ @lemontree In fact, I have to present about some problem, but I do not have enough time. And I wonder just for logical reasons. $\endgroup$ – amoogae Apr 17 at 14:32
  • $\begingroup$ @MauroALLEGRANZA Thank you for your kind answer. I think I am misunderstanding something.. $\endgroup$ – amoogae Apr 17 at 15:20
  • 1
    $\begingroup$ You can use induction on the number of connectives, but in many cases you'll still need unique readabiity. $\endgroup$ – Andreas Blass Apr 17 at 18:53

Your Answer

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

Browse other questions tagged or ask your own question.