All language subtitles for captions_compactness_en

hello everybody so we can continue on the theme
of the week which is uh we're going to look at

compactness theorem so as i mentioned earlier
compactness theorem is a really important result

not only for propositional logic but also
for first sort of logic it's also one of the

i would say the more challenging parts
of the course so i encourage you to um

yeah i mean take a look at this video a couple
of times and also take a look at the materials um

at the at the handout the notes yeah um a couple
of times and yeah try to in order to get in order

for you to get a good sense of how to apply the
result you might need to yeah you might need to

look at a few examples and just try to think about
them a little bit and to try to apply yeah to a

number of different examples so that you can
get a good feel all right so let's continue

so so firstly what is compactness theorem
so this is a kind of a general theorem um

that allows you to analyze an infinite

an infinite object so this so to speak yeah
in particular an infinite set of formulas

and yeah you want to do it you want to do so
by some kind of finite means okay so this is uh

yeah just the general description of what
the compactness theorem is about and this is

actually a feature of proposition logic
and also predicate logic yeah and it's not

always satisfied by any logic that one can come up
with yeah so this is uh really important to note

um also what is interesting about compactness
theorem is that it has a lot of really interesting

applications for example in graph coloring
i mean surprise surprise you can apply this

to something that is might seemingly be really
different and far away from proposition logic

you can also apply this for example to ramsey
theorem and finally you can use this to also show

um to also understand the limitation of the
expressive power of for example proposition logic

and also of predicate logic and yeah i mean this
uh the very last point is especially relevant

when we talk about private logic because um as
i mentioned um i think in week one yeah private

logic is the basis for for example database query
languages when you look at relational databases

and in that kind of setting you might you it's
important to understand what you can express what

kind of queries you can ask to your database yeah
i mean if you you have this uh you have this logic

what is the limitation of this query language uh
do we need to extend or do we need to add certain

extra feature that does not actually um that is
not that is not present in the original logic

so yeah that's uh for example one important
question as you can see later on yeah it's

a question of for example um yeah if you have a
graph can you express whether or not uh there's

a path in the graph yeah can you express this in
first sort of logic or practical logic so this is

uh you will see this in about i think um in
around five in around five weeks from now i guess

okay so that's compactness theorem

so here's an outline of what we're going to
talk about so firstly we're going to look at

formal statement of compactness theorem and
then we're going to move on to the proof of

the compactness theorem after that we're going
to look at applications of compactness there

so here is the setting of the compactness theorem

so i'm going to fix some notation and also
some preliminary definitions before we move

on to the statement of the theorem yeah so so
far we've only analyzed we've only looked at uh

a single formula and to see whether or not it
decides uh it it is satisfiable valid etc but the

main object is always a single formula
but when we look at compactness theorem

the main object is actually a set of a set
of propositional formulas in particular

we usually care about an infinite
set of propositional formula okay

so we use usually this notation here

sigma capital sigma sometimes you'll use capital
gamma in order to refer to sets of propositional

formulas so there are two definitions here that
are important the first one is satisfiability here

and the second one is of finite satisfiability
so we know already what it means for a single

formula to be satisfiable so what does it mean
now for a set of formulas to be satisfiable the

interpretation here is supposed to be as follows
so if you have a set of formulas remember when we

looked at constraint programming yeah so if you
have um if you want to put extra constraints yeah

so if you have uh if you have a set of constraints
it is typically interpreted as a conjunction of

these constraints and in our case here this is
very consistent yeah with what we want to do

here no and in particular a set of formulas is
satisfiable if there exists an interpretation

i that makes all of the formulas in sigma true
okay so it's important to note here that it is uh

here is a single interpretation yeah that's a
single interpretation that makes everybody true

so it is a very as you can see here um it's
a very strong condition yeah so this is uh

so there's one uniform solution for everybody yeah
um so this you can check that this is actually

a generalization of the satisfiability uh the
notion of satisfiability for a single formula

um for example you can put uh sigma to be as a
singleton yeah and you can see here that this

would mean that uh yeah a singleton set consisting
of your formula and you can say like okay so the

uh this would be uh consistent with the original
uh notion of satisfiability for a formula

uh some of you might ask okay so why don't we just

why do we need a set of formulas why don't we
just take a conjunction of them yeah well that's

not going to work right if you take a conjunction
of the formulas in sigma you're going to you're

not going to get a propositional formula because
propositional formulas are always finite yeah okay

so this is why here we cannot just reduce this to
a single uh to a single uh propositional formula

right so that's uh satisfiability um and before
i gonna uh before we go through an example here

let's just take a look quickly at what it means
uh for a formula to be fondly satisfiable so uh so

four set of formulas so a set of formula sigma is
finally satisfiable and we're going to abbreviate

it like this f dot s yeah if every finite subset
of sigma sigma prime if we find a subset of sigma

