数理逻辑

Size: px

Start display at page:

Download "数理逻辑"

矩全
5 years ago
Views:

1 数理逻辑杨睿之复旦大学哲学学院 2018 年秋季

2 前情提要

3 前情提要定理 ( 前束范式定理 ) 对任何公式 α 都存在量词前束公式 α ( 形如 Q 1 x 1 Q n x n β), 使得 α α

4 前情提要定理 ( 前束范式定理 ) 对任何公式 α 都存在量词前束公式 α ( 形如 Q 1 x 1 Q n x n β), 使得 α α

5 前情提要证明前束范式定理用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

6 前情提要一阶逻辑的语义语言 L 中参数符号的语义 L 结构自由变元的语义赋值 s : V A 项的语义由 A 和 s 唯一决定的 s : T L A 公式的语义满足关系 :(A, s) φ

7 前情提要合同引理记法 : φ(x 1,, x n ) A φ[d 1,, d n ] 闭语句与真 :A σ, A Σ 此时, 我们称 A 是 σ( 或 Σ) 的模型逻辑蕴含 :Γ φ, α β

8 可定义性

9 Berry paradox the smallest positive integer not definable in fewer than twelve words

10 Berry paradox the smallest positive integer not definable in fewer than twelve words

11 结构内的可定义性定义给定语言 L,L- 结构 A 以及 L 中公式 φ(x 1,, x k ), 我们称 φ 在结构 A 中定义了 ( A 上的 )k- 元关系 R, 当且仅当 R = { (a 1,, a k ) A k A φ[a1,, a k ] } 我们称一个 k- 元关系 R A k 是 L 结构 A 中可定义的, 当且仅当存在一个 L 公式在结构 A 中定义它

12 结构内的可定义性定义给定语言 L,L- 结构 A 以及 L 中公式 φ(x 1,, x k ), 我们称 φ 在结构 A 中定义了 ( A 上的 )k- 元关系 R, 当且仅当 R = { (a 1,, a k ) A k A φ[a1,, a k ] } 我们称一个 k- 元关系 R A k 是 L 结构 A 中可定义的, 当且仅当存在一个 L 公式在结构 A 中定义它

13 结构内的可定义性例考虑只含有一个二元谓词符号的语言 L = {R}, 以及 L 结构 ( {a, b, c}, {(a, b), (a, c)} ), 如图 b a c {a, b, c} 的哪些子集是可定义的? 哪些 {a, b, c} 上的二元关系是可定义的?

14 结构内的可定义性例考察关于数论的语言 L = {0, S, +, } 令 L 结构 N 的论域为自然数集 N, 其他的符号都按照通常的解释, 则序关系 { (m, n) m < n } 在 N 中是可定义的对每一个自然数 n, 单点集 {n} 都是 N 中可定义的所有素数的集合在 N 中是可定义的思考 : 有否不可定义的自然数的子集? 能不能举出例子?

15 结构内的可定义性例考察关于数论的语言 L = {0, S, +, } 令 L 结构 N 的论域为自然数集 N, 其他的符号都按照通常的解释, 则序关系 { (m, n) m < n } 在 N 中是可定义的对每一个自然数 n, 单点集 {n} 都是 N 中可定义的所有素数的集合在 N 中是可定义的思考 : 有否不可定义的自然数的子集? 能不能举出例子?

16 结构内的可定义性例考察关于数论的语言 L = {0, S, +, } 令 L 结构 N 的论域为自然数集 N, 其他的符号都按照通常的解释, 则序关系 { (m, n) m < n } 在 N 中是可定义的对每一个自然数 n, 单点集 {n} 都是 N 中可定义的所有素数的集合在 N 中是可定义的思考 : 有否不可定义的自然数的子集? 能不能举出例子?

