5. Soundness and Completeness - Logic for Beginners
ฝัง
- เผยแพร่เมื่อ 23 ก.ค. 2024
- This video in the Logic for Beginners series looks at two important concepts in logic, soundness and completeness. These are properties of a logic which tell us how the propositions which can be inferred using a deductive system relate to the semantics. We also take a brief excursion into Gödel's Incompleteness Theorem.
• Previous video: • 4. Deductive Systems -...
• Logic for Beginners playlist: • Logic for Beginners
• Next video: • 6. Examples - Logic fo...
Additional Notes:
• 02:19 - The truth table displayed here and the mention of an interpretation is an example specific to Propositional Logic. Other logics will have different notions of interpretations. The overall point is that semantic entailment means our sentence is true under any interpretation.
• 09:52 - By "true in the syntax" I mean that we can find a proof for the sentence using the deductive system. I.e. we have syntactic entailment.
• 06:48 - The description of Gödel's Incompleteness Theorem is simply a high level overview, it is not intended to show why the result is as it is.
00:00 - Introduction
00:29 - Syntactic Entailment
01:57 - Semantic Entailment
03:07 - Soundness
04:08 - Semantic Completeness
04:40 - Syntactic Completeness
06:48 - Gödel's Incompleteness Theorem
10:13 - Conclusion
Thank you for explaining this better than my teacher
There are not so many videos on this subject, so I'm glad I stumbled upon this great vid. Thanks!
Thanks! It's good to hear it was useful
Thanks for this video! I'm doing a Masters in Cognitive Science and this helped me. You explain things very clearly.
Thank you, I'm glad this helped
woooow. I really had difficulty in understanding completeness and soundness and this video really helped me
That's some great work you've done. Keep up:)
Thank you, that's very kind
Great video! I didn't understand the difference between the two types of turn tiles and soundness and completeness, u explained it so well.
Thanks for your kind words, glad I could help!
This was really helpful, thank you!
Thanks - I'm glad I could help!
I love the video style!
Thank you, that's very kind!
omg thank you!! your video really clarified everything I was confused with....
Fantastic, I'm glad it helped!
THANK YOU
No worries, I'm glad you found it useful!
Excellent video - really enjoyed your style of expositing. If you get the time, please make some more detailed videos of proofs of completeness and soundness for propositional logic and maybe predicate logic. Perhaps you could make some videos on modal and other logics too? Bravo.
Thank you for you comments and suggestions. Making more videos is definitely something I'd like to do in the future... turns out getting a job has made that a bit harder than it was though!
Hey love your channel and wish you would keep going!!!!!
May I pose a few questions kind soul:
Hey so here are the “soft” questions I have compiled. If anything is unclear just let me know!
1)
Does naive set theory require attaching a logic to it to “work” or does logic require set theory to “work”? I am having trouble understanding the true nature of their relationship and they seem really connected during this first pass through some TH-cam videos.
2)
With just naive set theory - no first order logic - can we make truth valuations? Can we even do anything at all in set theory without logic?
3)
why is “first order logic” “fully axiomatizable”, but “independence-friendly first order logic” and “second order logic” isn’t?
4)
Does this mean we can’t trust “independence-friendly first order set theory” and “second order logic” to always make true statements? If not, what consequences does it have if a logic isn’t fully axiomatizable?
Thanks so much!
Good work
Thanks!
Thanks for your lecture. I have a question regarding soundness and completeness. When you say a logic must have the "soundness" property...but as far as I can see, it is not a property of the logic, but the deduction system. Would you mind elaborating more, please?
Thanks for bringing this up.
In general the deductive system will have the biggest impact on whether a logic is sound (and complete). However, do remember that the soundness property is also based on the semantics: we could change the semantics and suddenly soundness might no longer hold!
As a general point, I think it's worth bearing in mind that there's an element of flexibility around the language we use. Sure, it is vital to define rigorously our terms, and I found it was very useful to understand them when learning. However in reality (e.g. in discussions, lectures, lecture notes, etc.) is it often more contextual. This is both because humans aren't very good at being precise, and just because it makes things easier. So I might say "this logic is sound" or "this deductive system is sound", and assuming an understanding of what the terms technically mean, it shouldn't be too tricky to work out what they mean from context.
(Having said that, do pick me up on it if you find anything I've said wrong!)
Is the property of expressing arithmetic effectively (recursive computability of arithmetic) the same as expressive completeness?