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 < 6 → (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 B ∀x[x < 6 → (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 < 6 → (x = 0 ∨ x = 1 ∨ x = 2 ∨ x = 3 ∨ x = 4 ∨ x = 5)]
However it is easy to see that N € ∀x[x < 6 → (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代写
