A Mathematical Introduction to Logic -- Section 1.4

发表于 更新于 分类于 ， 阅读次数：

\(\def\tauequ{\mathbin{\vDash\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}\) \(\def\Dashv{\mathbin{\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}\) \(\def\DEF{\sf{D\scriptsize EF}.\quad}\) \(\def\DEFi{\sf{D\scriptsize EF}^*.\quad}\) \(\def\DEFn{\sf{D\scriptsize EF}_*.\quad}\) \(\def\DEFin{\sf{D\scriptsize EF}^*_*.\quad}\) \(\def\llbracket{\unicode{x27E6}}\) \(\def\rrbracket{\unicode{x27E7}}\) \(\def\PROOF{\sf{P\scriptsize ROOF}.\quad}\) \(\def\MYNOTE{\sf{M\scriptsize{Y}}\sf{N\scriptsize{OTE}}.\quad}\) \(\def\EXAMPLE{\bf\sf{E\scriptsize{XAMPLES}}\quad}\) 这是一个关于数理逻辑的读书笔记和学习总结, 书名是A Mathematical Introduction to Logic (以下简称AMIL), 作者Herbert B. Enderton, University of California

点击这里进入AMIL的目录

本文是Section 1.4, 内容是介绍归纳(Induction)和递归(Recursion)在命题逻辑这个数学模型下的精确定义.

由于中文版错误太多, 大部分章节读的是英文第二版, 所以笔记也是中英文夹杂着写的. 英文一般是关键原文. 中文有的是原文的翻译, 有的是我自己的理解, 还有的是 为了做练习写的证明和计算过程.

前缀关键字的含义:

  • \(\DEF\) : 表明后面是概念定义.
  • \(^*\) : 表明后面内容并不是数学上的精确表达.
  • \(_*\) : 表明后面的内容并不来自于这本书.
  • \(\MYNOTE\) : 后面的内容是我用自己的话做的总结,或心得体会

Induction 归纳

归纳在各个数学分支都在使用的构造方法. 通过对集合\(U\)的某些初始元素重复使用几种运算, 可以构造\(U\)的一个子集. 这个子集是包含初始元素并且对相应运算是封闭的最小集合.

本节的符号:

  • \(U\)我们关心的对象的全集.
  • 用符号\(B\)表示这些初始元素组成的集合.
  • 符号\(C\)表示这个构造出来的集合.
  • 符号\(\mathcal{F}\)表示\(U\)上n元运算的函数类(class).\(n\)是正整数, n为1时代表一元运算. 事实上\(\mathcal{F}\)可以是any set of relations on \(U\)
  • \(S\)是\(U\)的一个子集.

\(\DEF\) \(S\) is Inductive(\(S\)是归纳的) iff \(B\subseteq S\) and \(S\) is closed under all operations in \(\mathcal{F}\).

\(\DEF\) \(C\) is the set generated from \(B\) by the functions in \(\mathcal{F}\). \(C\)是由初始集合\(B\)通过\(\mathcal{F}\)中的函数运算生成的集合

这个定义可以有两种自上而下和自下而上的等价的定义.

  • From the top down: Let \(C^*\) be intersection of all the inductive subsets of \(U\).
  • From the bottom up: Let \(C_*\) contain the things that can be reached from B by applying operations in \(\mathcal{F}\) a finite number of times. Temporarily define a construction sequence to be a finite sequence \(\langle x_1,\ldots,x_n\rangle\) of elements of \(U\) such that each member of the sequence either is in \(B\) or results from earlier members by applying operations in \(\mathcal{F}\). Let \(C_n\) be the set of points \(x\) such that some construction sequence of length n ends with \(x\). Then \(C_1=B\), \[ C1\subseteq C2\subseteq C3\subseteq\cdots, \] Let \(C_*=\bigcup_n C_n\), which means let \(C_*\) be the set of all points \(x\) such that some construction sequence ends with \(x\).

\(\sf{I\scriptsize{NDUCTION}}\enspace\sf{P\scriptsize{RINCIPLE}}\quad\)(归纳原则) Assume that \(C\) is the set generated from \(B\) by the operations in \(\mathcal F\). If \(S\) is a subset of \(C\) that includes \(B\) and is closed under the operations of \(\mathcal{F}\) then \(S=C\).

\(\MYNOTE\) 归纳原则: 生成集是最小的归纳的集合.

\(\EXAMPLE\) 通过归纳原则可以定义:

  1. 自然数
    • \(U\): real numbers
    • \(B\): \(\{0\}\)
    • \(\mathcal{F}\): \({S}\) where \(S(x)=x+1\)
  2. 整数
    • \(U\): real numbers
    • \(B\): \(\{0\}\)
    • \(\mathcal{F}\): \({S, P}\) where \(S(x)=x+1\) and \(P(x)=x-1\)
  3. The algebratic functions class:
    • \(U\): all functions whose domain and range are each sets of real numbers.
    • \(B\): contain the identity function and all constant functions.
    • \(\mathcal{F}\): contain the operations of addition, multiplication, division, and root extraction.
  4. The well-formed formulas
    • \(U\): all expressions
    • \(B\): the set of sentence symbols.
    • \(\mathcal{F}\): contain the five formula-building operations on expresssions: \(\mathcal{E}_\lnot, \mathcal{E}_\land, \mathcal{E}_\lor, \mathcal{E}_\to, \text{and } \mathcal{E}_\leftrightarrow\)

Recursion 递归

\(\DEF\) Say that \(C\) is freely generated from \(B\) by operations in \(\mathcal{F}\) iff in addition to the requirements for being generated, the restrictions \(f_C\) of each \(f\) in \(\mathcal{F}\) to \(C\) meet the following conditions:

  1. \(f_C\) of each \(f\) in \(\mathcal{F}\) are one-to-one
  2. The range of \(f_C\) of each \(f\) in \(\mathcal{F}\), and the set \(B\) are pairwise disjoint.

\(\MYNOTE\) 自由生成这个概念限制很强, 条件一意味着\(\mathcal{F}\)中的运算对不同输入不能产生相同输出. 条件二意味着, 没有一个值能够通过两种或以上的运算得出, 初始集合里的值也不能通过运算得到.

\(\sf{R\scriptsize{ECURSION}}\enspace\sf{T\scriptsize{HEOREM}}\quad\) 递归定理

Assume that the subset \(C\) of \(U\) is freely generated from \(B\) by \(f\) and \(g\), where \[ \begin{align*} f:U\times U&\to U, \\ g:U&\to U. \\ \end{align*} \] Further assume that \(V\) is a set and \(F\), \(G\), and h functions such that \[ \begin{align*} h:B&\to V, \\ f:V\times V&\to V, \\ g:V&\to V. \\ \end{align*} \]

Then there is a unique function \[ \overline{h}:C\to V \] such that

  1. For \(x\) in \(B\), \(\overline{h}(x)=h(x);\)
  2. For \(x,y\) in \(C\), \[ \begin{align*} \overline{h}(f(x,y)) &= F(\overline{h}(x),\overline{h}(y)), \\ \overline{h}(g(x)) &= G(\overline{h}(x)), \\ \end{align*} \]

\(\MYNOTE\)

递归定理本质上在讲, 若满足如下条件

  1. 由\(B\)通过\(\mathcal{F}\)能够自由生成的\(C\).
  2. 如果两个集合\(U\)和\(V\)有结构相同的运算.
  3. \(U\)的初始子集\(B\)能通过\(h\)映射到\(V\)里

那么一定能够把\(h\)扩展成一个从\(C\)到\(V\)中的同态\(\overline{h}\)

\(\EXAMPLE\)

  1. 自然数, \(B=\{0\}\) with one operation, the successor operation \(S\). Then \(C\) is freely generated from {0} by \(S\). 因此根据递归定理对于任意集合\(V\), 任何\(a \in V\), 以及任何运算\(F:V\to V\). 一定有一个唯一的\(\overline{h}:\mathbb{N}\to V\), 使得\(\overline{h}(0)=a\)并且\(\overline{h}(S(x))=F(\overline{h}(x))\)对每一个\(x\in\mathbb{N}\)成立.
  2. 整数, 有successor和predecessor两个运算, 由于运算的值域有交集, 所以不是自由生成的
  3. The algebraic function, 也不是自由生成的.
  4. The wffs, 是自由生成的.

\({\sf U\scriptsize{NIQUE}\enspace R\scriptsize{EADABILITY}\enspace T\scriptsize{HEOREM}}\) 唯一可读性定理

The set of wffs is freely generated from the set of sentence symbols by the five operations.

有个唯一可读性定理和递归定理, 1.2节的真值分配的定理12A不言自明.

\(\MYNOTE\) 一旦命题符号的真值给定, 所有合式公式都有唯一的真值.