当前位置:天才代写 > 作业代写 > 数学逻辑代写 Exercise代写 lab代写 C++/C代写 Essay代写

数学逻辑代写 Exercise代写 lab代写 C++/C代写 Essay代写

2021-05-09 16:30 星期日 所属: 作业代写 浏览:51

数学逻辑代写

Mathematical Logic Final Solutions

数学逻辑代写 Use Soundedness Theorem for first-order logic to prove that T1 is independent of the other axioms, that isT2, T3 b T1, T2, T3 b ¬T1

XXX December 14th, 2019

Exercise 3

Use Soundedness Theorem for first-order logic to prove that T1 is independent of the other axioms, that is

T2, T3 b T1, T2, T3 b ¬T1

Proof. We first give an L-structure R such that R T2, T3 and R B T1. The universe is N w , where w is something other than a natural number. Let

S  be the successor function so that S(x) = x + 1, if x N and S(w) = w. Define the relation < by

<= {(a, b)|a, b R} ∪ {(w, w)}数学逻辑代写

It is  easy to  see that  R T2, T3 . Also R B T1 since w < w. Thus by  soundedness theorem, we have T2, T3 b T1.数学逻辑代写

Next we give another L-structure R such that R €  T2, T3  and R B  T1. Ther universe in this case is simply R, where < is given by the usual inequality and S  the successor function.  It follows that  R €  T2, T3   and R B   T1 as x < x for all x N. Thus by Soundedness theorem, we have T2, T3 b T1,

which completes the proof.

数学逻辑代写
数学逻辑代写

Exercise 4

Is T a consistent theory? Justify your answer.

Proof. T is a consistent theory. By completeness theorem it suffices to give a model R for this theory. The universe is the natural numbers N, with < the ususal strict inequality. S is the usual successor function, i.e., S(x) = x + 1 for x N. It is easy to see that all T1, T2, T3 are satisfied. Hence it is a consistent theory.数学逻辑代写

Exercise 5

Give a T -deduction of x[ Sx < Sx]. Give a full deduction. Name all the logical axioms and inference rules involved in the deduction.

Proof. First note that from T1, we know that x[ x < x]. Since Sx is substitutable for x, we apply Q1 and conclude that Sx < Sx. Now we have shown

