Original subtitles

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