数理逻辑 (3) 模型论初步.

Presentation on theme: "数理逻辑 (3) 模型论初步."— Presentation transcript:

1 数理逻辑 (3) 模型论初步

2 公理系统 一个公理系统首先必须具备的性质是协调性，即无矛盾。 最好具有完备性。
自明性不再像欧式几何那样是必须的。但是数学柏拉图主义决定了公理系统必须有“意义”。

3 希尔伯特 德国 欧式几何的公理化。

4 皮亚诺 意大利 皮亚诺算术公理系统(PA): ∀n(n+1≠0) ∀n∀m(m+1=n+1→m=n) ∀m(m+0=m) ∀m(m0=0) ∀n∀m(m(n+1)=(mn)+m) ∀n(n⊀ 0) ∀m∀n(m<n+1→(m<n∨ m=n)) (φ(0) ∧ ∀ n(φ(n) →φ(n+1))) →∀ nφ(n)。

5 协调性的证明 一个理论T是指一个句子的集合。 T是协调的(consistent)，如果没有句子φ使得 T┠φ∧¬φ。 T是完全的(complete)，如果它是极大的协调理论。 证明理论T协调性的方法:(1)模型论。(2)证明T是不完 备的。

6 语言的结构 给定一个语言L，它的一个结构M=（M，…)包含一个定义域(Domain)M，并且所有常量，谓词，函数作用在这个定义域上。
（Z,+,0）就是群论语言的一个结构。 (N, +,,<,0,1)就是算术语言的一个结构。

7 指派 给定一个语言L和它的一个结构M=（M，…）。 一个指派(assignment)是一个从变量集到M的函数s。
有了指派，则每一个项t都有一个值s(t)。 在一个指派s下，我们可以归纳地定义满足关系Mㅑ ϕ[s]。 Mㅑt[s]=t’[s]如果s(t)=s(t’)。 MㅑR(u_0,u_1,…u_n)[s]如果u_0[s],u_1[s],…u_n[s] ∈RM。 Mㅑ¬ϕ[s]如果¬Mㅑϕ[s]。 Mㅑφ∨ψ[s]如果Mㅑφ[s]或者Mㅑψ [s]。 Mㅑφ∧ψ[s]如果Mㅑφ[s]并且Mㅑψ [s]。 Mㅑxϕ[s]如果对每一个d∈M,我们让新指派s’（x）=d但是s’对于其它变量的值与s相同，则Mㅑϕ[s’]。 Mㅑxϕ[s]如果存在一个d∈M,我们让新指派s’（x）=d但是s’对于其它变量的值与s相同，则Mㅑϕ[s’]。

8 理论的模型 定理：对于一个句子ϕ以及任意的指派s,s’,Mㅑ ϕ[s] 当切仅当 Mㅑ ϕ[s’]。 因此句子的满足关系不依赖于指派。 对于一个句子ϕ,我们可以定义Mㅑ ϕ。 一个理论T，MㅑT,如果对于T中每一个句子ϕ，Mㅑ ϕ。 M称为T的一个模型. T是可满足的，如果T有一个模型。

9 哥德尔 1906-1978,奥地利 歌德尔完备性定理：T是可满足的当切仅当T是协调的。 证明：φ┠ψ并且Mㅑφ， 则Mㅑψ。
因此可满足性蕴含协调性。 协调性蕴含可满足性：韩钦(Henkin)常量法。

10 一个重要推论 Tㅑ ϕ 如果 T的每一个模型都是ϕ的一个模型。 推论：Tㅑ ϕ当且仅当 T┠ϕ。
证明：如果T┠ϕ,则存在X有穷子集Y使得∧ψ∈Yψ ┠ϕ。因此Tㅑ ϕ。 如果T不证明ϕ，则T与¬ϕ是协调的，因此由完备性定理，T∪｛¬ϕ｝存在模型。 QED

11 紧致性定理 紧致性定理：T是可满足的当切仅当它的每一个有穷子集都是可满足的。 证明：歌德尔完备性定理的直接推论。 QED
证明：对于任何无穷基数κ, T∪{cα≠ cβ｜α≠β<κ}是可满足的。 QED 因此一个理论不可能完全决定它的模型。

12 几个例子 PA的任何模型必然包含所有自然数。 PA的模型可以任意大。 PA的非标准模型。 PA∪{0<c,1<c,…}。

13 子模型 给定同一语言的两个结构M=（M，…)和N=（N，…)， 记为M⊆N，如果M⊆N，并且M所有的谓词，函数限制 在N上都与N中的对应谓词，函数一致，则M称为N的 子模型。 如果M⊆N并且对于所有公式ϕ(v0, v1,…)以及M中所有元 素a0, a1,…, Mㅑϕ(a0, a1,…)当且仅当Nㅑϕ(a0, a1,…),则M称为N的初等子模型,记为M≺N。

14 模型的关系 给定同一语言的两个结构M=（M，…)和N=（N，…)，记为M≡ N，如果对于所有句子ϕ， Mㅑϕ当且仅当Nㅑϕ，则称M与N初等等价。 如果存在一个双射函数f:M->N使得对于所有公式ϕ(v0, v1,…)以及M中所有元素a0, a1,…, Mㅑϕ(a0, a1,…)当且仅当Nㅑϕ(f(a0),f(a1)…),则称M与N同构，记为M≅N。 显然M≺N和M≅N蕴含M≡ N。

15 几个例子 （Z,+,0）是（Q,+,0）的子模型。 （Q,+,，0,1）是（R,+,，0,1）的子模型。
但是他们都不是初等子模型。考虑 yx(x+x=y) 以及 x(xx=1+1) 。 (ω,<) ≡（ω∪{½},<）但是(ω,<)不是（ω∪{½},<）的初等子模型。 （Q,+,0）是（R,+,0）的初等子模型。因此（R,+,0）≡（Q,+,0）但是不同构。

16 可定义性 给定一个语言的结构M=（M，…)，一个集合A⊆M是可定义的，如果存 在一个公式ϕ以及a∈M使得对于所有的m∈M, m∈A当且仅当Mㅑ ϕ(m,a)。 定理：如果A⊆M是无参数可定义的并且f是M的一个自同构，则f(A)=A。 对于任何可数语言的无穷结构M=（M，…)，M必然存在一个不可定义的 子集。 自然数集合在整数环中是可定义的但在整数群中不可定义。

17 斯科伦 挪威 给定一个结构M，φ（u,v）的斯科伦函数是一个函数f 使得Mㅑ∀u(vφ（u,v）↔φ（u,f(u)）)。 斯科伦定理：如果｜L｜＝κ，M是L的一个结构并且 X⊆M，则有一个N≺M使得X⊆N并且｜N｜≤κ+|X|+ℵ0。

18 斯科伦悖论 斯科伦悖论：如果集合论是协调的，则集合论有一个可 数模型。

19 习题 如果M是PA的一个非标准模型并且对于所有的自然数n, Mㅑϕ(n), 则存在一个非标准自然数c∈ M使得Mㅑ ϕ(c)。
对于任何无穷结构M以及任意基数κ>｜M｜，存在一 个结构N，使得|N|=κ并且M≺N。 证明对于整数环（Z,+,,0,1)，每一个公式φ（u,v） 都有一个可定义的斯科伦函数。

20 阅读材料 《Model Theory》, David Marker
《Model Theory》, C.C. Chang and Jerome. Keisler 《Model Theory》, Wilfrid Hodges