集合论简介

有限和无穷的这个特点可以从下面的小故事反映出来，这个故事据说是希尔伯特说的。

　　某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为1，2，3，4，……我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合（1，2，3，4，…），称为可数无穷集。

　　有一天开大会，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老板于是引用“旅馆公理”说：“满了就是满了，非常对不起！”。正好这 时候，聪明的旅馆老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬一下，从这间房搬到下一间”。于是1号房间的客人搬到2号 房间，2号房间的客人搬到3号房间……依此类推。最后1号房间空出来，请这位迟到的客人住下了。

　　第二天，希尔伯特旅馆又来了一个庞大的代表团要求住旅馆，他们声称有可数无穷多位代表一定要住，这又把旅馆经理难住了。老板的女儿再一次来解 围，她说：“您让1号房间客人搬到2号，2号房间客人搬到4号……，k号房间客人搬到2k号，这样，1号，3号，5号，……房间就都空出来了，代表团的代 表都能住下了。”

　　过一天，这个代表团每位代表又出新花招，他们想每个人占可数无穷多间房来安排他们的亲戚朋友，这回不仅把老板难住了，连女儿也被难住了。聪明的女儿想了很久，终于也想出了办法。（因为比较繁琐，这里不详细介绍了）

　　希尔伯特旅馆越来越繁荣，来多少客人都难不倒聪明的老板女儿。后来女儿进了大学数学系。有一天，康托尔教授来上课，他问：“要是区间[0，1] 上每一点都占一个房间，是不是还能安排？”她绞尽脑汁，要想安排下，终于失败了。康托尔教授告诉她，用对角线方法证明一切想安排下的方案都是行不通的。

　　由康托尔的定理，可知无穷集合除了可数集台之外还有不可数集合，可以证明：不可数集合的元素数目要比可数集合元素数目多得多。为了表示元素数目 的多少，我们引进“基数”也称“势”的概念，这个概念是自然数的自然推广。可以与自然数集合N一一对应的所有集合的共同性质是它们都具有相同的数目，这是 最小的无穷基数记做ω。（ω是希伯来文字母第一个，读做阿列夫）。同样，连续统（所有实数或[0，1]区间内的所有实数集合）的基数是C.康托尔还进一步 证明，C＝2ω。，问题是C是否紧跟着ω。的第二个无穷基数呢？这就是所谓连续统假设。

集合论的创立

1 集合论的创立和传播

　　集合论的创立者格奥尔格·康托尔，1845年3月3日出生于俄国圣彼得堡（前苏联列宁格勒）一个商人家庭。他在中学时期就对数学感兴趣。1862年，他到苏黎世上大学，1863年转入柏林大学。

　　当时柏林大学正在形成一个数学教学与研究的中心，他在1867年的博土论文中就已经反映出“离经叛道”的观点，他认为在数学中提问的艺术比起解法来更为重要。的确，他原来的成就并不总是在于解决间题，他对数学的独特贡献在于他以特殊提问的方式开辟了广阔的研究领域。他所提出的问题一部分被他自己解决，一部分被他的后继者解决，一些没有解决的问题则始终支配着某一个方向的发展，例如著名的连续统假设。

　　1869年康托尔取得在哈勒大学任教的资格，不久就升为副教授，并在1879年升为教授，他一直到去世都在哈勒大学工作。哈勒是一个小地方，而且薪金微薄。康托尔原来希望在柏林找到一个薪金较高、声望更大的教授职位，但是在柏林，那位很有势力而且又专横跋扈的克洛耐克处处跟他为难，阻塞了他所有的道路。原因是克洛耐克对于他的集合论，特别是他的“超穷数”观点持根本否定的态度。由于用脑过度和精神紧张，从1884年起，他不时犯深度精神抑郁症，常常住在疗养院里。1918年1月6日他在哈勒大学附近的精神病院中去世。

　　集合论的诞生可以说是在1873年年底。1873年11月，康托尔在和戴德金的通信中提出了一个问题，这个问题使他从以前关于数学分析的研究转到一个新方向。他认为，有理数的集合是可以“数”的，也就是可以和自然数的集合成一对一的对应。但是他不知道，对于实数集合这种一对一的对应是否能办到。他相信不能有一对一的对应，但是他“讲不出什么理由”。

　　不久之后，他承认他“没有认真地考虑这个问题，因为它似乎没有什么价值”。接着他又补充一句，“要是你认为它因此不值得再花费力气，那我就会完全赞同”。可是，康托尔又考虑起集合的映射问题来。很快，他在1873年12月7日又写信给戴德金，说他已能成功地证明实数的“集体”是不可数的了，这一天可以看成是集合论的诞生日。

　　戴德金热烈的祝贺了康托尔取得的成功。其间，证明的意义也越来越清楚。因为康托尔还成功地证明代数数的集合也是可数的。所谓代数数就是整系数代数方程的根，而象π与e这样的不能成为任何整系数代数方程的根的数，则称为超越数。

　　早在1847年，刘维尔就通过构造的方法（当时大家认为是唯一可接受的方法）证明了超越数的存在，也就是具体造出超越数来。可是，康托尔 1874年发表的有关集合论的头一篇论文《论所有实代数集合的一个性质》断言，所有实代数数的集合是可数的，所有实数的集合是不可数的。因此，非代数数的超越数是存在的，并且其总数要比我们熟知的实代数数多得多，也就是说超越数的集合也是不可数的。