is satisfiable so this one is a seemingly
weaker condition than satisfiability right

because here we just ask that yeah i mean if you
take any finite subset of sigma then there has to

be a um an interpretation i that makes this sigma
prime every formula in sigma prime true so this is

kind of uh yeah so the i here in this case might
actually depend on sigma prime yeah the uh the

the uh the solution i here the interpretation i
might depend on sigma prime okay so just before

we continue again to the example i'm gonna just
uh fix a couple of uh i'm gonna go to this uh

the speed here um we're going to look at um just
some i'm just going to we're going to fix some

lingo here some terminologies in particular we say
here that if you have uh so here you have there

this interpretation i such that blah blah blah
yeah this we can just say that i satisfies sigma

okay alternatively you can also say i is a model
for sigma right so yeah this is uh all of these

things are very common um common terminologies
used in logic yeah so the um the term model

always means a satisfying interpretation
there is interpretation that satisfies

everybody yeah um sometimes you also call this um
a solution yeah so there's really quite a lot of

uh terminologies for this um we've
talked about satisfiability we've

talked about finite satisfiability let's
just take a look at a little example here

so here we have an infinite set of formulas
consisting of p0 p0 implies p1 p1 implies p2 p2

implies p3 etc etc yeah this is an infinite set as
you can see now this is both satisfiable as well

as find it satisfiable so how do we know this well
i mean this is satisfiable because i can just set

p0 p1 all of the guys to be one here so this
would give us um interpretation that satisfies

all of the formulas yeah so you can check that
yeah this is not not not that difficult to check

now this is also finally satisfiable um so well

rather than giving you proving that let's just
prove something more general that every set of

formulas that is satisfiable yeah so that is
here and this is here this proposition here

every set of formulas that is satisfiable is
also finally satisfiable yeah so let's try to

give a proof for that and this would also
in particular implies that this oops sorry

here yeah

okay so let's try to prove this so sigma is
satisfiable it means that sigma is finitely

satisfiable well this is uh this is actually not a
difficult proof yeah so um the proof is uh firstly

if sigma is satisfiable then

you will get a model for sigma yeah that
is that satisfies every formula in sigma so

oops sorry typo here

every

as a model i so it satisfies

for each

so this will satisfy every formula in sigma

so in order to show that this
is finally satisfiable take

well actually you don't need this to be
a finite set just take any sigma prime

then

i it's a model for i satisfies

sorry this is gonna get a little bit small yeah

um this satisfies sigma prime so what it's what
it's saying here is that i satisfy sigma prime

because i satisfies every formula in sigma
prime yeah that's because sigma prime is a

subset of sigma so this is actually a
pretty obvious proposition here right

so um all right okay so just to conclude so what
we've talked about here is uh satisfiability

finally satisfy a finite satisfiability
and we've talked about also the um

the notion of model solution that
um interpretation satisfies a set

of formulas okay so basically what we're doing
here is we're really generalizing the notion

that we've looked at to well to infinite set
of formulas or just set formulas in general

and we've also seen that satisfiabilities
implies finance satisfiability now the

next obvious question is whether or not the
converse holds yeah that is whether or not um

final satisfiability implies satisfiability so
as you can see here final a satisfiability seems

much weaker than satisfiability you
might feel so but it turns out that

they are actually really the same notion yeah
so sigma is satisfiable if and only if sigma

is fantastic satisfiability so this is very
surprising that uh seemingly weaker notion is

actually equivalent to the original the original
notion yeah so um there's a couple of uh so that's

the statement of compactness theorem and there's
a couple of corollaries that are uh really useful

uh to mention the first one is the um the converse
to the converse of the um of the theorem here

so in particular if sigma is unsatisfiable okay
so if basically you take the the converse of this

if sigma is unsatisfiable then it means sigma
is not finitely satisfiable from the theorem

yeah in other words there exists an unsatisfiable
finite set sigma sigma sigma prime yeah

so this is uh in some sense really interesting
because what's going on here is as follows yeah so

um it means that if you want to show
that sigma is unsatisfiable this is uh

infinite set is unsatisfiable apparently
there is a witness okay a finite witness

there's always a finite witness for that for
this for this unsatisfiability of an infinite set

okay so you can find among this infinite set of
guys i find it a finite set that is already in

conflict all right so this is uh yeah i mean this
is uh i would say this is a pretty interesting

pretty interesting statement with that as you can
see soon has a lot of has a lot of implications

so before we proof this theorem we're gonna go
through a couple of um um we're just gonna go

through some preliminaries particularly we're
gonna look at the um we're gonna look at uh the

so-called deduction theorem and contradiction
uh uh proposition yeah so both of these are

um are called the semantics versions because
we will also see uh later on um i think in a

couple of weeks yeah the syntactic version of this
right so um let's go through this preliminaries

