❛❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜

❜
❜
❜
❜
❜
❜❝
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡

❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡

❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞
❡
❡
❢❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❤
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN

————oOo————


NGUYỄN KHÁNH LINH

¨
CƠ SỞ GROBNER
VÀ

ĐỊNH LÝ CƠ SỞ HILBERT

Chuyên ngành: ĐẠI SỐ

HÀ NỘI, 05/2019


❛❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜

❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜
❜❝
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞

❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡

❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞

❡
❡
❡
❞❞❞
❡
❡
❡
❞❞❞
❡
❡
❡
❢❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❣❤
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN

————oOo————

NGUYỄN KHÁNH LINH

¨
CƠ SỞ GROBNER
VÀ

ĐỊNH LÝ CƠ SỞ HILBERT

Chuyên ngành: ĐẠI SỐ

NGƯỜI HƯỚNG DẪN KHOA HỌC:

Th.S Đỗ Văn Kiên


HÀ NỘI, 05/2019


Lời cảm ơn
Trong thời gian học tập tại khoa Toán Trường Đại học Sư phạm Hà Nội
2 được sự dạy dỗ, chỉ bảo tận tình của các thầy cô giáo, em đã tiếp thu
được nhiều tri thức khoa học, kinh nghiệm và phương pháp học tập mới,
bước đầu làm quen với việc nghiên cứu khoa học.
Qua đây em xin gửi lời cảm ơn sâu sắc tới toàn thể các thầy cô trong
khoa toán – những người đã dạy dỗ chúng em trưởng thành như ngày
hôm nay.
Đặc biệt em xin gửi lời cảm ơn thầy giáo Ths Đỗ Văn Kiên người đã
trực tiếp hướng dẫn, chỉ bảo tận tình và đóng góp nhiều ý kiến quý báu
trong thời gian thực hiện khóa luận này.
Với điều kiện hạn chế về thời gian cũng như kiến thức của bản thân
nên khóa luận khó tránh khỏi thiếu sót. Kính mong sự chỉ bảo, các ý
kiến đóng góp của thầy cô cũng như các bạn sinh viên.
Em xin chân thành cảm ơn!

1


Hà Nội, ngày 07 tháng 5 năm 2019
Sinh viên

Nguyễn Khánh Linh

2



Lời cam đoan

Khóa luận của em được hoàn thành dưới sự hướng dẫn của thầy giáo
Đỗ Văn Kiên cùng sự cố gắng của bản thân. Trong quá trình nghiên cứu
và thực hiện khóa luận em có tham khảo tài liệu của một số tác giả (đã
nêu trong mục Tài liệu tham khảo).
Em xin cam đoan các kết quả trong khóa luận là kết quả của bản
thân, không trùng với kết quả của tác giả khác. Nếu sai em xin hoàn
toàn chịu trách nhiệm.

Hà Nội, ngày 07 tháng 5 năm 2019
Sinh viên

Nguyễn Khánh Linh

i


Mục lục

Lời mở đầu

1

1 Kiến thức cơ sở

3

1.1


Quan hệ thứ tự . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Vành đa thức . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.1. Vành đa thức nhiều ẩn . . . . . . . . . . . . . . .

5

1.2.2. Bậc của đa thức . . . . . . . . . . . . . . . . . . .

7

2 Cơ sở Gr¨
obner
Thứ tự đơn thức trong k [x1 , x2 , ..., xn ] . . . . . . . . . .

10

2.1.1. Thứ tự đơn thức . . . . . . . . . . . . . . . . . .

10

2.1.2. Thứ tự từ điển . . . . . . . . . . . . . . . . . . .


13

2.1.3. Thứ tự từ điển phân bậc . . . . . . . . . . . . . .

17

2.1.4. Thứ tự từ điển ngược phân bậc . . . . . . . . . .

18

2.2

Phép chia đa thức trong k [x1 , x2 , ..., xn ] . . . . . . . . . .

22

2.3