　　康托尔的这种证明是史无前例的。他连一个具体的超越数都没有举出来，就“信口开河”的说超越数存在，而且比实代数数的“总数”多得多，这怎么能不引起当时数学家的怀疑甚至愤怒呢？

　　其实，康托尔的著作主要是证明了无穷之间也有差别，既存在可数的无穷，也存在那种像实数集合那样不可数的、具有“连续统的势”的无穷。过去数学家认为靠得住的只有有限，而无穷最多只是模模糊糊的一个记号。而康托尔把无穷分成许多“层次”，这真有点太玄乎了。

　　1878年，康托尔发表了集合论第二篇文章，其中把隐含在1847年文章中的“一一对应”概念提出来，作为判断两个集合相同或不同的基础，这就是最原始的等价观念。而两个集合相互之间如果能够一一对应就称为等势，势的概念于是应运而生。

　　从1879年到1884年，康托尔发表了题为“论无穷线性点集”的一系列文章，共有六篇，这些文章奠定了新集合论的基础。特别是在1883年的文章中引进生成新的超穷数概念，并且提出了所谓连续统假设，即可数基数后面紧接着就是实数基数。他相信这个假设正确，但没能证明。这个假设对于二十世纪数学基础的发展起着极其重大的作用。

　　康托尔最后的集合论著作是1895年和1897年发表的两篇文章，其中最重要的是引进“序型”的概念，并定义相应的序数。这个时期，反对集合论的势力逐渐削弱，但是集合论的内在矛盾已经开始暴露出来了。

　　康托尔自己最早发现了集合论的内在矛盾。他在1895年文章中遗留下两大问题未解决：一个是连续统假设，另一个是所有超穷基数的可比较性。他虽然认为无穷基数有最小数但没有最大数，但没有明显叙述其矛盾之处。

　　第一个发表集合论悖论的是意大利数学家布拉里·福蒂，他指出所有序数的集合这个概念的内在矛盾，但是当时认为这也许能够补救。一直到1903年罗素发表他的著名悖论，集合论的内在矛盾才突出出来，并成为二十世纪集合论和数学基础研究的出发点。

　　康托尔的集合论是数学上最具有革命性的理论，因此它的发展道路自然很不平坦。在当时，占统治地位的观念是：你要证明什么，你就要具体造出什么来。因此，人们只能从具体的数或形出发，一步一步经过有限多步得出结论来。至于“无穷”的世界，即完全是超乎人的能力之外，决不是人所能掌握和控制得了的。

　　反对集合论最激烈的克洛耐克认为只有他研究的数论及代数才最可靠。他有一句著名的话：“上帝创造了正整数，其余的是人的工作”。他认为除了由数经过有限多步推出的事实，其他一概无效。他甚至认为圆周率 π都不存在，证明 π是超越数也毫无意义。当时柏林是世界数学的中心之一，克洛耐克又是柏林学派的领袖人物，因此他对集合论发展的阻碍作用是非常大的。克洛耐克在1891年去世之后，阻力一下子减少了，康托尔发挥出自己的组织才能，积极筹建德国数学联合会（1891年成立）以及国际数学家大会（1897年第一届大会在苏黎世召开），给集合论获得承认铺平了道路。

　　另—方面，许多大数学家支持康托尔的集合论。除了戴德金以外，瑞典的数学家米太格－莱夫勒在自己创办的国际性数学杂志“数学学报”（1882年创刊）上，把康托尔集合论的论文译成法文转载，从而大大促进了集合论在国际上的传播。柏林大学教授威尔斯持拉斯也是集合论的同情者，为了捍卫集合论而勇敢战斗的则是希尔伯特。

　　从此，围绕集合论形成了二十世纪初关于数学基础的大论战。

C计算时间代码！

//min_sec.c--把秒转换为分钟和秒
#include
#define SEC_PER_MIN 60 //每分钟的秒数
int main(void)
{
int sec,min,left;
printf("Convert seconds to minutes and seconds!\n");
printf("Enter the number of seconds (<=0 to quit):\n");
scanf("%d",&sec); //读入秒数
while(sec>0)
{
min = sec /SEC_PER_MIN;//截尾后得到的分钟数
left = sec % SEC_PER_MIN;//剩下的秒数
printf("%d seconds is %d minutes. %d seconds.\n",sec,min,left);
printf("Enter next value (<=0 to quit):\n");
scanf("%d",&sec);

}
printf("Done!\n");
return 0;
}

C实现递减

#include
#define MAX 100
int main(void)
{
int count = MAX +1;
while(--count>0)
{
printf("%d bottles of spring water on the wall,"
"%d bottles of spring water!\n",count,count);
printf("Take one down and pass it around.\n");
printf("%d bottles of spring water!\n\n",count - 1);
}
return 0;
}

running.c －－一个对于长跑运动员有用的程序

