41. Logic. Gödel's Completeness theorem

Hellenic Legacy
8 followers
5 Video Views·Jan 18, 2025
Welcome back everybody so our last theorem which we won't prove today
actually we will spend the whole next two weeks proving it is the completeness
theorem. GEDL's famous completeness theorem. The completeness theorem says
that if a formula or a sentence phi is implied logically from gamma then it can
be proved from gamma. So what this is saying is if it's true that in every model of
gamma satisfies phi then there is an actual proof a syntactical proof of phi
from gamma which is the most you can hope for right because we know already
from soundness that if you prove something then that has to be true in
terms of models so now we are proving the reverse that if it's true in terms of
models then you can prove it. So that means everything that is possible to
prove you can prove just with this modus ponens rule and the logical axioms. So in
that sense is that this is the completeness theorem. It's telling you that the rules
for writing formal proofs namely modus ponens and the logical axioms are
complete there is nothing else that you need to do for your proof so whenever
you do a proof that's like if you want to prove something is that something is
true in this sense then there is a proof from there using those logical axioms and
the rules. So it's gonna be hard to prove this one but let's talk about it a
little bit more. So the second part is an equivalent statement so they both mean
the same thing and that if a set of formulas is consistent then it is
satisfied. We already show from soundness that if you're satisfiable you must be
consistent so this is kind of the reverse of that and the proof is essentially the
same as we had before. The proof of this is that if gamma is not satisfiable then
for every formula beta gamma semantically implies beta. The reason for that is that
if you're not satisfied we don't have any model so it's trivially true that every
model of gamma is a model of beta. Every model of gamma is a model of beta just
because there are no models of gamma. So this is true for every formula
you've implied and also then that means also you will get also the negation that
will also be implied but then by the completeness theorem by part one
you will get that gamma proves beta and gamma proves not beta. So that's how you
get that one implies two which you haven't provided. What's the reason that
two implies one? And this is by a contrapositive if gamma
does not prove phi then by the reduction to absurdum that we proved
last week if you don't prove something then gamma and the negation are
consistent. Okay so we're going to use this one in the opposite direction. If you
don't prove then this is not inconsistent. So if you don't prove phi
then gamma together with not phi is consistent but then by part two gamma
together with not phi is satisfiable but then that implies the gamma does not
logically imply phi because gamma logically implies phi means that every
model of gamma is a model of phi and this being satisfiable says that there
exists a model of gamma which is not a model of phi. So that means gamma cannot
imply phi and that's what we get in this contrapositive. Cool so those two are
equivalent and together they are called completeness theorem. We are
actually going to prove this one. We're going to show that if you're consistent
then you're satisfiable and that's going to imply the other one. Okay and then
this is actually going to get this together with soundness we get even
only essentially we get that logical implication is equivalent to
syntactical implication and we get the consistency is equivalent to
satisfiability using soundness for the other direction. Okay so one corollary of
this that we've been using for a long time is compactness. So the
compactness theorem follows directly from here. The compactness theorem has two
versions I also like this one too which we saw already that they are
equivalent. The first one says that if gamma logically implies phi then there's
a finite subset of gamma that already logically implies phi and equivalently
we say that this is the same thing as saying that if every finite subset of a
gamma is satisfiable then the whole gamma is satisfied. Right so we use both
versions. Both are equivalent we even prove that they are equivalent. So that's
compactness and why does it follow from completeness? Well it's very simple
because by completeness and soundness together we know that logical
implication is the same as a formal semantic a syntactic implication right
and so therefore they are the same. So if a whole set of sentences proves this
sentence phi that means we have a deduction a formal deduction of phi from
gamma. In the formal deduction we can only use finitely main sentences right
a formal deduction is a finite list of formulas and some of those are used
account in the section as assumptions but only finitely many. So we are using
finitely many of the assumptions in the proof not more than that. So we can take
a finite subset which are the ones that are used in the proof and that's enough
to prove phi which again if you prove phi then by soundness you logically imply phi.
So that's the proof of compactness. So compactness is very easy if you look at
formal deductions and completeness and soundness tell you the formal deductions
are the same as logical deductions. Okay so we'll actually do this proof in the next
coming weeks. See you guys later