so in order to talk about this uh results a
reduction theorem and contradiction we're gonna

first generalize the notion of entailment okay
so this is uh very similar to what we just did

when we generalized the notion of unsatisfiably
satisfiability um so how do we do that

uh so this is the definition i've written uh
it down here so given a set of propositions

so this is uh can be infinite or finite sigma yeah

and a formula phi a propositional
formula sorry prop here means

propositional formulas yeah so sigma here
of course is a set of propositional formulas

not propositions so we say that uh so a little
typo we say we say that sigma entails phi written

see written like this yeah if every
model i for sigma satisfies phi

in particular this would this
would mean that uh yeah i

so every model i for sigma satisfies
phi so if you remember every model of i

said every model for sigma here it simply
means i satisfies so this bit here yeah

this means i satisfies psi for each psi

in

yeah so this implies

yeah this is basically just a reformulation
of the of the um of the definition here

okay so let's take a look at uh one possible uh
yeah uh statement of entailment here and just

an example of an intelligence so for example
if we take this uh formula here this is the

example that we had from earlier this one yeah so
this entails p100 yeah so it's like okay this uh

yp by yp100 and how do we prove that okay so we'll
we'll talk about this later on yeah so actually

yeah so we'll um we'll we'll actually just use
contradiction uh in a bit uh this statement here

to show that uh this example is uh the
statement in the example is true but yeah just

bear with me for a bit so let's move on to
this reduction theorem and contradiction

so what does this statement say i mean so some
of these statements it might just seem like

really abstract so when um in proof theory and
also in logic in general so this is some kind

of uh these are in some sense just like little
results that you um that you need in order to

smoothen the proof for the big theorem yeah so
because they they they establish some kind of

a connection between um two seemingly well i mean
the the both of these results are not really that

difficult to prove but they are very convenient
when we want to um use them in the proof for

example for this compactness theorem yeah so let's
just say a little bit what's going on here so

the first thing is deduction theorem
uh let's talk about this one here

so here it says that if you want to prove that phi
implies size uh if you want to provide plus psi

from uh using sigma as the
assumptions yeah then you can

then it is equivalent to proving
that is equivalent to proving sigma

using sorry it is equivalent to
proving psi using sigma union phi

as the assumption all right this is pretty much
this is pretty much what it's uh pretty much what

it says and um yeah you might think like well okay
this is uh this is this this is supposed to be

this is supposed to be obvious yeah i mean it
is in fact not really that difficult to prove

um this particular statement but
this is pretty much what it says but

what is really i guess what is really interesting
is that this allows you to kind of uh um

to push the implication so to speak yeah from
the syntax of the um of the uh from the syntax of

proposition logic you can you sort of push this
into the semantics of propositional logic yeah

so you sort of push this here into the
semantics of the of proposition logic

right so you can see here this in in here this
implication does not appear anymore but instead

it is kind of replaced or it is kind of implied
by this uh uh by this entailment symbols yeah

right so this is pretty much what i mean if you
want to get an intuition of the deduction theorem

this is pretty much what it's what it really means
intuitively all right so we'll take a look at um

part of the proof of this on the next slide but
before that we just got to mention contradiction

this proposition here is says as follows so in
order to prove phi okay so sigma entails phi

is really equivalent to saying that sigma union
not phi is unsatisfied yeah so in some sense it's

kind of like okay so if i want to prove that
phi is um so sigma uh entails phi it is just

sufficient to uh it is already equivalent or it
already um it is equivalent to just uh to just

say that yeah i mean so sigma and uh not phi here
cannot be um you cannot have uh interpretation

that satisfies all of the all of the um all of the
formulas in this in the set here yeah all right so

so that's the uh statements of this
little propositions we're just gonna

take a look at this example again here

okay so so if we

use for example the uh proposition the second
proposition that is contradiction yeah then

if you want to prove this thing here
this would be equivalent to proving that

p0 p100 p0 p1 v1 p2 p2 p3 oops p3

is unsatisfiable okay

so this is equivalent to proving that
is unsatisfiable and as you can see here

this is this is really unsatisfiable because you
can just take um the first p0 up to sorry p0 p1

implies p2 p2 implies p3 up to p um 99 implies
p100 yeah you can take in this union with um

p100

yeah so this is not this is this cannot
be satisfiable the reason is of course um

uh why is this not uh sorry
ah okay i think i made a

little mistake here that this has
to be a negation here yeah of course

yeah so this cannot be satisfiable
and why is this not satisfiable

so can you give a reason why it is not

satisfiable so um well so in order to show
that this is not satisfiable of course

the first thing to do here is that okay so this
thing should uh the first thing let me just use

different color this means that a so let's say
satisfiable let's prove this by contradiction

if this were satisfiable a formula
an interpretation i would set p1 to

