公理化数学的公理化数学公理化起源于欧几里德公理化的要求 : 协调性, 即无矛盾性完备性喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

Size: px

Start display at page:

Download "公理化数学的公理化数学公理化起源于欧几里德公理化的要求 : 协调性, 即无矛盾性完备性喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28"

椰涕伊
7 years ago
Views:

1 可计算性与可判定性第三讲 : 模型论引论喻良南京大学现代数学研究所 October 30, 2013 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

2 公理化数学的公理化数学公理化起源于欧几里德公理化的要求 : 协调性, 即无矛盾性完备性喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

3 公理化协调性证明理论 T 协调性的方法 : 语法证明 ; 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

4 公理化协调性证明理论 T 协调性的方法 : 语法证明 ; 语义证明喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

5 模型论的概念什么是模型论模型论处理形式语言及其解释的关系喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

6 模型论的概念什么是模型论模型论处理形式语言及其解释的关系模型论研究特定结构的构造及分类喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

7 模型论的概念结构给定一个语言 L, 它的一个结构 (structure)m 包括 : 定义域 M; 常量 c M M; n- 元关系 R M M n ; m- 元函数 f M : M m M 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

8 模型论的概念结构给定一个语言 L, 它的一个结构 (structure)m 包括 : 定义域 M; 常量 c M M; n- 元关系 R M M n ; m- 元函数 f M : M m M 结构 M 的基数是指 M 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

9 模型论的概念子结构给定同一语言的两个结构 M, N, 我们称 M 是 N 的子结构, 记作 M N, 如果 M N 并且任何关系和函数在 M 的作用上一致喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

10 模型论的概念结构举例 (Z, +, 0) 是群语言的结构, 它是 (Q, +, 0) 的子群 ; (Z, +,, 0, 1) 是环语言的结构 ; (N, 0, 1, +,, <) 是算术语言的结构喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

11 模型论的概念指派指派是一个从变量到结构 M 的定义域的函数 s s 诱导了一个从项到 M 的函数 s(c) = c M ; s(v) = s(v); 如果 t = f(t 0, t 1,, t n ) 是一个项, 则 s(t) = f M (s(t 0 ), s(t 1 ),, s(t n )) 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

12 满足关系模型论的概念给定一个指派 s, 定义满足关系 (M, s) = φ(v) 如下 : φ(v) 是原子公式 : φ(v) 是 R( t), 则 (M, s) = φ(v) 如果 s(t) R M ; φ(v) 是 t 0 = t 1, 则 (M, s) = φ(v) 如果 s(t 0 ) = s(t 1 ); φ(v) 是 ψ, 则 (M, s) = φ(v) 如果 (M, s) = ψ; φ(v) 是 ψ 0 ψ 1, 则 (M, s) = φ(v) 如果 (M, s) = ψ 0 并且 (M, s) = ψ 1 ; φ(v) 是 ψ 0 ψ 1, 则 (M, s) = φ(v) 如果 (M, s) = ψ 0 或者 (M, s) = ψ 1 ; φ(v) 是 uψ(u, v), 则 (M, s) = φ(v) 如果存在指派 s 与 s 在 v 上一致使得 (M, s ) = ψ(u, v); φ(v) 是 uψ(u, v), 则 (M, s) = φ(v) 如果对于任何指派 s 与 s 在 v 上一致, (M, s ) = ψ(u, v); 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

13 指派的基本性质模型论的概念 Theorem 对于任何一个公式 φ(v), 如果 s 和 s 在 v 上一致, 则 (M, s) = φ(v) 当且仅当 (M, s ) = φ(v) Corollary 对于任何结构 M, 指派 s, s 以及句子 φ, (M, s) = φ 当且仅当 (M, s ) = φ 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

14 指派的基本性质模型论的概念 Theorem 对于任何一个公式 φ(v), 如果 s 和 s 在 v 上一致, 则 (M, s) = φ(v) 当且仅当 (M, s ) = φ(v) Corollary 对于任何结构 M, 指派 s, s 以及句子 φ, (M, s) = φ 当且仅当 (M, s ) = φ 因此对于句子 φ, 我们用 M = φ 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