17 结构内的可定义性例考察关于数论的语言 L = {0, S, +, } 令 L 结构 N 的论域为自然数集 N, 其他的符号都按照通常的解释, 则序关系 { (m, n) m < n } 在 N 中是可定义的对每一个自然数 n, 单点集 {n} 都是 N 中可定义的所有素数的集合在 N 中是可定义的思考 : 有否不可定义的自然数的子集? 能不能举出例子?

18 结构内的可定义性例考察关于数论的语言 L = {0, S, +, } 令 L 结构 N 的论域为自然数集 N, 其他的符号都按照通常的解释, 则序关系 { (m, n) m < n } 在 N 中是可定义的对每一个自然数 n, 单点集 {n} 都是 N 中可定义的所有素数的集合在 N 中是可定义的思考 : 有否不可定义的自然数的子集? 能不能举出例子?

19 结构内的可定义性例考察关于数论的语言 L = {0, S, +, } 令 L 结构 N 的论域为自然数集 N, 其他的符号都按照通常的解释, 则序关系 { (m, n) m < n } 在 N 中是可定义的对每一个自然数 n, 单点集 {n} 都是 N 中可定义的所有素数的集合在 N 中是可定义的思考 : 有否不可定义的自然数的子集? 能不能举出例子?

20 定义结构类定义给定语言 L 令 Σ 是 L 闭语句集我们称 Mod Σ = { A A 是 L 结构且,A Σ } 是 Σ 所定义的 L 结构类 ( 所有 Σ 的模型组成的类 ) 若 Σ = {τ}, 我们记 {τ} 所定义的结构类为 Mod τ

21 定义结构类定义给定语言 L 令 Σ 是 L 闭语句集我们称 Mod Σ = { A A 是 L 结构且,A Σ } 是 Σ 所定义的 L 结构类 ( 所有 Σ 的模型组成的类 ) 若 Σ = {τ}, 我们记 {τ} 所定义的结构类为 Mod τ

22 定义结构类定义给定语言 L, 我们称一个 L 结构类 K 是 L 初等类 (elementary class), 当且仅当存在一个 L 闭语句 τ 使得 K = Mod τ 我们称 K 是 L 广义初等类, 当且仅当存在一个 L 闭语句集 Σ 使得 K = Mod Σ 广义初等类与初等类到底有何区别?

23 定义结构类定义给定语言 L, 我们称一个 L 结构类 K 是 L 初等类 (elementary class), 当且仅当存在一个 L 闭语句 τ 使得 K = Mod τ 我们称 K 是 L 广义初等类, 当且仅当存在一个 L 闭语句集 Σ 使得 K = Mod Σ 广义初等类与初等类到底有何区别?

24 定义结构类定义给定语言 L, 我们称一个 L 结构类 K 是 L 初等类 (elementary class), 当且仅当存在一个 L 闭语句 τ 使得 K = Mod τ 我们称 K 是 L 广义初等类, 当且仅当存在一个 L 闭语句集 Σ 使得 K = Mod Σ 广义初等类与初等类到底有何区别?

25 定义结构类例令语言 L 只含有等词语句 ε 2 : x y(x y) 定义的 L- 结构类是什么? 所有含有 2-4 个元素的集合组成的类是 L 初等类? 所有无穷集合组成的类是不是 L 广义初等类? 是不是初等类?

26 定义结构类例令语言 L 只含有等词语句 ε 2 : x y(x y) 定义的 L- 结构类是什么? 所有含有 2-4 个元素的集合组成的类是 L 初等类? 所有无穷集合组成的类是不是 L 广义初等类? 是不是初等类?

27 定义结构类例令语言 L 只含有等词语句 ε 2 : x y(x y) 定义的 L- 结构类是什么? 所有含有 2-4 个元素的集合组成的类是 L 初等类? 所有无穷集合组成的类是不是 L 广义初等类? 是不是初等类?

28 定义结构类例令语言 L 只含有等词语句 ε 2 : x y(x y) 定义的 L- 结构类是什么? 所有含有 2-4 个元素的集合组成的类是 L 初等类? 所有无穷集合组成的类是不是 L 广义初等类? 是不是初等类?