1 and p 100 to zero but then of
course by this implications here

you would simply get

oops different color here

you would simply set you would have to set p2

p3 etc to be all b1 yeah up to even 100 but then
see you you get a contradiction because on the

one hand here 100 has to be one but also b100 is
actually it's actually the value the value zero

all right so let's proceed now with the proof of
deduction theorem as well as contradictions uh

the proposition for contradictions yeah that
we mentioned just now i'm only gonna do one

side namely from left to right okay so for
the other side i leave this as an exercise

and please take a look at the notes for the proof
right so let's take a look at the proof here um

so you want to prove from left to
right so we assume here that um

sigma entails phi implies psi yeah so in
particular uh so you make two assumptions here

the first one is uh sigma implies uh intel's
phi uh implies psi and the other one is that

um you have an interpretation for sigma
union phi okay and you want to show that

this interpretation satisfies psi right
so let's take a look here so we assume

you have a model for sigma union

psi okay so you have a model
for sigma union f5 sorry

now by i will put

let's put here

by star

we have i satisfies 5 plus psi that's because i
also i also satisfy sigma so i has to satisfy 5

and plus sigma as well sorry phi in plus
psi as well right because of this star

okay so now what do we have here so we
have uh we have two cases so we have

i implies psi so i satisfies psi phi and i
satisfies phi implies psi okay um so because

i satisfies phi and i satisfies phi phi

it must mean that i satisfies psi okay
so this is uh just by the semantics of um

of of implication yeah all right so okay so that's
basically pretty much the proof of this side and

yeah for the other side as i mentioned to you
this is going to be left as uh as an exercise so

i'm just gonna i'm just gonna say qed here next
we're going to take a look at um contradiction

and for this we're also just going to
take a look at one side of the proof

namely from left to right so for the other side
let's for you for you to do as an exercise oops

let's try this okay so we want to prove that sigma

union not phi is unsatisfiable assuming that
sigma entails phi okay so how do we do that

um so let's do it by contradiction
we assume that by contradiction

assume that

this is uh

so that you have a model i for sigma union not phi

yeah assuming the left hand side
so what can we derive here well um

from the left hand side we should we so
because uh i satisfies i as a model for

this so this has to it also has to be the
case that so just put star here by star

we also have that i satisfies phi

yeah but then we get a contradiction
here so on the one hand i satisfies pi

but on the other hand

oops

but by assumption

but we have also

from the

the assumption

of contradiction yeah so or thus yeah

see here this assumption here the assumption that
we start with here that is this one cannot be the

case so we have to have the negation of that
which is that this is actually unsatisfiable

okay so that's pretty much
the proof for left to right

and the other side as i mentioned left as an
exercise so i'm just going to put qed here

okay

so we've looked at uh uh the preliminaries we've
gone through the preliminaries now we've looked at

uh reduction theorem contradictions and one
another useful corollary of compactness here

we get we're going to state here because
this is expressed in terms of intelligent and

i think you can get a really good intuition for
this in fact so let's take a look of the statement

so it says that if sigma entails phi then there
exists a finite sigma prime find a subset sigma

prime of sigma such that uh that intel's phi yeah
so sigma prime tells phi so one way to get a good

intuition for this is um as follows so uh it's
written here so to proof phi from sigma it is

sufficient to use finitely many assumptions from
it is sufficient to use finitely many assumptions

from sigma so this is uh um yeah i mean this is
very surprising yeah because um if you look at

for example if you want to if you want to sort
of think of this entitlement here some kind of

a proof yeah so you want to prove something from
something else so the proof is actually always

finite it's a finite object even though you
have an infinite set so um this is uh um yeah

i mean i found it sometimes from time to time
i still find it really surprising okay so um

to let's take a look at the same example that
we saw before here yeah so if you want to for

example um proof uh if you want to show that
p100 is entailed by the set here on the left

as we saw this there's already um yeah there's
a finite sigma prime yeah such that this is the

case i mean we saw that already and this final
sigma prime is in fact in this case for example

it could be sigma prime here could be p0 p0 m plus
p1 p1 implies p2 so on and so forth up to p 99

implies p 100 so this should be enough to
um yeah this should be enough to entail

uh to intel phi all right so yeah that's the um uh
the not the other useful corollary of compactness

uh so we will use this interchangeably but just
just to recap the statement the original statement

of compactness relates satisfiability with fondant
satisfiability and it doesn't have entailment the

second one talks about um the second one talks
about basically just the conversion which is

that sigma is um um if sigma is uh if sigma is
unsatisfiable you can find a witness you can

find an inconsistent set uh inconsistent subset
of sigma right so this is expressed in terms of

consistency and third one here is another
variant is expressed in terms of entailment

okay so we're going to continue now
to the proof of compactness theorem

and we've proven one side
of the compactness theorem