Iđêan đơn thức và Bổ đề Dickson . . . . . . . . . . . . .

28

2.3.1. Iđêan đơn thức . . . . . . . . . . . . . . . . . . .

28

Cơ sở Gr¨obner . . . . . . . . . . . . . . . . . . . . . . . .

31


2.1

2.4
3

10

Định lý cơ sở Hilbert

37

ii


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

3.1

Vành Noether . . . . . . . . . . . . . . . . . . . . . . . .

37

3.2

Định lý cơ sở Hilbert . . . . . . . . . . . . . . . . . . . .

39


Kết luận

43

Tài liệu tham khảo

44

iii


Lời mở đầu

Ngày nay những tư tưởng, phương pháp và kết quả đại số đã thâm
nhập vảo hầu hết các lĩnh vực của toán học. Cơ sở Gr¨obner là một công
cụ rất mạnh và hữu hiệu trong Đại số máy tính, Hình học đại số và Đại
số giao hoán. Định lý cơ sở Hilbert có nhiều ứng dụng trong Đại số hiện
đại. Việc nghiên cứu đề tài “Cơ sở Gr¨obner và Định Lý cơ sở Hilbert”
giúp người học phát triển tư duy và có tầm nhìn sâu rộng hơn về toán
học.
Thấy được tầm quan trọng của đề tài cùng với sự giúp đỡ tận tình
của thầy Đỗ Văn Kiên em mạnh dạn thực hiện khóa luận tốt nghiệp với
đề tài “Cơ sở Gr¨obner và định lý cơ sở Hilbert”.
Đề tài này nghiên cứu về thứ tự trên vành đơn thức, cơ sở Gr¨obner
và vành Noether. Sử dụng cơ sở Gr¨obner để chứng minh định lý cơ sở
Hilbert và một số ứng dụng của chúng.
Nội dung của khóa luận gồm có ba chương như sau:
• Chương 1: Kiến thức cơ sở
• Chương 2: Cơ sở Gr¨obner


1


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

• Chương 3: Định lý cơ sở Hilbert và một số ứng dụng
Do khuôn khổ về thời gian cũng như trình độ kiến thức của bản thân
còn hạn chế nên khóa luận khó tránh khỏi những thiếu sót. Kính mong
nhận được sự đóng góp ý kiến của các thầy cô và các bạn sinh viên để
đè tài được hoàn thiện và phát triển hơn.

2


Chương 1
Kiến thức cơ sở
Chương này trình bày các kiến thức cơ sở về quan hệ thứ tự và vành đa
thức nhiều ẩn để chuẩn bị cho các chương tiếp theo.

1.1

Quan hệ thứ tự

Định nghĩa 1.1.1 (Quan hệ hai ngôi). Giả sử X, Y là những tập hợp.
Một quan hệ hai ngôi từ Xđến Y là một tập con R của tích đề các
X × Y . Ta nói, với hai phần tử x ∈ X và y ∈ Y , rằng x có quan hệ R
với y khi và chỉ khi (x, y) ∈ R. Khi đó ta viết xRy.

