【computer theory】一、集合、關系和語言

1.1集合

1.2關系和函數

1.2.1數學研究關于對象以及它們之間的關系和陳述。

關系本身看作集合。屬于關系的對象在本質上是是的關系成立的個體的組合。

因而小于關系式第一個數小于第二個數的所有數對組合的集合。

1.2.2有序對、笛卡爾積，有序組

函數，滿射，單射，雙射

1.3特設類型的二進制關系

有向圖，邊，頂點

自反、對稱、反對稱、傳遞

把自反、對稱和傳遞的關系叫做等價關系。

自反、反對稱和傳遞的關系叫做偏序。

極小元：存在于偏序關系中

全序：任意兩個元素都滿足偏序關系。

1.4 有窮集合與無窮集合

等勢：如果集合A到集合B存在雙射

與自然數集合N等勢的結合是可數無窮的，有窮的貨可數無窮的集合稱為可數的。

1.5三個基本的證明技術

a.數學歸納法的原理

b.鴿巢原理：設A和B是兩個有窮結合且|A|>|B|，則不存在從A到B的一對一的函數

c.對角化原理。設R是集合A上的二進制關系，D={a:a屬于A,且(a,a)不屬于R}稱作R的對角線集合。對于每個a屬于A，令Ra={b:b屬于A，且(b,b)屬于R}，則D與每一個Ra都不相同。

對角線的補與每一行都不同。

集合2N是不可數的。