15 模型论的概念举例 (Z, +, 0) 满足群论的所有公理 (Z, +,, 0, 1) 满足环论的所有公理喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

16 结构的关系模型论的概念 M 初等嵌入 ( f ) 于 N, 如果存在一个函数 f : M N 使得对于任何公式 φ( v) 以及 m M, M = φ( m) N = φ( f(m)) M 是 ( )N 的初等子模型, 如果 f 是恒等映射 M 同构 ( =) 于 N 如果 f 是双射 M 初等等价 ( ) 于 N 如果它们满足相同的语句喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

17 结构的关系模型论的概念 M 初等嵌入 ( f ) 于 N, 如果存在一个函数 f : M N 使得对于任何公式 φ( v) 以及 m M, M = φ( m) N = φ( f(m)) M 是 ( )N 的初等子模型, 如果 f 是恒等映射 M 同构 ( =) 于 N 如果 f 是双射 M 初等等价 ( ) 于 N 如果它们满足相同的语句 Theorem Ṃ = f N = M f N = M N 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

18 模型论的概念一些例子 (Z, +, 0) (Q, 0, +) 例如 φ : x y(y + y = x) (Q, +, 0) (R, +, 0) 但是 (Q, +, 0) = (R, +, 0) (Q, +,, 0, 1) (R, +,, 0, 1) 例如 φ : x y(y y = x y y = x) 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

19 理论的完备性理论的定义一个理论 T 是一个句子的集合喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

20 理论的完备性理论举例群论 T 包括群论的所有公理环论 T 包括环论的所有公理喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

21 理论的完备性皮亚诺算术 PA 是算术语言的理论, 它包括以下语句 : (1) x(x + 1 0); (2) x y(x + 1 = y + 1 x = y); (3) x(x + 0 = x); (4) x y(x (y + 1) = x y + x); (5) x y z(x < y x y x + z = y); (6 φ ) (φ(0) x(φ(x) φ(x + 1))) xφ(x) 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

22 完备理论理论的完备性一个理论 T 是完备的, 如果对于所有的句子 φ, 或者 T φ, 或者 T φ 一个协调的理论 T 是完备的当且仅当 {φ T φ} 是极大协调的 Theorem 任何协调的理论 T, 都存在一个协调的完备理论 T T 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

23 理论的完备性稠密无端点全序偏序语言 L = {<} 稠密无端点全序公理 DLP x( x < x); x y z(x < y y < z x < z); x y(x < y y < x x = y); x y z(x < y x < z < y); x y z(y < x < z) Theorem ḌLP 的所有可数模型都是同构的喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

24 完全性定理理论的完备性 Theorem (Godel 完全性定理 ) 一个理论 T 是协调的当且仅当它有模型 Proof 如果 T 有模型, 则按照证明长度进行归纳, 可以证明 T 是协调的如果 T 是协调的, 那么我们构造 T 的模型我们采用 Henkin 的方法首先假设语言 L 是可数的对语言 L 加可数个常量 {d i } i ω 扩张成语言 L 扩张 T 为 L 中的极大协调理论 T 1 使得对于每一个 L 公式 φ 存在一个 d i 使得 T 1 vφ φ(d i ) 定义 d i d j, 如果 T 1 d i = d j 那么{[d i ] i ω} 就是 T 的模型的定义域喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

25 几个应用理论的完备性 Theorem ( 紧致性定理 ) 一个理论 T 有模型当且仅当它每个有穷子集都有模型 T = φ 表示 T 的每一个模型都是 φ 的模型 Theorem 对于任何一个句子 φ, T = φ 当且仅当 T φ Theorem 如果 T 有一个无穷模型, 则对于任何基数 κ ℵ 0, T 都有基数为 κ 的模型 Theorem ḌLP 是完备的喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

26 PA 的非标准模型理论的完备性令 L 为算术语言将 L 加入常量 c 以及 { n n ω} 扩张成语言 L 令 PA = PA { n < n + 1 < c n ω} 因为 PA 的每个有穷子集都可满足, 因此由紧致性,PA 有一个可数模型 M 显然 M = N 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

