Lecture Tutorial : Week 12

Ok, let's begin. So, the first question that we will try today is to find four different models of the theory of dense linear orders where any pair is not elementarily equivalent. Dense linear orders everybody understands? Yeah, between any two distinct elements there is a third element ok. So, can you give me at least one example of a dense linear order first? Rational numbers, any other example? Real numbers, any other example? Irrational numbers also satisfy the same property, any other example? See, if you are given a dense linear order then any interval in that dense linear order is also a dense linear order. So, some examples of intervals? Open 0, 1 ok. So, open 0, 1 in R then something else? Yes. So, this one then similarly this one and similarly close 0, 1 ok. So, now, look at all four of them, can you tell me if these are elementarily equivalent or not? They are not. Why? One has a least element which can be expressed as a first order sentence whereas, the other one does not have a least element and you can similarly distinguish between all four of them ok. So, any pair is not elementarily equivalent. Now, the question is can you do it with five models instead of four? Five models. So, if I just talk about rational numbers then where should I put rational numbers? Is it elementarily equivalent to one of them? First one can you prove that? It is unbounded and the theory of unbounded dense linear orders is complete. Similarly, the theory of bounded below only dense linear orders is complete and the theory of bounded on both sides is also complete. So, all these four theories are complete if they have at least two elements yeah I mean. So, that is must I cannot say that closed interval 1 comma 1 is a dense linear order which is bounded and it is of model of that theory no yeah because there is nothing to check there yeah. So, we do not want singletons, we want that there are at least two elements ok. So, similarly rational numbers are here they are elementarily equivalent to this and in fact, every single dense linear order which has at least two elements because if it has two elements then how many elements does it have? Infinitely many ok. So, all infinite dense linear orders they are elementarily equivalent to one of these four ok. So, you cannot repeat the same exercise with five elements any questions ok. So, let us go to the next question. Suppose gamma is a complete theory and has a model of size n cardinality n where n is some fixed number then can you prove that each model of gamma has cardinality n? How do you express that some universe some set has cardinality n it has at least n elements and it does not have n plus 1 elements ok. So, once you know how to express that then. So, let sigma bigger equal n denote the sentence which states that we have done this in the last tutorial yeah which states that there are at least n elements. Does anybody remember the sentence itself there exist w 1 w 2 up to w n such that none of them are equal this is a finite conjunction. So, we just write this ok. So, let sigma n be the sentence and this sentence I am writing in any language yeah because I just need equality I do not need anything else. So, because the language of sets L sets is contained inside any other language this sentence is a valid sentence in every language. So, let sigma n be the sentence that sigma is bigger equal n and sigma is bigger equal n plus 1 is not true ok. Once we have that then since gamma is complete what can we say and there is some model M of gamma such that M satisfies sigma n yeah we must have. So, this is a model what did we say last time that if you have a model of a complete theory then what is the theory of that model that is equal to the deductive closure of gamma. So, then gamma bar is equal to theory of M where gamma bar is the set of all those sentences in an appropriate language such that this happens. So, all these sentences in gamma bar are true in M and conversely every sentence true in M is also in gamma bar. So, in particular see M satisfies sigma n because it has exactly n elements. So, therefore, theta sorry sigma n belongs to gamma bar ok. So, now, gamma has decided that sigma n is true is it is a logical consequence. So, simultaneously gamma has made a choice that negation sigma n is not true. Therefore, for every model now you understand yeah. So, i.e. gamma has sigma n as a logical consequence this is simply the definition of gamma bar. Once we have this therefore, every model therefore, if M dash is a model of gamma then M dash satisfies sigma n i.e. cardinality of M dash is n it is a very simple exercise any questions let us do another simple exercise yeah this is a standard application of the compactness theorem. So, what we are trying to say here yeah that if a theory gamma means it is satisfiable if it has models of arbitrarily large finite cardinalities. So, sorry this one I should make clear arbitrarily large finite cardinalities then show that gamma has an infinite model. Now first of all tell me what is the meaning of arbitrarily large finite cardinality for every n n belongs to n there is a model of that cardinality no that is not true that is not true arbitrarily large cardinalities only means that there is a model of cardinality at least n for every n. So, for every n there is a model of cardinality. So, for each n in omega n bigger than 0 there is a model M of cardinality model of something yeah I have to first say model of gamma such that cardinality of M is bigger equal n this is what the hypothesis means it does not mean that for every cardinality there is a model yeah that is wrong. So, the do you remember the statement that we said earlier when we started with predicate logic Euclid's theorem on infinitude of primes it says that for every natural number there is a bigger natural number bigger equal natural number which is a prime number yeah that is infinitude of primes. So, there are arbitrarily large primes similarly here we are saying there are arbitrarily large cardinalities of models of gamma ok. So, that is our hypothesis now we want to show that there is an infinite model and we had to use compactness tell me some ideas if we are given gamma yeah and sigma bigger equal n we just wrote down right. So, let gamma prime be defined as gamma union sigma bigger equal n where n is bigger equal 1 ok. So, what will be the cardinality of any model of gamma prime if it is satisfiable sigma bigger equal n says that it has at least n elements, but we are putting all sigma bigger equal n's. So, therefore, so if gamma prime is satisfiable then any m prime modeling gamma prime will have cardinality infinity yeah at least a left naught ok. So, therefore, what is our claim gamma prime is satisfiable, but thanks to compactness we do not actually have to check for satisfiability we have to check for finite satisfiability. So, so we will show that gamma prime is finitely satisfiable ok. How do we show something like this we take any finite subset. So, let gamma naught be a finite subset of gamma prime then gamma naught contains only finitely many sentences of the form sigma bigger equal n. So, let us let n be the largest natural number such that sigma bigger equal n belongs to gamma naught then what can you say about gamma naught it is contained inside the set gamma union singleton sigma bigger equal n yeah I put back all the things which were in gamma. Now, this is not a finite set not necessarily a finite set because we do not know anything about gamma whether it is finite or not ok, but gamma naught is contained inside this and what will be a model of the right hand side it will be a model of gamma which has size at least capital n and that we know yes. So, by hypothesis gamma union sigma bigger equal n is satisfiable and hence so is gamma naught. Now, since gamma naught was arbitrary finite subset is arbitrary is an arbitrary finite subset gamma prime gamma prime is finitely satisfiable and we are done. So, usual applications of the compactness theorem which do not involve adding new constant symbols to your language yeah then everything just works fine yeah it is a very simple application this is even simpler than the coloring problem or yeah what else did we do? Konig's lemma. Konig's lemma yeah this is simpler than that yeah you just need to know that there are arbitrarily large finite models. So, actually this is a very I mean this statement and this statement yeah. So, here if gamma is complete and has a model of size n then in fact, every single model of gamma is the same up to isomorphism yeah. So, this is known as absolute categoricity, but a very interesting consequence of the compactness theorem is that if you have a theory which has at least one infinite model ok. If there is a theory with at least one infinite model or arbitrarily large finite models by this statement that we just proved then it has an infinite model of any given cardinality a very very strong statement. These statements we will see next time in the next week these are called Lewenheim's Coulomb theorems it is a very strong consequence of this. So, for example, you know that there is a dense linear order which is numbers ok. So, what is the cardinality of rational numbers? Aleph naught, but now you ask the question do I know if there is a dense linear order that is unbounded on both sides and has cardinality 2 to the aleph naught. So, for example, you do not know about real numbers then Lewenheim's Coulomb theorem says yes there is a model of cardinality 2 to the aleph naught. Then you can also ask it for aleph omega some cardinal number that you do not necessarily understand, but Lewenheim's Coulomb guarantees that it does exist. Similarly, you can also get models if you know existence of models of a large infinite cardinality then you can guarantee the existence of models of slightly lower infinite cardinalities yeah. So, all these statements will be made precise later on ok. So, we have talked a bit about I mean we have defined the product structure yeah. So, just to give you a feel of product structures I have asked a very simple question here. So, 2 less than what is the ordering on 2 what are the elements of 2 first of all 0 and 1 and 3 is 0 and 1 and 2 the ordering is the usual ordering and now we are supposed to show that I mean first of all find out the universe of this product structure how many elements will the universe have 6 elements and how are they arranged in the form of a Hasse diagram in what form can somebody draw it on their notebooks and show it to me raise your paper of course, people who are busy with their phones should continue to do. So, yeah they are just here for attendance yes very good please draw it this is very simple structure yes if you do not number then 0 comma 2 appears at the bottom you should call them 0 0 comma 1 and 0 comma 1 comma 2 yeah. So, this will be 0 comma 0 comma 0 yes that will be 1 comma 0 0 comma 1 1 comma 1 1 comma 2 correct 0 comma 2 now we still have to understand a bit about what this structure is trying to tell us what is the language here L odd. So, in the product structure what happens a 1 comma b 1 is less equal a 2 comma b 2 if and only if a 1 is less equal a 2 and b 1 is less equal b 2 right. So, this is the definition a 1 comma b 1 is less equal a 2 comma b 2 if and only if a 1 is less equal a 2 and b 1 is less equal b 2. So, that is precisely what you observe in this yeah. So, 2 coordinates there is a path between pairs if and only if both coordinates are less equal yeah. So, a very simple exercise just to make sure you understand the concept ok. Now, next interesting question. So, we are talking about hyper naturals over here and these are like real hyper naturals yeah I mean real means I do not mean real numbers, but u is non principle if u is principle then what will happen star n will be a copy of n itself yeah we saw that yesterday. The dictatorship principle ultra filter means that the ultra product which is the average structure it is simply the original structure one of the original structures. So, star n is a copy of hyper years and you have to show it is uncountable. How do you go about something like this? Find an injection from a bigger set and which bigger set r plus and how do you show that alpha maps to seal sealing of e to the power alpha n alpha is coming from where alpha is coming from r plus and this function is let me write it down I am not sure I understand what is going on. So, alpha maps to sealing of e to the power alpha multiplied by n this is a function from. So, that. And how will you show something like this? Eventually every term. Eventually every term will be different. So, they cannot. They do not agree on any infinite set. So, therefore, everything. So, you choose for alpha in r plus that is what your claim is this sequence. I mean sealing is I think usually written like this with right perhaps I mean we will have to go into some dynamical systems or things I mean proving that the equivalence class is always different. If alpha is less than beta then e to the power alpha n will be. If alpha is less than beta then sealing of e to the power alpha n is strictly less than e to the power beta n eventually. I had a an alternate solution and which is much simpler. So, because we are talking about an ultra filter u on the set of natural numbers. So, either evens or odds will be in u. So, without. So, either evens either 2 n or 2 n plus 1 2 n minus 1 perhaps 2 n minus 1 which is all the things which can be written of no 2 n plus 1 is better or written like this is in u. So, if without loss of generality assume 2 n is in u. Then what can we can play around with we can always change the entries yeah the equivalence class means that we can always change the entries of entries which are in a small set which means now 2 n is large. So, even if you change the odd entry they will lie in the same equivalence class 2 sequences will lie in the same equivalence class. So, I am clay going to simply claim that and therefore, the sequences yeah I mean given a maybe I should write. So, if f and g are functions from natural numbers to 2 twice the natural numbers which means even natural numbers. Then sorry and f prime and g prime are sequences of natural numbers such that f prime restricted to even numbers wait I should have said something opposite I should say 2 n 2 n. So, f prime restricted to 2 n is f and g prime restricted to 2 n is g then f prime is u equivalent to g prime if and only if f is equal to g right because 2 functions they are equivalent if and only if they agree smaller or larger set I was thinking that these 2 sets are different. So, eventually you take all these functions and therefore, it will be infinite subset of even numbers. I was thinking that just because we can make a choice here I cannot think of any other solution right now. So, perhaps have you written this down properly yeah I think that would work write it down properly. So, this idea does not work fine should not you say r bigger equal 1 no it by Archimedean property this will be large right. So, let us try another exercise that an element of a ring is torsion free. So, just real numbers yeah we do not want to talk about an arbitrary element because you probably do not know rings yeah. So, element of real numbers is torsion free. So, let me quickly give you the definition. So, A in R is torsion free if A to the power n is not equal to 0 for all n in natural numbers ok. So, no power of it can be equal to 0 ok. So, which elements of real numbers are torsion free all yeah which elements of let us say z mod 3 z are torsion free or what about integers just integers which elements are torsion free all non zero elements are torsion free very good then z mod n z where n is arbitrary co prime multiples of n no multiples of n do not exist in z mod n z factors of n. So, if I take 6 and then I take 2 yeah. So, z mod 6 z and I take 2 the equivalence class of 2 then its power is 4 then 8 and then 16 and will it ever be all the some root some number which has same prime factors as n yeah No, not a subset as I just told you yeah you consider z mod 6 z then what will be the square of 2 4 what will be the cube of 2 8 is 2 modulo 6 z 8 is 2 then power 4 will be 16, but 16 modulo 6 is 4. So, it will just move between 2 4 2 4 2 4 yeah nothing else can happen. For each prime factor if it exists. Yes. So, all prime factors have to be present as factors of that entry then it can happen fine I mean that that was just a brief introduction to torsion elements yeah and another yeah. So, do you know that circle is also a group yeah circle also has like you consider circle with respect to multiplication then it has torsion elements circle as in complex plane circle yeah unit radius complex numbers. So, which of them will give you 0 I mean 0 is 1 there yeah I mean I am talking about slightly different concept here, but yes right anyway let us come back to this the question is now can you express this in a single sentence that it is torsion free is the concept of torsion free finitely axiomatizable you are saying no we have a proof no means you cannot think of a way, but this is similar to the question that we asked in the last tutorial yeah that is the theory of infinite sets finitely axiomatizable you have to say something about every single natural number yeah. So, this is not like for all n yeah a dot a dot n yeah this could be some somebody's idea n times this is not equal to 0 this one is not a valid sentence because it involves a quantifier over something which is not the universe what will be the universe our universe is a ring. So, real numbers. So, we cannot vary that quantifier over natural numbers which is an external object. However, we can add infinitely many sentences of this form yeah. So, this is not necessarily finitely axiomatizable it is, but nonetheless it is still axiomatizable ok. So, we can add a sentence oh I mean perhaps not a sentence, but a formula theta n of x which is x dot I mean now we have to write x dot yeah how do we write that we usually use I mean our language is that of rings. So, it is L ring and we have f g c e this is binary binary and then maybe there is an h which is unary then 0 and 0 this one stands for 0 this one stands for 1 plus dot minus 0 1 yeah these are our notations. So, we have to write that g of g of and so on finally, you will have g of x comma x comma x and dot you come out of it and that is equal to c and you put a negation ok. So, this is the formula which expresses that it is not x is not a torsion element of order n and then you have to say that x is not a torsion element of any order n yeah. So, how do you write that for all w yeah if w is not 0 then theta n of w holds this will say that every nonzero element is torsion free of order n and then you put one set sentence yeah n less than omega now this is a set of sentences. So, this is our theory of torsion free n can be arbitrary product is occurring n times, but the product is of w with itself. So, why do we need different things how many times that is expressed in theta n theta n is the formula which says that you do this n times and n is fixed yeah n is not varying n is fixed. So, I am adding one sentence of this type for each n. So, I am not just talking about a single sentence I am talking about an infinite collection of sentences and this collection does express what I need yeah. So, this is the theory of torsion free elements and we are excluding the obvious thing 0 is always torsion of every order. So, why should we bother adding it anyway yeah. So, every element is torsion free you can express it in terms of infinitely many sentences, but this is not finitely axiomatizable yeah maybe let us spend some time talking about 8 because perhaps that is the most difficult thing out of this. So, perhaps we are talking about show that the interpretation of a relation symbol in an ultra product is well defined ok. How did we define this I am not doing the function symbol part I am just doing the relation symbol part how did we define this relation symbol we said that given h 1 h 2 up to h m yeah in our universe no not in the universe I do not think I need this just the product structure and an m-ary relation symbol are what do we say that the equivalence classes of all these elements this tuple of equivalence classes of these choice functions lies in the interpretation of the relation symbol in the ultra product if and only if I mean this is just definition. So, if and only if what can we say this set of those indices where the ith component structure satisfies sorry I mean this is same as satisfies, but h 1 i up to h n i yeah this belongs to the interpretation of the same relation symbol in the constituent structure m i is a large set ok. So, tell me how to show that this is well defined what is the meaning of being well defined if I choose like this is a tuple of equivalence classes of choice functions. So, if h 1 is u equivalent to h 1 prime h 2 is u equivalent to h 2 prime and so on h m is u equivalent to h m prime then we need that the set of indices where h 1 i dot dot dot h n i h m i. So, this is m sorry h m i this tuple belongs to r the interpretation r m i belongs to u if and only if the c similar set for h 1 i h 1 dash i up to h m dash i this belongs to r m i this is large. So, how do we show something like this that this is in this is large if and only if the other one is large exactly both sets contain something common what is that common thing yes. So, both of them should happen yeah. So, the set. So, enough to show that the set of all indices such that both of them belong yeah h 1 i comma h m i as well as h 1 prime i up to h m prime i they are both in r m i is in u, but this particular set contains what the set of all those indices where h 1 i is equal to h 1 prime i correct intersection the set of all indices where h 2 i is equal to h 2 prime i and so on finally, the set of all indices where h m i is equal to h m prime i whenever for a particular index h 1 and h 1 prime agree h 2 and h 2 prime agree all of them agree then obviously, this and that will both belong to that it simultaneously and this one we already know by definition because they are u equivalent. So, each one of them belongs to u and therefore, ultimately the intersection of all of them belongs to u and therefore, everything follows by upper bounds upward closed property any questions similarly you show it for function symbols and constant symbols. Now here I mean please observe something that our relation symbols are finitary and that property is being heavily used here similarly our function symbols are also finitary that is also being used because ultra filters are only closed under finite intersections and not arbitrary intersections you understand yeah. So, that is why compactness theorem which is a consequence of Walsh's theorem it holds for finitary logic, but not for infinitary logic yeah lots of things go wrong if your logic is infinitary. So, let us end it here a big thank you to all the in class students as well as online learners I hope that you enjoyed this journey through set theory and logic with me and the course has taught you a few new things thanks again.