FoundationsofLogic (7).pdf
《FoundationsofLogic (7).pdf》由会员分享,可在线阅读,更多相关《FoundationsofLogic (7).pdf(30页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FoundationsofLogic 7
限制150内