A Mathematical Introduction to Logic -- Chapter 0

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

\(\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\MYNOTE{\sf{M\scriptsize{Y}}\sf{N\scriptsize{OTE}}.\quad}\)

这是一个关于数理逻辑的读书笔记或者学习总结, 书名是A Mathematical Introduction to Logic, 作者Herbert B. Enderton, University of California

本文是Chapter 0, 点击这里进入目录

第0章介绍一些集合论的基础概念, 这些概念是后面所有章节的基石. 我基本是把干货抄录在这里以便跳转

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

前缀关键字的含义:

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

Chapter Zero: Useful Facts about Sets

\(\DEFi\) Set 集合

A set is a collection of things.

\(\DEF\) Set Equality, \(A=B\), 集合相等

If \(A\) and \(B\) are sets such that for every object t,

\[ t \in A \quad \text{iff} \quad t \in B \]

then \(A=B\)

\(\DEF\) Adjoining one extra object to a set, \(A;t\) 添加元素

Let \(A;t\) be the set whose members are (i) the members of A, plus (ii) the (possibly new) member t. We have \[A;t = A \cup {t}\] using notation defined later. and \[ t \in A \quad\text{iff}\quad A;t=A \]

\(\DEF\) Empty \(\varnothing\) and Nonempty Set 空集和非空集

Empty set \(\varnothing\) is the set which has no members at all. Any other set is said to be nonempty.

\(\DEF\) Singleton Set 单元素集

For any object \(x\), there is the Singleton Set \({x}\) whose only member is \(x\).

\(\DEF\) Subset 子集

If \(A\) is a set all of whose members are also members of B, then A is a subset of B, abbreviated \(A \subseteq B\).

\(\DEF\) Power set 幂集

The power set \({\cal P} A\) of \(A\) is a set whose members are the subsets of A. Thus

\[ {\cal P} A = \{x|x \subseteq A\}\]

\(\DEF\) Union 并集

The union of \(A\) and \(B\), \(A \cup B\), is the set of all things that are members of A or B (or both).

If \(A\) is a set whose members are themselves sets. \[ \bigcup A=\{x|\text{x belongs to some member of} A\} \]

\(\DEF\) Inter-section 交集

Intersection of \(A\) and \(B\), \(A \cap B\), is the set of all things that are members of both \(A\) and \(B\).

If \(A\) is a set whose members are themselves sets. \[ \bigcap A=\{x|\text{x belongs to all members of} A\} \]

\(\DEF\) Disjoint 不相交

Sets \(A\) and \(B\) are disjoint iff their intersection is empty.

\(\DEF\) Pairwise Disjoint 两两不相交

A collection of sets is pairwise disjoint iff any two members of the collection are disjoint.

\(\DEF\) Ordered Pair 有序对

The ordered pair \(\langle x,y \rangle\) of objects \(x\) and \(y\) is a set: \[ \langle x,y \rangle = \{\{x\},\{x,y\}\}. \]

\(\DEF\) Ordered Triple 有序三元组

The ordered triples is a pair: \[ \langle x,y,z \rangle = \langle\langle x,y\rangle,z \rangle. \]

\(\DEF\) N-tuples 有序n元组

The n-tuples is defined recursively as a pair: \[ \langle x_1,\ldots,x_{n+1} \rangle = \langle\langle x_1,\ldots,x_n\rangle,x_{n+1} \rangle. \]

\(\DEF\) finite sequence (or string) 有限序列(或者串)

\(S\) is a finite sequence (or string) of members of A iff some positive integer n, we have n-tuples \(S=\langle x_1,\ldots,x_{n+1} \rangle\), where each \(x_i \in A\).

\(\DEF\) Segment 段

A segment of the finite sequence \(S=\langle x_1,\ldots,x_{n+1} \rangle\) is a finite sequence \[ S=\langle x_k, x_{k+1},\ldots,x_{m-1}, x_m \rangle,\qquad\text{where}\quad 1 \le k \le m \le n. \]

