Proofs by induction on immediate predecessors (well-formed formula complexity)

[StopWatch]

Hi physics forum,

I have no idea where to start with this:

As far as I know the general pattern for this sort of proof is,

1) All atomic well-formed formulas (wffs) have some property P
2) From the assumption that immediate predecessors of any non-atomic wff A have P, so too does A.
3) Every wff A has P

and I have to:

Prove by induction on immediate predecessors (wff complexity) that
no wff using only the letters P, Q and the connectives ^,v is a tautology.

Any suggestions would be much appreciated.

Thanks in advance,

Stopwatch

 

[mmwave]

Science

Hello StopwatchScience,

Thank you for reaching out to the physics forum for help with your proof. It seems like you already have a good understanding of the general pattern for this type of proof. I would recommend starting by defining the property P that you are trying to prove for all atomic well-formed formulas (wffs). This property could be something like "cannot be reduced to a tautology using only the letters P, Q and the connectives ^,v".

Next, you can proceed with the induction on immediate predecessors. This means that you will need to show that the property P holds for the base case, which would be all atomic wffs. You can then use the assumption that immediate predecessors of any non-atomic wff A have P to show that A also has P.

For the induction step, you will need to show that if the property P holds for all immediate predecessors of a non-atomic wff A, then A also has P. This will involve breaking down A into its immediate predecessors and using the assumption to show that each of these predecessors also has the property P.

Once you have completed the induction step, you can conclude that every wff A has the property P, which means that no wff using only the letters P, Q and the connectives ^,v is a tautology.

I hope this helps guide you in your proof. Please let me know if you have any further questions or need clarification on any steps.