x[¬x < x ¬Sx < Sx

We apply QR and conclude that x[¬Sx < Sx], which completes the proof.

Exercise 6 数学逻辑代写

Sketch a T -deduction of x[ Sx = x]. ame all the logical axioms and infer- ence rules involved in the deduction.

Proof. Note that

¬x < x (x < Sx) → ¬x = Sx

Here we are using T1 and T3 and the fact that the above statement is a tautology (one can use a Truth table to prove this). Hence we apply PC and QR and conclude that x[¬x Sx].

Exercise 7

Prove that any model for T is infinite.数学逻辑代写

Proof. Assume, on the contrary, that there is a finite model. Suppose the universe is some finite set. Let x be an element in this set. Note that by T3, we have x < Sx and Sx < S2x. Since the set is finite, there must exist j, i  N with i =ƒ j  such that Six Sjx.  Assume without loss of generality that i < j(here < means the usual order for natural numbers). By T2 andT3, we conclude that Six < Sjx. But since Six = Sjx, we have Six < Six, which contradicts Axiom T1. Therefore any model for T must be infinite.

Exercise 8

Prove that we have

R φ N0 φ

for any purely existential sentence φ.

Proof. Let φ be a purely existential sentence. By the inductive definition, one can prove inductively from N0 axioms that N0 € φ, hence N0 φ by completeness theorem.

Exercise 9 数学逻辑代写

Prove that

N0 b x[x <  (x = 0  x = 1  x = 2  x = 3  x = 4  x = 5)]

Proof. We  will give another LNT -structure R such that R € N0 but R B

x[x  <  6   (x  =  0  x  =  1  x  =  2  x  =  3  x  =  4  x  =  5).   The

universe is the set of all integers Z with usual addition and standard strict ordering of integers. It is clear that this model satisfy all N0 axioms, namely, R € N0(all purely existential properties that hold in natural numbers also

hold in integers).  However,  R x[x <  (x = 0  x = 1  x = 2  x = 3 x = 4 x = 5), since x can also be all negativer integers.

Exercise 10 数学逻辑代写

Do we have

N φ N0 φ

for any purely existential sentence? Justify your answer.数学逻辑代写

Proof. First suppose N φ for any purely existential sentence φ. By sound- edness theorem, we have R φ. Then by what we have proved in Problem 8, we have N0 φ.

Next we suppose that N0 φ. By soundedness theorem, we have N0 € φ. Since φ is purely existential, by N0 axioms we conclude that N φ. Finally, by completeness theorem, we must have N  φ, which completes the proof.

Exercise 11

Do we have

N φ N0 φ

for any Σ-sentence φ? Justify your answer.

Proof. This is not true. From Problem 9 we have

N0 b x[x <  (x = 0  x = 1  x = 2  x = 3  x = 4  x = 5)]

However it is easy to see that N   x[x <  (x = 0  x = 1  x = 2  x = 3 x = 4 x = 5)] by a standard N -deduction.

Exercise 12 数学逻辑代写

Does there exist an LNT -structure R such that R N and R B N0? Justify your answer.

Proof. Yes, there exists one. Let R be one LNT -structure whose universe is N w  ,  where w is an element other than natural numbers.  Addition is  the usual addition of numbers with a + w = w for all a N w . S is the sucessor function with  S(x) = x + 1 if x   N and S(w) = w.  The relation <  is defined by

<= {(a, b)|a, b N} ∪ {(a, w)|a N ∪ {w}}数学逻辑代写

It is easy to see that R N . However R B N0.  For  instance, w + 5 = in the usual standard structure, but nevertheless R w + 5 = w + 3

数学逻辑最终解决方案

XXX 2019年12月14日

练习3

使用Soundedness定理进行一阶逻辑证明T1独立于其他公理,即
T2,T3 b T1,T2,T3 b¬T1
证明。我们首先给出一个L结构R,使得R€T2,T3和R B T1。宇宙是N w,其中w是自然数以外的东西。让
S是后继函数,因此,如果x N和S(w)= w,则S(x)= x + 1。定义关系<由
<= {(a,b)| a,b∈R}∪{(w,w)}
很容易看到R€T2,T3。因为w <w,所以也是R B T1。因此,根据健全性定理,我们有T2,T3 b T1。
接下来,我们给出另一个L结构R,使得R€T2,T3和R B T1。在这种情况下,整个宇宙就是R,其中<由通常的不等式给出,S由后继函数给出。因此,对于所有x N,R€T2,T3和R B T1都为x <x。因此,根据听起来定理,我们有T2,T3 b T1,
这样就完成了证明。

练习4

T是一个一致的理论吗?证明你的答案。数学逻辑代写

证明。 T是一个一致的理论。通过完备性定理,足以为该理论给出模型R。宇宙是自然数N,通常小于严格不等式。 S是通常的后继函数,即对于x N,S(x)= x +1。很容易看出,所有T1,T2,T3都已满足。因此,这是一个一致的理论。

练习5

给出x [Sx <Sx]的T推论。进行全额扣除。列出推论中涉及的所有逻辑公理和推理规则。

证明。首先请注意,从T1开始,我们知道x [x <x]。由于Sx可以替代x,因此我们应用Q1并得出Sx <Sx的结论。现在我们已经显示
∀x[¬x<x]→¬Sx<Sx
我们应用QR并得出结论∀x[¬Sx<Sx],从而完成了证明。数学逻辑代写

练习6

画出x [Sx = x]的T推论。归纳到推论中涉及的所有逻辑公理和推论规则。

证明。注意

¬x<x∧(x <Sx)→¬x= Sx

在这里,我们使用T1和T3,并且上面的语句是一个重言式(可以使用Truth表来证明这一事实)。因此,我们应用PC和QR并得出结论∀x[¬x= Sx]。

练习7

证明T的任何模型都是无限的。

证明。相反,假设存在一个有限模型。假设宇宙是一个有限集。令x为该集合中的一个元素。请注意,到T3,我们有x <Sx和Sx <S2x。由于集合是有限的,因此必须存在
j,i∈N且i =ƒj使得Six = Sjx。在不失一般性的前提下,假设i <j(此处<表示自然数的通常顺序)。由T2和
T3,我们得出结论,六个<Sjx。但是由于6 = Sjx,所以我们有6 <6,这与Axiom T1相矛盾。因此,T的任何模型都必须是无限的。

练习8

证明我们有

R€φ→N0€φ

对于任何纯粹存在的句子φ。

证明。令φ是一个纯粹存在的句子。通过归纳定义,可以从N0公理来归纳证明N0€φ,因此根据完备性定理可以证明N0φ。数学逻辑代写

练习9

证明
N0 b∀x[x <6→(x = 0∨x = 1∨x = 2∨x = 3∨x = 4∨x = 5)] 证明。我们将给出另一个LNT结构R,使得R€N0但R B
x [x <6→(x = 0 x = 1 x = 2 x = 3 x = 4 x = 5)。这

Universe是所有整数Z的集合,并具有通常的加法和整数的标准严格排序。显然,该模型满足所有N0公理,即R€N0(所有在自然数中也存在的纯存在性
保持整数)。但是,R B x [x <6→(x = 0 x = 1 x = 2 x = 3 x = 4 x = 5),因为x也可以都是负整数。

练习10

我们是否有

N€φ⇔N0€φ

对于任何纯粹存在的句子?证明你的答案。

证明。首先,假设任何纯存在句子φ为Nφ。根据健全性定理,我们有R€φ。然后通过问题8中的证明,得到N0φ。数学逻辑代写
接下来,我们假设N0φ。根据健全定理,我们有N0€φ。由于φ是纯粹存在的,因此根据N0公理,我们得出N€φ。最后,根据完备性定理,我们必须有N€φ,从而完成了证明。

练习11

我们是否有

N€φ⇔N0€φ

对于任何Σ句φ?证明你的答案。

证明。这不是真的。从问题9我们有
N0 b∀x[x <6→(x = 0∨x = 1∨x = 2∨x = 3∨x = 4∨x = 5)] 然而,很容易看出,通过标准的N推导可以得出N€x [x <6→(x = 0 x = 1 x = 2 x = 3 x = 4 x = 5)]。

练习12

是否存在一个LNT结构R,使得R€N和R B N0?证明你的答案。数学逻辑代写

证明。是的,存在一个。令R为一个LNT结构,其宇宙为N w,其中w是自然数以外的元素。加法是通常对所有N w加上a + w =​​ w的数字的加法。如果x N和S(w)= w,则S是S(x)= x + 1的后继函数。关系<由以下项定义

<= {(a,b)| a,b∈N}∪{(a,w)| a∈N∪{w}}
很容易看到R€N。但是R B N0。例如,在通常的标准结构中,w + 5 =,但是R€w + 5 = w + 3

数学逻辑代写
数学逻辑代写

其他代写:algorithm代写 analysis代写 app代写 assembly代写 Haskell代写 homework代写 java代写 数学代写 考试助攻 web代写 program代写 cs作业代写 source code代写 finance代写 Exercise代写 essay代写 python代写

合作平台:essay代写 论文代写 写手招聘 英国留学生代写

 

天才代写-代写联系方式