Đặc biệt khi X = Y ta nói R là một quan hệ hai ngôi trên X.
Định nghĩa 1.1.2 (Quan hệ thứ tự). Giả sử X là một tập hợp, R là
một quan hệ hai ngôi trên X. Khi đó R được gọi là một quan hệ thứ tự
trên X nếu nó thỏa mãn các điều kiện sau:
(i) Phản xạ: Với ∀x ∈ X thì xRx.
(ii) Phản đối xứng: Với ∀x, y ∈ X sao cho xRy và yRx thì x = y.
(iii) Bắc cầu: Với xRy và yRz thì xRz.
3


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Ta nói X là một tập được sắp thứ tự nếu trong X có một quan hệ
thứ tự nào đó.
Kí hiệu: Cho ≥ là một quan hệ thứ tự trên X, hai phần tử x, y ∈ X.
Ta ký hiệu x > y nếu x ≥ y và x = y.
Ví dụ 1.1.3. (1) Quan hệ ≤ trên tập hợp các số tự nhiên N là một quan
hệ thứ tự.
(2) Quan hệ chia hết trên N là một quan hệ thứ tự.
(3) Quan hệ chia hết trên Z không là một quan hệ thứ tự vì nó không
có tính chất phản đối xứng. Ví dụ như
Định nghĩa 1.1.4 (Quan hệ thứ toàn phần). Giả sử X là một tập hợp,
R là một quan hệ thứ tự trên X. Ta nói R là một quan hệ thứ tự toàn
phần trên X nếu với hai phần tử bất kì x, y ∈ X một trong hai quan hệ
xRy hoặc yRx xảy ra.
Ví dụ 1.1.5. Các quan hệ “≤” và “≥” thông thường trên tập số thực là
một quan hệ thứ tự toàn phần.
Định nghĩa 1.1.6 (Quan hệ thứ tự tốt). Cho R là một quan hệ thứ tự

trên X. Ta nói R là quan hệ thứ tự tốt nếu mọi bộ phận khác rỗng của
X đều có một phần tử bé nhất.
Rõ ràng nếu R là một quan hệ thứ tự tốt thì mọi bộ phận của X
gồm hai phần tử đều có phần tử nhỏ nhất, do đó một quan hệ thứ tự
tốt luôn là quan hệ thứ tự toàn phần.
Ví dụ 1.1.7. Tập hợp các số tự nhiên N với thứ tự thông thường là
một tập hợp sắp thứ tự tốt. Nhưng tập hợp các số nguyên Z với thứ tự
4


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

thông thường là một tập hợp sắp thứ tự toàn phần nhưng không là tập
sắp thứ tự tốt.
Định nghĩa 1.1.8. Giả sử X là một tập hợp sắp thứ tự.
i) Một phần tử a ∈ X được gọi là phần tử cực đại (hay cực tiểu) của
X nếu với ∀x ∈ X sao cho a ≤ x (hay x ≤ a) thì x = a.
ii) Một phần tử b ∈ X được gọi là phần tử lớn nhất (hay nhỏ nhất)
của X nếu với ∀x ∈ X ta có x ≤ b (hay b ≤ x).
Bổ đề 1.1.9 (Bổ đề Zorn). Cho X là một tập hợp được sắp thứ tự (bộ
phận) sao cho mọi tập con khác rỗng của X được sắp thứ tự toàn phần
đều bị chặn trên trong X. Khi đó X có phần tử cực đại.

1.2

Vành đa thức

1.2.1.


Vành đa thức nhiều ẩn

Cho A là một vành giao hoán có đơn vị 1 và x1 , x2 , ..., xn là n biến số
với n ∈ Z>0 . Ta gọi một đa thức n ẩn (biến) trên vành A là một tổng
hình thức có dạng
λa xa ,

f (x) =
a∈Nn

trong đó x = (x1 , x2 , ..., xn ), a = (a1 , a2 , ..., an ), xa = xa11 xa22 ...xann , λa ∈ R
và chỉ có một số hữu hạn hệ số λa = 0.
Khi λa = 0 ta gọi λa xa là một hạng tử của f (x), xa là một đơn thức
của f (x)
Hai đa thức f (x) =

λa xa và g(x) =

nếu λa = µa với mọi a ∈ Nn .
5

µa xa được gọi là bằng nhau


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Phép cộng hai đa thức được định nghĩa như sau

λa xa +
a∈Nn

µa xa :=
a∈Nn

(λa + µa )xa .
a∈Nn

Chú ý rằng tổng này được định nghĩa tốt vì hầu hết λa = 0, hầu hết
µa = 0 nên ta cũng có hầu hết λa + µa = 0.
Phép nhân hai đa thức được định nghĩa như sau

a∈Nn

trong đó γa =

γa xa ,

µa xa :=

λa xa .

a∈Nn

a∈Nn

b,c∈Nn ,b+c=a λb µc .