27 定义可定义性可定义性 Definition 给定语言 L, 对应的结构 M 以及一个集合 X M 一个集合 A M n 称为 X- 可定义的, 如果存在一个公式 φ(v 1,, v n, v n+1,, v n+m ) 使得 A = {(a 1,, a n ) b 1 X b m XM = φ(a 1,, a n, b 1,, b m )} 如果 X =, 则 A 称为可定义的喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

28 可定义性几个例子偶数集合是 N 可定义的正整数集合 Z + 是 (Z, 0, 1, +, ) 可定义的 Z + = {x (Z, 0, 1, +, ) = x 0 y 0 y 1 y 2 y 3 (x = y 2 0+y 2 1+y 2 2+y 2 3)} 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

29 不可定义性 I 可定义性对于任何一个充分丰富的协调的集合理论 T, 没有一个公式 φ 使得对 T 所有的模型 M,(N, <) = ({m M = φ(m)}, ) 否则存在一个这样的公式 φ 扩充 L = L {c} { n n ω} 令 ψ n = n n + 1 c φ(c) 则 T {ψ n } n ω 是协调的, 因此存在 T 的一个模型 N = φ(c) 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

30 不可定义性 I 可定义性对于任何一个充分丰富的协调的集合理论 T, 没有一个公式 φ 使得对 T 所有的模型 M,(N, <) = ({m M = φ(m)}, ) 否则存在一个这样的公式 φ 扩充 L = L {c} { n n ω} 令 ψ n = n n + 1 c φ(c) 则 T {ψ n } n ω 是协调的, 因此存在 T 的一个模型 N = φ(c) 因此自然数, 进而有穷性, 没有一个绝对的定义喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

31 可定义性不可定义性 II Theorem 如果 M = f N 并且 A 是 X 可定义的, 则 f (A) 是 f (X) 可定义的 Corollary Ẓ + 是 (Z, <) 中 {0}- 可定义的但不是可定义的 Corollary 对于任何有穷集合 X, Z 不是 (Q, <) 中 X- 可定义的喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

32 可定义性模型论的一些其它结论 Theorem 如果一个可数语言的理论 T 有模型 M, 那么 T 必然有可数模型 N M Theorem 一个可数语言的理论 T 的可数模型或者可数多个, 或者 ℵ 1 个, 或者 2 ℵ 0 多个 Conjecture 一个可数语言的理论 T 的可数模型或者可数多个, 或者 2 ℵ 0 多个喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

33 可定义性阅读材料 1 model theory, CC Chang and J Keisler 2 model theory, W Hodges 3 model theory,d Marker 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

34 习题可定义性 1 证明如果 (ω, <) M, 那么存在一个 f : ω M 使得 (ω, <) f M 2 证明存在 DLP 的不可数模型 M = N 但是 M = N = ℵ 1 3 如果理论 T 有任意大的有穷模型, 则 T 必然有一个无穷的模型 4 如果 M 是一个无穷模型并且 κ M, 那么存在一个基数为 κ 的模型 N M 5 证明 ``<"- 关系是 (Z, 0, 1, +, ) 中可定义的但在 (Z, 0, 1, +) 中不是可定义的喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

数理逻辑

数理逻辑杨睿之复旦大学哲学学院 2018 年秋季前情提要前情提要定理 ( 前束范式定理 ) 对任何公式 α 都存在量词前束公式 α ( 形如 Q 1 x 1 Q n x n β), 使得 α α 前情提要定理 ( 前束范式定理 ) 对任何公式 α 都存在量词前束公式 α ( 形如 Q 1 x 1 Q n x n β), 使得 α α 前情提要证明前束范式定理用到的元定理 Q1a xα x

公理化 数学的公理化 数学公理化起源于欧几里德 公理化的要求 : 协调性, 即无矛盾性 完备性 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28

公理化数学的公理化数学公理化起源于欧几里德公理化的要求 : 协调性, 即无矛盾性完备性喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, / 28