《FoundationsofLogic (7).pdf》由会员分享，可在线阅读，更多相关《FoundationsofLogic (7).pdf（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsOnline Course:Foundations of LogicDag Westerst ahlTsinghua LogicModels as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsThis is a first part of Chapter 6We now think of models(interp
2、retations of FOL)asmathematical structures that can be studied in their ownright.Their connection to FOL is the truth relation.M|=Two kinds of questions are then natural:IGiven M,what sentences are true in M?IGiven (or),what models does it have?These are questions about the expressive power of FOL.1
3、 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsModels as structuresLet(N,)be an ordered set.That is,a set N and a binary relation on N which is reflexive,transitive,anti-symmetric(a b and b a implies a=b),andlinear(for all a,b N,a b or b a).N=(N,)can be
4、seen as a model for the vocabulary L=R,where R is a binary predicate symbol.And the properties of N canbe expressed in FOL.Let LO be the set of these sentences:xRxxxyz(Rxy Ryz Rxz)xy(Rxy Ryx x=y)xy(Rxy Ryx)Then,for any model M=(M,S)for L:M|=LO iffM is anordered set.That is,the property of being an o
5、rdered set isexpressible in FOL.2 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsExamples of ordered setsOrdered sets models of LO are easy to visualize:This is a discrete order:every element has a unique successor(asmallest among those that are greater).
6、This is a dense order:between two elements there is always a third.3 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsModels as structures,cont.Similarly for the property of being(a set with an)equivalencerelation:reflexive,symmetric,transitive.Let Eq be th
7、e set ofthe following sentences:xRxxxy(Rxy Ryx)xyz(Rxy Ryz Rxz)Then(M,E)|=Eq iffE is an equivalence relation on M.So this property is also expressible.4 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsNumerical statementsIn FOL we can easily say that a set
8、 A has at least two elements:xy(Ax Ay x 6=y)Similarly,let nx(x)abbreviate a sentence that says that at leastn things have the property:nx(x):=Thus:nx(x):=nx(x):=5 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsNumerical quantifiersFor example,to say“The d
9、omain has exactly 100 elements”,you can use the sentenceThis abbreviates a very long FOL-sentence.An alternative would be to treat netc.as new quantifiers(for all n 1),with the obvious meaning.This can be practical in some contexts,but doesnt changethe expressive power.6 of 29Models as structuresNum
10、erical statementsEquivalence relationsIsomorphic modelsFunctionsNotation for equivalence relationsAs we saw,models of Eq(for the vocabulary L=R)are sets withequivalence relations.For simplicity,we will write such a modelM=(M,E)where E is an equivalence relation on M,and we will use the samebinary pr
11、edicate symbol E,with infix notation,in the formallanguage.SoEq=x xEx,xy(xEy yEx),xyz(xEy yEz xEz)What kind of equivalence relations are there,and can we classifythem in some way?This is a typical model-theoretic question:What are the modelsof Eq?7 of 29Models as structuresNumerical statementsEquiva
12、lence relationsIsomorphic modelsFunctionsPartitionsIf E is an equivalence relation on M,recall that for each a M|a|E=b M:aEbis the equivalence class of a.The equivalence classes partition M inthe following sense:Ieach equivalence class is non-empty(since a|a|E);Idistinct equivalence classes are disj
13、oint(if not aEb,then|a|E|b|E=);Ithe union of all the equivalence classes is MIn general,any class of non-empty pairwise disjoint subsets of Mwhose union is M is called a partition of M.In a picture:8 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsPartitio
14、ns and equivalence relationsFactIf E is an equivalence relation on M,then the set of equivalenceclasses is a partition of M.Conversely,every partition of Mcorresponds to a unique equivalence relation on M.9 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsC
15、lassifying equivalence relationsWe can classify equivalence relations byIthe number of equivalence classes;Ithe number of elements in the equivalence classes.This sentence says“there are at least three equivalence classes”:(E3)xyz(xEy yEz xEz)Similarly for E3(n=1,2,.).10 of 29Models as structuresNum
16、erical statementsEquivalence relationsIsomorphic modelsFunctionsThe number of equivalence classes“There are exactly three equivalence classes”:(E=3)xyz(xEy yEz xEz u(uEx uEy uEz)Consider the following set of sentences:=E1,E2,E3,.says“There are infinitely many equivalence classes”.That is,if(M,E)is a
17、 model of Eq,then(M,E)|=iffE is an equivalence relation with infinitelymany equivalence classes11 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsThe size of equivalence classes 1The identity relation is the smallest equivalence relation on M:aEb iffa=bSo
18、for all a M,|a|=aAs many equivalence classes as elements of M,each with size 1.The universal relation is the largest equivalence relation on M:forall a,b M,aEb.Just one equivalence class:M itself.This relation makes as few distinctions as possible(i.e.nodistinctions!),whereas the identity relation m
19、akes as manydistinctions as possible.All other equivalence relations are in between.12 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsThe size of equivalence classes 2We can use numerical quantifiers to count the number of elementsin equivalence classes.E
20、.g.:(M,E)|=7y xEy a iff|a|Ehas at most 7 elementsNow lets say:“There are(exactly)three equivalence classes,twowith one element,and one with three elements”:13 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsIsomorphic equivalence relationsConsider these tw
21、o equivalence relations(partitions),one withdomain 1,2,3,4,5 and the other with domain 6,7,8,9,10:We can express how many equivalence relations there are,and howmany elements in each class.But no FOL-sentence can distinguish(M1,E1)from(M2,E2).They are isomorphic.14 of 29Models as structuresNumerical
22、 statementsEquivalence relationsIsomorphic modelsFunctionsIsomorphic modelsInformally,(M1,E1)and(M2,E2)are isomorphic because(a)theirdomains have the same size,and(b)the two models have the samestructure.Formally,if M and M0are models for the same vocabulary L:DefinitionM is isomorphic to M0,in symb
23、ols,M=M0if there is a one-one function h from M onto M0(a bijection)such thatfor all a1,.,an M,(a)if c L,then h(cM)=cM0(b)if PL is n-ary then PM(a1,.,an)PM0(h(a1),.,h(an)(c)if f L is n-ary then h(fM(a1,.,an)=fM0(h(a1),.,h(an)15 of 29Models as structuresNumerical statementsEquivalence relationsIsomor
24、phic modelsFunctionsRecap about functions(see Chapter 16)Let A and B be sets.A function f from A to B maps every element a inA to an element f(a)in B.We writef:A BFunctions can be seen as a special kind of relations:R(a,b)f(a)=b.Then the characteristic property of a functional relation R isIf R(a,b)
25、and R(a,b0),then b=b0.16 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsDomain and range of a functionLet f:A B.dom(f)=a A:b B f(a)=b=Arange(f)=b B:a A f(a)=b B17 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctions
26、Domain and range of a functionLet f:A B.f is one-one,or an injection,if a 6=a0implies f(a)6=f(a0).f is onto,or a surjection,if b B a A s.t.f(a)=b,that is,ifrange(f)=B.f is a one-one correspondence,or a bijection,if it is one-one andonto.Thats what we require of isomorphisms.18 of 29Models as structu
27、resNumerical statementsEquivalence relationsIsomorphic modelsFunctionsBijections and numberRecall that if A is a set,|A|is the cardinality of A,i.e.the number of elements in A.We have:(1)|A|=|B|iffthere is a bijection from A to B.(2)|A|B|iffthere is an injection from A to B.This is a fact about fini
28、te cardinalities,and true by definition of infinitecardinalities.So if M=M0,then|M|=|M0|.Let N=0,1,2,.Terminology:|N|=0=.0is the smallestinfinite cardinal number.A is countable iff|A|0iff|A|is a finite number or|A|=0.19 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic mod
29、elsFunctionsBack to equivalence relations20 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsThe Isomorphism LemmaHere is a fundamental fact:Sentences in logical languages do notdistinguish isomorphic models.Thus,in FOL:(1)If M=M0,then for every L-sentence:
30、M|=iffM0|=.We want to prove(1)by induction,but as usual this doesnt workfor sentences,so we prove a more general fact for formulas:Lemma(Isomorphism Lemma)If h is an isomorphism from M to M0(written h:M=M0),(x1,.,xn)is an L-formula,and a1,.,an M,thenM|=(x1,.,xn)a1,.,an iffM0|=(x1,.,xn)h(a1),.,h(an)P
31、roof.See Chapter 6.4.1.21 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsHow many models?One consequence of the Isomorphism Lemma is that thequestionHow many models does a sentence,or a set of sentences,have?makes no sense!Instead,a question that makes(a
32、lot of)sense is:How many non-isomorphic models does,or,have?This is another typical model-theoretic question.We will see some answers soon.22 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctions(Non-)isomorphic orders23 of 29Models as structuresNumerical state
33、mentsEquivalence relationsIsomorphic modelsFunctionsIsomorphic equivalence relationsWe consider countable models of Eq,i.e.equivalence relations(M,E)where M is countable;|M|.Up to isomorphism,(M,E)is completely characterized by(a)thenumber of equivalence classes,and(b)the number of elements ineach e
34、quivalence class.We can present this information as a list,the signature of(M,E):M=(M0,M1,M2,.)whereM0is the number of equivalence classes with elements;M1is the number of equivalence classes with 1 element;M2is the number of equivalence classes with 2 elements;etc.24 of 29Models as structuresNumeri
35、cal statementsEquivalence relationsIsomorphic modelsFunctionsSignatures of equivalence relations:examplesSuppose(M,E)|=Eq and M has 5 elements;we write this|M|=5(for any set X,|X|is the cardinality of X)What are the signatures of the identity relation,the universalrelation,and the equivalence relati
36、on in our earlier example?25 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsFactTwo countable equivalence relations(models of Eq)are isomorphiciffthey have the same signature.Proof.26 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctionsNext Thursday:The rest of Chapter 627 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctions28 of 29Models as structuresNumerical statementsEquivalence relationsIsomorphic modelsFunctions29 of 29