Ta thấy γa = 0 khi và chỉ khi tồn tại


b, c thỏa mãn λb = 0 và µc = 0 sao cho a = b + c = 0. Do đó cũng chỉ
có một số hữu hạn hệ số γa khác không. Vì vậy phép nhân hai đa thức
trên cũng cho ta một đa thức n ẩn.
Với hai phép toán ở trên, tập tất cả các đa thức n ẩn với hệ số trên
R lập thành một vành giao hoán và có đơn vị (1; 0; ...; 0).
Định nghĩa 1.2.1. Vành được xây dựng như ở trên được gọi là vành
đa thức n ẩn với hệ tử trên A. Ký hiệu là A[x1 , x2 , ..., xn ] hay A[x].
Chú ý 1.2.2.
• Đồng cấu A → A[x1 , x2 , ..., xn ] cho bởi 1 → x01 x02 ...x0n là một đơn cấu
vành. Vì vậy ta có thể coi A là một vành con của A[x1 , x2 , ..., xn ] bằng
cách đồng nhất 1 = x01 x02 ...x0n , tức là α = αx01 x02 ...x0n với mọi α ∈ A.
• Khi n = 1 ta có khái niệm vành đa thức một ẩn trên A.
• Vành đa thức n ẩn có thể xem là vành đa thức một ẩn bởi A[x1 , x2 , ..., xn ] =
(A[x1 , x2 , ..., xn−1 ])[xn ].

6


Khóa luận tốt nghiệp Đại học

1.2.2.

Nguyễn Khánh Linh

Bậc của đa thức

Định nghĩa 1.2.3. Bậc của đa thức f (x) =

a∈Nn


λa xa được định nghĩa

là
deg f (x) = max{a1 + a2 + · · · + an | λa = 0}.
Ta gọi một đa thức có dạng xa = xa11 xa22 ...xann là một đơn thức và
a1 + a2 + · · · + an được gọi là bậc của đơn thức này.
Đối với đa thức 0 được qui ước bằng −∞.
Mệnh đề 1.2.4. Nếu A là miền nguyên, thì A [x] cũng là miền nguyên.
Chứng minh. Bằng qui nạp theo n ta chỉ cần chỉ ra khẳng định đúng
cho vành đa thức một biến A[x]. Giả sử
m

k
i

f (x) =

bj xj ∈ A[x]

ai x , g(x)
i=0

j=0

là hai đa thức khác không. Ta có thể coi am = 0, bk = 0. Khi đó
m+k

ai bj xi+j .


f (x)g(x) =
i+j=0

Do A là miền nguyên nên am bk = 0, từ đó f (x)g(x) = 0. Vậy A[x] là
một miền nguyên.
Định lý 1.2.5. Cho A là một miền nguyên và f (x) và g (x) là hai đa
thức khác 0 trong A[x]. Khi đó:
(1) deg(f (x) + g(x)) ≤ max{deg f (x), deg g(x)}.
(2) deg (f (x) deg g (x)) = deg f (x) + deg g (x) .
Dấu "=" trong bất đẳng thức xảy ra khi và chỉ khi deg f (x) =
7


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

deg g(x) hoặc tổng các thành phần thuần nhất bậc cao nhất của f và
g khác không.
Chứng minh. Bất đẳng thức trong (1) là hiển nhiên. Ta sẽ chứng minh
(2). Đặt m = deg f (x), k = deg g(x) và tách f (x), g(x) thành tổng các
thành phần thuần nhất như sau
f (x) = fm (x) + · · · + f1 (x) + f0 , g(x) = gk (x) + · · · + g1 (x) + g0 ,
ở đó fm (x) = 0, gk (x) = 0. Khi đó ta có
f (x)g(x) = fm (x)gk (x) + (các hạng tử thuần nhất có bậc nhỏ hơn).
Do A là miền nguyên nên theo Mệnh đề 1.2.4 ta có fm (x)gk (x) = 0. Do
đó
deg f (x)g(x) = deg fm (x)gk (x) = m + k = deg f (x) + deg g(x).