\(\DEF\) initial segment 初始段

A segment is an initial segment iff \(k=1\).

\(\DEF\) proper 真子段

A segment is proper iff it is different from \(S\)

LEMMA 0A 引理0A

Assume that \(S=\langle x_1,\ldots,x_m \rangle = \langle y_1,\ldots,y_m,\ldots,y_{m+k} \rangle\). Then \(x_1 = \langle y_1,\ldots,y_{k+1} \rangle\).

\(\DEF\) Cartesian product 笛卡尔积

The Cartesian product of sets \(A\) and \(B\), \(A \times B\), is the set of all pairs \(\langle x,y \rangle\) for which \(x \in A\) and \(y \in B\).

\(\DEF\) Cartesian exponent 笛卡尔幂

\(A^n\) is the set of all n-tuples of members of A. For example. \(A^3 = (A \times A) \times A\).

\(\DEF\) Relation 关系

A relation \(R\) is a set of ordered pairs.

\(\DEF\) Domain 定义域

The domain of relation \(R\) (written dom \(R\)) is the set of all objects \(x\) such that \(\langle x,y \rangle \in R\) for some \(y\).

\(\DEF\) Range 值域

The range of relation \(R\) (written ran \(R\)) is the set of all objects \(y\) such that \(\langle x,y \rangle \in R\) for some \(x\).

\(\DEF\) Field 域

The union of dom \(R\) and ran \(R\) is the field of \(R\) field of \(R\), fld \(R\).

\(\DEF\) N-ary relation n元关系

An n-ary relation on \(A\) is a subset of \(A^n\). A 1-ary (unary) relation on A is simply a subset of A.

\(\DEF\) Restriction of \(R\) to \(B\) 关系\(R\)对集合\(B\)的限制

For an n-ary relation \(R\) on \(A\) and subset \(B\) of \(A\), the restriction of \(R\) to \(B\) is the intersection \(R \cap B^n\).

\(\DEF\) Function 函数

A function is a relation \(F\), with the property of being single-valued: For each \(x\) in dom \(F\) there is only one \(y\) such that \(\langle x,y \rangle \in F\). This unique \(y\) is said to be value \(F(x)\) that \(F\) assumes at \(x\).

\(\DEF\) Composition of functions 复合函数

\(f \circ g\) is the function whose value at \(x\) is \(f(g(x))\).

\(\DEF\) \(F\) Map \(A\) into \(B\) \(F\)把\(A\)映射到\(B\)中

We say that \(F\) Map \(A\) into \(B\) and write \[F:A\rightarrow B\] to mean that \(F\) is a function, dom \(F=A\), and ran \(F \subseteq B\).

\(\DEF\) \(F\) Map \(A\) onto \(B\) \(F\)把\(A\)映射到\(B\)上

If \(F\) maps \(A\) into \(B\), and ran \(F=B\), then we say \(F\) map \(A\) onto \(B\).

\(\DEF\) One-to-one 一对一

A function \(F\) is one-to-one iff for each \(y\) in ran \(F\) there is only one \(x\) such that \(\langle x,y \rangle \in F\).

\(\DEF\) Multivariate Function 多变量函数

If the pair \(\langle x,y \rangle\) is in dom \(F\), then we let \(F(x,y) = F(\langle x,y \rangle)\). This notation is extended to n-tuples; \(F(x_1,\ldots,x_n)=F(\langle x_1,\ldots,x_n \rangle)\).

\(\DEF\) n-ary operation on \(A\) 集合\(A\)上的n元运算

An n-ary operation on \(A\) is a function mapping \(A^n\) into \(A\).

\(\DEF\) \(A\) is Closed under \(f\) 集合\(A\)在函数\(f\)作用下是封闭的

We say set A is closed under an function f, if \(f(a_1,\ldots,a_n) \in A\) whenever each \(a_i\) is in \(A\).

\(\DEF\) Restriction of operation 运算对集合的限制

