资源描述：
《高等数理逻辑作业答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、高等数理逻辑作业无限集合初步ò写出集合论公理的一阶描述.解答外延公理:]xy(]z(zJx?zJy)>x=y)空集公理:^x]y(yJ/x).偶对公理:]xy^u]z(zJu?z=xZz=y).全部并集公理:]x^u]y(yJu?(^z(zJx[yJz))).子集公理:]x,l,x]x^y]z(zJy?zJx[9).1n幂集公理:]x^y(]z(zJy?zNx)).无穷公理:^x(IJx[(]y(yJx>y+Jx))).替换公理:]x,l,x]x(<>^y]z(zJy?^uJx9[u,z])).1n正规公理:]x(
2、x=/I>^y(yJx[yQx=I)).选择公理：]x(x=/I>^y(9[9)).12□ò证明:可数符号表上有限长字符串集合是可数的.证明假设给定的可数符号表是集合A,则ô长度是的字符串的集合1S=A.1ô长度是的字符串的集合2S={ab
3、a,bJA}.2lô每个S都是可数集合,这可数个可数集合的并集是可数的.n□ò证明:.R.R#R证明可以仅考虑开区间(0,1)内的实数,证明(0,1)#(0,1).(0,1).可以按照以下方式构造双射:对于以下两个实数:u=0$aaal012v=0$bbbl012对应于以下实数
4、:w=0$abababl001122□公理集合论初步ò空集是函数.证明a是一个函数,当且仅当以下性质成立:9[9.12其中ô9是公式]x(xJa>^uv(x=)).1ô9是公式]uvw(Ja[Ja>v=w).2I是一个函数.这是因为:在上述定义中,两个蕴涵式xJa>^uv(x=),Ja[Ja>v=w的前提不成立.□ò对于集合xy及,则它们的交集是集合.证明a-b={x
5、xJa[xJ/b}.这个集合是存在的,是由子集公理保证的:a-b={xJa
6、xJ/b}.
7、相应的集合是、一阶公式是axJ/b.□ò对于集合xy及,它们的卡氏积x#y={
8、uJx,vJy}是集合.证明对于集合及,乘积aba#b的存在性可以由子集公理保证:a#b={w
9、wJc[9(w)}.其中:ôc是集合:3(3(x)P3(aPb)).ô9(w)是公式:^uv(uJa[vJb[w=).□ò假设A,B是两个集合,存在A到B的满射.证明:存在B到A的单射.证明假设f:A>BB是满射,则可以定义到A的映射:g对每个yJB,考虑集合f-1({y})={xJA
10、f(x)=y},ff-1({y})x
11、Jf-1({y})y因为是满射,所以不是空集,任取作为的象,则可以定义BA到的映射.ggy-1({y})Qf-1({y})=I是单射,这是因为当=y/JB时,f,所以1212g(y)=g(y/).12□公理集合论及自然数理论初步ò证明:存在无限集合{0,{1},{{2}},{{{3}}},l}.证明定义以下公式)(x,y):(x=0>y=x)[(x=0>^f(9[9[y=f(x)))12其中9func(f)[0Jdom(f)[f(0)=x[dom(f)=x+ô是公式:.19]u(uJdom(f)[u+Jdom(f
12、)>f(u+)={f(u)})ô是公式:.2对任意的nJ=,存在唯一一个函数满足f9[n][9.12由此可知,对任意的nJ=,存在唯一的使得a)[n,a].根据替换公理,可知存在集合.={a
13、^n(nJ=[)[n,a])}.这时0,{1},{{2}},{{{3}}},lJ..□]mn(mJ=[nJ=[m+=n+>m=n).ò证明:证明m,nm+=n+假设是两个自然数,满足,这时,根据定义可知:mP{m}=nP{n}.若m=n/,则ô从mJmP{m}可知mJnP{n},因而mJn.ô从nJnP{n}可知nJmP{m}
14、,因而nJm.这时集合x={m,n}不满足正规公理:x=/I>^y(yJx[yQx=I).这个矛盾表明m=n.□命题逻辑的可靠性证明命题逻辑具有可靠性.证明如下定义公理系统:ò公理:ô9:A>(B>A).1ô9:(A>(B>C))>((A>B)>(A>C)).2ô9:(A>B)>((A>B)>A).3ò规则:!A,A!!!!!!!!>!!!!!B!!!.B定义DUC为:存在公式序列使得12nò或者AJ>;iò或者A是公理;iò或者存在j,kA.kji且A是C.n这时,对任意
15、的赋值,都有vv(9)=1,v(9)=1v(9)=1.123同时当v(A)=1且v(A>B)=1,时,v(B)=1.所以若DUC,则DXC.这是命题逻辑的可靠性质.如下定义公理系统:ò公理:AUA.ò规则:!!!!D!!!!U!!!A!!!!!!!ô.单调性D,DdUA!D!!!!,!!!!!A!!!U!!!!B!!!!且!!!!!D!!!,!!!!!!