Định nghĩa 1.2.6. Cho đa thức f (x) ∈ A[x], B là một vành chứa A.

Một phần tử α ∈ B được gọi là một nghiệm của f (x) nếu f (α) = 0.
Chúng ta nhắc lại một định lý quen thuộc trong vành đa thức một
ẩn đó là định lý phép chia có dư, định lý này là cơ sở của thuật toán
Euclid để tìm ước chung lớn nhất của hai đa thức.
Định lý 1.2.7 (Phép chia có dư). Cho f (x), g(x) ∈ A[x] là hai đa thức
trên một miền nguyên A, trong đó g(x) có hệ tử cao nhất khả nghịch.

8


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Khi đó tồn tại duy nhất một cặp đa thức q(x), r(x) ∈ A[x] sao cho
f (x) = g(x)q(x) + r(x) với deg r(x) < deg g(x).
Ta gọi q(x) là thương và r(x) là dư của phép chia f (x) cho g(x).
Trong chương tiếp theo chúng ta sẽ xét một mở rộng của Định lý
1.2.7 trong vành đa thức nhiều ẩn. Một hệ quả của định lý này cho bởi
Hệ quả 1.2.8 (Định lý Bezout). Cho đa thức f (x) trong vành đa thức
một ẩn A[x] trên một miền nguyên A. Phần tử α ∈ A là nghiệm của đa
thức f (x) nếu và chỉ nếu f (x) chia hết cho x − α trong vành A[x].
Hệ quả 1.2.9. Trên một trường một đa thức bậc n > 0 có không quá n
nghiệm.

9


Chương 2
Cơ sở Gr¨

obner
Chương này trình bày về cơ sở Gr¨obner. Đây là một công cụ quan trọng
trong nhiều ngành đặc biệt là trong Đại số. Nội dung chương này được
trình bảy chủ yếu theo [1].
Trong toàn bộ chương này xét k là một trường.

Thứ tự đơn thức trong k [x1, x2, ..., xn]

2.1
2.1.1.

Thứ tự đơn thức

Định nghĩa 2.1.1. Một thứ tự đơn thức trên vành k [x1 , x2 , ..., xn ] là
một quan hệ hai ngôi “≥” trên Nn (hoặc trên tập tất cả các đơn thức)
thỏa mãn:
i) Quan hệ “≥” là một quan hệ thứ tự toàn phần trên Nn .
ii) Với mọi α ≥ β (α, β ∈ Nn ) và γ ∈ Nn thì α + γ ≥ β + γ.
iii) Quan hệ “≥” là quan hệ thứ tự tốt trên Nn (nghĩa là mọi tập con
khác rỗng của Nn đều có phần tử nhỏ nhất theo quan hệ này).

10


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Ví dụ 2.1.2. Trên tập N2 xét quan hệ (a, b) ≥ (c, d) nếu a > c hoặc
a = c và b ≥ d. Khi đó “≥” là một thứ tự đơn thức.

Thật vậy, trước hết ta chỉ ra “≥” là một quan hệ thứ tự.
• Phản xạ: Rõ ràng với mọi (a, b) ∈ N2 ta luôn có (a, b) ≥ (a, b).
• Phản đối xứng: Với mọi (a, b) , (c, d) ∈ N2 sao cho (a, b) ≥ (c, d) và
(c, d) ≥ (a, b). Suy ra


a>c







 a = c, b



c>a






 c = a, d

d

⇔



a = c, b

d

c = a, d

b

⇔


a = c
b = d

b

Do đó (a, b) = (c, d).
• Bắc cầu: Với mọi (a, b) , (c, d) , (e, g) ∈ N2 sao cho (a, b) ≥ (c, d) và
(c, d) ≥ (e, g). Khi đó


a>c








 a = c, b



c>e






 c = e, d

a > c, c > e
⇔
a > c, c = e, d

d

g