1 //running.c －－一个对于长跑运动员有用的程序
2 #include
3 const int S_PER_M =60;
4 const int S_PER_H = 3600;
5 const double M_PER_K = 0.62137;
6 int main(void)
7 {
8 double distk,distm;//分别以公里和英里计跑过的距离
9 double rate;//以英里／小时为单位的平均速度
10 int min,sec;//跑步用时的分钟数和秒数
11 int time;//用秒表示跑步的用时
12 double mtime;//跑完1英里所用的时间以秒计算
13 int mmin,msec;//跑完1英里所用时间，以分钟和秒计
14 printf("This program converts your time for a metric race\n");
15 printf("to a time for running a mile and to your average\n");
16 printf("speed in miles per hour.\n");
17 printf("Please enter,in kilometers,the distance run.\n");
18 scanf("%1f",&distk);//%1f表示读取一个double类型的数值
19 printf("Next enter the time in minutes and seconds.\n");
20 printf("Begin by entering the minutes.\n");
21 scanf("%d",&min);
22 printf("Now enter the seconds.\n");
23 scanf("%d",&sec);
24 //把时间转换为全部用秒表示
25 time=S_PER_M*min+sec;
26 //把公里转换为英里
27 distm=M_PER_K * distk;
28 //英里／秒X秒／小时＝英里／小时
29 rate=distm/time*S_PER_H;
30 //时间／距离＝跑完每英里的用时
31 mtime=(double)time/distm;
32 mmin=(int)mtime/S_PER_M;//求分钟数
33 msec=(int)mtime%S_PER_M;//求出剩余的秒数
34 printf("You ran %1.2f km(%1.2f miles)in %d min,%d sec.\n",distk,dist m,min,sec);
35 printf("That pace corresponds to running a mile in %d min.\n",mmin);
36 printf("%d sec.\nYou average speed was %1.2f mph.\n",msec,rate);
37 return 0;
38 }

打印A-Z

