Hi, Thank you for the video I only know introductory terms, I plan on taking Computer science they also have a formal logic class which I'm most excited to do. I hope to continue from Incompleteness theorem
Hello again. I have used proof by induction many times. Here is an example that I have used recently used to develop a weakly intuitionistic asymmetric modal logic, that is transitive and irreflexive, which corresponds nicely to directed acyclic graphs, or topological orderings. The proof by induction goes as follows, given there are n accessible relations, for any n+1 accessible relation, there must be n+1 vertices in the graph that has transitive closure for which n is not an element of n+1. Given aRb implies ~(bRa), with the added condition ~(aRb). Fun fact, Alfred Tarski developed a nontrivial axiomization of the reals using < over the reals be asymmetric. This is indeed equivalent to Zermelo ordinals, and Zorm's Lemma. In fact, proof by induction is so deep that it is often represented as a basic axiom for the natural numbers, and often conditions the Bolzano-Weierstrass theorem.
Isn't it true that strong induction is also implied by weak induction, and not only vice versa? I'm pretty sure you can prove that strong induction works by using weak. So, the two are equivalent, and so it's always boggled my mind a bit why I'd ever want to use the one rather than the other. Also, as for why induction works, I think it's worth mentioning that this relies on how natural numbers are defined (Peano induction axiom). Thanks for the great content!
That’s right. Strong is usually used in logic, for induction on complexity of formulas, since complexity of, say, A&B will be >, but needn’t be +1, complexity of A.
Hello Mark, thank you for your dedication to Logic. The first time I saw a mathematical induction proof, I didn't feel too satisfied with the mathematical explanation. After I notice that the process looks a lot like an iteration of "Modus Ponens" and the generalization happens because a general term is used in the inductive hypothesis, then I felt much better. Now these days, I see mathematical induction and its variations as an application of "Modus Ponens". Am I on the right track?
Induction proof is a method used in maths proofs when integers are involved ( n+1 case ). Is it justified to extend this method to Logic using complexity as a equivalent to measure of Integer? It looks more like we are , like some idem with square bolts and spanners", i cant recall exact words. My DIY skills tells me if you can use the wrong tools, it just takes a lot more effort and you might get the same result.
You can use induction on anything you can measure with integers. The complexity of a formula is an integer, so you can use induction on the complexity of formulas. That's how it's used in logic proofs.
Have you used proof by induction? Got any questions? Leave me a comment below!
Hi, Thank you for the video I only know introductory terms, I plan on taking Computer science they also have a formal logic class which I'm most excited to do. I hope to continue from Incompleteness theorem
Hello again. I have used proof by induction many times. Here is an example that I have used recently used to develop a weakly intuitionistic asymmetric modal logic, that is transitive and irreflexive, which corresponds nicely to directed acyclic graphs, or topological orderings. The proof by induction goes as follows, given there are n accessible relations, for any n+1 accessible relation, there must be n+1 vertices in the graph that has transitive closure for which n is not an element of n+1. Given aRb implies ~(bRa), with the added condition ~(aRb). Fun fact, Alfred Tarski developed a nontrivial axiomization of the reals using < over the reals be asymmetric. This is indeed equivalent to Zermelo ordinals, and Zorm's Lemma. In fact, proof by induction is so deep that it is often represented as a basic axiom for the natural numbers, and often conditions the Bolzano-Weierstrass theorem.
Great example! So yes, it's not always proof by induction on the complexity of some sentence.
Isn't it true that strong induction is also implied by weak induction, and not only vice versa? I'm pretty sure you can prove that strong induction works by using weak. So, the two are equivalent, and so it's always boggled my mind a bit why I'd ever want to use the one rather than the other. Also, as for why induction works, I think it's worth mentioning that this relies on how natural numbers are defined (Peano induction axiom). Thanks for the great content!
That’s right. Strong is usually used in logic, for induction on complexity of formulas, since complexity of, say, A&B will be >, but needn’t be +1, complexity of A.
Hello Mark, thank you for your dedication to Logic. The first time I saw a mathematical induction proof, I didn't feel too satisfied with the mathematical explanation. After I notice that the process looks a lot like an iteration of "Modus Ponens" and the generalization happens because a general term is used in the inductive hypothesis, then I felt much better. Now these days, I see mathematical induction and its variations as an application of "Modus Ponens". Am I on the right track?
That's right, it's like a universal generalisation, with each instance giving a step of modus ponens.
Induction proof is a method used in maths proofs when integers are involved ( n+1 case ). Is it justified to extend this method to Logic using complexity as a equivalent to measure of Integer? It looks more like we are , like some idem with square bolts and spanners", i cant recall exact words. My DIY skills tells me if you can use the wrong tools, it just takes a lot more effort and you might get the same result.
You can use induction on anything you can measure with integers. The complexity of a formula is an integer, so you can use induction on the complexity of formulas. That's how it's used in logic proofs.
why didn't my teacher say it like you. Thank you
I feel like there's a part 2
Not yet there isn't!