a = c, b
hoặc 
g
a = c, b

11


d, c > e
d, c = e, d

g


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Suy ra

a>e

a = e, b

g

Vậy (a, b) ≥ (e, g)
Do đó (a, b) ≥ (c, d) là một quan hệ thứ tự

(1).

Hơn nữa với mọi (a, b) , (c, d) , (m, n) ∈ N2 sao cho (a, b) ≥ (c, d), ta
có


a>c




a=c

b≥d



a+m>c+m


⇔  a+m=c+m

 b+n≥d+n

Suy ra (a + m, b + n) ≥ (c + m, b + n) hay
(a, b) + (m, n) ≥ (c, d) + (m, n) (2)
Bây giờ lấy tập ∅ = A ⊆ Nn , đặt
a = min {x ∈ N| (x, y) ∈ A ∀y ∈ N} ,
b = min {y ∈ N| (x, y) ∈ A ∀x ∈ N} .
Khi đó với mọi x ∈ N ta luôn có x ≥ a, và với mọi y ∈ N ta luôn có
y ≥ b. Do vậy (a, b) là phần tử nhỏ nhất của A.
Từ đó quan hệ ≥ ở trên là một quan hệ thứ tự tốt trên N2

(3).

Từ (1) , (2) và (3) suy ra “≥” là một thứ tự đơn thức.
Bổ đề sau cho ta tiêu chuẩn cần và đủ để kiểm tra một quan hệ thứ
tự có là tốt hay không.

12



Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Bổ đề 2.1.3. Một quan hệ thứ tự “≥” trên Nn là quan hệ thứ tự tốt khi
và chỉ khi mọi dãy giảm α (1) ≥ α (2) ≥ α (3) ≥ ... trong Nn đều dừng.
Chứng minh.
[⇒] Giả sử “≥” là một quan hệ thứ tự tốt nhưng có một dãy trong Nn
giảm thực sự, tức là dãy giảm không dừng, chẳng hạn là
α (1) > α (2) > α (3) > ...
Khi đó tập hợp A = {α(1), α(2), α(3), ...} là một tập con khác rỗng của
Nn mà không có phần tử nhỏ nhất. Điều này mâu thuẫn với “≥” là một
quan hệ thứ tự tốt. Vậy điều giả sử là sai nên mọi dãy giảm trong Nn
đều dừng.
[⇐] Lấy bất kỳ tập con S ⊆ Nn , S = ∅. Giả sử S không có phần tử nhỏ
nhất theo quan hệ “≥”. Vì S = ∅ nên tồn tại α (1) ∈ S. Vì α (1) không là
phần tử nhỏ nhất trong S nên có α (2) ∈ S để α (1) > α (2) . Quá trình
tiếp tục ta thu được một dãy giảm thực sự α (1) > α (2) > α (3) > · · ·
trong S (mâu thuẫn với giả thiết). Do đó S có phần tử nhỏ nhất.
Vậy “≥” là một quan hệ thứ tự tốt trên Nn .
Trong các phần tiếp theo chúng ta sẽ đi xét một số thứ tự đơn thức
thường dùng.
2.1.2.

Thứ tự từ điển

Định nghĩa 2.1.4. Cho α = (α1 , α2 , ..., αn ) , β = (β1 , β2 , ..., βn ) ∈ Nn ta
nói α ≥lex β nếu α = β hoặc thành phần khác 0 đầu tiên bên trái của

α − β là dương.