29 定义结构类例考虑含有等次和二元谓词符号的语言 L = {R} 令 τ 1 = xrxx, τ 2 = x y z(rxy Ryz Rxz), Mod{τ 1, τ 2 } 是什么? 给出定义偏序类全序类的闭语句 ( 集 ) 给出定义等价关系的闭语句 ( 集 )

30 定义结构类例考虑含有等次和二元谓词符号的语言 L = {R} 令 τ 1 = xrxx, τ 2 = x y z(rxy Ryz Rxz), Mod{τ 1, τ 2 } 是什么? 给出定义偏序类全序类的闭语句 ( 集 ) 给出定义等价关系的闭语句 ( 集 )

31 定义结构类例考虑含有等次和二元谓词符号的语言 L = {R} 令 τ 1 = xrxx, τ 2 = x y z(rxy Ryz Rxz), Mod{τ 1, τ 2 } 是什么? 给出定义偏序类全序类的闭语句 ( 集 ) 给出定义等价关系的闭语句 ( 集 )

32 定义结构类例考虑含有等次和二元谓词符号的语言 L = {R} 令 τ 1 = xrxx, τ 2 = x y z(rxy Ryz Rxz), Mod{τ 1, τ 2 } 是什么? 给出定义偏序类全序类的闭语句 ( 集 ) 给出定义等价关系的闭语句 ( 集 )

33 定义结构类例考虑含有等次和二元谓词符号的语言 L = {R} 令 τ 1 = xrxx, τ 2 = x y z(rxy Ryz Rxz), Mod{τ 1, τ 2 } 是什么? 给出定义偏序类全序类的闭语句 ( 集 ) 给出定义等价关系的闭语句 ( 集 )

34 定义结构类例群论语言 L = {,, 1 e}, 则下列闭语句 x y z (x (y z) (x y) z) x (x e e x x) x (x x 1 x 1 x e) 定义了群这个初等类阿贝尔群是不是初等类? 无扭的阿贝尔群呢?

35 定义结构类例群论语言 L = {,, 1 e}, 则下列闭语句 x y z (x (y z) (x y) z) x (x e e x x) x (x x 1 x 1 x e) 定义了群这个初等类阿贝尔群是不是初等类? 无扭的阿贝尔群呢?

36 以上, 我们给出了可定义的严格定义, 意味着我们可以证明形如 XXX 是不可定义的的命题了

37 同态与同构

38 同态与同构定义 ( 同态 ) 给定语言 L 令 A 和 B 为两个 L 结构我们称函数 h : A B 是一个从 A 到 B 的同态 (homomorphism), 当且仅当它满足下述条件对每个 n 元谓词符号 P, 和每组 a 1,, a n A, 有 (a 1,, a n ) P A ( h(a 1 ),, h(a n ) ) P B

39 同态与同构定义 ( 同态 ) 给定语言 L 令 A 和 B 为两个 L 结构我们称函数 h : A B 是一个从 A 到 B 的同态 (homomorphism), 当且仅当它满足下述条件对每个 n 元谓词符号 P, 和每组 a 1,, a n A, 有 (a 1,, a n ) P A ( h(a 1 ),, h(a n ) ) P B

40 同态与同构定义 ( 同态 ) 给定语言 L 令 A 和 B 为两个 L 结构我们称函数 h : A B 是一个从 A 到 B 的同态 (homomorphism), 当且仅当它满足下述条件对每个 n 元函数符号 f, 和每组 a 1,, a n A, 有 h ( f A (a 1,, a n ) ) = f B( h(a 1 ),, h(a n ) )

41 同态与同构定义 ( 同态 ) 给定语言 L 令 A 和 B 为两个 L 结构我们称函数 h : A B 是一个从 A 到 B 的同态 (homomorphism), 当且仅当它满足下述条件对每个常数符号 c, 有 h(c A ) = c B

