離散數學筆記（3.4）集合的歸納定義

一、集合的歸納定義

集合定義的另兩種方式：列舉法、描述法

歸納定義

基礎條款：規定某些元素為待定義集合成員，集合其它元素可以從基本元素出發逐步確定；

歸納條款：規定由已確定的集合元素去進一步確定其它元素的規則；

終極條款：規定待定義集合只含有基礎條款和歸納條款所確定的成員。

基礎條款和歸納條款稱作“完備性條款”，必須保證毫無遺漏產生集合中所有成員；

終極條款又稱“純粹性條款”，保證集合中僅包含滿足完備性條款的那些物件。

例1：歸納定義：偶數集合

個體域

為自然數集，定義偶數集

基礎條款：

歸納條款：若

，則

終極條款：除了有限次使用上述條款確定的元素以外，

中沒有別的元素

例2：歸納定義：程式

基礎條款：v：=e是程式（其中v是變數，e是算術表示式）

歸納條款： ①若p1，p2是程式，則p1；p2也是程式；②若p1，p2是程式，則if c then p1 else p2 end if也是程式（其中c是條件表示式）；③若p是程式，則while c do p end while也是程式；

終極條款（略）

二、自然數定義

數學中“數”是最基本的原始概念，在集合論創立之後，採用集合來定義自然數，使得數學建立在更為簡單的概念“集合”基礎之上。

1.在算術公理化系統中，皮亞諾(Peano)的5大公理刻畫了自然數概念

P1：至少有一個物件是自然數，記做0；

P2：如果n是自然數，那麼n必定恰有一個直接後繼，記做n‘

P3：0不是任何自然數的直接後繼

P4：如果自然數m，n的直接後繼m’，n‘相同，那麼m=n

P5：沒有不滿足上述條件的物件是自然數

2.自然數集N的歸納定義

基礎條款：

歸納條款：如果

，則

終極條款（略）

於是自然數集有如下形式：

實際上有：

①

，

，

，

②

，同時也有

③

，同時也有

體現了順序關係，而且子集關係具有傳遞性。

3.加法的定義

例如：3+2=（3+1）’ =（（3+0）‘）’ =（3‘）’=4‘=5

4.乘法的定義

例如：3×2＝（3×1）+3 =（（3×0）+3）+3=（0+3）+3 =（0+2）’+3 =（（0+1）‘）’＋3=（（（0+0）‘）’）‘+3 =（（0’）‘）’+3 =3+3=……=6