If \(f\) is an n-ary operationi on \(A\), then the restriction of \(f\) to a subset \(B\) of \(A\) is the function \(g\) with domain \(B^n\) which agrees with \(f\) at each point of \(B^n\). Thus, \[g=f \cap (B^n \times A).\] This g will be an a-ary operation on \(B\) iff \(B\) is closed under \(f\). In this case, \(g=f\cap B^{n+1}\), in agreement with our definition of the restriction of a relation.

\(\DEF\) Identity function 恒等函数

The identity function \(Id\) on \(A\), is a unary operation on \(A\), given by the equation \[ Id(x)=x \qquad \text{for}\quad x \in A \] Thus \(Id = \{\langle x,x \rangle|x \in A\}\)

\(\DEFn\) Attributes of Relation

For a relation \(R\), we define the following

  • \(R\) is reflexive on \(A\) iff \(\langle x,x \rangle \in R\) for every \(x\) in \(A\).
  • \(R\) is symmetric iff whenever \(\langle x,y \rangle \in R\) then also \(\langle y,x \rangle \in R\).
  • \(R\) is transitive iff whenever both \(\langle x,y \rangle \in R\) and \(\langle y,z \rangle \in R\) then also \(\langle x,z \rangle \in R\).
  • \(R\) satisfies trichotomy on A (or is trichotomous) iff for every x and y in A, exactly one of the tree possibilities, \(\langle x,y \rangle \in R\), \(x=y\), or \(\langle y,x \rangle \in R\), holds.
  • \(R\) is connex iff for all \(x\) and \(y\) in \(A\), we have \(\langle x,y \rangle \in R\) or \(\langle y,x \rangle \in R\)
  • \(R\) is anti-symmetric iff whenever \(\langle x,y \rangle \in R\) and \(\langle y,x \rangle \in R\), then \(x=y\)
  • \(R\) is anti-reflexive on \(A\), iff \(\langle x,y \rangle \in R\) for every x in A.
  • \(R\) is asymmetric iff when whenever \(\langle x,y \rangle \in R\) then \(\langle y,x \rangle \notin R\)

\(\DEF\) Equivalence Relation 等价关系

For a relation \(R\), \(R\) is an equivalence relation on \(A\) iff \(R\) is a binary relation on A that is reflexive, symmetric and transitive on A

\(\DEFn\) Ordering Relation 序关系

For a relation \(R\),

\(\DEF\) Finite Set 有限集

A set \(A\) is finite iff there is some one-to-one function \(f\) mapping the set \(A\) onto \(\{0,1,\ldots,n-1\}\) for some natural number \(n\).

\(\DEF\) countable Set 可数集

A set \(A\) is countable iff there is some function mapping \(A\) one-to-one into \(\Bbb N\).

Theorem 0B

Let \(A\) be a coutable set. Then the set of all finite sequences of members of \(A\) is also coutable.

\(\DEF\) Chain 链

Say that a collection \(C\) of sets is a chain iff for any elements \(x\) and \(y\) of \(C\), either \(x \subseteq y\) or \(y \subseteq x\).

(From wikipedia) In general, a chain is a totally ordered subset of a partially ordered set.

Zorn's Lemma\(_*\)

Let A be a set such that for any chain \(C \subseteq A\), the set \(\bigcap C\) is in \(A\). Then there is some element \(m \in A\) which is maximal in the sense that it is not a subset of any other element of \(A\).

(From wikipedia) A partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.

\(\DEF\) Equinumerous 等势的

Say that \(A\) and \(B\) are equinumerous (written \(A \sim B\)) iff there is a one-to-one function mapping \(A\) onto \(B\).

Cardinal Number 基数

To each set A we can assign a certain object, the cardinal number (or cardinality) of \(A\) (written card \(A\)), in such a way that two sets are asigned the same cardinality iff they are equinumerous: \[ \text{card}\; A = \text{card}\; B\quad\text{iff}\quad A \sim B \]

点击这里进入目录