the easy side so we're now going to prove the
difficult side of the compactness theorem which

is that if sigma is finally satisfiable
this implies that sigma is satisfiable

in order to do this proof
we're going to have to make

use of the following lemma technical
lemma so the lemma stays as follows

suppose you're given sigma here a
set of affinitely satisfy a finite

finally satisfiable set of formulas
and you're given phi a formula then

it is possible to add either phi or not phi to
sigma while preserving finite satisfiability

in other words either sigma union
phi is finally satisfiable or

that sigma union not phi is finally satisfiable

so this is the technical lemma we're
going to prove this technical emma

later on firstly we're gonna have a look at
how to use this to prove compactness theorem

so in order to prove compactness theorem
let's just firstly spell out the assumptions

that we've made first one we are given we
are assuming that we are given sigma here

a finally satisfiable set of formulas and
we want to prove that sigma is satisfiable

the second assumption we're going to make um yeah
there are only countably many variables in sigma

and this is an assumption that is that we've
made in the first week when we define the set v

of variables yeah and yeah this is a reasonable
assumption in computer science but in mathematics

for example you might be interested in
uncountably many variables in which case

it is still interestingly it is still possible
to prove compactness theorem but you need to

use zorn's lemma which is beyond the scope of
the course and i'm gonna leave it for you to

uh uh if you're interested to take a
look and yeah as a challenging exercise

but that's beyond the scope of the course
so we got to make these two assumptions

and we gonna now try to show that sigma is
satisfiable okay so how do we use this lemma

so in order to use this lemma the first
thing that we're gonna and here is a little

yeah so what we want to do here is we want to
define an increasing chain of sets of formulas

all of which are finitely satisfiable and it's
also going to be finitely satisfiable in the limit

quote-unquote here so let me write it down
here so we want to or instead of define

this is the goal here we want is to define
an increasing chain of sets of formulas

and all of which going to be fondly satisfiable

so we're going to do this by
induction sorry actually just before i

write down what this definition is
so what do i mean by in the limit

the limit here so i'll just put it here
the limit of this is going to be gamma

which is going to be defined as
the union of all of the sigmas

okay so we want to define sigma

0 sigma 1 etc and also the limit gamma and we want
to show that all of these guys are going to be

finely satisfiable

okay so that's the very very first step

right so how are we gonna how are we gonna define
the sigmas we're gonna define this by induction

so

the base case is sigma zero we're
gonna define this to be sigma yeah

and of course by assumption we we made
the assumption that sigma is finally

satisfiable so sigma zero at the beginning is
already we know that it's finally satisfiable

so that's finally satisfiable okay so now
we're gonna do the inductive step here

so we assume that we have sigma i

a finitely satisfiable set of formulas

and we're going to define sigma
i plus 1 okay so we're going to

define the sigma i plus 1 as follows so
sigma i plus 1 is going to be defined as

sigma i union

x i

in fact x i plus one in this case

if it is

apparently satisfiable otherwise we're going to
define it to be sigma i union not x sub a plus 1.

yeah so we're gonna define this um otherwise
we can define it to be sigma i plus one

so okay so what do we know now well what we know
now is that um well so firstly we know that sigma

zero um so sigma i is um finally satisfiable
set of formulas and using the lemma here

we know that at least one of this guys here yeah

has to be finitely satisfiable right it's because
uh you adding either here um phi or not phi the

phi here is just x i plus one right so um it
just means that um you're you keep building now

um you keep adding uh something to x as to sigma
in such a way that it it says stays uh being

finally satisfied right so now we we have built
now this chain of in increasing chain of finally

satisfiable set of formulas and we've defined
the sigma right so what we're gonna show next is

oops not sigma here it's gone sigma i is

finitely satisfiable for each i so we saw that
from the previous slide and here's another one

that sigma that is the limit
is also finally satisfiable

okay so the first one that is this one here
we've already seen this to be true from

the previous slide how do we prove the second
lemma so this is um not that difficult to prove

so if you in order to prove that it's
finitely satisfiable take a finite

subset of gamma we just put here um

take a final subset of gamma then

this gamma prime has to be a subset
of at least one of the sigma i

because it's finite so it has to be a subset
of at least one of the sigma i for some i yeah

and we've already assumed uh we've already shown
that sigma i is gonna be uh is finally satisfiable

so i'm gonna put here by this yeah
so by this sigma prime is finally

sorry sorry sigma prime is satisfiable so sigma
is finally satisfiable right so that's basically

the proof of this step yeah okay so
um all right so we've now established

we've constructed this infinite chain of an
increasing infinite chain of sets of formulas

all of them are finally satisfiable it's also
kind of satisfiable in the limit now what do

we do next what we are interested in next is
actually we're going to make the following claim

that um sigma is actually satisfiable okay so this
is the what we want to prove sigma is uh not sorry

