Lecture 43 - Predicate Logic: Categoricity (Continued...) and Quantifier Elimination

Let us begin. So, we have seen yesterday that an L-theory is categorical or now what is called absolutely categorical, if it has only one model up to isomorphism. That was the original definition of Weblen. However, thanks to Lohenheim's column, his dreams were never to be realized. Because if a theory has an infinite model, then it has a model of every cardinality bigger equal the size of the language. Every infinite cardinality bigger equal the size of language, thanks to Lohenheim's column theorem. So, then we started looking at some weaker version of categoricity and which is the most appropriate one. So, we say that an L-theory is kappa categorical for a cardinal kappa bigger equal size of L infinite cardinal. If any two models of gamma with size kappa are isomorphic and we looked at some examples. So, the theory of real vector spaces is indeed kappa categorical for every kappa bigger than the size of the field. Because every vector space of size kappa has a kappa bigger than 2 to the L F naught has a basis of the same size. And whenever two vector spaces have same size basis, then they are isomorphic. So, therefore, this one works. Then obviously, gamma inf set yeah any the theory of infinite sets in the empty language L set yeah that is kappa categorical for every infinite kappa. Obviously, because there is only one set up to isomorphism and here I mean without loss we are assuming axiom of choice yeah otherwise this statement would not be true. Because thanks to axiom of choice every set has a cardinality every set is in bijection it can be well ordered. So, therefore, you can find the least ordinal with which it is in bijection and therefore, you can define the cardinality yeah. So, well ordering theorem or equivalently axiom of choice is being assumed and we have been doing that since we started with like more advanced parts of logic anyway. Because we proved compactness theorem yeah that is a consequence of axiom of choice it uses prime filter theorem ok. Then yesterday we also showed an interesting result for dense linear orders that if your dense linear order is unbounded, then cantor isomorphism theorem or which is also known as back and forth method it shows you that this theory is aleph not categorical which means there is only one countable model up to isomorphism. Now just to add to this list yeah I am going to say something more yeah that is also a very interesting well first let me define the language. So, let us say this is the language of rings yeah which is F, G, H, C, E that is what we have been using yeah this is a binary unary 0-ary 0-ary, but I am going to interpret F and G as meet and join and H as complement and C and E as 0 and 1 the top bottom and top element. So, now I take the theory not of just Boolean algebras, but atom less Boolean algebras ok. So, atom less Boolean algebras you remember do you remember any example of atom less Boolean algebras propositional logic provides one example can you be more specific chain is not an example of a Boolean algebra unless it is only two element chain say something more Lindenbaum-Tarski algebra yes for a countably infinite language yes that is definitely. So, L T algebra for a countably infinite propositional language what was our notation we used B L yeah. So, B L, but size omega I mean size aleph naught. So, this is an example, but in fact, this theory is aleph naught categorical ok. So, what do I mean by that that there is only one countably infinite model up to isomorphism. So, there is this is the only atom less Boolean algebra which is countably infinite and how do you prove something like that. If you remember yesterday we saw something about this Cantor isomorphism theorem what was given to you that I mean even if let us say a DLO and bounded yeah there are two dense linear orders which are bounded and contain at least two elements yeah. So, suppose that is given to you then you map the least element to least element largest element to largest element and then in between you can play around just like this unbounded case you can map any element to any element and then below that there is a non-minimal element above that there is a non-maximal element and between any two elements there is a thanks to density. Now, if you remember there was an exam question about density of atom less Boolean algebras right. So, atom less means that below any non-zero element there is another non-zero element. So, that is like unbounded below you will map 0 to 0 1 to 1, but removing 0 and 1 it is unbounded below it is unbounded above and it is also dense. So, using these properties if you can list all the elements of one Boolean algebra one countably infinite atom less Boolean algebra and another countably infinite atom less Boolean algebra then you can just follow the back and forth method. You have to simply make sure that meets will get mapped to meets joints will get mapped to joints yeah there is slightly more work to do, but you can ultimately get there and therefore, by a same argument essentially the same argument you can prove that this is the only countably infinite atom less Boolean algebra. So, as soon as you have density and all yeah everything starts working fine density and unboundedness any questions yes the idea is still the same. Another thing which might be interesting for you yeah. So, now, I am going to talk about consists of one relation symbol which is binary and we saw that one of the examples is I mean the simplest possible example is directed graphs, but I can also talk about graphs they do not have to be directed what is a graph do you remember the definition of a graph what should you put in this theory simple graphs are there are two properties irreflexive and symmetric very good. So, simple graphs. So, I am going to take theory of simple graphs. So, this is irreflexive plus symmetric binary relation. So, this is the definition, but I am going to add something more to it. So, for every single graph. So, for example, I am giving you this just this collection this is a graph this is a simple graph how many vertices does it have 3. Now, can you write down a sentence which says that a sub graph of my graph is isomorphic to this the induced sub graph is isomorphic to this induced sub graph is isomorphic what does that mean I have some graph and it has 3 vertices if I restrict to only those 3 vertices then the graph will look exactly like this. So, what should I write down there exists W 1 W 2 W 3 such that R W 1 W 2 very good R W 2 W 3 and not R W 1 W 3 do you understand this what does this say this says that there is let me call this G equal to V E vertex and H set. So, this sentence says that let me call this phi G. So, phi G says that there is like G is an induced sub graph G is isomorphic to maybe I should be precise is isomorphic to an induced sub graph. So, every single finite graph can be written like this definitely every single finite graph will have a corresponding sentence phi G. So, what if I say random simple graph this consists of yeah I mean gamma simple graph union phi G such that G is a finite simple graph. So, what am I claiming I am claiming that there is I mean first of all I am claiming that this theory is satisfiable first try to understand what it is saying this is satisfiable means that there is a graph which has 1 copy of a given finite simple graph as an induced sub graph and this should happen for any finite simple graph. So, obviously, you can imagine this structure if it is satisfiable then it must have an infinite model correct because the size of this finite graphs can grow larger and larger and larger. So, therefore, if it is satisfiable then it must be infinite. Now, how do you show this is satisfiable compactness yeah you choose the theory of simple graphs that much you should always retain it just 2 sentences and then you should add phi G for finitely many of them well do you know any such example if there are only finitely many such graphs then you take disjoint union of all such and then that is a model of that finite subset. So, therefore, this is finitely satisfiable. So, by compactness this is satisfiable and by Lohenheim's Coulomb theorem it must have a countable model because the language is singleton. So, the smallest infinite cardinal bigger equal size of language is aleph naught ok. So, I said lot of things yeah. So, this must have an infinite model of size aleph naught ok. So, thanks to compactness we know this exists. So, this one is called a random graph why is it called a random graph. So, basically you start with a countably infinite set of vertices yeah let me draw some picture for you and then. So, random graph you start with countably infinite set of vertices and between any two vertices if you want to put whether you want to add an edge or not you decide that by doing a coin toss if it is heads I will put an edge if it is tails if it is a fair coin yeah then what however, I construct this graph and you had to do it for every single pair. So, that is why it is called a random graph and how many such random graphs are there countable countably infinite random graphs well I am writing it as an as the fifth example. So, you can guess there is only one up to isomorphism ok. So, this depends on coin toss you have question ok. So, there is only one such random graph and how do you prove that there is only one such random graph the idea is very simple back and forth method there is no other argument that you know ok. So, you start by mapping any vertex to any other vertex then you look at it is now you choose another vertex and now you look at the subgraph generated by those two yeah now that subgraph is finite. So, you must be able to find by appropriate choice of capital G you must be able to find such induced subgraph in this model and then you keep on building and building and you will get an isomorphism using back and forth method you have to be a little bit more careful, but back and forth method works let us not go into details. So, I am giving you all sorts of examples of how logic can be helpful in ordinary mathematics pure mathematics yeah we have seen one example of hyper reals which is analysis yeah this is graph theory this is Boolean algebras we are we have been talking about algebraically closed fields. So, algebra is there yeah everything can be done appropriate with appropriate choice of languages and theories. So, yes one more thing I think we also wrote did we write this gamma S E F 0 is kappa categorical for kappa bigger than aleph naught well actually if you observe all these examples yeah then if you cross a certain threshold then we are saying its kappa categorical for all kappa bigger than a certain threshold is that a coincidence the behavior is very different for aleph naught or in this case real numbers the cardinality of real numbers the behavior is different I mean how many vector spaces are there up to isomorphism of cardinality same as real numbers r r square r cube. So, for each non zero natural number as dimension you have a different one right. So, the behavior was different for the cardinality of real numbers, but if you cross that then the behavior is identical similarly here yeah the behavior is yes here atomless Boolean algebras it is aleph naught categorical, but it is not categorical for uncountable cardinals. Similarly this is aleph naught categorical, but it is not uncountably categorical yeah for example, real numbers real numbers are a model of this right real numbers are dense rational numbers are dense right. So, you can actually play around with things perhaps I should not say more if you remember Dedekind cuts yeah then using Dedekind cuts you can say certain things over here because Dedekind cuts I mean they are they materialize they realize in real numbers, but they do not realize in rational numbers yeah because in rational numbers there are gaps in real numbers there are no gaps. So, that way the behavior of reals and rationals is different they are not in same cardinality, but I am trying to provide you with one model of real with of this theory which is not isomorphic to real numbers. So, what you do you take real numbers plus a single vertex single point plus a copy of rational numbers that is a model of this, but it is not isomorphic to real numbers it has the same size, but it is not isomorphic that is because of Dedekind cuts. So, my main point is that there is a very fixed cardinality which is the size of language plus aleph naught this cardinality and then all higher cardinals. So, there is a clear distinction in behavior of this and that is not a surprise when people observed this then one very prominent model theorist logician he proved this result. So, that is called and it is proof is very hard Morley categoricity theorem. So, suppose kappa is bigger than size of L plus aleph naught if gamma is an L theory that is kappa categorical then gamma is lambda categorical for each lambda bigger than size of L plus aleph naught. So, the behavior is only different for this particular cardinal number size of L plus aleph naught and if it is categorical for some kappa then it is categorical for all kappa satisfying this cardinality condition this is a very deep theorem in model theory and all the examples that we have seen definitely make this belief strong. For example, this I gave you some examples yesterday of countable models of this Q-algebra then Q-algebra X, X 1, X 2, X n you add some finite transcendence degree and then there are different non isomorphic pair wise non isomorphic models any questions about this. Now, perhaps we should come back to a simpler question. So, we have shown that if a theory has model which is finite then if a complete theory has a finite model then every model of that theory is has the same size ok, but I think we also mentioned something about the converse a test for completeness you remember that it is called Walsh-Watt test. So, let us quickly state and prove this if gamma is an L theory without any finite model and gamma is kappa categorical for some kappa bigger equal a left naught plus size of L then gamma is complete what is our favorite method of proof in logic induction yes, but the second most favorite induction cannot be used here what will you induct on proof by contradiction. So, we are going to do that. So, suppose not suppose gamma is incomplete. So, incomplete theory that is a prelude to tomorrow's lecture Goddard's incompleteness theorems it is about incomplete theories. So, suppose gamma is incomplete then what can you say it is incomplete. So, it cannot decide about some sentence. So, then there is some phi such that gamma does not logically imply phi and gamma does not logically imply negation phi. So, by there was an exercise which we have done several times like. So, then what can you say about this both of them are satisfiable. So, let m 1 be a model of gamma union negation infinity negation phi and m 2 be a model of gamma union phi. So, since gamma does not have a finite model m 1 and m 2 are infinite now using a combination of both Lewin-Holmes-Colomb theorems using L S theorems there is a model n 1 of theory of m 1 such that size of n 1 is equal to kappa theory of m 1 is a satisfiable collection of sentences right. So, therefore, we can get some n 1 of size kappa because you can go up and down upward and downward Lewin-Holmes-Colomb theorems they will guarantee existence of this and similarly n 2 satisfying theory of m 2 such that size of n 2 is equal to kappa. Now, observe I am talking about theory of m 1 which is the collection of sentences which are true in m 1. So, gamma is contained inside there in particular n 1 satisfies gamma and it also satisfies negation phi and n 2 satisfies gamma and it satisfies phi. So, n 1 and n 2 are both models of gamma, but one satisfies phi and another one satisfies negation phi. So, can they be isomorphic therefore, n 1 and n 2 are models of gamma that are not isomorphic models of gamma with size kappa and therefore, what we have shown therefore, gamma is not kappa categorical end of proof. We simply proved the contra positive and this is wash what test very simple proof. So, using this now you can conclude lots of things yeah let me go back to this slide where we have we are looking at examples of categorical theories. So, let us look at this the theory of infinite vector spaces yeah I mean this is important I am not saying 0 is a real vector space I do not want that I want to say add an axiom which says that there exists a w such that w is not equal to 0. If I add that then this theory is kappa categorical for any kappa. So, it is it satisfies the hypothesis of wash what test look at this it should be an L theory without any finite model. So, I said that there is at least one nonzero element and as soon as there is one nonzero element I should have all its scalar multiples. So, it becomes infinite. So, therefore, the theory of vector spaces without nonzero vector spaces or infinite vector spaces that theory is kappa categorical and hence complete. Similarly, the theory of dense linear orders which are unbounded that is a left not categorical can it have a finite model no. So, therefore, it is also a complete theory what if I talk about bounded dense linear orders then I should add the hypothesis that there are at least 2 elements because by density by 2 elements I can generate infinitely many of them. So, the theory of bounded dense linear orders with at least 2 elements is also a left not categorical and hence complete right. Theory of atom less Boolean algebras of course, every atom less Boolean algebra has to be infinite. So, the theory of atom less Boolean algebras is also complete. Similarly, theory of random graphs is complete and ACF 0 is also complete. Similarly, ACF p is also complete for any prime p if you understand what is characteristic of a ring. So, there are so many examples of complete theories, but yeah I mean let me quickly say something that for finite things it does not really work. One theory can have one finite model and another finite model of the same size, but they are not isomorphic. So, for example, z mod 2 z we have seen this then you can take its product with z mod 2 z and z mod 4 z is another group both of them contain 4 elements, but they are not isomorphic ok. You consider 1 in z mod 4 z then you how many times do you need to add 1 to itself to get 0? 4 times 1 plus 1 plus 1 plus 1 is 4, 4 is 0 modulo 4 z. So, therefore, there is 1 element of order 4 in that side, but every element on this side has order 2 ok. So, therefore, yeah I mean its pairs of 1 and 0s 1 comma 1 is of order 2 because 1 1 comma 1 plus 1 comma 1 is 2 comma 2 which is 0 comma 0. This is called Klein fear group fear is 4 in German yeah Klein was German. So, he said its Klein fear group and he did not name it Klein fear group, but ok. So, there can be a theory which has a finite 2 non isomorphic finite models of same cardinality right. So, now, let us go ahead I think I have said everything I wanted to say about this ok. Now, we want to understand this let us go back to high school around 8th grade you must have first heard of the term quadratic equation 7th 8th yeah I am older than you. So, I do not know when you learnt it. So, how do you solve a quadratic equation which one completing this square yes fine, but I am going to ask you this suppose a b and c are fixed coefficients. So, if I write a w square plus b w plus c equal to 0 and then I am asking you whether there is a real number because you only knew at that time you only knew real numbers yeah. So, whether there is a real number which satisfies this just the question whether there is one I am not asking you to find it can you do it in terms of a b and c what is the answer b square minus 4 a c is bigger equal 0 ok. So, this is true if and only if b square minus 4 a c is bigger equal 0. So, if I am talking about the ordered field of real numbers then look at that side of the formula does it contain any quantifiers no. So, that is the quantifier free formula which is logically equivalent to this modulo theory of real numbers ok. I mean this modulo theory of real numbers needs a little bit more explanation. So, I can write it for you see the it says that the theory of real numbers witnesses that for all w a w b w c there exists a w such that a w a square plus b w b plus w c equal to 0 if and only if w b square minus 4 w a w c is bigger equal 0. So, basically the theory of real numbers witnesses that these two sent these two formulas are the same. So, what we have said that one formula with quantifiers this one is logically equivalent modulo the theory to a quantifier free formula. So, if you can do it. So, now, let me write down the more technical term. So, say that an L theory gamma eliminates quantifiers if for any formula phi x bar there exists a quantifier free formula psi x bar such that gamma witnesses that for all w bar phi w bar and psi w bar are logically equivalent w a what oh sorry yes I made a mistake here. Thank you let me write it again w a w square plus w b w plus w c equal to 0. So, a theory is said to eliminate quantifiers if for any formula there is a quantifier free formula which is logically equivalent to it. Now, this is the process that I mean in general there is no recipe for this for eliminating quantifiers there is no recipe there are some well practice techniques, but they work only in special situations, but before we do this let me remind you that every formula is logically equivalent to one in a particular form what is that form called the prenex normal form. So, prenex normal form has all the quantifiers in the beginning. So, this is simply a reminder that all quantifiers q w 1 bar q w 2 bar I mean q 1 w 1 bar q 2 w 2 bar and so on q k w k bar and then inside it is quantifier free. Now, if I want to eliminate the quantifiers then I should first look at only this just the last quantifier which is present there and then if I can eliminate that then I will go to a larger q k minus 1 then I will eliminate that then I will eliminate all from. So, we open it up from the inside and then we get to outside is that clear yeah we try to eliminate quantifiers from inside out and what is the quantifier that we have chosen in our language we always choose there exist and not for all because for all is negation there exist negation. So, even if you can eliminate yeah just there exist is it is ok. Moreover, now a quantifier free formula in what format can we write that a quantifier free formula you remember from propositional logic what is the normal form for that d n f yeah. So, the d n f also works here. So, d n f always looks like this disjunction of conjunctions and if there is a there exist outside then actually if you remember we proved a logical equivalence that I can take it inside this is logically equivalent to this if you do not remember this do it as an exercise that disjunction and there exist you can swap ok. So, therefore, now the whole process of eliminating quantifiers simply boils down to eliminating quantifiers from a conjunction of atomic formulas conjunction of literals. So, in this case literals are either atomic formulas or their negations ok. So, eliminating quantifier simply boils down to eliminating a quantifier from a conjunction of literals finite conjunction of literals ok. First let us try to understand what this quantifier really means. So, for example, yeah I am writing down this particular equation which you all know x square plus y square equal to 1 in real numbers what is the definable set of this it is a circle yeah you are all scared to say the circle now yeah, but this is actually a formula and I am asking you what is the set defined by this. So, fine this is a circle I am going to draw a circle what is the origin 0 0 and this point is 1 0 ok good. Now, I am asking if I project on to the first component which means I should write this there exists a w such that x square plus w square is equal to 1 what are the values of x which satisfy this what are the values of real numbers which satisfy this minus 1 it does satisfy 0 1 everything in between everything in between. So, this is satisfied yeah. So, the set defined by is the interval minus 1 to 1 ok. So, basically what I am doing I am looking at a point then I am drawing the vertical line at that point and I am asking whether this vertical line intersects the circle if I draw vertical line over here does it intersect the circle no. So, therefore, that point is not in minus 1 1 the closed interval I mean the formula here is simple right it is minus 1 less equal x less equal 1 this is the formula yeah minus 1 is less equal x and x is less equal 1. So, that is the formula. So, what is the meaning what is the geometric interpretation of their exist its projection. So, geometric interpretation of their exist is projection. So, if you are given a definable set then you try to project it down to something smaller you are studying linear algebra yeah. So, in linear algebra you solve solution solve systems of linear equations now those linear equations are finite conjunctions of atomic formulas yeah because what are atomic formulas in the case of real vector spaces the language of real vector some variables is equal to scalar multiples of constants. So, ultimately you can rewrite it as a single linear equation R linear equation right. So, that one you can project and then you ask whether this particular system of linear equations has a solution what are you doing you are asking for their exist a w such that some system some matrix equation yeah a bar then usually you write w bar y bar and you are asking for w bar and is equal to some b bar this is what you are asking Gaussian elimination method will let you solve this system of equations well actually if you work a little bit harder you can show that that gamma R vector spaces eliminates quantifiers I mean essentially the argument is based on Gaussian elimination. So, you are asking for projections of solution sets of linear systems to lower dimensions and that projection is there exist if you want a geometric interpretation of for all quantifier universal quantifier then this vertical line has to lie entirely inside the definable set see there exist says that the vertical green line there is a point on the green line which is also on the definable set for all says for all points on the green vertical line it is inside the definable set. So, there is lot of geometry hidden in these pictures I will end this by giving you more. So, this is usually called Q E yeah quantifier elimination Q E is quantifier elimination. So, some more examples of theories which admit quantifier elimination. So, that is gamma S E F yeah the theory of algebraically closed fields it eliminates quantifiers in algebraic geometry this is a celebrated theorem it is called Chevali's theorem I mean in more technical terms it says that the projection of any algebraic variety is a constructible set. Constructible set is a finite Boolean combination of algebraic varieties and algebraic varieties are solution sets of polynomial equations. So, this is the one then gamma R C F real closed fields which means the theory of real numbers as an ordered field. So, this is called Tarski Seidenberg theorem yeah there are big names associated with this then similarly you can show that theory of dense linear orders also eliminates quantifiers. Then theory of ordered abelian groups also eliminates quantifiers. Pressberger arithmetic which is a weaker form of our normal arithmetic on natural numbers that also eliminates quantifiers and it has applications in computer science because you want to eliminate quantifiers fast enough yeah. So, computer scientists are very heavy on this because decidability problems and algorithms they all depend on how fast you can eliminate quantifiers. So, yeah with this I am going to end today's lecture.