偽樹

偽樹(pseudo-tree)是由鏈組成的一種集合，在偏序集〈A，R〉中，若對任何a∈A，所有滿足bRa的A中元素b的集合B都是R鏈，則稱〈A，R〉為一棵偽樹，而集合B稱為樹枝。

基本介紹

• 中文名：偽樹
• 外文名：pseudo-tree
• 所屬學科：數學（集合論）
• 簡介：由鏈組成的一種集合

基本介紹

定義 一偏序集合<S，R>叫做關於R的一偽樹，如果，對於每一x∈S，則x的R前節：

都是S的一個R-鏈，並稱它為樹枝。

圖1

全序集是一棵偽樹，並且它的枝疊合在一起，偏序結構〈A，R〉成為偽樹時，其哈塞圖在直觀上像一棵或多棵分離開的樹，只有向上的分叉，而無向下的分叉，並且無閉合的枝。如圖1表示的結構是偽樹，而圖2、圖3表示的結構不是偽樹。當〈A，R〉是偽樹時，〈A，R〉稱為倒偽樹。

圖2

圖3

例題解析

【例1】令S={2，4，6，8，10}，偏序<S，1_s>是—偽樹，因為它的任一元的1_s前節都是一1_s鏈。

圖4

【例2】令S={2，8，10，20，16，24}，那么偏序集合<S，1_s>也是一偽樹。

圖5

【例3】令S={2，8，10，16，20，24，32，96}偏序集合<S，1_s>如圖4所示，它不是一偽樹，因為96的1_s前節O_1s(96)={32，16，24，8，2}，而24與16在1_s下不可比較，不構成一個1_s鏈。

圖6

【例4】偏序結構{ω，∈ω)是一偽樹。