it's not sigma gamma is um gamma is um satisfiable
and this would directly imply that sigma is

satisfiable because remember sigma is a subset
of gamma yeah so if the bigger one is satisfiable

bigger the bigger set is satisfiable
then the subset the smaller set so

a smaller subset which is gamma is also
satisfied okay so we're going to claim that

this would be a claim this is what we want
to prove here so we'll just put this slim

okay so let's prove this in order
to prove this we're gonna build a um

we're gonna we're gonna build
a model for for gamma yeah

so the model actually is uh pretty much
determined because remember what we've done

so far we've added for each eye we've added
either x i or not x i into into sigma right

so this gamma here that is in the limit
it will have um either x i or not x i

yeah so and it can only have one of them
because yeah because we assume that sigma is

because we've shown that
gamma is finitely satisfiable

so let's try to spell this out in detail so

we want to define here

an interpretation

okay mapping set variables to either zero and
one yeah and we got to define it as follows

so i of x i so remember the v here is
just going to be x1 x2 x3 and etc yeah

so x i here is going to be defined to be 1 0.
so this is going to be 1 if x i is in gamma

if not x i see and um so this is
well defined so i'm just gonna put a

little lemma again here is well defined

so what it means here is
the following that this is a

um so in order to show that this is well defined
you need to show that i of x i the value of i

of x i here is this firstly this is i mean you
need to show that this is a total function yeah

so in order to show that this is a total function
you would well firstly you would either have

um for each xi yeah you would uh only one of
them you will only get one value all right so

um so you uh there are a couple of things firstly
it's going to be defined yeah i of x is defined to

be either one or zero yeah because we've already
added this thing when we constructed sigma i

yeah the second point is that it's only going to
be defined to be one value that this is a function

and in order to show that this is a function what
you need to make use of here is the fact that

it is so gamma is finally satisfiable in in
particular if x i and not x i are both in gamma

then it cannot be finally satisfiable yeah because
uh you get you get conflict that is you can take

x one sorry x i and not x i together yeah
to be um to be a finite subset and this is

uh not satisfiable yeah so this this is
uh that cannot be the case right so i will

leave it to you to spell this out in detail that
this is uh is well defined but yeah the proof is

i just pretty much spelled it out just now right
so we've defined something here and the claim here

is we've defined an interpretation
the claim here is that this is a model

that i satisfies gamma right so
that's the claim so what i'm gonna um

and yeah if if this claim is true yeah then
of course uh yeah the the theorem is proven

because this would show that sigma sorry
gamma is satisfiable let's try to prove this

so to prove this we're gonna take

an arbitrary

formula in gamma

and we will show

that i is a model for phi okay
so that's what we got to do now

let's say well so we have
phi here so let's say u is

the set of variables

appearing in phi

so this has to be a finite set of course
because it's phi of course is a finite formula

so we're going to define lu to be the
set of all formulas in gamma that uses

only variables in u

okay

lu here is the finite set of formulas the
reason of course is because there are only

so we fix the number of well so u here is the
finite set of variables yeah and if we look at

um i mean there can only be finitely
many that can only be up to eq up to

equivalence there can only be finitely many
formulas yeah that uses only variables in u

okay since

is finally satisfiable and i'll
use a subset of gamma then we have

a inter a model yeah

we have a model let's say this just we just
care about from x1 up to um oops let me just

just take you here okay so we have a
model for uh we have a model um i prime

for all formulas in lu okay so this uh so we have
such that i prime satisfies value okay so what

we're going to do next is we want to show that
i prime is actually consistent with i right so

so oh so this is a claim or a sub claim let's say

i and i prime are consistent on u that is

i of um oops x equals i prime x

for x in u

okay so this is the um what you want to show and
of course if this is the case we would show um

this would actually implies that i also
satisfies um i i satisfies iso model for

lu and therefore is also a model for phi
because phi of course is also in value

so let's try to prove this so we have
enumerated x1 um we have enumerated

all the variables in in u in in gamma so
that is for each formula sorry for each

for each variable x in u either x or not x appears

in in gamma yeah or actually and also in
fact it should also appear in you yeah

so basically it says that if x is in u

then

both i x x prime it's going to be one yeah

if x naught x is in u

then i x will be zero and

only one of them is possible yeah because

of as we talked as we mentioned before
this is because of unsatisfiability gamma

yeah so that's

that concludes the proof again as i uh the
reason it concludes the proof is of course

because we've taken an arbitrary so just to recap
again we've taken an arbitrary phi okay and we've

shown that i um we've constructed a bigger set
value that contains phi and we have shown now

from this claim here and with that i is also iso
model of lu and therefore is a model for phi as

well

okay so we're going to conclude now with
applications of compactness theorem we're going

to only look at one application in this video in
particular we're going to look at graph coloring

