Lecture 42 - Predicate Logic: Reduced Products, Categoricity

Let us begin. So, today I want to talk about a little bit about ultraproducts again, generalization of ultraproducts and Wasser's theorem. So, before we do that I want to show you something very interesting about the structure of formulas ok. So, let us start with a particular formula in appropriate languages the languages are going to be different. So, the first formula I am writing down is this for all w 1 w 2 g w 1 w 2 is equal to g w 2 w 1. What does this represent? Commutativity of the function symbol g or its interpretation fine. Then another thing I am going to write down is this for all w 1 w 2 there is a bracket r w 1 w 2 conjunction r w 2 w 1 this thing implies w 1 is equal to w 2. What does this represent? Antisymmetry of the interpretation of the relation symbol r and last one I am going to write down is for all w 1 negation w 1 equal to 0 implies there exists a w 2 such that g w 1 w 2 is equal to e and g w 2 w 1 is also equal to e. What does this represent? Multiplicative inverse yeah in an appropriate language oh sorry I made a slight error here I should not be writing 0 I should be writing c ok. So, these are three different types of sentences. The first one is called a universal horn sentence. So, what is its form? Its form is very simple its bunch of universal quantifiers in the front and inside it is an atomic formula. Then the second one is called a strict horn sentence. It has this particular form. So, a bunch of universal quantifiers in the front and then inside there is a conjunction of atomic formulas some finitary conjunction and this conjunction whole conjunction implies another conjunction another single formula. So, in particular if I choose n to be equal to 0 what do I get? The universal horn sentence ok. So, strict horn sentence yeah its horn as in these horns yeah its a name of a person ok. And the last one is not a strict horn sentence. Are you all convinced? The last one has a negation of an atomic formula and implies something else and then the there exist is inside even if I use the logical standard logical equivalences to bring this there exist out still I will not get anything nicer yeah there exist will come out as there exist. So, its not in the universal form like universal quantifiers and then inside something else happens. Now, I am also going to ask you something related to this. So, the this is like 1, 2 and 3 yeah maybe I should write here that phi i's and psi are atomic ok. Now, the first one is satisfied let us say by a group yeah when G is interpreted as a binary function. So, is the cross product of 2 groups a group I mean if you do not know what a group is properly then just think about r plus 0 r plus 0 cross r plus 0 is that a commutative group does it satisfy commutativity how is this sum defined in r r cross r component wise ok. So, r plus 0 cross r plus 0 is commutative ok. So, in general any interpretation if you have 2 structures for which there is some G which is commutative then I take cross product of those 2 structures the product structure yeah we have defined product structure properly then that will satisfy this commutativity property ok. Second one if I take 2 different posets. So, P 1 less equal cross P 2 less equal yeah this is also a product of structures is it still antisymmetric component wise if in both components you have this yeah means a 1 b 1 is less equal a 2 b 2 and a 2 b 2 is less equal a 1 b 1 then a 1 b 1 is equal to a 2 b 2 right ok. So, this one is antisymmetric third one on the other hand if I take real numbers with addition multiplication minus 0 1 our usual thing and I take it is cross product with itself yeah we have already seen this is not a field this is the field axiom it says that every nonzero element has a multiplicative inverse whereas, this one is not a field because 1 comma 0 multiplied by 0 comma 1 is 0 or 1 comma 0 is a nonzero element, but it does not have a multiplicative inverse is that clear ok. So, this is not a field similarly can you tell me the distinguishing property between linear orders and partial orders trichotomy. So, fourth one I will write trichotomy and what is the form of that sentence for all w 1 w 2 there exists a w 3 trichotomy either r w 1 w 2 or r w 2 w 1 or w 1 is equal to w 2 just to be safe even if it is interpreted as a strictly strict order. Now, if I take a cross product of 2 linear orders yeah we did that cross product of a 2 element linear order with a cross product of 3 element linear order Sahil wrote that on the screen was it a linear order no. So, cross product of 2 linear orders. So, l 1 less equal cross l 2 less equal does not satisfy trichotomy. So, again look at the form of this particular sentence this is not a horn sentence it is not a strict horn sentence because it uses universal quantifiers and then disjunction inside ok. So, what is important here is that if your sentence if your axiom happens to be a universal horn sentence then it is preserved under products and conversely also it is true ok. So, a sentence is a universal horn sentence if and only if it is preserved under generalized products ok. Now, I am using a slightly different word, but anybody has any problem with this well perhaps you can ask the question cannot you find out anything which is logically equivalent to let us say trichotomy and which is a universal horn sentence, but the answer is you cannot yeah and that is because it is not preserved under products because this is an if and only if statement. So, more generally yeah I mean now let us go and do some theory. So, all of you remember this structure product of m i, i in I yes this is the product structure if I quotient it out by a relation yeah I mean instead of this I maybe I should write. So, you remember this was an ultra product and at one point we did check that tilde u yeah tilde u is an equivalence relation equivalence relation on the product of the sets underlying sets and if you remember the proof of this equivalence relation then reflexivity transitivity and symmetry where the 3 conditions that we checked, but in none of those conditions we actually use the full definition of an ultra filter. Every time whatever we used was or it should be closed under intersections finite meets and it should be closed under upper bounds we never used. So, we only used yeah, but we only used that u is a filter. So, my point is that even if you relax this condition a bit even if you do not say it is a an ultra filter you just say it is a filter then also everything will go through. So, the same construction the ultra product construction goes through if the if an ultra if the ultra filter u is replaced by a filter say f can you give me one very simple example of a filter just singleton top element yeah singleton i that is a filter yeah because it is non-empty it is proper subset it is closed under upper bounds because it only has one element and it is closed under finite meets because meet of the top element is again itself. So, in that case if I construct this relation what does this say two things are equivalent two tuples are equivalent if and only if the set of indices where the tuples agree lies in i I mean is equal to i yes maybe if you are confused I will write down yeah in particular if f is equal to singleton i then a i in i is f equivalent to b i i in i if and only if the set of all indices such that a i is equal to b i this one belongs to f, but what is in f only capital I. So, if and only if for all i in I a i is equal to b i well this means that we are not quotienting out by any non-trivial equivalence relation it is this just the identity. So, therefore, product of m i i in I modulo f is equal to just the product of m i's we are not identifying anything here. So, this shows that if you replace an ultra filter by an arbitrary filter then product is also a filtered product an ordinary product is also a filtered product. Oh yes here I should write the name yeah to get a reduced product yeah this is the name yeah this is the name of that. So, this is I in I modulo f yeah. So, ultra products are generalized to reduced products and reduced products it is not just one reduced product yeah if you change your filter you will get another reduced product and one particular example of a reduced product is just the product. So, for every reduced product also yeah I mean let me write that theorem down. So, suppose L is a language and f sorry I is an is a non-empty set m i f a filter on I then m i I in I an indexed family of L structures and phi is in S L then the reduced product oh sorry I should not have said this I will change it slightly yeah the filter is not given yet then phi is logically equivalent to a strict horn sentence if and only if for all filters f oh wait I should say something more in this in the hypothesis and m i satisfies phi for all I if and only for all filters f the reduced product satisfies phi. I already gave you lots of examples yeah that antisymmetry, commutativity, associativity, identity they are all examples of strict horn sentences. And if your component structures satisfy the strict horn sentence then for all reduced products that will happen yeah because this is an if and only if characterization and you can see how beautifully you can know about the form the syntactic form of a sentence based on a model theoretic property ok. Now, once again focus on this red sentence what does this say that we have only used that u is a filter then why are we talking about ultra filters at all where exactly was it used in Walsh's theorem. So, I am going to show you that part now. So, if you remember Walsh's theorem I am not going to write down full statement, but just this. So, product of m i i in I modulo u satisfies phi x let us say phi at h 1 h 2 h n their equivalence classes if and only if the set of indices such that m i satisfies the individual components h 1 i up to h n i lies in u. We never really proved this yeah I told you that the proof is very simple it is just induction on the complexity of formulas, but I am going to point out your attention to one particular proof one particular part of the proof. So, let us say suppose by induction hypothesis the conclusion I mean the statement is true for phi x bar and we want to show it we want to prove the statement for negation phi x bar. So, negation is the only part where we really use that it is an ultra filter. So, when will that happen? So, what do we need to start with? So, let us look at the definition yeah. So, product of m i i in I modulo u satisfies negation phi at these equivalence classes of choice functions if and only if yes I am going to write this what can you say about the product satisfying phi at this collection it does not. So, by induction hypothesis what do you get this does not satisfy. So, by induction hypothesis for phi what do you get that this collection of indices is not in u. Such that m i is not in u by induction hypothesis ok. Now, comes the important property if this set does not belong to u then by the ultra filter property what belongs to u its complement yes this is the crucial step where we use that the set of i's such that m i does not satisfy I mean maybe I should write down one more thing yeah. So, if and only if the complement of this set belongs to u by ultra filter property ok. Now, this is same as the set of indices where what should I write now m i does not satisfy phi H n i belongs to u well what is the meaning that m i does not satisfy phi m i satisfies negation very good. So, now, we are done. So, m i satisfies negation phi at these components and this is precisely what we wanted to show all the remaining things there exist and conjunction everything is simple, but this is the only crucial property where we use that it is an ultra filter and that is why Wasch's theorem is a very strong statement it says that if majority of these structures component structures satisfy your property phi then the ultra product will also satisfy it, but we just saw on the previous slide to contrast that that even if all of the structures satisfy phi the reduced product may not satisfy it unless it is a very particular type of sentence it is a strict horn sentence ok. So, that is why r cross r is not a field yeah and we had to work hard and to get hyper reals to quotient out by an ultra filter you understand this part now and I also gave you a sketch of some part of the proof I mean this is an actual proof of the negation part yeah there is no point in writing down the full proof of Wasch's theorem let us go ahead then fine. So, now we are going to talk about a concept which was originally introduced by Oswald Veblen in 1904. So, if you are given a theory now what can you do with that theory you would like to find its models you know it is satisfiable you would like to find its models and once you know that models exist you would like to understand all its models well obviously, you cannot understand all the models like individually because you can always change the names of elements in that model. So, up to isomorphism you would like to understand all the models right. So, Veblen was also thinking like that in 1904 yeah very early more than 100 years ago now. So, he said a theory gamma is categorical if any two of its models are isomorphic ok. Now can you give me one example of a theory which is categorical. Sets with n elements. Sets with n elements yeah if you if set with n elements is the theory then sigma n is the sentence that we write. So, if one model satisfies sigma n and another model satisfies sigma n then there are n elements and you cannot really say anything else about them you cannot distinguish between those two elements and then there is a bijection between any two n element sets right. So, therefore, any two models are isomorphic that bijection is an isomorphism of structures. So, therefore, yes. So, for example, gamma n equal to singleton sigma n is categorical and it was not really surprising, but Veblen and all his successors only found examples of categorical theories which have finite models ok. So, then in 1917 or 18 just after first world war. So, Leuvenheim and Skolem I mean I think it was just Leuvenheim in the beginning and then Skolem added something. So, this is around 1917. So, they proved their theorems yeah which says that if your theory has one infinite model then it has infinite models in all cardinalities bigger equal the cardinality of the language yeah. So, if a theory gamma has one infinite model then for all kappa bigger equal the size of L there is a model of size kappa. So, if two different models have different cardinalities they be isomorphic? Obviously, not yeah because there cannot even exist a bijection. So, for isomorphism existence of a bijection is the basic requirement. So, therefore, you cannot have any categorical theory right. So, no categorical theories with infinite models ok. So, this was a very easy consequence of that, but a mathematician does not really stop if you get a counter example then you modify your definition ok. So, then people said why not study a graded version of categoricity. What is the graded version that you fix a cardinality and then ask whether there is a unique model of that cardinality up to isomorphism. So, this is the definition of kappa categoricity. So, let kappa be a cardinal say that a theory gamma is kappa categorical if any two models of size kappa are isomorphic. This one is more believable yeah because now you can at least talk about bijections. Yeah the problem with Lohenheim's Coulomb theorems conclusion is that their cardinalities are very different. So, you it does not really make sense to ask for something nice ok. So, when kappa is aleph naught yeah this is just a note yeah. So, note if kappa is equal to aleph naught then the literature mentions omega categoricity instead of aleph naught categoricity yeah perhaps when this discussion started the notation aleph naught was not in practice. So, therefore, they only talked about omega categoricity omega and aleph naught are the same as ordinals they are the same yeah, but if you read something then you will find omega categoricity to be a more popular choice of name ok. Now, let us if we have defined something then let us give an example. So, the first example is that the theory of r vector spaces this is kappa categorical for all kappa bigger equal 2 to the aleph naught. I think you know the proof of this statement. So, can somebody spell it out for me what is a model of the theory of r vector spaces r vector space. So, 2 models of size kappa how are they determined sorry I should not say this I should say bigger 2 models of size kappa bigger than 2 to the See I am not talking about r and r square r and r square have the same cardinality yeah and are they isomorphic as vector spaces why different dimensions very good. So, dimension is the key whereas, if you go to infinite dimensional real vector spaces the dimension is simply a cardinal number and we know what that dimension has to be I mean you do you remember that we proved that real numbers must have or real numbers thought of as a rational vector space has uncountable basis you remember that ok. So, similarly if I am given an r vector space of cardinality kappa strictly bigger than 2 to the aleph naught then what will be the size of the basis you can show its kappa. So, therefore, any 2 vector spaces of cardinality kappa bigger than 2 to the aleph naught have basis of size kappa and any 2 sets with size kappa are in bijection. So, therefore, this is kappa categorical you can set up a nice bijection, but in the cardinality 2 to the aleph naught this is not true yeah because you already know there is real numbers then r square then r cube and r to the power 4 and so on so forth. Another thing you remember this and I am going to add a 0 yeah. So, this is the theory of algebraically closed fields with no multiplicative torsion element no nonzero multiplicative torsion element what do I mean by that that if a is not equal to 0 then that implies that a to the power n is not equal to 0 ok. So, this is what I mean. So, this is kappa categorical for all kappa bigger than aleph naught. So, all uncountable cardinalities this is kappa categorical. So, do you know any uncountable algebraically closed field satisfying this property real numbers real numbers are they algebraically closed because x square plus 1 equal to 0 does not have a root. So, they are not algebraically closed, but complex numbers are. So, complex numbers what is their cardinality 2 to the aleph naught. So, it is strictly bigger than aleph naught thanks to Cantor's theorem yeah. So, this one is also like complex numbers are the only algebraically closed fields of characteristic 0 that is the 0 is written as characteristic 0 in cardinality 2 to the aleph naught yeah very interesting statement. In fact, yeah and I will give you more examples, but at the same time we saw yesterday yeah, but gamma A C F 0 is not aleph naught categorical yeah because yesterday we saw this q bar h ok. Then I can also take yeah this is perhaps a bit too much for you, but if I take polynomials in with coefficients from q bar h and I take quotients of them. So, these are called rational functions a polynomial divided by another polynomial which is nonzero yeah. So, this is p x bar p x divided by q x where q x is not equal to 0 not identically 0 polynomial yeah. So, this is called the field of rational functions. So, this is another example of an algebraically closed field. Similarly, yeah I can always attach another variable and I can also say q bar h x 1 x 2 x n for any n variables. So, you take polynomials in n variables take their quotient rational functions and that is also an algebraically closed field ok. So, these are different algebraically closed fields they are not isomorphic because the number of variables is called the transcendence degree. So, the transcendence degree in this case is 0 in that case is 1 2 and n ok. So, transcendence degree is different. So, they cannot be isomorphic. So, this is not true. However, yeah and perhaps we should look at one most important example yeah the third one that is gamma DLO unbounded. So, this is Aleph naught categorical. Do you remember what was the first theorem that we proved in the class the very first theorem Cantor's theorem very good. So, this one is also due to Cantor ok. So, this is called Cantor isomorphism theorem. So, unbounded you understand yeah it does not have a least element it does not have a largest element ok. So, I am going to give you a sketch of the proof of this yeah I would not do it. So, suppose L 1 and L 2 are countable unbounded dense linear orders ok. So, it is a dense linear orders which are unbounded have this property that between any two distinct elements there is a third element below any element there is another element and after any element there is another element. So, these are the properties and these are countable that is given what does countability entail that there is a bijection with natural numbers. So, bijection with natural numbers means which means that we can list all the elements. So, let us list. So, L 1 I am going to list as a 0 a 1 a 2 a 3 and dot dot dot then L 2 I am going to list as b 0 b 1 b 2 b 3 and dot dot dot ok. Now, I am going to describe I am going to construct a bijection between these two the idea is called back and forth method this is a very interesting and useful technique in mathematics ok. So, it is like a ping pong ball match ok. So, back and forth method you first say that a 0 is mapped to b 0 then you look at the least index here that is not used what is that b 1 b 1 is not used. Now, you compare yeah this is the comparison part. So, either b 1 and b 0 what can happen either b 0 is less than b 1 or b 0 is bigger than b 1 ok. Now, if this happens if this happens then what I what do I where do I map to b 1 where do I map b 1 to. So, a 0 is mapped is paired with b 0 now b 1 is bigger. So, in this list I find the first element which is bigger than a 0 why does it exist because it is unbounded. So, suppose a 3 is the least index such that a 0 is less than a 3 then what will I do I will map b 1 to a 3. Now, one round of back and forth is done see first I mapped something from l 1 to l 2 second time I mapped something from l 2 to l 1. Now, I will again choose the least unused index what is that a 1 ok. Now, a 1 I am supposed to map somewhere, but I already have the configuration of chosen elements. Now, suppose a 0 and a 3 and a 1 now I have to look at where exactly a 1 lies. So, maybe it lies between these two or maybe it lies like this or maybe it lies like this whichever property for the first one I will have to use density of l 2 yeah by density of l 2 I can find an element between b 0 and b 1 and which has the least index. So, I will map it to that if the first one is true then I will use that it is unbounded below and for the last case I will use that it is unbounded above, but I will always find one element and by unbounded because we are ordering. So, this is well ordering I will always find the least b i with this property and then I can map let us say this one to this one and then again the ball is passed on to l 2 and then you complete this and you just have to argue that you have exhausted all the elements on both sides you understand. So, this will set up an order preserving bijection between two linear orders. So, this was the original argument of Cantor yeah that is why it is called Cantor isomorphism theorem. So, rational numbers are a dense linear order without end points. Similarly, any open interval 0 1 yeah this is isomorphic rational numbers and 0 1 are isomorphic I mean sorry I mean not this whole interval, but intersection with rational numbers the rational interval 0 1 rational interval 2 3 they are all isomorphic to rational numbers as a model of gamma DLO unbounded. On the other hand if you had one lower bound let us say it is bounded below, but unbounded above then you always map in this process the lower bound to lower bound and you continue with the process get it. And similarly if it is bounded on both sides then also you map lower bound to lower bound upper bound to upper bound and in between you just play the same game. So, there are four different theories which are categorical and if you remember washboard test it talked about something like categoricity implies completeness ok. So, we are going to start tomorrow with the proof of washboard test and will prove that this particular theory is complete. Similarly, this theory gamma SEF 0 is complete.