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

• StopWatch
In summary, "proofs by induction on immediate predecessors" is a method used in mathematical logic to prove the validity of a statement. It involves dividing the proof into smaller cases based on the immediate predecessors of a well-formed formula and gradually building up to the more complex cases. The complexity of the formula determines the number of cases needed for the proof. The steps involved include identifying the immediate predecessors, dividing into cases, proving the base case, and using the inductive hypothesis to prove subsequent cases. This method is advantageous as it breaks down complex proofs and allows for a systematic approach. However, it can only be used for statements involving well-formed formulas and not for statements with quantifiers or other logical operators.
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

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.

1. What is the concept of "proofs by induction on immediate predecessors" in mathematical logic?

"Proofs by induction on immediate predecessors" is a method used to prove the validity of a statement in mathematical logic. It involves dividing the proof into smaller, simpler cases based on the immediate predecessors of a well-formed formula. This allows for a step-by-step approach to proving a statement, starting from the simplest cases and gradually building up to the more complex ones.

2. How does well-formed formula complexity play a role in proofs by induction on immediate predecessors?

The complexity of a well-formed formula refers to the number of logical operations and symbols used to construct it. In proofs by induction on immediate predecessors, the complexity of a formula is used to determine the number of cases needed for the proof. As the complexity increases, the number of cases also increases, making the proof more intricate.

3. What are the steps involved in a proof by induction on immediate predecessors?

The first step is to identify the immediate predecessors of the well-formed formula in question. Next, the formula is divided into cases, each of which corresponds to a different predecessor. Then, the base case (the simplest predecessor) is proved. After that, the inductive hypothesis is assumed for the next predecessor and used to prove the next case. This process continues until the final case is reached, proving the validity of the original formula.

4. What are the advantages of using proofs by induction on immediate predecessors?

Proofs by induction on immediate predecessors are advantageous because they break down complex proofs into smaller, more manageable steps. This makes it easier to understand and verify the validity of a statement. It also allows for a systematic approach to proving a statement, making it less prone to errors.

5. Can proofs by induction on immediate predecessors be used to prove any statement in mathematical logic?

No, proofs by induction on immediate predecessors can only be used for statements that involve well-formed formulas. They cannot be applied to statements that involve quantifiers or other logical operators. In those cases, different proof methods such as mathematical induction or proof by contradiction may be used.

Similar threads

• Set Theory, Logic, Probability, Statistics
Replies
40
Views
7K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Quantum Physics
Replies
210
Views
15K
• Calculus
Replies
8
Views
602
• Calculus
Replies
3
Views
409
• Calculus
Replies
7
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K