可计算性与可判定性 第三讲 : 模型论引论 喻良 南京大学现代数学研究所 October 30, 2013 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 1 / 28
公理化 数学的公理化 数学公理化起源于欧几里德 公理化的要求 : 协调性, 即无矛盾性 完备性 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 2 / 28
公理化 协调性 证明理论 T 协调性的方法 : 语法证明 ; 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 3 / 28
公理化 协调性 证明理论 T 协调性的方法 : 语法证明 ; 语义证明 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 3 / 28
模型论的概念 什么是模型论 模型论处理形式语言及其解释的关系 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 4 / 28
模型论的概念 什么是模型论 模型论处理形式语言及其解释的关系 模型论研究特定结构的构造及分类 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 4 / 28
模型论的概念 结构 给定一个语言 L, 它的一个结构 (structure)m 包括 : 定义域 M; 常量 c M M; n- 元关系 R M M n ; m- 元函数 f M : M m M 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 5 / 28
模型论的概念 结构 给定一个语言 L, 它的一个结构 (structure)m 包括 : 定义域 M; 常量 c M M; n- 元关系 R M M n ; m- 元函数 f M : M m M 结构 M 的基数是指 M 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 5 / 28
模型论的概念 子结构 给定同一语言的两个结构 M, N, 我们称 M 是 N 的子结构, 记作 M N, 如果 M N 并且任何关系和函数在 M 的作用上一致 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 6 / 28
模型论的概念 结构举例 (Z, +, 0) 是群语言的结构, 它是 (Q, +, 0) 的子群 ; (Z, +,, 0, 1) 是环语言的结构 ; (N, 0, 1, +,, <) 是算术语言的结构 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 7 / 28
模型论的概念 指派 指派是一个从变量到结构 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, 2013 8 / 28
满足关系 模型论的概念 给定一个指派 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, 2013 9 / 28
指派的基本性质 模型论的概念 Theorem 对于任何一个公式 φ(v), 如果 s 和 s 在 v 上一致, 则 (M, s) = φ(v) 当且仅当 (M, s ) = φ(v) Corollary 对于任何结构 M, 指派 s, s 以及句子 φ, (M, s) = φ 当且仅当 (M, s ) = φ 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 10 / 28
指派的基本性质 模型论的概念 Theorem 对于任何一个公式 φ(v), 如果 s 和 s 在 v 上一致, 则 (M, s) = φ(v) 当且仅当 (M, s ) = φ(v) Corollary 对于任何结构 M, 指派 s, s 以及句子 φ, (M, s) = φ 当且仅当 (M, s ) = φ 因此对于句子 φ, 我们用 M = φ 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 10 / 28
模型论的概念 举例 (Z, +, 0) 满足群论的所有公理 (Z, +,, 0, 1) 满足环论的所有公理 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 11 / 28
结构的关系 模型论的概念 M 初等嵌入 ( f ) 于 N, 如果存在一个函数 f : M N 使得对于任何公式 φ( v) 以及 m M, M = φ( m) N = φ( f(m)) M 是 ( )N 的初等子模型, 如果 f 是恒等映射 M 同构 ( =) 于 N 如果 f 是双射 M 初等等价 ( ) 于 N 如果它们满足相同的语句 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 12 / 28
结构的关系 模型论的概念 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, 2013 12 / 28
模型论的概念 一些例子 (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, 2013 13 / 28
理论的完备性 理论的定义 一个理论 T 是一个句子的集合 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 14 / 28
理论的完备性 理论举例 群论 T 包括群论的所有公理 环论 T 包括环论的所有公理 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 15 / 28
理论的完备性 皮亚诺算术 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, 2013 16 / 28
完备理论 理论的完备性 一个理论 T 是完备的, 如果对于所有的句子 φ, 或者 T φ, 或者 T φ 一个协调的理论 T 是完备的当且仅当 {φ T φ} 是极大协调的 Theorem 任何协调的理论 T, 都存在一个协调的完备理论 T T 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 17 / 28
理论的完备性 稠密无端点全序 偏序语言 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, 2013 18 / 28
完全性定理 理论的完备性 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, 2013 19 / 28
几个应用 理论的完备性 Theorem ( 紧致性定理 ) 一个理论 T 有模型当且仅当它每个有穷子集都有模型 T = φ 表示 T 的每一个模型都是 φ 的模型 Theorem 对于任何一个句子 φ, T = φ 当且仅当 T φ Theorem 如果 T 有一个无穷模型, 则对于任何基数 κ ℵ 0, T 都有基数为 κ 的 模型 Theorem ḌLP 是完备的 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 20 / 28
PA 的非标准模型 理论的完备性 令 L 为算术语言 将 L 加入常量 c 以及 { n n ω} 扩张成语言 L 令 PA = PA { n < n + 1 < c n ω} 因为 PA 的每个有穷子集都可满足, 因此由紧致性,PA 有一个可数模型 M 显然 M = N 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 21 / 28
定义可定义性 可定义性 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, 2013 22 / 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, 2013 23 / 28
不可定义性 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, 2013 24 / 28
不可定义性 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, 2013 24 / 28
可定义性 不可定义性 II Theorem 如果 M = f N 并且 A 是 X 可定义的, 则 f (A) 是 f (X) 可定义的 Corollary Ẓ + 是 (Z, <) 中 {0}- 可定义的但不是可定义的 Corollary 对于任何有穷集合 X, Z 不是 (Q, <) 中 X- 可定义的 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 25 / 28
可定义性 模型论的一些其它结论 Theorem 如果一个可数语言的理论 T 有模型 M, 那么 T 必然有可数模 型 N M Theorem 一个可数语言的理论 T 的可数模型或者可数多个, 或者 ℵ 1 个, 或者 2 ℵ 0 多个 Conjecture 一个可数语言的理论 T 的可数模型或者可数多个, 或者 2 ℵ 0 多个 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 26 / 28
可定义性 阅读材料 1 model theory, CC Chang and J Keisler 2 model theory, W Hodges 3 model theory,d Marker 喻良 ( 南京大学现代数学研究所 ) 可计算性与可判定性 October 30, 2013 27 / 28
习题 可定义性 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, 2013 28 / 28