利用函数强制转换打印A-Z字母！
#include
#define TEN 90
int main(void)
{
int n =64;
while(n++
printf("%5c",(char)n);
printf("\n");
return 0;
}

如果打印小写的a-z请改数字则是：
#include
#define TT 122
int main(void)
{
int n = 96;
while(n++
printf("%3c",n);
printf("\n");
return 0;
}

C文件读取与保存！

1. C文件读取与保存！
2. #include
3. #include
4. #define MAXT 40
5. #define MAXA 40
6. #define MAXB1 10 //图书的最多本书
7. struct book{
8. char title[MAXT];
9. char author[MAXA];
10. float value;
11. };
12. int main(void)
13. {
14. struct book library[MAXB1];
15. int count=0;
16. int index,filecount;
17. FILE *pbooks;
18. int size = sizeof(struct book);
19. if((pbooks=fopen("book.dat","a+b"))==NULL)
20. {
21. fputs("Can't open book.dat file\n",stderr);
22. exit(1);
23. }
24. rewind(pbooks);
25. while(count
26. {
27. if(count==0)
28. puts("Current contents of book.dat:");
29. printf("%s by %s:$%.2f\n",library[count].title,library[count].author,library[count].value);
30. count++;
31. }
32. filecount=count;
33. if(count==MAXB1)
34. {
35. fputs("The book.dat file is full.",stderr);
36. exit(2);
37. }
38. puts("Please add new book titles.");
39. puts("press [enter] at the start of a line to stop.");
40. while(count
41. {
42. puts("Now enter the author.");
43. gets(library[count].author);
44. puts("Now enter the value.");
45. scanf("%f",&library[count++].value);
46. while(getchar()!='\n')
47. continue;
48. if(count
49. puts("Enter the next title.");
50. }
51. if(count>0)
52. {
53. puts("Here is the list of your books:");
54. for(index=0;index
55. printf("%s by %s:$%.2f\n",library[index].title,library[index].author,library[index].value);
56. fwrite(&library[filecount],size,count-filecount,pbooks);
57. }
58. else
59. puts("No books?Too bad.\n");
60. puts("Bye.\n");
61. fclose(pbooks);
62. return 0;
63. }

Scheme/Lisp宏定义-Let

(define-syntax my-let
(syntax-rules ()
((_ ((n v)) e1 e2 ...)
(let ((n v)) e1 e2 ...))
((_ ((n1 v1) (n2 v2)) e1 e2 ...)
(let ((n1 v1))
(my-let ((n2 v2))
e1 e2 ...)))))
(my-let ((x 1) (y x))
(+ x y))
let* 函数的完全构造过程！

我们经常使用的let*就是以上代码？也就是它的原函数体的实现。

阴阳迷题的原始代码

(define call/cc call-with-current-continuation)

;(let* ((yin ((lambda (foo) (display "@") foo) (call/cc (lambda (bar) bar))))
; (yang ((lambda (foo) (display "*") foo) (call/cc (lambda (bar) bar)))))
; (yin yang))
;;;阴阳迷题的原始代码

(define bar (lambda (bar) bar))
(define foox (lambda (foo) (display "@") foo))
(define fooy (lambda (foo) (display "*") foo))

;(let* ((yin (foox (call/cc bar)))
; (yang (fooy (call/cc bar))))
; (yin yang))
;;;第一次简化后的代码

;(let ((yin (foox (call/cc bar))))
; (let ((yang (fooy (call/cc bar))))
; (yin yang)))
;;;第二次简化后的代码

((foox (call/cc bar)) (fooy (call/cc bar)))
;;;最后去掉let的代码

Scheme/Lisp高级属性（2）

---------------------------------------------------------------------
require 调用函数库，调用当前系统时间，date是linux系统命令，如：
(require (lib "process.ss")
(system "date")
---------------------------------------------------------------------
quasiquote 准引用
(quasiquote '(1 2 3))=> '(1 2 3)
还有一用法加@：
`(1 ,@(cdr '(boy gril) 'bave))
Scheme/lisp本身很灵活，只要想得到就做得到，我这里举出以上两种方法
---------------------------------------------------------------------
map函数，将函数施加到一个列表进行计算：
(map (lambda (x)
(* x x))
'(1 2 3)) =>1 4 9
还有一写法
(map (lambda (x y)
(* x y))
'(1 2 3) '(4 5 6)) =>4 10 18
Scheme/lisp本身很灵活，只要想得到就做得到，我这里举出以上两种方法
---------------------------------------------------------------------
for-each将列表转化为函数
(for-each
(lambda (x)
(display x))
'(1 2 3))=>123
可以用换行函数(newline)看得更明白，这里是 1 ， 2 ， 3不是123呵呵mzscheme解释出来是这样的，为了好看最好加上(newline).
---------------------------------------------------------------------

Scheme/Lisp高级属性（1）

------------------------------------------
;;;;do相当于c语言里的for.
(do ((i 0 (+ i 1))
(j 0 (- j 1)))
((= (+ i j) 2))
(begin
(display "laohuo")
(newline)
(display "henlaohuo")
(newline)))
-------------------------------------------
;;;;判断读取一个文件的某一字符，当程序读取时判断当前字符是否x如果是 则终止程序打印出该字符的前一部分 no.直到读取到这一个字符才停止。
(let ((in (open-input-file "foo.bar")))
(do ((c (read-char in) (read-char in)))
((eqv? c #\x)
(degin
'yes
(close-input-port in))
(degin
(display c))) c))
-------------------------------------------
;;;;判断读取一个文件的某一段，当程序读取到字符#或g打印出yes,如果读取到m或n 则打印 no.直到读取到这两个判断中的某一个字符才停止
(let ((in (open-input-file "foo.bar")))
(let loop ((c (read-char in)))
((case c
((#\# #\g) 'yes)
((#\m #n) 'no)
(else
(loop (read-char in))))))
-------------------------------------------
read-line (读取整行）

some notes

Article appeared：http://citypw.blogspot.com/ Shawn's Blog!

I was "trapped" in somewhere which is a gift from Lord Jesus.Im just here,to hacking.make a preparation for cultural mission that for glorify Him.Im going no where for next 6 months.stay here...be here...forget what i know at first.what's the purpose of my life?I have to answer it,thats why im here.Im searching the Tao(logos) from any fields what i can understand.math,computing,philosophy...oohh yeah~reformed theology is the best one.Thank to Von neumann,Alonzo Church,Alan Turning,Soren Kierkegarrd,Blaise Pascal,John Calvin,St Augestine,author of Hebrews(in new testament)......The Trinity God--Holy FATHER HOly SON HOly SpIrit.

People has necessary needs that not love,not money,not fame,even not the faith,but give me truth.

Happy hacking!my brothers!

首 先谈谈哲学观对于我们认知事物的影响,认知科学的基础就是找出异同关系,道在最早时处于混沌状态,道要可道的第一步就是化分领域的界限,比如科学 (sicence),哲学(philosophy),etc.而第二步则是探讨非科学(non-sicence),非哲学(non- philosophy),etc的这种"非我"的形态.从本质上,也是一种信息的传递,而在这一方法中又有四个必须面对的问题:
1,主体.进行认知过程的人.
2,客体.被进行认知过程的人进行认知的事物(包含上帝,自己,人和物质).
3,环境.进行认知的人必须被限定的范围内.
4,媒介.通过人的五官等媒介进行信息传递.

系统,即广义的硬件和广义的软件的复合;在认知系统的过程中就会有更加直接的方法可
以参考:
以计算主义在面对DNA配对关系问题为例,
1,观察.对DNA配对的本身进行观察.
2,实验.用物理的仪器对DNA进行实验.
3,推理.通过观察和实验建立有效的计算模型,他们假设了一个前提,即如果人类有一台计算
能力为2的78次方的"终极量子计算机",那这个问题是可解决的,反之既然.
4,计算.由于这个问题的计算量是3的500次方,因此放弃计算.

之后谈到了数学中的分类,大类主要分为:集合论,组合数学,数理逻辑,图论,代数结构.集合
论主要是研究确定行止的对象.而数理逻辑中又分为了几个主要的分支:
1,证明论;
2,公理集合论;
3,递归论;
4,模型论

之后谈到了数学的一些方法,比如分析,拓扑和概率.当然变分变法变是最有趣的一个思想试验,
我们无法观测到这个世界的本质一样,即蚂蚁以二维的方式无法观测到生活在三维空间的人类,而人类也无法理解更高层的世界.这个我想需要更多的了解了数学史可以有更加深入的思考.

之 后谈到了中国先秦哲学<易经>对于现代数学的类比,道是无形的,道看似无为,却有无所不为.但站在人类有限理性的角度去认知道的本身是一件很 难的事情,所以我们只能认识到那有限的"道,可道"(logy),却无法看清楚"非,常,道"(logos),在这种境况下古代的先哲们也有自己的方法去 了解这个世界,即异同和对比的方法,简单的来讲,也就是先认知到混沌中的边界:阴和阳.

之后以此为基础去推导出这个宇宙的规律如下:
阳是physical,阴是metaphysical.
阳:阳,古字(正),可知.
阴:阳,古字(常),常态.
阳:阴,古字(奇),不可测度,cant measurable.
阴:阴,古字(浑),不可知.

阴和阳再与以上的结果对比,最后就产生了八卦:
乾,古字(天),集合A,辖域.
坤,古字(地),集合B隶属于集合A.
天地乃时空的描述.<老子>上讲"人法地,地法天,天法道,道法自然",也就是说站在人最低级的
位置,只需要地就可以作为人的尺度,而人透过对天地的认识建立了时空观,在希伯来旧约圣经
里谈到"地"时也指的是低级的价值和刻度,如"不要思念地上的事","人终归于尘土"即非永恒性的事物,而在犹太人的文化中探寻永恒性是重要的.

兑,古字(泽)
艮,古字(山)
道如流水行云,山和水的特性就想如此,和拓扑有类比的关系,外表变化无偿,而内部固定不变,
我们可以看到水是有形的,而它的形又不断的变化,但是它的本质是不会发生变化的,这种变化
就尤如阳和阴的转换,阳是主动的,而阴则是被动的.

震,古字(雷)
巽,古字(风)
雷和风代表这能量,前者的能量存在方式是离散的,至少以人的尺度来认知是这样,而风的能量
则是连续性的,此二者代表了能量的传递方式.

离,古字(日)
坎,古字(月)
日和月表示了信息的本身,日即太阳的周期从人的基本观察是每日一次,而月亮是每月一次,这
或 许是命名的原因.在信息论当中,信息的改变频率越高,熵则越大,即信息量越大.新约圣经希伯来书讲到:"神既在古时借着众先知,多次多方的晓谕列祖,就在 这末世,借着他儿子晓谕我们,又早已立他为承受万有的,也曾借着他创造诸世界.Hebrew 1:1--2".这里的"多方"英文是"various ways",而"多次"则是"many times",主动性的是"神",被动者是"列祖"对应"我们",媒介则是"众先知"对应"他儿子"(指耶酥基督),时间的刻度是"古时"对应"末 世".various ways有点类似C++里的GP,更类似于lambda calculus,一个lambda的左结合可以接收任何的信息(广义上的lambda).

How does a mathematician describing the relationship?
1,words.eg,man and woman:a couple
pro:描述确切,用于写作.
con:不直观
2,graph theory.
pro:直观,用于授课.
con:元素较多后描述比较复杂
3,matrix.
pro:在计算机中表达方便,也易于在计算机中进行计算,用于写程序.
con:不直观,元素较多后描述复杂.

集合论中的关系,泛序关系
reflexive relation(自反关系):x R x,一个元素与自己的关系.
只要存在的元素就肯定有自反关系,对自我存在的一种关系的描述是
很重要的,比如人类就具备这种关系,经过了数千年的存在主义(Existentialism)哲学探讨至今基本分为2种:
1,主体性的观察的存在,即只要你能够明白(understand),认知(know)和相信(faith)的就是存在,不能明白,认知和相信的就是对主动认知的主体(人类)的不存在.

2,客观性的存在,即实在存在(existing theory),客观真理是存在的,客观真理是不由主动观察的主体(人类)的意志而变化,比如宇宙中最基本微粒的碰撞所形成的今天这个物质世界的事件在人类能够观察以前就已经存在.

不过以上2者到最终都必须面对一个极其困难但又是至关重要的问题,即存在的意义是什么?或者说存在的意义是谁赋于的?

symmetric relation(对称关系):x R y => y R x
比如兄弟关系,x是y的兄弟,而y肯定也是x的兄弟.

asymmetric relation(非对称关系):x R y
<和>都是属于这种关系,即x<> x=y
1>=1,1& lt;=1,比如MD5的加密也是属于反对称关系,MD5先把原有的明文转化成密文,也生成一个效验sum,原文和密文其本质都是一样,但密文不能通过明 文来进行比较,只能通过效验sum来比对. identity relation(恒等关系): 对角线上的所有的点. transitive relation(传递性关系):(x R y,y R z) => z R x
1<2<3,1<3.> #t

(define x 1)
(eqv? x 1) => #t

(define func (lambda (n) (* n n)))
(eqv? x (lambda (n) (* n n))) => #f

(eqv? "hello" "hello") => #t

等价聚类的结果:商集
商化:U/R
积化:从不相交的集合组成新的set.
eg,{N} {1,2,3,4...}/7
1*7+3=10
2*7+3=17
3*7+3=24
=> {10,17,24...}/同余同关系R

分类对策:cond
eg:
(define pnz (lambda (x)
(cond
((> x 0) "positive")
((<> "is 0"

良序集合:有头元素的全序集合是良序集合(well-ordered set)

泛序关系:广泛的次序
eg:
'(5 (4 . (3 . ()))
(2 . (1 . ())))
=>(5 (4 3) (2 1))

we have done some type-transform test in computer.one of important is
that string->list then list-> if we want to convert string into vector.

逻辑Logic
关于历史上出现过的logic探讨:
1,古代中国的墨子对名和实的探讨,公孙龙对白马是马的一个名字的探讨.韩非子的"自相矛盾"的典故.

2,古代印度的英明学派对"宗,喻,名"的探讨.

3,古代希腊的亚里士多德(Aristotle)的逻辑学中的三段论进行了阐述,即大前提+小前提=结论.逻辑学遵守3个规律:
1,同一律,专注在同一个事情,不能偷换概念.
2,矛盾律,不能自相矛盾.
3,排中律,不能似是而非.eg,即不是男的也不是女的.

斯多葛学派的创始人是Zeno,他们最大的贡献是提出了命题和演绎逻辑.

逻辑学探讨的3个方面:
1,基础逻辑,探讨人的思维的规律.
2,原逻辑,探讨逻辑本身.
3,应用逻辑,比如电子上的数字逻辑.

逻辑的分类大体上分为:形式逻辑和辩证逻辑
形式逻辑又大体分为:演绎逻辑(Aristotle,Zeno)和归纳逻辑(Francis Bacon)
演绎逻辑大体分为:传统演绎逻辑和数理逻辑(用集合论来看待关系的演化)

逻辑的方法
1,概念
很多概念组成了2,判断
很多判断组成了3,推理

推理在遵守3律的情况下有3中形式:
1,演绎,即大前提+小前提=结果
2,归纳推理,一组同质的对象的观察.eg,如果观察100只大象都有鼻子,判断大象是有鼻子的.
3,类比推理,观察2类对象的性质.

The first paradox in math
逻辑的规则,在毕达哥拉斯看来万物的本源就是数,即所有的数可以用2个正数比
对(有理数).

此悖论是Hippasus(希伯斯)提出.

一个正方形,边为1,对角线为square root of 2(根号2),但是1~2+1~2!=~/2
eg,
反证法:
假设square root of 2 is rational number.
~/2 = p/q (p,q属于z)
z=p^2/q^2
p^2=2q^2
p^2是偶数
p*p是偶数
p是偶数
p=2r (r属于z)
p^2=4r^2

4r^2=2q^2=>2r^2=q^2
q也是偶数
q=2m (m属于z)
p=2r

p/q=2r/2m (可以归约)
所以~/2不是有理数

谈到了dedekind cut,即一条数轴上有无数多个数,用x把2边的书切分开,x可能是有理数,也可能不是.
1,x*x<2>2
可以逐步逼近的方式来求平方根.eg:
(define q3 (lambda (n x)
(cond
((= (* x x) n) x)
((> (* x x) n) (- x 0.001))
((< (* x x) n) (q3 n (+ x 0.001)))))) (q3 2 1.0)=>1.141
(q3 3 1.4)=>1.732
(q3 3 1.5)=>1.732
(q3 4 1.0)=>2

数理逻辑和可计算性理论有很大的关系.
lambda-calculus,作者是Alonzo Church
从数学的角度看:
A,y=x^2+2x+1
B,y=(x+1)^2
A=B

从存在性的角度看以上正确,但从构造性的角度看则不然,如下:
A,y=x*x+2*x+1
B,y=(x+1)*(x+1)

eg:
A,(+ (* x x)
(* 2 x)
1)

B,(* (x+1) (x+1))

所以轮到lambda出场了:
lambda-exp ::= {constant}
|{varibale}
|{lambda-exp1} {lambda-exp2}
|lambda {variable} . {lambda-exp}

两个lambda-exp有2种方式求值:
1,normal ordered:"fully expand and then reduce"
evaluate the lambda-exp1 at first

2,application ordered:"evaluate the arguments and then apply"
evaluate the parameter at first.

eg,a procedure which from sicp can provide a test for make sure whether the
interpreter is normal ordered or application ordered.
(define (p) (p))

(define (test x y)
(if
(= x 0) 0
y))

(test 0 (p))
=>if dead loop,it's application ordered.
app is (lambda (0 (p)))
=>0,it's normal ordered.

if we have a procedure which living in a Interpreter,it would be
maintained by sybolic table like below:
(define square (lambda (x) (* x x)))
---------------------------
|square|lambda(x) (* x x) |
|--------------------------
| |

what is algorithm?Aha,algorithm!
在有限的步骤内完成问题的求解.
real problem->philosophy thinking->math model->computing model->coding
glossary:indefinitely small=im
im>0,|x-A|
无穷小 2 无穷大

套区间,有自然数的特性.
induction:
1+2+3+...+n= n(n+1)/2

1,if n=1, 1= 1(1+1)/2
2,if n=k, 1+2+3+..+k= k(k+1)/2
3,n=k+1, 1+2+3+..k+(k+1),
k(k+1)/2+2(k+1)/2= k(k+1)+2(k+1)/2
=(k+1)(k+2)/2=> n(n+1)/2

组合:C(n r),r<=0,n中选择r个元素. 排列:P(n r),r<=0 P(n r) C(n r) * r! C(n r) = n!/(n-r)! 1,2,3...r........n ------------------>
|__r___| |_(n-r)__|

eg:
(define tail-fac (lambda (x)
(let loop ((n x) (acc 1))
(if
(= n 0) 1
(if
(= n 1) acc
(loop (- n 1) (* n acc)))))))

(define fac (lambda (n)
(if
(= n 0) 1
(* n (fac (- n 1))))))

(define fib (lambda (n)
(cond
((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1)) (fib (- n 2)))))))

(define tail-fib (lambda (x)
(let fib ((n x) (acc1 0) (acc2 1))
(if
(= n 0) 0
(if
(= n 1) acc2
(fib (- n 1) acc2 (+ acc1 acc2)))))))

the recognize process:material->sybolic system->new recognition
自 然数,是人类认知最直接的数,19世纪的德国数学家Leopold Kronecker曾经讲"God made the integers; all else is the work of man" (Bell 1986,p. 477).上帝创造了自然数,其他数都是人造的.自然数在圣经中也有严肃而有趣的联系,圣经中描述的三位一体(trinity)的上帝,三个位格分别是圣 父,圣子和圣灵,在犹太人的先知赞美上帝时呼喊"圣哉!圣哉!圣哉!"也是3次,耶酥基督对于自我的存在性的实在和意义的宣称"我是道路,真理与生命". 也是3,圣经中关于3的描述还不止于此,但关于在描述方向时就不是3而是4,4个方向:东,南,西,北;同时也有四季:春,夏,秋,冬.而表示绝对创造者 本身的3和作为被造相对者的人类产生关系时,即3+4=7,一个礼拜有7天,罗马帝国曾经尝试把一个礼拜搞成5天,结果把人们搞的都不想做事情(和前新教 伦理有关系),斯大林也尝试把一个礼拜搞成10天,结果弄的不少苏联人得了累的要死.7天是最适合人类的,圣经中7的描述也有很多,包括对教会,节日(7 年释放一次奴隶).同时7在希伯来文化中也代表一个完整的过程.自然数7到今天也影响着我们,一个礼拜仍然是7天,Intel的员工都盼望着7年一次的长 假,etc.我们对自然数的确是有先验式的敏感,所以很多方法论也由此而生,eg:尝试把数学上的描述都能够简化到用自然数系.

the basic Primitive recursion function:
1,Constant function:The 0-ary constant function 0 is primitive
recursive.(if n =1)

2,Successor function:The 1-ary successor function S, which returns the
successor of its argument (see Peano postulates), is primitive
recursive. That is, S(k) = k + 1.

3,Projection function:For every n≥1 and each i with 1≤i≤n, the
n-ary projection function Pin, which returns its i-th argument, is
primitive recursive.

General Function:
1,前继,n!(fac)
2,后续,(n-1)!(fac (- n 1))
3,测零,(= n 0)
4,不动点算子,1

eg:
(define a (lambda (n)
(if (= n 0) 1
(* n (fac (- 1))))))

Church-Turning thesis
1,Church's thesis: "Every effectively calculable function (effectively
decidable predicate) is general[1] recursive" (Kleene 1952:300)
可计算函数都可以用一般递归函数构造.

2,Turing's thesis: "Turing's thesis that every function which would
naturally be regarded as computable is computable under his
definition, i.e. by one of his machines, is equivalent to Church's
thesis by Theorem XXX." (Kleene 1952:376)
一切递归函数可以用一般递归函数(1..4)来构造

reduce-law:
alpha:λx.exp-->λy.exp [y/x]
beta: <λ-exp1><λ-exp2>--> <λx.exp1> [/x]
eta:(λx.exp)y--> λ-exp

bound variable:
((lambda (n) (* n n)) 6)=>36
(let ((n 6)) (* n n))=>36

block structure里只能通过arguments作为外部能见的接口.

regular-exp cant be reduced.

Church-Rosser TH I
is x--(reduce)->y,so x->z->y.存在性

Church-Rosser TH II
x--->y.构造性

Ackerman function
{n+1 if m=0
A(m,n)={A(m-1,1) if m>0 and n=0
{A(m-1,A(m,n-1)) if m>0 and n>0

(define ackermann (lambda (m n)
(cond
((= m 0) (+ n 1))
((and (> m 0) (= n 0)) (ackermann (- m 1) 1))
((and (> m 0) (> n 0)) (ackermann (- m 1)
(ackermann m (- n 1)))))))

ackermann(1,5)

(a 0 (a 1 4))
(a 0 (a 0 (a 1 3)))
(a 0 (a 0 (a 0 (a 1 2))))
(a 0 (a 0 (a 0 (a 0 (a 1 1)))))
(a 0 (a 0 (a 0 (a 0 (a 0 (a 1 0))))))
(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 1))))))
(a 0 (a 0 (a 0 (a 0 (a 0 2)))))
(a 0 (a 0 (a 0 (a 0 3))))
(a 0 (a 0 (a 0 4)))
(a 0 (a 0 5))
(a 0 6)
7

scheme中lambda表达式的形参表有3种接收参数的`方式:
1,定长,eg:
(define square (lambda (n) (* n n)))
(square 5)=>25

2,全定长,eg:
(define foo (lambda x x))
(foo 1 2 3)=>(1 2 3)

3,半定长,eg:
(define f (lambda (x . y) (* x x)))
(f 10 20 30)=>100

(define f (lambda (x y . z)
(begin
(display (+ x y))
(newline)
(car z))))
(f 20 30 10 20 30)=>50
10
此方式在C语言中的printf函数是很好的体现.

tail-recursive version of n!
(define tail-fac (lambda (x)
(let fib((n x) (result 1))
(if (= n 0) result
(fib (- n 1) (* result n))))))

odd? or even?
(letrec ((odd? (lambda (n)
(if (= n 0) #f
(even? (- n 1)))))
(even? (lambda (n)
(if (= n 0) #t
(odd? (- n 1))))))
(odd? 98))
=>#f

count n...1 or count n...1
(define Nto1 (lambda (n)
(let count((x n))
(if (= x 0) x
(begin
(display x)
(newline)
(count (- x 1)))))))

(define 1toN (lambda (n)
(let count((x 1))
(if (<= n x) x (begin (display x) (newline) (count (+ x 1))))))) ;Exercise 1.3. Define a procedure that takes three numbers as arguments and ;returns the sum of the squares of the two larger numbers. (define square (lambda (x) (* x x))) (define sum-of-square (lambda (a b) (+ (square a) (square b)))) (define sum-2-square (lambda (x y z) (cond [(and (<= x y) (<= x z)) (sum-of-square y z)] [(and (<= y x) (<= y z)) (sum-of-square x z)] [(and (<= z x) (<= z y)) (sum-of-square x y)] ))) (define sum-2-square2 (lambda (x y z) (cond ((and (>= x z) (>= y z)) (sum-of-square x y))
((and (>= x y) (>= z y)) (sum-of-square x z))
((and (>= y x) (>= z x)) (sum-of-square y z)))))

;Exercise 1.12. The following pattern of numbers is called Pascal's triangle.
; 1
; 1 1
; 1 2 1
; 1 3 3 1
; 1 4 6 4 1
;The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of
;the two numbers above it.35 Write a procedure that computes elements of Pascal's triangle by means
;of a recursive process.

(define pascal (lambda (x y)
(cond
((= x y) 1)
((= x 1) 1)
((= x 2) 1)
((= y 1) 1)
(else
(+ (pascal (- x 1) y) (pascal (- x 1) (- y 1)))))))

;Exercise 1.30. The sum procedure above generates a linear recursion. The procedure can be
;rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing
;expressions in the following definition:
;(define (sum term a next b)
; (define (iter a result)
; (if
;
; (iter )))
; (iter ))

(define (inc n) (+ n 1))
(define (idents x) x)
(define (sum-int a b)
(sum idents a inc b))

(define (sum2 term a next b)
(let iter((a a) (result 0))
(if (> a b)
result
(iter (next a) (+ result (term a))))))

(define (inc n) (+ n 1))
(define (idents x) x)
(define (fac n)
(product2 idents 1 inc n))
;recursive
(define product (lambda (term a next b)
(if (> a b)
1
(* (term a) (product term (next a) next b)))))
;iterative
(define product2 (lambda (term a next b)
(let loop((a a) (result 1))
(if (> a b)
result
(loop (next a) (* result (term a)))))))

Article appeared：http://citypw.blogspot.com/ Shawn's Blog!

lambda演算

(define fo (lambda(bar) ;lambda=匿名函数

(* bar bar))) ;bar的平方，是它自身乘以自身

(define f1 "B.Hacking") ;定义f1变量，是将“B.Hacking”当作函数参数传给F1

(define f2 #\t) ;#\t代表字符串的意思。

(set! fo #\b) ;重新定义fo，在这样的情况下，使用set!定义fo前面使用define定义的fo 会被set!定义的foo取代掉，就列如C语言里面的指针，当C中的指针指向另一个地址时，前面的指针会被取代掉。在scheme中会被垃圾回收机制自动回收。

(set! fo #\q) ;如果我们另外在重新定义一个字符串，运行看看，结果变化为#\q，而先前的#\b却被替换掉，那么#\b在哪里去了，因为这个#\b已经没用了，也就成为了垃圾数据，这个时候被垃圾回收机制回收。

我真真感受了下Scheme的lambda演算，也是第一次完全明白define与set！的定义，可能我的理解和大家不同，也许大概是个人原因吧，我喜欢这样去理解它。

The use recursion sorting

The use recursion sorting

Generally recursion:
------------------------------------------------------------------------------------
(define (f x)
(if (null? (cdr x))
(list (car x))
(append (f (cdr x)) (list (car x)))))
------------------------------------------------------------------------------------
Tail recursion:
------------------------------------------------------------------------------------
(define (f x)
(let loop ((n x) (l '()))
(if (null? (cdr n)) (cons (car n) l)
(loop (cdr n) (cons (car n) l)))))
------------------------------------------------------------------------------------
Equal tail recursion :
------------------------------------------------------------------------------------
(define (foo x)
(let loop((n x) (l '()))
(if (null? (cdr n)) (append (list (car n)) l)
(loop (cdr n) (append (list (car n))l)))))
------------------------------------------------------------------------------------
This is the Scheme/Lisp procedure !!

Scheme/Lisp Tail recursion:

Scheme/Lisp Tail recursion:

(define foo (lambda (x)
(let loop(lambda((i n)(k 1))
(if (= i 0)k
(loop (- i 1) (* i k)))))))
鹧鸪天，尾递归
山上林荫布谷闻，啼声似已悟经纶。
调神静坐调息气，遍历循环闹梦魂。
何处止？但求真，清晨苦思到黄昏。
常年困惑今春了，雨打梨花深闭门。
------------------------------------此诗乃改编-----------------------