Chương I
CẤU TRÚC THỨ TỰ TRÊN VÀNH BOOL HỮU HẠN
T
rong chương này, chúng ta xét một lớp vành đặc biệt, lớp các vành Bool
hữu hạn. Cho một vành Bool hữu hạn B bất kỳ (có 2
n
phần tử). Chúng ta chỉ ra rằng
B đẳng cấu với vành Bool Z
2
xZ
2
x…x Z
2
(có n thừa số). Hơn nữa, P(X) gồm tất cả
các tập con của tập X với phép giao và tổng đối xứng cũng là một vành Bool có 2
n
phần tử, nên P(X) đẳng cấu với B mặt khác các đẳng cấu này bảo toàn quan hệ
thứ tự do đó để thuận tiện cho việc trình bày. Trong một số trường hợp, chúng tôi
chọn vành Bool Z
2
xZ
2
x…x Z
2
để làm việc. Kế tiếp, chúng tôi trình bày một số khái
niệm và kết liên quan đến quan hệ thứ tự trên B cần thiết cho chương sau.
§1. Các khái niệm về vành Bool
Đònh nghóa 1.1. Một vành B có đơn vò được gọi là vành Bool nếu mọi phần
tử x ∈ B thỏa x
2
= x.
Một ví dụ quen thuộc về vành Bool là tập P(X), tập tất cả các tập con của
tập X khác rỗng, cùng với hai phép toán ∩ và Δ ; trong đó ∩ là phép giao thông
thường của hai tập hợp và Δ là phép cộng đối xứng xác đònh như sau: ∀ A, B ∈
P(X) AΔB = (A \ B) ∪ (B \ A). Và để thuận tiện cho việc trình bày về sau ta viết ∩
theo lối nhân (.) và Δ theo lối cộng (+).
Bây giờ ta chứng minh (P(X),+ ) là một vành Bool. Ta cần kiểm tra các tiên
đề của vành:
• Phép toán cộng có tính kết hợp :
∀A, B, C ∈ P(X), ta cần kiểm tra: (A + B) + C = A + (B + C)
i) Chứng minh (A + B) + C ⊂ A + (B + C)
Lấy x ∈ (A + B) + C, khi đó ta có:
x ∈ C \ [(A \ B) ∪ (B \ A)] hoặc x ∈ [(A \ B) ∪ (B \ A)] \ C
+ Nếu x ∈ [(A \ B) ∪ (B \ A)] \ C thì x ∈ (A \ B) ∪ (B \ A) và x ∉ C
tức là x ∈ A \ B ; x ∉ C hoặc x ∉ B \ A ; x ∉ C
+ Trong trường hợp thứ nhất ta có : x ∈ A ; x ∈ B ; x ∈ C
do đó x ∈ A và x ∉ (B \ C) ∪ (C \ B)
3
tức là: x ∈ A \ [(B \ C) ∪ (C \ B)].
+ Trong trường hợp thứ hai, ta có x ∈ B, x ∉ A, x ∉ C
do đó : x ∈ (B \ C) ∪ (C \ B) và x ∉ A
tức là : x ∈ [(B \ C) ∪ (C \ B)] \ A
nên x ∈ A + (B + C)
Vậy (A + B) + C ⊂ A + (B + C)
ii) Chiều ngược lại: A + (B + C) ⊂ (A + B) + C. Chứng minh tương tự.
Vậy (A + B) + C = A + (B + C).
• Phép toán cộng có tính giao hoán : Với mọi A, B ∈ P(X) ta có :
A + B = (A \ B) ∪ (B \ A) = (B \ A) ∪ (A \ B) = B + A
• Phép cộng có phần tử không là tập
φ
vì ∀A ∈ P(X), ta có :
A + Φ = (A \
φ
) ∪ (
φ
\ A) = A
• Phần tử đối của phần tử A là phần tử A vì :
∀ A ,A + A = (A\A) ∪ (A\A) ∈ (A\A) =
φ
• Tính kết hợp của phép nhân : ∀A, B, C ∈ P(X) ta có :
(A ∩ B) ∩ C = A ∩ (B ∩ C) nên (AB)C = A(BC)
• Phép toán nhân phân phối với phép toán cộng : ∀A, B, C ∈ P(X) ta có :
A(B + C) = A [(B \ C) ∪ (C \ B)]
= [A (B \ C)] ∪ [A (C \ B)]
= [A B \ AC] ∪ [AC \ AB]
= AB + AC
và (B+C)A = [(B \ C) ∪ (C \ B)] A
= [(B \ C) A] ∪ [(C \ B) A]
= (BA \ CA) ∪ (CA \ BA)
= BA + CA
• Phép toán nhân có phần tử đơn vò là X vì ∀ A ∈ P(X)
XA = A ∩ A = A
AX = A ∩ X = A
4
Vậy P(X) là vành Bool.
Nhận xét :
Trong vành Bool P(X), ta đã chứng minh A ∈ P(X) thì phần tử đối là A và
P(X) là một vành giao hoán. Ta cũng mở rộng tính chất này lên cho vành Bool tổng
quát, cụ thể ta có :
Đònh lý 1.2. Trong vành Bool B, mọi phần tử đều có phần tử đối là chính nó,
nghóa là : ∀x ∈ B -x = x
Chứng minh : Do B là vành nên ∀x ∈ B ⇒ -x ∈ B
Theo đònh nghóa vành Bool : (x+x)
2
= x+x hay
x
2
+x
2
+ x
2
+ x
2
= x + x
⇔
x + x + x+ x = x+x
⇔
x+x =0 x =-x
⇔
Nhận xét : Do kết quả này, vành Bool là vành có đặc số 2.
Đònh lý 1.3. Mọi vành Bool đều giao hoán
Chứng minh : ∀x, y ∈ B ta có :
x
2
+ y
2
= x + y = (x + y)
2
= x
2
+ xy + yx + y
2
nên xy + yx = 0
Suy ra : xy = -yx = (-y)x = yx (do -y = y) đònh lý 1.1)
Vậy B là vành Bool giao hoán.
Ta biết rằng, trong vành Bool P(X) có quan hệ thứ tự tự nhiên như sau :
A ⊆ B ⇔ AB = A, ∀A, B ∈ P(X)
Quan hệ này cũng được tổng quát lên cho mọi vành Bool như sau :
Đònh lý 1.4. Trong vành Bool B, đònh nghóa quan hệ :
∀x, y ∈ B : x ≤ y ⇔ xy = x.
khi đó : ≤ là một quan hệ thứ tự trên B.
Chứng minh :
+ ∀x ∈ B ta có : x.x = x nên x ≤ x, tức có tính chất phản xạ.
+ ∀x, y ∈ B sao cho : x ≤ y và y ≤ z, ta có :
xy = x và yz = y. Do vành Bool giao hoán nên xy = yx hay x = y
tức quan hệ ≤ có tính phản đối ứng.
+ Với x, y, z ∈ B sao cho x ≤ y và y ≤ z ta có :
xy = x và yz = y
Suy ra : xz = (xy)z = x(yz) = xy = x, tức là : x ≤ z
5
Nên ≤ có tính chất bắc cầu.
Vậy ≤ là một quan hệ thứ tự của B.
Chú ý :
1. Khi x ≤ y ta nói : x nhỏ hơn hoặc bằng y hay y lớn hơn hoặc bằng x.
2. Với x, y ∈ B ta nói : x, y so sánh được với nhau nếu x ≤ y hoặc y ≤ x.
Trở lại vành Bool P(X), ta biết P(X) có phần tử đơn vò là X và phần tử không
là rỗng và ta cũng có : mỗi A ∈ P(X) thì tồn tại CA = X + A thỏa :
CA + A = X và (CA) A = Φ
CA : gọi là phần bù của A. Đối vành Bool bất kỳ ta cũng có điều tương
tự. Cụ thể là :
Đònh lý 1.5. Cho B là vành Bool, với mỗi x ∈ B luôn tồn tại duy nhất phần tử
x* ∈ B thỏa :
x + x* = 1
xx* = 0
Chứng minh :
• Sự duy nhất : với mỗi x ∈ B, giả sử có y ∈ B cũng thỏa :
x + y = 1
xy = 0
khi đó : y = 1 - x = x*∈ B
Nên x* là duy nhất.
• Sự tồn tại : Với mọi x ∈ B, xét x* = 1 + x
Khi đó : x + x* = x + (1 + x)
= x + x + 1
= 1
và xx* = x (1 + x) = x + xx = x + x =0
Chú ý
: Phần tử x* trong đònh lý cũng gọi là phần tử bù của phần tử x ∈
B và x* = 1 + x. Khái niệm phần bù có một số tính chất đơn giản là :
1* = 0 và 0* = 1 và (x*)* = x, ∀x ∈ B
Thực ra là sự mở rộng các kết quả trong P(X): CX = Φ, CΦ = X và C(CA) =
A, ∀A ∈ P(X)
6
§2. Vành Bool hữu hạn
Trong mục này ta sẽ mô tả vành Bool hữu hạn thông qua các phần tử cực
tiểu. Vì thế trước tiên ta nghiên cứu các phần tử cực tiểu của vành Bool hữu hạn.
Ta có đònh nghóa sau :
Đònh nghóa 2.1. Cho vành Boll hữu hạn B với quan hệ thứ tự ≤ được đònh
nghóa trong mục 1, phần tử a ∈ B \ {0} gọi là phần tử cực tiểu của B nếu mọi phần
tử x ∈ B \ {0} mà x ≤ a thì x = a.
Chẳng hạn, đối với vành Bool P(X), với X = {x
1
, x
2
, x
n
} có hữu hạn phần tử
là 2
n
và với phép toán bao hàm là quan hệ thứ tự thì các phần tử cực tiểu là {x
1
},
i=1, n. Bây giờ trong vành Bool hữu hạn B ta chứng minh sự tồn tại của phần tử
cực tiểu.
Đònh lý 2.1. Trong vành Bool hữu hạn thì tồn tại phần tử cực tiểu.
Chứng minh :
Xét x ∈ P(X) \ {0}
+ Nếu x là phần tử cực tiểu của B thì x là phần tử cần tìm. Nếu không x có
phần tử x
1
∈ B \ {0} sao cho x
1
< x.
+ Nếu x
1
là phần tử cực tiểu của B thì x
1
là phần tử cần tìm. Nếu không x
1
có
phần tử x
2
∈ B \ {0} sao cho x
2
< x
1
.
+ Nếu x
2
là phần tử cực tiểu của B thì x
2
là phần tử cần tìm. Nếu không x
2
có
phần tử x
3
∈ B \ {0} sao cho x
3
< x
2
.
Do B hữu hạn và các phần tử x
1
, x
2
, đôi một khác nhau, quá trình sẽ dừng
lại sau hữu hạn bước, khi đó tồn tại x
0
là phần tử cực tiểu của B.
Như vậy, tập hợp tất cả các phần tử cực tiểu của vành Bool hữu hạn là khác
rỗng. Để tiện lợi cho việc trình bày, từ đây về sau ta giả sử B là vành Bool hữu hạn
có tập các phần tử cực tiểu là M = {x
1
, x
2
, x
n
}.
Bằng cách chứng minh tương tự đònh lý 2.1, ta có kết quả sau :
Đònh lý 2.2. Mọi x ∈ B \ {0} thì tập N các phần tử cực tiểu của B nhỏ hơn
hoặc bằng x là khác rỗng.
Chúng ta xét các đặc trưng của phần tử cực tiểu của B, dựa vào từ tổng quát
của vành Bool hữu hạn P(X). Trong P(X), tập các phần tử cực tiểu là :
X = {x
1
x
2
, x
n
}. Khi đó ta có {x
i
} ∩ {x
j
} = Φ hay {x
i
} , {x
j
} = 0. Và mọi A
∈ P(X) thì A là hợp của các phần tử cực tiểu tức A = , m ≤ n thì A =
}x x,x{
m
kkk
21
7
}x{
i
k
∪ ∪ = Δ Δ , với chú ý trong P(X) : Nếu A, B ∈ P(X)
và A ∩ B = Φ thì AΔB = A ∪ B. Điều này sẽ được tổng quát cho vành Bool bất kỳ
như sau :
}x{
m
k
}x{
i
k
}x{
k
2
}x{
m
k
Đònh lý 2.3. Nếu x
i,
x
j
là hai phần tử cực tiểu phân biệt của B thì x
i
x
j
= 0
Chứng minh :
Giả sử x
i
x
j
≠ 0 tức x
i
x
j
∈ B \ {0}
Ta có : x
i
x
j
≤ x
i
và x
i
x
j
≤ x
j
(Do x
i
(x
i
x
j
) = (x
i
x
i
)x
j
= x
i
x
j
và x
i
(x
i
x
j
) = (x
i
x
j
) x
j
= x
i
x
j
)
Vì x
i
x
j
là các phần tử cực tiểu nên
x
i
x
j
= x
i
và x
i
x
j
= x
j
Nên x
i
= x
j
, điều này mâu thuẫn.
Vậy x
i
x
j
= 0
Đònh lý 2.4. Mọi ∀ x ∈ B \ {0} đều có thể viết dưới dạng :
x = trong đó : , i = 1, m là các phần tử cực tiểu của
B thỏa : ≤ x.
m
kkk
x xx +++
21 i
k
x
i
k
x
Chứng minh :
Do ∀x ∈ B \ {0} nên theo đònh lý 2.2, tồn tại phần tử cực tiểu x
k
≤ x và gọi
tập là các phần tử cực tiểu của B nhỏ hơn hoặc bằng x là tập khác
rỗng.
}x x,x{
m
kkk
21
Đặt y =x+ (
m
kkk
x xx +++
21
).
Giả sử y 0 . Khi đó tồn tại phần tử cực tiểu a
≠
≤
y
Mặt khác ,ta có y
≤
x
Thật vậy : yx =xx+ (
m
kkk
x xx +++
21
) x
= x+
xx xxxx
m
kkk
+++
21
= x+(
m
kkk
x xx +++
21
) = y (do ≤ x ⇔ x = )
i
k
x
i
k
x
i
k
x
Suy ra a x, do đó tồn tại i sao cho a =
≤
i
k
x
là cực tiểu của x
Khi đó: ya = y
i
k
x
=
i
k
x
≠
0 (do
i
k
x
là phần tử cực tiểu)
Va øy
i
k
x
=x
i
k
x
+(
m
kkk
x xx +++
21
)
i
k
x
=
i
k
x
+
i
k
x
=0 (tính chất vành bool)
8
⇒
mâu thuẫn, vậy y=0
⇔
x=
m
kkk
x xx +++
21
Kết luận : Mỗi phần tử khác không của B luôn biểu diễn thành tổng các
phần tử cực tiểu của B nhỏ hơn hoặc bằng x. bây giờ, chúng ta khẳng đònh cách
biểu diễn qua các phần tử cực tiểu trên là duy nhất sai khác một hoán vò thứ tự của
các phần tử cực tiểu.
Đònh lý 2.5. Nếu , là các phần tử cực tiểu của B sao cho :
1
l
y
t
l
y
x = + + + thì D = { , , }= C ={ }
1
l
y
2
l
y
t
l
y
1
l
y
2
l
y
t
l
y
m
kkk
x, x,x
21
Trong đó : là các phần tử cực tiểu của B thỏa ≤ x.
m
kk
x, x
1 i
k
x
Chứng minh :
Giả sử , là các phần tử cực tiểu của B thỏa :
1
l
y
t
l
y
x = + + + =
1
l
y
2
l
y
t
l
y
m
kkk
x xx +++
21
giả sử tồn tại và
k
l
yD∈
k
l
yC∉
khi đó ta có
x =( + + + ) =(
k
l
y
1
l
y
2
l
y
t
l
y
k
l
y
m
kkk
x xx +++
21
)
k
l
y
k
l
y
= = 0 (do tích các phần tử cực tiểu khác nhau bằng 0)
2
k
l
y
⇒
mâu thuẫn (vì các phần tử cực tiểu đều khác 0)
⇒
{ , , } = { } (1)
1
l
y
2
l
y
t
l
y
m
kkk
x, x,x
21
Đến đây ta có thể khẳng đònh : Tổng các phần tử cực tiểu của B đều thuộc
vào B và ngược lại x B \ {0} đều được viết thành tổng các phần tử cực tiểu của B
nhỏ hơn hoặc bằng x. Vậy ta có :
B = {
∑
và x
i
là phần tử cực tiểu của B}.
=
∈εε
n
i
iii
},{lx
1
10
Mặt khác : Z
2
⊕ Z
2
⊕ ⊕ Z
2
= {(ε
1
, , ε
n
) / ε
i
∈ {0, 1}}
Xét đồng cấu ψ : B → Z
2
⊕ Z
2
⊕ ⊕ Z
2
x =
∑
=
εεε
n
i
nii
), ,(x
1
1
ta có được do mỗi phần tử x của B đều được viết một cách duy nhất x =
nếu ta cố đònh thứ tự từ 1 đến n.
∑
=
ε
n
i
ii
x
1
9
Rõ ràng ψ là một song ánh nên ta có hệ quả sau :
Hệ quả
. Nếu B là một vành Bool hữu hạn, có tập các phần tử cực tiểu là
thì số phần tử của vành B là 2
n
.
Hơn thế nữa, ánh xạ ψ còn bảo toàn các phép toán trong B, bảo toàn quan
hệ thứ tự trong B. Sau đây chúng ta sẽ chứng minh điều đó :
Đònh lý 2.6
. Nếu (ε
1
, , ε
n
), (ε’
1
, , ε’
n
) thì
(ε
1
, , ε
n
) + (ε’
1
, , ε’
n
) = (ε’
1
+ ε
1
, , ε’
n
+ ε
n
)
với ε
1
+ ε’
i
= 0 nếu ε
1
+ ε’
i
và bằng 1 nếu ε
1
≠ ε’
i
Chứng minh
:
Giả sử B có tập các phần tử cực tiểu là {x
1
, , x
n
}
Với mọi (ε
1
, , ε
n
) = ψ ( ) và (ε’
1
, , ε’
n
) = ψ ( )
∑
=
ε
n
i
ii
x
1
∑
=
ε
n
i
i
i
'
x
1
Xét x + y = (ε
1
+ ε’
1
) x
1
+ (ε
2
+ ε’
2
)x
2
+ + (ε
n
+ ε’
n
)x
n
Ở đây :
+ Nếu ε
i
+ ε’
i
(tức cùng bằng 0 hoặc cùng bằng 1) thì ta có (ε
i
+ ε’
i
)x
i
= 0 (do B là
vành có đặc số 2).
+ Nếu ε
i
≠ ε’
i
(tức trong {ε
i
, ε’
i
} có một phần tử bằng 0 và phần tử còn lại
bằng 1) nên (ε
i
+ ε’
i
) x
i
= x
i
Do vậy x + y = và ψ (x + y) = (ε’
1
+ ε
1
, , ε’
n
+ ε
n
)
∑
=
ε+ε
n
i
ini
x)(
1
Đònh lý 2.7
. Nếu (ε
1
, ε
n
), (ε'
1
, , ε’
n
) ∈ B thì
(ε
1
, , ε
n
) (ε’
1
, , ε’
n
) = (ε
1
ε’
1
, , ε
n
ε’
n
)
với ε
i
ε’
i
bằng 1 nếu ε
i
= ε’
i
= 1 và bằng 0 nếu ε
i
= 0 hoặc ε’
i
= 0
Chứng minh.
Giả sử B có tập các phần tử cực tiểu là {x
1
, , x
n
}
Với mọi (ε
1
, , ε
n
) = ψ ( ) và (ε’
1
, , ε’
n
) = ψ (
∑
)
∑
=
ε
n
i
ii
x
1 =
ε
n
i
ii
x'
1
Từ hai đònh lý trên ta có :
Đònh lý 2.8
. Vành Bool hữu hạn B có tập các phần tử cực tiểu là thì B
đẳng cấu với vành (tổng của n số hạng Z ) trong đó vành có phép toán + và
như trong đònh lý 2.6 và đònh lý 2.7.
Chúng ta đã biết trong P(X) với x = {x
10
Hệ quả 2.9
. Mọi vành Bool B
hữu hạn bất kỳ đều đẳng cấu với vành P(X)
với X là tập có n phần tử nào đó.
Ngoài sự
chuyển các phép toán
trên B qua vành (tổng của n số hạng Z ) y
còn
chuyển các phần tử bù và quan hệ thứ tự
như sau :
Đònh lý 2.10
. Nếu x = ∈ B thì (ε
1
, , ε
n
)* = (ε*
1
, , ε*
n
)
∑
=
ε
n
i
ii
x
1
Với ε*
i
= 1 nếu ε
i
= 0 và ε*
i
= 0 hoặc ε
i
= 1, i = 1, , n.
Chứng minh
. Với mọi (ε
1
, , ε
n
) = ψ ( ) và (ε
1
, , ε
n
)* = ψ (x*)
∑
=
ε
n
i
ii
x
1
Thì x* = 1 + x = 1 + ε
1
x
1
+ + ε
n
x
n
= (x
1
+ + x
n
) + (ε
1
x
1
+ + ε
n
x
n
)
= (1 + ε
1
) x
1
+ + (1 + ε
n
) x
n
Đặt ε*
i
= 1 + ε
i ;
i = 1, n.
Khi đó : ε*
1
= 1 nếu ε
i
= 0 và ε*
i
= 0, nếu ε
i
= 1 (do 2x
1
= 0)
Nên (ε*
1
, , ε*
n
) = y (x*) hay (ε
1
, , ε
n
)* = (ε*
1
, , ε*
n
)
Đònh lý 2.11
. Nếu x = , y = ∈ B và x ≤ y thì
∑
=
ε
n
i
ii
x
1
∑
=
ε
n
i
ii
x'
1
ε
1
≤ ε’
i
, i = 1, n
Chứng minh. Giả sử (ε
1
, , ε
n
) ≤ (ε’
1
, , ε’
n
)x
n
= (ε
1
x
1
+ + ε
n
x
n
)
Do x ≤ y ⇔ xy = x tức : (ε
1
ε’
1
)x
1
+ + (ε
n
ε’
n
)x
n
= (ε
1
x
1
+ + ε
n
x
n
)
Suy ra ε
i
(1 + ε’
i
) = 0, i = 1, , n.
Khi đó : ε
i
= 0 hoặc ε’
i
= 1, i = 1, ,n.
Cả hai khả năng ta đều có ε
i
≤ ε’
i
, i = 1, , n
Tóm lại, trong chương này ta thu được kết quả sau : Cho một vành Bool hữu
hạn B bất kỳ thì B đẳng cấu với tổng trực tiếp với một số các trường Z
2
và cùng
đẳng cấu với vành P(X), trong đó X là một tập hữu hạn phần tử nào đó. Và hơn nữa
khái nệim phần tử bù, các quan hệ thứ tự đều tương ứng với nhau giữa B và P(X).
3.1. Một số khái niệm cơ bản.
Cho một tập có thứ tự P bất kỳ, (P, ≤). Chúng ta có một số khái niệm sau :
•
Hai phần tử x, y ∈ P gọi là
so sánh được với nhau
nếu x ≤ y hoặc y ≤ x.
•
Nếu x ≤ y và x ≠ y thì ta viết x ≤ y
•
Nếu x < y và không có phần tử z ∈ P nào thỏa x < z < y thì ta
gọi phần tử
y phủ x.
11
•
Nếu tồn tại duy nhất phần tử z ∈ P sao cho z ≤ x, với mọi x ∈ P thì ta gọi
z
là phần tử không và được kí hiệu là 0.
•
Nếu phần tử x ∈ P thỏa không tồn tại y ∈ P nào sao cho y < x thì x gọi là
phần tử tối tiểu.
Ngược lại, nếu phần tử x ∈ P thỏa không tồn tại y ∈ P
nào sao cho x < y thì x gọi là
phần tử tối đại
.
•
Nếu x
1
< x
2
< < x
n
thì ta gọi x
1
, x
2
, , x
n
lập nên xích.
Một
xích bảo
hòa
là xích x
1
< x
2
< < x
n
sao cho x
i+1
phủ x
i
, ∀i < n.
•
Nếu tất cả các xích bảo hòa từ 0 đến x có
cùng kích thước
và nếu đònh
nghóa độ dài của một xích là lực lượng của xích trừ đi 1. Khi đó : ta có thể
đònh nghóa hạng của phân tử x
là r(x), là độ dài của một xích bảo hòa từ
0 đến x. Với khái niệm hạng r(x), ta có đònh nghóa hàm hạng như sau :
Đònh nghóa 3.2:
Hàm số r : P → R
+
gọi là
hàm hạng của P
x
r(x)
trong đó : r(x) là độ dài của một xích bảo hòa bất kỳ từ 0 đến x như đònh
nghóa trên. Để dễ dàng trong việc sử dụng hàm hạng của một tập có thứ tự P ta tìm
các tương đương của nó như sau :
Mệnh đề 3.1.2. Cho (P, ≤) với hàm hạng r. Khi đó :
(i) r(x) ∈ N và r(0) = 0, N : là tập các số tự nhiên.
(ii) Nếu x phủ y thì r(x) = r(y) + 1
Chứng minh.
(i) Theo đònh nghóa hàm hạng r ta có r(x) là độ dài của một xích bảo hòa bất
kỳ từ 0 đến x nên r(x) là một số tự nhiên và r(0) = 0
(ii) Giả sử x phủ y, vì y ∈ P nên xét một xích bảo hòa bất kỳ từ 0 đến y là
0 < x
1
< x
2
< < x
r(y)-1
< y nên ta có một xích bảo hòa từ 0 đến x là
0 < x
1
< x
2
< < x
r(y)-1
< y < x nên theo đònh nghóa hạng của một phần tử, ta
có r(x) = r(y) + 1.
3.3 Một số kết quả cơ bản trên tập có thứ tự
Trước hết ta có thêm một số đònh nghóa cơ bản sau :
Đònh nghóa 3.4.1. Cho một tập
có thứ tự (P,
≤
), có hàm hạng r.
Với x
1
, x
2
x
n
gọi là lập nên
một xích đối ứng
x
1
< x
2
< < x
n
nếu :
(i)
x
i+1
phủ x
i
, ∀i < h
(ii)
r(x
1
) + r(x
h
) = r(P) với r(P) là hạng lớn nhất trong P.
12
Không có nhận xét nào:
Đăng nhận xét