Copyright By wangyoutian@nilnul.com

Notational Conventions For Heading Slides: Background Hue: Red, Yellow, Green, Cyan, Blue, Magenta as in Iris Saturation decreases Brightness increases Color offset to Background Font size decreases Position Shifted right Sideline slides are grey , the Greek goddess of the rainbow and a messenger of the gods

Notational Conventions Unordered List Bullets Ordered by color and the bigness of colored area Font size decreases

集合

内容 定义 性质 关系 运算 有限的集合 递归定义的可数集合 无限集合

很多东西放在一起 不讲顺序 忽略重复

有限的集合 对于有限的元素，可以通过穷举来定义集合 ｛1，2｝ ｛2，1｝ ｛3，1，3，2｝ {} Φ Ω:根据上下文包含我们所有谈到的事物

Element of ∈ ∉ 必须两者取其一，且仅取其一 帅哥 is not a set. 否则：模糊集合、悖论

元素 集合的元素可以是任何东西，包括集合本身. The following 4 sets are different from each other {} {{}} {{},{{}}} {{}, {{}},{{},{{}}}

势 Cardinality 元素的个数 比如 {}的势为0，｛{}｝为1，｛｛｝，｛｛｝｝｝为2 有限集合的势为自然数。反之亦然。 A的势记为#A或|A|

关系

集合的关系 由于集合的定义完全由其元素是哪些决定，所以集合的关系也在于他们的元素。

集合的基本关系 子集、真子集 ⊆ ⊇ ⊂ ⊃ ⊄ ⊅ = Joint 有共同的元素 Disjoint

disjoint Venn Diagram

Joint Not Disjoint

Subset/superset Proper subset/superset

equality =

运算

集合的运算 集合A和B的运算得到C，则 x∈A 和x∈B运算得到x∈C的值 这是逻辑运算

Intersect 2 3 5 6 4 A∩B=C x∈A & x∈B = x∈C 满足结合律

Union ∪ x∈A | x∈B = x∈C 满足结合律

Subtract 差集： A-B=A\B=C x∈A & x∉B = x∈C 对应逻辑的↛ 补集：Complement of A U-A A

∆ Symmetric Difference

运算律

其它转换

Cartesian Product 记录学生选课情况—所有备选情况为一个集合，元素为元组<学生，课程>， 学生1 学生2 课程1 课程2 课程3 记录学生选课情况—所有备选情况为一个集合，元素为元组<学生，课程>， 此为Cartesian Product 学生 课程 1 N 2 3 Y

Power Set A collection of all the subsets of a set. |P（A）|=2^|A| {1,2} {} {1} {2} |P（A）|=2^|A| ‘cuz every member can be either be included or not included.

Recursive Defined Set

Recurring {} {{}}包含前面定义的{} {{},{{}}}包含前面定义的{}和{{}} {{}, {{}},{{},{{}}}包含前面定义的{},{{}},{{},{{}}} …… 包含前面所有的 ……

Properties Nothing ∈ 0 0∈1∈2∈3∈…… to infinity Well-founded Regular There is an end 0∈1∈2∈3∈…… to infinity No end

Recurring Set vs Natural Number {}=0 {{}}={0}=1 {{},{{}}}={0,1}=2 {{}, {{}},{{},{{}}}={0,1,2}=3 ……

countable 可以和自然数N一一对应 凡是和N一一对应的，我们统称为可数个 这是我们最开始定义的无限，具有重要意义 你可以一个一个编号（号码是自然数） 这是我们最开始定义的无限，具有重要意义 我们能够定义、认识无限了。 用有限定义有限，成为认识。 无限两个字是有限的，但定义了无限这个意义

Cardinality 有限集合的势为自然数 |N|>任意的自然数 自然数都是有限的 N是无限的 0，1，2，……,N

等势 对于有限集合，A ⊂B 则 #A<#B 对于无限集合，则不一定成立 当有无限的时候，直观往往不准；即按照直观推导会产生悖论。 #偶数=#N ！ f(n)=2n 当有无限的时候，直观往往不准；即按照直观推导会产生悖论。

势的计算 有限个可数集合的并仍然可数 #整数=#N! 因为整数可以按照一定的规则编号（对应自然数） 0，-1，1，-2，2 f(n)= n/2 if n为偶数 -（n+1）/2 if n为奇数

The diary of Tristram Shandy Tristram spends two years to write about two days…, will all his life be covered? the hero of a novel by Laurence Sterne, writes his autobiography so conscientiously that it takes him one year to lay down the events of one day. If he is mortal he can never terminate; if he lived forever then no part of his diary would remain unwritten for to each day of his life a year devoted to that day's description would correspond. No, if he is mortal Yes, if he is immortal

How to define a countable set? Enumeration is not ok You can recursive define {},{{}},{{},{{}}},… 即： 先定义好第一个：{} 对于已经定义好的，给定一个转换，转换出新的一个。 { 把以前的都放进来 } But the definition itself must be finite 比如上面的把以前定义的都放进来。 以前定义的毕竟有限，所以转换会在有限步结束 如果不能在有限步结束，我们就不知道转出来的是什么，这个就无法定义

计算机程序 如果一个集合是可数的，则可以编制计算机程序，把其中元素一个个列举出来。这里的一个个列举是指： 在程序已经编定的情况下，你任意指定一个集合中的元素，程序都会在有限的时间内列举到你指定的元素。

举例 Ienumerable<BigInteger> N(){ for(BigInteger i=0;i++;) { yield return i; } //上述集合虽然在计算个数等属性时不会终止，但仍可以进行其它一部分运算，因此是有意义的 N（）.First(); N().TakeWhile(…);

可数的集合 比 任意的有限集合要大 可数是无限的 有没有比“无限”还大的？

Uncountable 不可数

Uncountable-R |R|>|N| Proof: Suppose it’s countable, then .101101001000… .001100010100… .110000111001… .000010100111… Write down .0110…. It can be placed nowhere! .9999999999 should be written as 1. Here we only consider with (0,1)

R=2N .0111111010… .1001000010… .0101110101… .0111000011… 定义自然数子集 数位（通过整数）与自然数对应 0，1对应含不含这个元素 则 #R=2#N #R =F^#N

实数的无限 比 自然数的无限大 虽然都是无限，但不一样。需要加以区分 可数的 不可数 比可数大 有没有介于两者之间的呢？

Continuum Hypothesis #R > #A > #N ? No This cannot be proved or disproved. If it’s consistent, CH cannot be proved wrong or false. this hypothesis can neither be proved nor disproved within the widely accepted ZFC axiomatic set theory, if ZFC is consistent.

与实数等势

R2 Points on the plane are as much as the points on an axis (x,y) 与 z的对应 把z的奇数位和偶数位作为x和y

Can we have a system which generates functions to order? No! Computer language with flow controls of Sequential Switch Loops Cannot express more than countable. So human has to do the job himself; and this means human has some more powerful means of logic than computer language nowadays.

势>#R的集合

幂集的势总是大于对应的集合

2R the set of all subsets of R, i.e., the power set of R, written P(R) or 2R

RR=2R the set RR of all functions from R to R

Na For each set S, #P(S)>#S {Function SS }=#S#S No upper bound

Aleph Number

我们发现集合的无限可以没有穷尽 有当我定义了一个无限后，就产生了更大的无限

The cardinality of the natural numbers is (read aleph-naught, aleph-null, or aleph-zero), the next larger cardinality is aleph-one , then and so on.

Infinite #A>#B if there is an injective function, but no bijective function, from B to A.

我们定义了有限的集合，可数的，Aleph系列的集合 可见一个对象如果是集合，那这个对象可以很大。 集合可以无限地无限大，是不是就能装下所有的东西呢？

比集合还大的？

如果我们把所有的集合放在一块，称之为集合X。 由于X是集合，而X包含所有的集合，所以 X∈X。 可不可以呢？

那么包含所有集合的东西就不是集合，或者说X∈X这样的集合不存在（虽然X∈X若不是集合的话可能存在） 如果按照前面讲的，0∈1∈2∈3∈…… 左侧必须到头，右侧可以无穷的话，X∈X就不可能！ 不存在包含所有集合的集合。 那么包含所有集合的东西就不是集合，或者说X∈X这样的集合不存在（虽然X∈X若不是集合的话可能存在） 存在比集合还大的概念！ 哪怕集合可以无限地无限大 这种定义叫做类

类 Class 类是 用谓词定义的。 X>2 表示一类数，显然这也是个集合 集合是个类。所有的集合 叫做 集合 类。但集合类 概念本身 不是 集合 否则就陷入循环定义 这也是在集合理论领域，集合是不加定义的原因 集合是在类中定义的一类事物

Russell’s Paradox 用谓词定义 R={x|x ∈ x} 不存在这样的X R={x|x∉x} Then R∈R⇔R∉R 可见谓词定义的不一定是集合。

集合公理

若想用谓词定义集合又能一致，必须符合一定的约束 哪些约束可以呢？不同的人有不同的看法。 不能随便定义 哪些约束可以呢？不同的人有不同的看法。 流行的是ZF (Zermelo-Fraenkel Set Theory)公理+选择公理(Axiom of Choice) 这些公理都可以表示成一阶逻辑

外延公理: 两个集合相同，当且仅当它们拥有相同的元素。 空集公理: 存在着一个不包含任何元素的集合，我们记这个空集合为{}。 配对公理: 假如x, y为集合，那就有另一个集合{x,y}包含x与y作为它的仅有元素。 并集公理: 每一个集合也有一个并集。也就是说，对于每一个集合x，也总存在着另一个集合y，而y的元素也就是而且只会是x的元素的元素。 无穷公理: 存在着一个集合x，空集{}为其元素之一，且对于任何x中的元素y，y U {y}也是x的元素。 分类公理（或子集公理）：给出任何集合及命题P(x)，存在着一个原来集合的子集包含而且只包含使P(x)成立的元素。 替代公理 幂集公理: 每一个集合也有其幂集。那就是，对于任何的x，存在着一个集合y，使y的元素是而且只会是x的子集。 正规公理 (or axiom of foundation): 每一个非空集合x，总包含着一元素y，使x与y为不交集。

选择公理: (Zermelo‘s version) 给出一个集合x，其元素皆为互不相交的非空集，那总存在着一个集合y（x的一个选择集合），包含x每一个元素的一个元素。

ZF & Axiom of Choice Godel理论证明了C是独立于ZF的 即根据ZF公理不能证明C错或者对 所以我们可以不同的公理体系，也许在有些公理下，原来成立的就不在成立，比如可以存在包含一切（包括自身）的集合

集合的定义 枚举 递归 公理下的运算（运算意味着属于关系的逻辑运算） 幂集等集合运算 谓词

Set theory is the foundation of computation E.g. Number Natural Number Real Relation Function Sequence

Set theory is the foundation of computation E.g. Data Structure Type

Collection in Computer

Tuple Order is important <x,y> is different from <y,x>

Bag-Multiset Not distinct Convertible to {<object,#>,…} {1,1,2} is different from {1,2} Convertible to {<object,#>,…} {<1,2>,<2,1>}

Table is a bag of tuples Id Name Sex Class … 1 Zhangsan M 2 LI Si F

Data Structure

Array In Memory Benefits: Disadvantage Continuous Elment of same width Random Access Speedy, Easy Disadvantage Fixed Length For allocation and leaving space for others Can’t hold different types. Have to be continuous

LinkedList Distributable Slower/ more complex than array Address Limited count Taking space

Stack No random access Fast access Different type

Dictionary Key value pair Can hold data of different sizes

Type Typed Tuple <Student, Course> <张三，语文> ✔ <张三，语文> ✔ <1,教室203> ✗

Table A collection of typed(named) tuples 学生 课程 1 2 3

Key: Y = Behavior supported, N = Behavior not supported COLLECTIONS Indexed Variable-size Duplicates Sorting Holds Bag N Y Any object Set List Dictionary Key + any object Array OrderedCollection SortedCollection String Characters Symbol

Thanks The end

Countable Infinite |Q|=|N|=|Z|=ℵ0 for(var i;;i++){ yield return i; } //note in finite time, your number will show up.

Cardinality And equinumerosity

Finite A={1,2,3,7} |A|=4 It’s easy to compare among finite sets.

Infinite #A=#B if there is a bijective function

Type Theory

Bertrand Russell invented the first type theory in response to his discovery that Gottlob Frege's version of naive set theory was afflicted with Russell's paradox. This theory of types features prominently in Whitehead and Russell's Principia Mathematica. It avoids Russell's paradox by first creating a hierarchy of types, then assigning each mathematical (and possibly other) entity to a type. Objects of a given type are built exclusively from objects of preceding types (those lower in the hierarchy), thus preventing loops http://en.wikipedia.org/wiki/Type_theory Type thoery takes a step back from contradictary set thoery. It first postulate there exists a hierachial type system before a set is constructed.

Weak type Dynamic Underlying type Strong type Static Topmost type

Paradoxes

well-defined is not very well defined. to avoid these paradoxes, set theory was axiomatized based on first-order logic

Aximorize ZFC Type Theory Ernst Zermelo Abraham Fraenkel Axiom of Choice Type Theory Type is acyclic hierachy

Universal/Empty ∅ {} != {{}} Ω Universe of discourse

Special Instances P N Z Q R C