Soundness and Completeness Tutorial | Attic Philosophy

Soundness and completeness are central results about any logic. They both concern the relationship between proof and entailment. Soundness is our guarantee that the things we can prove are genuinely valid. Completeness, on the other hand, says that our proof system is powerful enough to prove all the valid entailments. In this video, I'll explain soundness and completeness in more detail, and why they are important. We'll look at how to prove them in future videos.

00:00 - Intro
01:31 - Soundness
03:05 - Why soundness & completeness are important
04:15 - Some logics aren’t complete
05:27 - Which proof system?
06:30 - Which logic?
07:25 - (In)complete logics
08:27 - Looking ahead

If there’s a topic you’d like to see covered, leave me a comment below.

Links:

Get in touch on Social media!

#logic #philosophy

[leonard]

Truly appreciating these videos on logic! Some of these concepts never stuck with me when I was first introduced to them. These videos seem to help a ton with that :)

[booguy]

Nice and simple breakdown. Looking forward to some deeper content on the topics! 👍

[AtticPhilosophy]

Any questions? Leave me a comment below!

[rektator]

Second order logic is complete, but you have to enlarge the space of semantics. Sets, functions and relations aren't large enough semantics for second order logic. Henkien proved that so called generalized models can provide complete semantics to second order logic. Then there are semantics that category theory offers that allow one to prove completeness of second-order logic and variants of it.

[tomholroyd]

Would you say that sound and complete means syntax is equivalent to semantics? That a formal system can indeed capture meaning? Some would argue that formal systems are too "small". But if a formal system is dialethic, it can be complete, and also sound

[tesafilm]

I don't quite understand the distinction between logic and proof system, is it that logic contains both syntactic and semantic notions while proof systems contain only syntactic ones? But if logic is also about semantics then wouldn't that make it not ontologically neutral (as I thought it was supposed to be) as it would be about truth values and variables?

[jupironnie]

well example of simple explanations to explain some bizarre stuff..

[chachachi-hhks]

We can prove soundness of given logic with metalogic. BUT, how can we be sure that metalogic itself is sound?

[maddycormier]

Great video! if we were to suppose something like a fitch system to be unsound, is it possible that it would be complete ever? im just wondering if we can have something be complete but unsound? thanks

[tomholroyd]

Soundness is more important than consistency

[tomrobingray]

I have a problem with this. I don't see that semantic entailment is even a meaningful concept. Ok for simple systems you can create something like a truth table, but the syntax of these systems will be always be sound and complete ie its 'semantics' will be exactly the same as its 'syntax', they are just different ways of proving the same thing. But for systems that are too complex for truth tables, then these just don't have a 'semantics', they are entirely represented by their syntactic form. So semantic notions are either redundant or undefined, and so basically useless.