Vài ứng dụng của lý thuyết cơ sở groebner

Thứ tự từ

1.1.1 Thứ tự, giả thứ tự

Cho X là một tập hợp không rỗng, và quan hệ hai ngôi trên X được định nghĩa là một tập con R của tích Đề các X × X Để đơn giản, ta thường viết xRy để biểu thị rằng (x, y) thuộc R, đồng thời sử dụng các ký hiệu như ~, ≡, ≤ để chỉ R.

Quan hệ R trên tập X được gọi là một thứ tự (bộ phận) nếu nó thỏa mãn ba điều kiện sau đây đối với mọi x, y,zX :

(ii) Nếu xRy và yRz thì xRz (tính chất bắc cầu)

(iii) Nếu xRy và yRx thì x y(tính chất phản đối xứng)

Thông thường để chỉ thứ tự bộ phận thì ký hiệu bởi  , 

Nếu R là một thứ tự bộ phận thì quan hệ ngược

R  1  ( x, y |( y,x )R ) cũng là thứ tự bộ phận và gọi là thứ tự ngược của R Và dùng  để chỉ thứ tự ngược của thứ tự  tương ứng và ngược lại

Trên X cho một thứ tự bộ phận  thì X là tập được sắp

Nếu ,x yX mà x y hoặc yx thì x, y so sánh được với nhau, nếu trái lại x, y không so sánh được với nhau

Quan hệ thứ tự  trên X được gọi là thứ tự toàn phần nếu mọi cặp phần tử của

X đều so sánh được với nhau và X được gọi là tập được sắp hoàn toàn

Quan hệ chỉ thỏa mãn tính chất phản xạ (i) và bắc cầu (iii) ở trên được gọi là giả thứ tự

Cho X là tập được sắp bởi thứ tự  và AX.

Phần tử aA được gọi là phần tử tối tiểu (tương ứng tối đại) nếu  b A mà ba (tương ứng ab) thì ab

Phần tử aA được gọi là phần tử nhỏ nhất (tương ứng lớn nhất) nếu b A

Phần tử bA được gọi là chặn trên (tương ứng chặn dưới) của A nếu b A

Tập X được xem là tập sắp thứ tự tốt khi nó hoàn toàn được sắp xếp và mọi tập con không rỗng đều có phần tử nhỏ nhất Thứ tự tương ứng với tập này được gọi là thứ tự tốt.

1.1.2 Thứ tự từ Thứ tự từ  là một thứ tự toàn phần trên tập M tất cả các đơn thức của vành K[x] thỏa mãn các điều kiện sau:

(ii) Nếu m m m, 1 , 2 M mà m 1 m 2 thì mm 1 mm 2

Cho  là một thứ tự từ Sau khi đổi chỉ số các biến, luôn có thể giả thiết

+ Thứ tự từ điển lex xác định: x 1  1 x n  n  lex x 1  1 x n  n khi và chỉ khi tồn tại

0 i n sao cho  1  1 ,  2  2 , ,  i  i và  i  1  i  1 , là một thứ tự từ + Thứ tự từ điển phân bậc glex xác định: x 1  1 x n  n  glex x 1  1 x n  n khi và chỉ khi

1 1 deg(x  x n  n )deg(x  x n  n ) hoặc deg(x 1  1 x n  n )deg(x 1  1 x n  n ) và

1 n n lex 1 n n x  x   x  x  , là một thứ tự từ

+ Thứ tự từ điển ngược rlex xác định: x 1  1 x n  n  rlex x 1  1 x n  n khi và chỉ khi

1 1 deg(x  x n  n )deg(x  x n  n ) hoặc deg(x 1  1 x n  n )deg(x 1  1 x n  n ) và thành phần đầu tiên khác không tính từ bên phải của vectơ (  1  1 , , n  n ) là một số dương, là một thứ tự từ

Giả sử  là một thứ tự từ đã được xác định trên tập các từ của vành R = K[x] Thứ tự này được ký hiệu là  và được định nghĩa rõ ràng trong ngữ cảnh của các từ trong vành.

Nếu 0, Kvà ,m nM sao cho mn (tương ứng mn) thì  m.n

1.1.3 Thứ tự theo trọng liên kết và tích từ điển của các thứ tự (bộ phận)

+ Hàm trọng số  trên vành K[x] là một phiếm hàm tuyến tính n 

Hàm trọng số nguyên là hàm trọng số mà ( n ) 