13


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Chúng ta sẽ viết xα ≥lex xβ nếu α ≥lex β, ở đó xα = x1 α1 xα2 2 ...xn αn và
xβ = x1 β1 xβ2 2 ...xn βn .
Ví dụ 2.1.5. Trong N3 ta có:
• α = (1, 2, 0) >lex β = (0, 3, 4) vì α − β = (1, −1, −4) .
• α = (3, 2, 4) >lex β = (3, 2, 1) vì α − β = (0, 0, 3) .
Nhận xét 2.1.6. Trong Nn ta có
(1, 0, ..., 0) >lex (0, 1, ..., 0) >lex ...>lex (0, 0, ..., 1) .
Do đó
x1 >lex x2 >lex · · · >lex xn .
Mệnh đề 2.1.7. Thứ tự từ điển ≥lex trên Nn là một thư tự đơn thức.
Chứng minh. i) Trước hết ta chỉ ra “≥lex ” là một quan hệ thứ tự. Thật
vậy với mọi α ∈ Nn ta luôn có α≥lex α, hay “≥lex ” có tính phản xạ.
Với mọi α, β ∈ Nn sao cho α≥lex β và β≥lex α. Giả sử α = β, đặt
α = (α1 , α2 , ..., αn ) , β = (β1 , β2 , ..., βn ) ∈ Nn . Do α >lex β nên ta có thể
viết
α − β = (0, ..., 0, αi − βi , αi+1 − βi+1 , ..., αn − βn )
với αi − βi > 0 (1 ≤ i ≤ n) là thành phần khác 0 đầu tiên bên trái của
α − β. Khi đó ta có
β − α = (0, ..., 0, βi − αi , βi+1 − αi+1 , ..., βn − αn ) .
Rõ ràng thành phần khác 0 đầu tiên bên trái của β − α là βi − αi < 0.
14



Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Điều này mâu thuẫn với giả thiết β >lex α. Vậy αi = βi . Do đó “≥lex ”
có tính phản đối xứng.
Với mọi α, β, γ ∈ Nn sao cho α≥lex β, β≥lex γ. Nếu α = β hoặc β = γ
thì ta luôn có α≥lex γ. Nếu ngược lại đặt α = (αi ), β = (βi ), γ = (γi ), ta
có α>lex β, β>lex γ. Ta có thể giả sử
α − β = (0, ..., 0, αi − βi , αi+1 − βi+1 , ..., αn − βn ) ,
β − γ = (0, ..., 0, βj − γj , βj+1 − γj+1 , ..., βn − γn ) ,
với αi − βi > 0 và βj − γj > 0. Xét 3 trường hợp sau:
+ Nếu i > j thì
α − γ = (0, ..., 0, βj − γj , ..., αi − γi , ..., αn − γn ) .
Ta có βj − γj > 0 nên α >lex γ.
+ Nếu i < j thì
α − γ = (0, ..., 0, αi − βi , ..., αj − γj , ..., αn − γn ) .
Ta có αi − βi > 0 nên α >lex γ.
+ Nếu i = j thì
α − γ = (0, ..., 0, αi − γi , ..., αn − γn ) .
Ta có αi − γi = (αi − βi ) + (βi − γi ) > 0 nên α >lex γ. Vậy “≥lex ” có
tính bắc cầu.
Vì vậy “≥lex ” là một quan hệ thứ tự trên Nn .
ii) Tiếp theo ta sẽ chỉ ra “≥lex ” là một quan hệ thứ tự tốt trên Nn .
15


Khóa luận tốt nghiệp Đại học


Nguyễn Khánh Linh

Thật vậy, giả sử “≥lex ” không là một quan hệ thứ tự tốt. Khi đó theo
Bổ đề 2.1.3 ta có một dãy giảm thực sự
α (1) >lex α (2) >lex α (3) >lex ...
Gọi a1i là thành phần đầu tiên của α (i) , ∀i = 1, 2, ... Nếu a11 < a12 thì
α (1) − α (2) có thành phần khác 0 đầu tiên là a11 − a12 < 0. Điều này
mâu thuẫn với α (1) >lex α (2) . Vậy a11 ≥ a12 . Tương tự so sánh hai vị trí
đầu tiên của α(2) và α(3) ta cũng có a12 ≥ a13 . Quá trình tiếp tục ta thu
được một dãy giảm
a11 ≥ a12 ≥ a13 ≥ ...
trong N. Do “≥” trong N là quan hệ thứ tự tốt nên dãy trên phải dừng
tức là tồn tại k ≥ 1 sao cho
a1k = a1k+1 = · · ·
Ta xét dãy
α (k) >lex α (k + 1) >lex α(k + 2) >lex ...
Gọi a2k là thành phần thứ hai của α (k), a2k+1 là thành phần thứ hai của
α (k + 1). Vì a1k = a1k+1 = ... nên ta phải có a2k ≥ a2k+1 ≥ ... trong N.
Cũng như vậy dãy này phải dừng, nghĩa là tồn tại l ≥ k để
a2l = a2l+1 = · · ·
Quá trình tiếp tục vì mỗi phần tử α (i) ∈ N chỉ có n thành phần nên

