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

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

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

## Mathematical Logic Final Solutions

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

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 φ

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 φ

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日

T2，T3 b T1，T2，T3 b¬T1

S是后继函数，因此，如果x N和S（w）= w，则S（x）= x + 1。定义关系<由
<= {（a，b）| a，b∈R}∪{（w，w）}

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

∀x[¬x<x]→¬Sx<Sx

¬x<x∧（x <Sx）→¬x= Sx

j，i∈N且i =ƒj使得Six = Sjx。在不失一般性的前提下，假设i <j（此处<表示自然数的通常顺序）。由T2和
T3，我们得出结论，六个<Sjx。但是由于6 = Sjx，所以我们有6 <6，这与Axiom T1相矛盾。因此，T的任何模型都必须是无限的。

R€φ→N0€φ

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（所有在自然数中也存在的纯存在性

N€φ⇔N0€φ

N€φ⇔N0€φ

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）]。

<= {（a，b）| a，b∈N}∪{（a，w）| a∈N∪{w}}