Lecture 41 - Predicate Logic: Lowenheim-Skolem Theorems

Now, one very simple application and a very useful application also of this compactness theorem is the upward Lewenheim-Skolem theorem. What does this particular upward Lewenheim-Skolem theorem say? Suppose, L is a predicate language and gamma an L-theory with an infinite model M. Then, if kappa is an infinite cardinal model bigger equal the size of L. Then, gamma has a model N with size kappa. So, very interesting result here. Now, let us talk for a bit. So, once we have let us say a dense linear order without endpoints. Do you know any model? Rational numbers, real numbers and now suppose you are interested in the question does there exist I mean suppose your cardinality of interest is aleph sub epsilon naught. You remember epsilon naught as an ordinal. Now, you would like to know whether there is a model of this theory dense linear order without endpoints. If there is a dense linear order without endpoints of cardinality aleph sub epsilon naught. Then, this theorem will guarantee the existence of this. So, what we are doing here is that if you know that a model of certain cardinality exists. Then, you know that the model of any cardinality above that will also exist. So, let us do another example. So, this one also says if you take your language to be empty L set. Then, and suppose you know that for a theory there is a model of cardinality aleph naught a countable model exist for a theory. Then, you know that there is a model of every cardinality. So, essentially this upward Levenhans Coulomb theorem says that you can I mean the class of models if it contains one infinite structure. Then, it is a proper class because for each cardinality there is a model. Eventually, there is a model for each cardinality that is what this says. And, there is a very minor condition here which says that kappa is an infinite cardinal. And, it has to be at least as large as the size of line the language. This is for a very silly reason yeah because maybe. So, assume that kappa is sorry size of L is 2 to the aleph naught. Do you remember any language which has size 2 to the aleph naught a language with size 2 to the aleph naught the theory of r vector spaces. I mean the language of r vector spaces there is one unary function symbol for each real number. So, obviously, that theory is very large that language is large it has 2 to the aleph naught many symbols the rest of the symbols are countable. So, 2 to the aleph naught plus of countable set well that is that is done. And, there is also essentially yeah all those function symbols they act differently if your vector space is non-trivial. So, obviously, you should not expect that there is a countable model can there exist a countable vector space countable real vector space yeah it does not make sense right. So, therefore, we have this silly restriction ok. In fact, this theorem is going to say something more, but I will first write down the proof of this and the proof is actually very simple. And, the technique that is used for such kinds of proofs and that is a standard application technique for the compactness theorem it is called expansion of language by constant symbols. So, the idea yeah I mean before we actually write down the proof the idea is very simple that you add you want a structure with size kappa you add one constant symbol one new constant symbol for every ordinal less than kappa. So, how many ordinal how many new constant symbols are you adding kappa many. And, then you put more sentences in your theory you already have gamma and then you say whenever alpha and beta are distinct ordinals less than kappa then C alpha and C beta are distinct their interpretations are different. This is our expansion of the theory once you have that then you use the compactness theorem to show that it is finitely satisfiable which we can do thanks to existence of an infinite model M and then we are done. So, we have a model of this entire theory where there are at least k kappa elements you understand this let us do it. So, I mean perhaps yeah I remember this from a previous time perhaps I should say that with size of n at least kappa because the proof will not exactly guarantee that it is kappa with the combination of upward and downward Levenhans-Colomb theorem we will get this exactly kappa. So, consider the expansion L bar of L where we add one constant symbol well I should say one new constant symbol. So, you just make sure that it is a different name of the constant symbol C alpha for each alpha less than kappa. So, here I would like you to recall some set theory some cardinals kappa is a cardinal number. So, it is an initial ordinal. So, it is an ordinal in particular it is a limit ordinal and it is an initial limit or limit ordinal. So, kappa less like alpha less than kappa is simply alpha belongs to kappa all the elements and how many elements are there in kappa many. So, I have added one new constant symbol yes for each ordinal alpha and set gamma bar to be an L bar theory defined as gamma union negation C alpha equal to C beta where alpha is not equal to beta and alpha and beta are less than kappa. We are going to claim that gamma bar is satisfiable. So, if you want to show something is satisfiable then what do you do you show that it is finitely satisfiable by compactness it is enough to show that gamma bar is finitely satisfiable. So, we can. So, let delta be a finite subset of gamma bar then the sentences in delta contain only finitely many new constant symbols can you see that gamma is totally new constant symbol free only these ones are the sentences which contain new constant symbols. So, then the sentences in delta contain only finitely many new constant symbols say C alpha 1 dot C alpha n then what can we say then delta is a subset of we do not have any problem with gamma. We have we only needed to control the size of new sentences that are added. So, negation C alpha i equal to C alpha j such that 1 is less equal i less than j less equal n do you agree with this and have you seen some similar proof you remember this proof of Konig's lemma yeah we only we added something new and then we want a finite subset of that. So, it is a standard compactness theorem application. So, delta is a subset of this then choosing C alpha i to be some element sorry wait let me write it down. So, delta is a subset of more properly. So, choosing C alpha i m where 1 is less equal i to be any finite subset of m yeah. So, we are saying any finite subset of m where m is a model an infinite model see why do we need it to be infinite because we want to interpret any finite number of distinct symbols as distinct elements that is the only requirement you understand. If it were finite let us say it had size 100 then for 101 new constant symbols we could not really do this we want yeah be any finite subset of m of size n. So, all these constant symbols which appear in delta we are interpreting them as distinct elements we see that m satisfies gamma union this collection and hence m satisfies I mean sorry m bar satisfies and hence m bar satisfies delta I should make some changes m is a model m is an l structure and m bar is an l bar structure yeah where I have yeah we obtain I should say we obtain an l bar structure m bar and we see that. So, we simply took m interpreted C alpha 1 as some element C alpha 2 as another element. So, because we just need to give interpretation of all the symbols the only new symbols which we need to add are these the rest of them do not really matter the do not say gamma it is an l structure. So, every symbol in l is interpreted just as an m yeah m as an l structure and actually I mean I can be more technical and say that this is an intermediate language the intermediate language which consists of l and C alpha 1 C alpha 2 C alpha n I can call it l prime and then I am defining an l prime structure here, but all I need to ensure yeah I mean this can be made into an l bar structure also all I need to ensure is that C alpha 1 and C alpha 2 they are interpreted as distinct symbols. So, that m bar this new structure satisfies the right hand side and hence the left hand side and we are done using just modifications of one infinite structure we could prove this any questions your faces are blank we do not have any hurry. We proved it is a yeah that l bar structure. So, you interpret other constant symbols as anything apart from C alpha 1 C alpha 2 C alpha n other things are interpreted as anything we do not really care we only want that this one is satisfied. It is a model of gamma bar I mean it is a model of that finite subset of this I mean are you confused why m is a m bar is a model of gamma yes m bar is not a model of gamma bar I am saying m bar is a model of gamma union these new finitely many sentences it cannot be a model of gamma bar I mean we want to find a model of gamma bar, but for that we use compactness. Yeah fine like suppose we found a model of. Because gamma bar is gamma union something else. No, but it is in a different language. Yes, but by reduction of language again yeah I mean you forget about all the new symbols what is the confusion here. So, therefore, now let me write this is the end of the proof of the claim. So, by compactness let n. So, there is a model model n of gamma bar. So, let us say there is a model n bar of gamma bar then what happens then thanks to yeah I mean thanks to these sentences negation c alpha equal to c beta for alpha and beta distinct and less than kappa we know that then n bar satisfies negation c alpha equal to c beta alpha not equal to beta and alpha beta in like less than kappa right. So, therefore, the universe n n bar of n bar has at least kappa elements kappa many kappa elements do you agree with this much. Now, just like we expanded the language we can also reduce the language. So, let n be an l structure where the underlying universe is equal to n bar and each symbol in l is interpreted in terms of kappa elements. So, in n as the interpretation of that symbol of the symbol in n bar. So, this is called the this is the l reduction of the l bar structure n bar. So, for this then what will happen then n satisfies gamma and n has size at least kappa you get that every symbol was interpreted in exactly the same way you simply forgot about the interpretation of the new constant symbols and you obtained n. So, it is like consider this natural numbers with order we have natural numbers with orders now you add 0 to it I mean you have a language for orders and you add a constant symbol to it. So, natural numbers less than and 0 is a structure then what is it is reduction to the language which consists of only the constant symbol natural numbers comma 0 you simply forgot about less than you can always forget some part of the language that is called reduction reduce structure for that language is your doubt clear do not seem. So, confusion no interpretation does not have to be distinct I just said that the interpretation is exactly the same. The interpretation of the new constants has to be distinct because of these sentences see that how do you when do you say yeah I mean when do you say. So, note that any structure k satisfies negations to c beta if and only if the interpretation of this in k is not equal to interpretation of this. So, therefore, for every distinct pair of constant symbols new constant symbols their interpretations are different which means there are at least kappa many elements any problem feel free to ask more questions I just want you to understand and get a feel of this as you know the proofs are not examinable only the sentences are not. So, let us do something different now there is also a downward Levenham's Coulomb theorem may be I should state that first and then we will not discuss the proof of it will be slightly complicated it uses some new terminology called Coulomb functions, but we do not want to do that, but let me just state it. So, downward Levenham's Coulomb theorem suppose L is a predicate language and gamma is a theory m is an infinite model of cardinality model of I should say m is an infinite model of gamma with cardinality with size of m bigger equal size of L this is important again suppose mu is an infinite cardinal satisfying mu lies between size of L and size of m now I can see why my mu and m are the same, but this is may be I will use a different cardinal number that is better let me use little lambda. So, suppose lambda is possibly a smaller cardinal then there is some structure then there is n a model of gamma with size of L and size such that n is a substructure of m. So, I can find a substructure of m which is a model of gamma such that the size of n is your prescribed size lambda. So, for example, do you all know algebraically closed fields algebraically closed fields is there anybody who does not know what is a field field has what is the structure what is the language for fields it is the language for rings it has plus dot minus 0 and 1 then what are the field axioms associativity commutativity distributivity identity and so on. Then inverse for addition only yeah I mean this associativity commutativity and identity for all for both operations and then finally, the sentence yeah I mean let me write down that sentence. So, the theory. So, let L ring be this language f g h c e yeah this is the and this stands for plus dot minus 0 1 then gamma a c f yeah the theory of algebraically closed fields yeah contains the axioms for a ring yeah I am not going to write them down then the axiom that every non zero element has right. So, what is that axiom let us write down that for all w if w is non zero then there exists a w prime such that g w w prime is equal to e and g w prime w is also equal to e yeah. So, the it has a multiplicative inverse. So, this is the axiom now can you tell me. So, far we have covered all the axioms for a field now we want to say that it is an algebraically closed field how do we say that add an axiom for every polynomial of degree n and where are the coefficients coming from. So, normally if I want to say x square plus 1 has a x square plus 1 equal to 0 has a solution I will say that there exists w such that w w dot w plus 1 equal to 0 this formula is satisfiable, but what if I want to say that complex numbers are algebraically closed. Yeah. Exactly. So, the coefficients yeah the coefficients are also coming from the coefficients. So, you can also put a universal quantifier for the coefficients. So, and for each n bigger equal 1 add the following axiom what is that axiom for all w 1 for all w 2 dot w perhaps I should say for all w 0 onwards yeah I do not want to say start at 1 for all w 0 w 1 dot dot dot w n and w. So, w is going to be our variable of the polynomial one variable polynomial and w 0 is the constant coefficient w 1 is the coefficient and w 2 is the constant coefficient of w this is coefficient of w square and this is coefficient of w n. So, we are going to say if w n is non zero then just a moment I think I should not write it over here yes for all these coefficients if w n is non zero then there is a there is a w such that now I am not going to use the complicated notation f g h yeah I am just going to write the polynomial in ordinary form such that w n w to the power n plus w n minus 1 w to the power n minus 1 plus dot dot dot w 1 w plus w is w 0 is equal to 0 and complete. So, it says that every non zero polynomial every polynomial of degree n yeah degree n is ensured by saying w n is non zero every polynomial of degree n has a root you understand. So, you add these axioms. So, this is not a finite list of axioms we are adding 1 axiom for each n bigger equal 1. So, by now we have got this theory of the theory of algebraically closed fields now what is a model of the theory of algebraically closed fields now note that complex numbers with plus dot minus 0 1 is a model of gamma s c f and what is the cardinality of complex numbers 2 power l f naught and what is cardinality of l ring well 5 yeah there is nothing to think about only 5 symbols exist there. So, 5 cardinality. So, for any infinite cardinal therefore, for an infinite cardinal lambda less than or equal to size of the complex numbers say lambda equal to l f naught we know that it is strictly smaller there is a model of gamma s c f with cardinality lambda ok. So, now, this is a question do you know if there exists a countable algebraically closed field by this theorem yes, but otherwise do you know that we have already seen a hint of this in our course you remember where was one particular tutorial problem where I asked you to show that all algebraic numbers are countable countably many what is an algebraic number it is a solution of a complex number a polynomial equation with integer coefficients you remember that what is an integer coefficient I can use this language to write down any polynomial with integer coefficient because if I want to say minus 5 x square plus 3 x plus 2 I can say 1 plus 1 plus 1 5 times then put a minus sign because minus exists in my language and then I can say multiplied by x multiplied by x and add 3 x. So, with integer coefficients I do not even need to add this first string of quantifiers this one integer coefficients you can write them down very easily you are not asking whether there is a solution of the polynomial pi x plus 3 equal to 0 you are asking for something very simple and you have shown that the set of algebraic numbers is countable. In fact, the set of algebraic numbers forms this is a model. So, the set of algebraic numbers say it is usually denoted Q algebra this is countably infinite and this Q algebra is also an algebraically closed field and the proof of the downward Levenhams-Colomb theorem will actually generate this what it does I mean I will give you a some sketch of the proof in this case you start with one polynomial equation then if it has a solution then you add that solution you start with a countable set let us say integers you always know integers do exist. So, you start with countable subset of C any countable subset would do actually, but I am starting with integers then I write down all polynomials polynomial equations in with coefficients from the chosen set z then if that polynomial has a solution I can list all of them. So, step one by one I ask whether this formula has a solution if it has a solution then I will add one solution using axiom of choice for each of those formulas to my set. So, I keep increasing my set and once I have done that I repeat the process because now maybe I have added root 2 x square plus 2 minus 2 is equal to 0 I have added root 2, but now I also want to make sure that because of this property that a polynomial with coefficient root 2 also has a solution. So, I repeat the process with newly found coefficients and again I keep doing that countably many times and after that whatever union of sets I obtain that will be my gamma SCF this q algebra that is how you prove the statement prove downward Lohenheim's column theorem. In fact, this is not the only model only countable model I will give you more, but tomorrow.