so we want to prove a statement above about graph
colorability of an infinite graph yeah and in the

note i also provided another application which is
ramsey theorem so the infinite randomly theorem

so yeah so i'm but i'm not going to go
through that in the video we also will

see some other applications in the tutorials
as well one thing i want to explain to you

is that most of the applications that we're going
to see in this course of compactness theorem

the pattern yeah there's some kind
of a pattern the pattern is usually

i would say quite similar so once you get a hang
of one of them you'd be able to generalize it to

proof uh to apply compactness theorem to proof
other kinds of applications as well so typically

what i want to say is that what you so the
application is typically typically goes as follows

you want to prove a statement about an infinite
object let's say an infinite graph here in the

sense of graph theory of course and in order to
prove this statement you want to map this graph

somehow to an infinite set of formulas
okay so you want to do you want to do a

mapping that is similar to what we did in the
constraint programming video from last week

so once you do that you have a correspondence
between the statement for this infinite graph and

satisfiability of this infinite set of formulas
so once we have that we gotta map it uh we can

map it down to um a statement about finite sets
of finite subsets of this infinite set of formulas

and then we want to make use of some results that
we already have for example for this finite set

of formulas either we make use of some results
or maybe that the statement is um vacuously or

easily seen to be true yeah so and then once we do
that we want to map the results back from formulas

statement above um satisfiability of formulas
we want to map the results back to this

the the desired the the desired property okay so
um that's roughly how the structure of the proof

would go and let's take a look at this specific
example here for the case of graph coloring

okay so here is um i mean some of you might
have seen this uh definition before and

in fact i also have this as well in the
constraint priming slides for the first week

so here is a definition of k colorability so
a graph like graph g can be infinite finite

it we say that it is k colorable if

there exists a k coloring for g so
what is okay coloring it is simply

a function mapping the vertices of g to one up to
k so this one up to k are colors yeah so to speak

such that the following condition is
satisfied so what is this following

condition well the following condition simply
says that two vertices that are adjacent

cannot receive the same colors yeah so the fv
and fw must be mapped to different colors okay so

let's take a look at an example here so we have so
here we have a little um graph with four vertices

so you can for example this is of
course four colorable because i can just

color all of them differently

so that's of course for colorable
but of course this is also um

three colorable because i can color this

vertex to be the same as the um i can i
can color it with black yeah so i could

color it with black

the reason why this would work of course is that
you can see that every adjacent vertices are

uh yeah they receive different colors so that's
good enough yeah so this is uh an example of a

three colorable three colorable graph okay
right so um here is another notion that we

will need here is the notion of sub graph well sub
graph is simply a sub graph of a graph is simply

a graph yeah whose vertices and edges take uh
our subsets of the vertices and edges from the

initial graph here so um the h here

so the v prime here has to be has to take
only a subset of b and e prime here can we

take subset of e so basically you take the
original graph a sub graph can be obtained

by removing some of the vertices and also some
of the edges from the original graphs okay so

for example if you take this guy here the example
here an example of sub graph could be for example

that's an example of a sub graph here right okay
so let's uh now go to the main statement of the

theorem so the theorem says the following so it's
about k colorability of infinite graph so it says

that an infinite graph g is k colorable if and
only if every finite sub graph of g is k colorable

okay so um this is a statement relating infinite
graph and it's finite sub graphs and one thing

that is cool here is a cool corollary is that
every infinite planar graph don't worry if you

don't really know what it means by planar graph
yeah but i'll give you an intuition in a bit but

it says that every infinite planar graph is four
colorable so just to say a little bit about planar

graphs the definition is actually a little bit
complex but intuition is pretty simple so planar

graph is a graph that can be mapped into a map
yeah a map so to speak so for example you oops

so if you just imagine well this is
this is a pretty horrible depiction of

a country for example we have a bunch
of provinces in the country yeah

and each of this guy here is imagined as
a each of the provinces imagine as a node

so you would get oops something like that yeah

and the vertices here um sorry the edges they
are connected by an edge if the provinces

are neighboring provinces yeah

okay so this is just a little example of

of a planar graph the intuition the actual
definition is actually a bit more complex but

the intuition is pretty simple but what it says
here is that every infinite planar graph is for

colorable now um there's of course a famous
theorem that the four color theorem that every

finite graph is for colorable um using this
theorem yeah this four color theorem and the

theorem that we have here we could show that every
infinite planar graph that is four colorable uh

how do we do that how do we show that well uh the
proof is pretty simple a simple corollary of this

if you take a infinite planar graph so basically
think of an infinite map yeah in this case

so

so okay given

an infinite planar graph

g so take an infinite take
an infinite planar graph g

um what can we say here

so what we know is that every finite sub graph
of g is planar so every if you think of think of

maps here so if you have a map so take a finite
finite sub map it's just still going to be a

