5. Soundness and Completeness - Logic for Beginners

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.

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

[yian]

Thank you for explaining this better than my teacher

[frankietank]

There are not so many videos on this subject, so I'm glad I stumbled upon this great vid. Thanks!

[nedasayad]

woooow. I really had difficulty in understanding completeness and soundness and this video really helped me

[MathCuriousity]

Hey love your channel and wish you would keep

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 YouTube 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!

[shivatmanyoga]

Thanks for this video! I'm doing a Masters in Cognitive Science and this helped me. You explain things very clearly.

[Joshua-hbcs]

Great video! I didn't understand the difference between the two types of turn tiles and soundness and completeness, u explained it so well.

[haileyh]

omg thank you!! your video really clarified everything I was confused with....

[dandyview]

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.

[None-sszi]

That's some great work you've done. Keep up:)

[rationalistbanner]

Is the property of expressing arithmetic effectively (recursive computability of arithmetic) the same as expressive completeness?

[Furukawanagisa]

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?