16


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh


sau n bước thì tồn tại vị trí s > 0 sao cho
α (s) = α (s + 1) = ...
Vậy “≥lex ” là một quan hệ thứ tự tốt trên Nn .
iii) Cuối cùng ta chứng minh điều kiện thứ hai trong định nghĩa thứ tự
đơn thức. Cho α, β, γ ∈ Nn sao cho α≥lex β. Nếu α = β thì α + γ = β + γ.
Suy ra
α + γ≥lex β + γ.
Nếu α = β thì ta viết α − β = (0, ..., 0, αi − βi , ..., αn − βn ), với αi − βi >
0. Mà (α + γ) − (β + γ) = α − β suy ra α + γ≥lex β + γ.
Vậy thứ tự từ điển là một thứ tự đơn thức.
Chú ý 2.1.8. Chúng ta cũng có thể định nghĩa thứ tự từ điển ngược như
sau: Cho α = (α1 , α2 , ..., αn ) , β = (β1 , β2 , ..., βn ) ∈ Nn . Ta nói α≥invlex β
nếu α = β hoặc thành phần đầu tiên bên phải của α − β là dương. Với
thứ tự này ta có
xn >invlex xn−1 >invlex · · · >invlex x1 .
2.1.3.

Thứ tự từ điển phân bậc

Định nghĩa 2.1.9. Cho α = (α1 , α2 , ..., αn ) , β = (β1 , β2 , ..., βn ) ∈ Nn .
Ta nói α≥grlex β nếu
n

|α| =

n

αi > |β| =
i=1


βi hoặc |α| = |β| và α≥lex β.
i=0

17


Khóa luận tốt nghiệp Đại học

Nguyễn Khánh Linh

Ví dụ 2.1.10. Trong N3 ta có:
• (1, 2, 3) ≥grlex (3, 2, 0) vì 1 + 2 + 3 > 3 + 2 + 0.
• (1, 2, 4) >grlex (1, 1, 5) vì 1 + 2 + 4 = 1 + 1 + 5 = 7 và
(1, 2, 4)≥lex (1, 1, 5).
Nhận xét 2.1.11. Trong Nn ta có
(1, 0, ..., 0) >grlex (0, 1, ..., 0) >grlex ...>grlex (0, 0, ..., 1) .
Do đó
x1 >grlex x2 >grlex · · · >grlex xn .
Tương tự như thứ tự từ điển ta cũng có kết quả sau.
Mệnh đề 2.1.12. Thứ tự từ điển phân bậc là một thứ tự đơn thức.
2.1.4.

Thứ tự từ điển ngược phân bậc

Định nghĩa 2.1.13. Cho α = (α1 , α2 , ..., αn ) , β = (β1 , β2 , ..., βn ) ∈ N ta
n

nói α≥grevlex β nếu |α| =

n


αi > |β| =
i=1

βi hoặc α = β hoặc |α| = |β|
i=0

và thành phần đầu tiên bên phải của α − β là âm.
Ví dụ 2.1.14.
(4, 7, 1)≥grevlex (4, 2, 3) vì 4 + 7 + 1 > 4 + 2 + 3.
(1, 5, 2)≥grevlex (4, 1, 3) vì 1 + 5 + 2 = 4 + 1 + 3
và α − β = (−3, 4, −1) .

18