计算机数理逻辑-集合论

1. Sets 集合

sets which allow repetition
$S(x)$ specifies the number of occurrences of the element x (of the base set X) within S
- S = {a, a, a, b, b} is a multi-set over {a, b, c}, then S(a) = 3, S(b) = 2, S(c) = 0
- denoted: $S: A\rightarrow{Z^{+}}$，A is the underlying set of the multiset
multi-set S over X is called finite, if { x ∈ X | S(x) > 0 | < ∞}.

Let S and T be sets. S is a subset of T , denoted S ⊆ T , iff every element of S is an element of T , that is, x ∈ S → x ∈ T . S is a proper subset真子集 of T , denoted S ⊂ T , iff S ⊆ T and S ≠ T
Union并集
- S ∪ T , the union of S and T , is the set consisting of those elements which are elements of either S or T (or both).
Intersection交集
- S ∩ T , the intersection of S and T , is the set consisting of those elements which are elements of both S and T . If S ∩ T =∅ then S and T are disjoint .
Difference差集
- S − T , the difference of S and T , is the set of elements of $S$ that are not elements of $T$
complement 补集
- Let S be understood as a universal set; then $\bar{T}$ , the complement of T , is S − T
Cartesian product笛卡尔积
- Let S and T be sets. S × T , their Cartesian product , is the set of all pairs ( s , t ) such that s ∈ S and t ∈ T

Let $S$ be a set.

A finite sequence $f$ on $S$ is a function from ${ 0,…, n−1 }$ to $S$ . The length of the sequence is $n$ .
- 也就是说sequence就是一个映射函数
An infinite sequence $f$ on $S$ is a mapping from $N$ to $S$

a relation is a subset of a Cartesian product of sets and a function is a relation with a special property
关系是集合的笛卡尔积的一个子集，函数是具有特殊属性的关系。

Let R be a binary relation on $S^2$ . (Notation: R(x,y) <=> yRx)

R is reflexive自反 iff R ( x , x ) for all x ∈ S .
- irreflexive非自反 iff $\lnot R ( x , x )$ for all x ∈ S
R is symmetric 对称 iff $R ( x_1 , x_2 )$ implies $R ( x_2 , x_1)$.
- An example of symmetric relation : “… is married to ___”.
- Asymmetric 非对称: $R ( x_1 , x_2)$ implies $\lnot R( x_2 , x_1)$
Antisymmetric 反对称
- 若对所有的 a 和 b 属于 X，下述语句保持有效，则集合 X 上的二元关系 R 是反对称的：“若 a 关系到 b 且 b 关系到 a，则 a = b。”
  注意，反对称关系不是对称关系（aRb 得到 bRa）的反义。有些关系既是对称的又是反对称的，比如”等于”（证明：a=b推出b=a；a=b且b=a推出a=b）；有些关系既不是对称的也不是反对称的，比如”爱上……”（证明：a爱b不能推出b爱a；a爱b且b爱a不能推出a和b是同一个人）
- Every asymmetric relation is also antisymmetric. But if antisymmetric relation contains pair of the form (a,a) then it cannot be asymmetric.
  - {<1,1>, <1,2>, <2,3>} is not asymmetric because of <1,1>, but it is antisymmetric.
R is transitive传递 iff R ($x_1 , x_2$ ) and R ( $x_2 , x_3$ ) imply R ( $x_1 , x_3$ ).

$R^{∗}$ , the reflexive transitive closure自反传递闭包 of $R$ , is defined as follows:

If R ( $x_1 , x_2$ ) then $R^{∗}$ ( $x_1 , x_2$ ).
- $R\subseteq{R^{*}}$
$R^{∗}$ ( x i , x i ) for all $x_i$ ∈ S .
- $R^{*}$ is symmetric
$R^{∗}$ ( $x_1 , x_2$ ) and $R^{∗}$ ( $x_2 , x_3$ ) imply $R^{∗}$ ( $x_1 , x_3$ )
- $R^{*}$ is transitive

Definition. A transition relation ⇒ on set S is

terminating终止 if there is no infinite s1 ⇒ s2 ⇒ . . . ⇒ sn ⇒ . . ..
compatible with an ordering ≻ on S if ⇒⊆≻.
A transition relation ⇒ is terminating if and only if there is a well-founded ordering ≻ compatible with ⇒

symmetric and reflexive but not transitive:

$R={(a,a),(a,b),(b,a),(b,b),(c,c),(b,c),(c,b)}$
- 满足aRa
- 满足aRb→bRa
  - 即: R(a,b)存在时R(b,a)存在
- 不满足aRb,bRc->cRa

A and B are multisets in a given universe全集 U, with multiplicity functions $m_a$ and $m_b$.

A is included in B, denoted A ⊆ B, if ${\displaystyle m_{A}(x)\leq m_{B}(x)\quad \forall x\in U.} {\displaystyle m_{A}(x)\leq m_{B}(x)\quad \forall x\in U.}$

其余关系定义参考：

The cardinality/ˈkɑː.dɪnˈæl.ə.ti/ of a set is the number of elements in the set
如果存在着从集合A到集合B的双射，那么集合A与集合B等势，记为A~B

The powerset of a set S , denoted $2^S$ , is the set of all subsets of S
- 由该集合全部子集为元素构成的集合
Let S be a finite set of cardinality n ; then the cardinality of its powerset is $2^n$