42 同态与同构直观上, 同态保持两个结构对谓词符号函数符号和常数符号的解释那么, 什么时候算是也保持对等词和量词的解释呢?

43 同态与同构直观上, 同态保持两个结构对谓词符号函数符号和常数符号的解释那么, 什么时候算是也保持对等词和量词的解释呢?

44 同态与同构定义 ( 嵌入与同构 ) 令 h : A B 是从 A 到 B 的同态如果同态 h 是单射的, 我们称 h 是一个从 A 到 B 的嵌入 (embedding); 如果 h 是双射 ( 既是单射, 又是满射 ), 我们称 h 是一个从 A 到 B 的同构 (isomorphism) 此时, 我们称 A 与 B 同构, 记 A B

45 同态与同构定义 ( 嵌入与同构 ) 令 h : A B 是从 A 到 B 的同态如果同态 h 是单射的, 我们称 h 是一个从 A 到 B 的嵌入 (embedding); 如果 h 是双射 ( 既是单射, 又是满射 ), 我们称 h 是一个从 A 到 B 的同构 (isomorphism) 此时, 我们称 A 与 B 同构, 记 A B

46 同态与同构定理 ( 同态定理 ) 给定语言 L 假定 h 是从 L 结构 A 到 B 的同态,s 是 A 赋值则 1 对任意项 t,h ( s(t) ) = h s(t) 2 对任何不含量词且不含等词的公式 α, (A, s) α (B, h s) α 3 若 h 是单射, 则 α 可含等词 ; 若 h 是双射, 可含量词

47 同态与同构定理 ( 同态定理 ) 给定语言 L 假定 h 是从 L 结构 A 到 B 的同态,s 是 A 赋值则 1 对任意项 t,h ( s(t) ) = h s(t) 2 对任何不含量词且不含等词的公式 α, (A, s) α (B, h s) α 3 若 h 是单射, 则 α 可含等词 ; 若 h 是双射, 可含量词

48 同态与同构定理 ( 同态定理 ) 给定语言 L 假定 h 是从 L 结构 A 到 B 的同态,s 是 A 赋值则 1 对任意项 t,h ( s(t) ) = h s(t) 2 对任何不含量词且不含等词的公式 α, (A, s) α (B, h s) α 3 若 h 是单射, 则 α 可含等词 ; 若 h 是双射, 可含量词

49 同态与同构定理 ( 同态定理 ) 给定语言 L 假定 h 是从 L 结构 A 到 B 的同态,s 是 A 赋值则 1 对任意项 t,h ( s(t) ) = h s(t) 2 对任何不含量词且不含等词的公式 α, (A, s) α (B, h s) α 3 若 h 是单射, 则 α 可含等词 ; 若 h 是双射, 可含量词

50 同态与同构定理 ( 同态定理 ) 给定语言 L 假定 h 是从 L 结构 A 到 B 的同态,s 是 A 赋值则 1 对任意项 t,h ( s(t) ) = h s(t) 2 对任何不含量词且不含等词的公式 α, (A, s) α (B, h s) α 3 若 h 是单射, 则 α 可含等词 ; 若 h 是双射, 可含量词

51 下期预告同态定理及其推论证明不可定义一阶逻辑的可靠性定理

52 习题 522, 523,

数理逻辑 I Mathematical Logic I

数理逻辑 I Mathematical Logic I 前情提要前情提要我们定义了两种可定义概念结构内的可定义性 : 给定结构关于该结构论域上的 k 元关系的性质由一个公式定义定义结构类 : 给定语言关于该语言的结构类的由一则闭语句定义 ( 初等类 ); 由一集闭语句定义 ( 广义初等类 ) 前情提要我们定义了两种可定义概念结构内的可定义性 : 给定结构关于该结构论域上的 k 元关系的性质由一个公式定义定义结构类 : 给定语言关于该语言的结构类的由一则闭语句定义