finite sub graph it's still going to be a map yeah
i found it every finite sub graph of g is planar

and also

uh four and therefore yeah
so i would say therefore

and therefore

by four color theorem four
fine graphs is four colorable

so using the theorem here

d is color for color

yeah so every final sub graph of g is
planar and therefore is four colorable

so it means every fourth um
that it the the original uh

graph g would be for colorable by the theorem
star okay so that's pretty much the proof of this

okay so um let's now um move on to the let's try
to let's attempt to prove this uh theorem here

so we want to prove that every infinite graph g is
k colorable if and only if every finite sub graph

of g is k colorable so just like in the proof of
compactness theorem one side is going to be easy

that is um infinite graph of g sk color
rule then it would mean that every final

sub graph of g is also k colorable
yeah this is the easy side because

the coloring of uh of g would be applicable
to every final sub graph of g of course yeah

so one side is easy let's prove the other side

so the other side here what we're going to
do we're going to construct some kind of a

mapping graphs to formulas so this is a little bit
like what we did in the first week as i mentioned

before so given a graph h we want to have a
transformation to sigma sorry sigma gamma of h

such that h is k colorable if only if gamma h is
satisfiable we're gonna fix some notation first

so we're gonna assume and with that loss
of generality of course we can assume that

so let's say g here is ve yeah

we assume that p here is the set
of all natural numbers yeah so

one thing i should say here is that we we need
to we can only prove this for countably for an

infinite graph with countably many vertices if you
want to show this for uncountably many vertices

you need to generalize this theorem of course
to the uncountable version of compactness so

so we assume that v here is the set of all
natural numbers and let's define this gamma h

so what do we need to do we need to as before
if you remember the key here is that we need

to define the variables we need to determine
what the variables are for our set of formulas

okay so the variables if you think about
it what is really important is to know um

whether or not a node or which color is
assigned to which node yeah so we need to

in particular have the following
variables so we need to have p oops

so press something wrong here so p i c yeah

note i or vertex i gets color
c so of course the i here is in

v and of course the c here is in one
up to k yeah so the set of all colors

okay so note i the interpretation is not i
gets color c so okay once we've defined the

variables we need to

define this set of formulas and in this is the
the process is called extrematization we want to

define uh this encoding yeah of h how do we
do that well we need to say uh the property

of what it means um by this um by this encoding
um by what it means by colors yeah so what what

does it really mean here so this simply says
that if i gets color c it cannot get either

it cannot get another different
color okay so if i gets color c

then you cannot get a different color so it would
mean that um for every color d that is not c

p not p i comma d yeah so
that's the first one okay

um so okay i will not annotate that you
see the annotation in the note that you

get um all right so that's the first one
and then you need to say as well that

okay so

okay so now you need to relate
so two notes that are adjacent

cannot get the same color so we need to
define a set of a template for that i comma j

so if i gets color c then j cannot get color c

oh sorry j can i get color c all right

um okay that's good now um okay

so let's have a look here so we
have uh scic fi ic and we also need

to say that we need to have a template
for um yeah that um every node must get

at least one color yeah so you gonna define
this snow feed i so this is defined to be

yeah so it means that every i gets at least one c
yeah is assigned at least one color so once we've

defined this set of formulas what we need now is
to define the sigma sigma g we're gonna define

gamma of g we're gonna define
this to be the following

so every eye every note
must get at least one color

yeah and

so we have this phi i comma j for all
vertices that are so for all adjacent vertices

so that they cannot get the
same color and finally we need

psi i comma c

for every i

and every c

okay i think i don't need um i don't need more
page so i'm gonna shrink it a little bit here

but um so we've defined this gamma g so this is an
encoding of uh the graph g and this uh this is a

faithful encoding of that therefore what we have
here is that um this is satisfiable even only if

if only if um h sorry g is k colorable

yeah okay that's good so what can we do now well

so let's go back to the assumption here so
we the assumption here that we have is every

final sub graph of g is k colorable yeah
so it would would mean that by assumption

gamma of h

is satisfiable yeah so this is because uh

h so for every h for every sub graph for sub graph

h of g

yeah so for every sub graph h of g we say
that the assumption is that it is k colorable

and therefore gamma h is satisfiable

now um one thing that um so i'm gonna i'm
running out of space so i'm gonna sort of

go up here and do a little bit of cheating

uh just try to get a bit of space so

one thing is so this okay so uh gamma of h is
satisfiable now gamma of h of course is a subset

of um gamma of g yeah so one thing that i will ask
you to check here and this is actually easy to you

can think about it a little bit but this is easy
to check that this would imply that every subset

of every subset of gamma of g is satisfiable every
final subset of gamma of g is satisfiable yeah

is finally satisfiable therefore by compactness

gamma of g is satisfiable

yeah gamma fg is satisfiable and
therefore so this would imply that