+ Thứ tự theo trọng liên kết với  là thứ tự bộ phận  trên M xác định bởi

+ Hàm trọng số  tương thích với thứ tự từ  nếu m 1   m 2 kéo theo m 1 m 2

Trong tập X, các thứ tự bộ phận được ký hiệu là    1 , , s Tích từ điển R  của các thứ tự này xác định một quan hệ giữa các phần tử x và y trong X, với điều kiện rằng tồn tại một chỉ số 1 i s sao cho x và y không thể so sánh với nhau theo các thứ tự    1 , , i  1 và x nhỏ hơn y theo thứ tự i.

+ Các hàm deg( )a    a 1 a 2 a n (gọi là hàm bậc tổng thể) và hàm  i ( )a a i ,

1 i n là những hàm trọng số

Hàm bậc tổng thể tương thích với một thứ tự từ, được gọi là thứ tự từ phân bậc Trong đó, thứ tự từ điển phân bậc và thứ tự từ điển ngược đều thuộc loại thứ tự từ phân bậc.

+ Thứ tự theo trọng là một thứ tự bộ phận, không phải là thứ tự từ

Nhận xét: (a) Cho   là thứ tự theo trọng liên kết với λ Khi đó với mỗi

(i) m m 1 , 2 so sánh được với nhau theo   khi và chỉ khi m 1 m 2 hoặc

(ii) m m 1 , 2 không so sánh được với nhau theo   khi và chỉ khi m 1 m 2 hoặc

(b) Cho  là thứ tự theo trọng Khi đó (1) 0 

1.1.4 Định lý Cho  là một thứ tự từ Khi đó nếu m m thì 1 2 m 1 m 2 Tuy nhiên điều ngược lại không đúng

Chứng minh: Giả thiết m m 1 2 suy ra tồn tại mMsao cho m 2 mm 1

Vì  là thứ tự từ nên 1 m m 1 1m m 1  m 1 m 2  Điều ngược lại không đúng Chẳng hạn xét cho thứ tự từ điển lex:

Chọn m 1 x x 1 2 , m 2 x 1 2 Rõ ràng m 1  lex m 2 nhưng m 2 không chia hết cho m 1

1.1.5 Định lý Cho  là một thứ tự từ và m 1 m 2

Nếu  là thứ tự từ phân bậc thì giữa m 1 , m 2 chỉ có hữu hạn đơn thức

Nếu  là thứ tự từ bất kỳ thì giữa m 1 , m 2 có thể có vô hạn đơn thức

Chứng minh Gọi n 1 deg(m 1 ), n 2 deg(m 2 )  n n 1 , 2  và n 1 n 2

(vì nếu ngược lại n 2 n 1 deg(m 2 )deg(m 1 )m 2 m 1 trái giả thiết)

+ Nếu đơn thức m ở giữa m m 1 , 2 ; tức là m 1  m m 2 Khi đó

1 2 1 2 deg(m)deg( )m deg(m ) n deg( )m n Giả sử mx a với a( ,a a 1 2 , )a n có

1 deg( a ) 2 1 1 2 n 2 n  x n     n a a a n Tuy nhiên tập các bộ số mũ a( ,a a 1 2 , )a n sao cho n 1    a 1 a 2 a n n 2 là hữu hạn nên tập các đơn thức m nằm giữa m 1 , m 2 là hữu hạn 

+ Nếu  là thứ tự từ bất kỳ giữa m m 1 , 2 có thể có vô hạn đơn thức

Thật vậy, chẳng hạn xét cho thứ tứ tự từ điển  lex :

Ta có mx x 1 2 2 n với n thỏa mãn m 1  m m 2

Rõ ràng m xác định như vậy là vô hạn 

1.1.6 Định lý Cho  là một thứ tự từ sao cho x 1 x 2   x n Khi đó với mọi s  2 thì x 1 s  x 2 s   x n s

Chứng minh: Cần chứng minh x 1 s x 2 s Thật vậy, chứng minh khẳng định tổng quát hơn x 1 s i  x 2 i x 1 s j  x 2 j , 0   i j s và sau đó cho i0 và js Hay cần chứng minh

Do x 1 x 2 và  là thứ tự từ nên

Định lý 1.1.7 khẳng định rằng cho một dãy số thực dương độc lập tuyến tính u = (u₁, u₂, , uₙ) trong không gian n chiều, ta có thể thiết lập một thứ tự u Cụ thể, mối quan hệ a ≤ᵤ b được định nghĩa là a