Quan hệ | Tóm tắt lý thuyết Toán rời rạc | Đại học Ngoại Ngữ Tin Học TP Hồ Chí Minh

CHƯƠNG 3: QUAN HỆ

QUAN HỆ

Định nghĩa 3.1.1

Một quan hệ giữa tập hợp 𝐴 và tập hợp 𝐵 là một tập hợp con 𝑅 của 𝐴 × 𝐵. Nếu ( 𝑎, 𝑏) ∈ 𝑅, ta viết 𝑎𝑅𝑏.

Một quan hệ giữa 𝐴 và 𝐴 được gọi là quan hệ trên 𝐴

Ví dụ:

1. 𝐴 = { 1,2,3,4}, 𝐵 = { 4,5}

𝑅 =   {( 1,4),( 1,5),( 3,5),( 4,4)}

Là một quan hệ giữa 𝐴 và 𝐵. Ta thường biểu diễn quan hệ 𝑅 bởi sơ đồ sau:

2. Quan hệ “=” trên một tập hợp 𝐴 bất kỳ: ( 𝑎𝑅𝑏) ⟺ 𝑎 = 𝑏

3. Quan hệ “≤” trên 𝑍, O hay 𝑅: ( 𝑎𝑅𝑏) ⟺ 𝑎 ≤ 𝑏

Trên 𝑍 quan hệ ≤ có thể biểu diễn bởi sơ đồ:

4. Gọi 𝑓 là tập hợp các đường thẳng trong mặt phẳng. Quan hệ song song được định nghĩa bởi: 𝐿𝑅𝑀 ⟺ 𝐿/ / 𝑀

5. Một số nguyên 𝑎 được nói là chia hết cho số nguyên 𝑛 nếu tồn tại số nguyên 𝑘 sao cho 𝑎 = 𝑘𝑛.

Khi ấy ta cũng nói 𝑛 là ước số của 𝑎 và 𝑎 là bội số của 𝑛.

Giả sử 𝑛 là một số nguyên >1 và 𝑎 ∈ 𝑁

Xét các bội số không âm của n: 0, 𝑛, 2𝑛,…, 𝑘𝑛,…

Trong số này, các bội số ≤ 𝑎 tạo thành một tập hợp hữu hạn nên ta có thể tìm được bội số 𝑞𝑛 lớn nhất:

𝑞𝑛 ≤ 𝑎 < ( 𝑞 + 1) 𝑛

Đặt 𝑟 = 𝑎 = 𝑞𝑛     ta có 𝑎 = 𝑞𝑛 + 𝑟     𝑣ới 0 ≤ 𝑟 < 𝑛

Ta nói rằng 𝑞 và 𝑛 là thương số và dư số trong phép chia (có dư) 𝑎 cho 𝑛.

Chú ý rằng 𝑞 và 𝑟 tồn tại duy nhất. thật vậy,giả sử tồn tại 𝑞′, 𝑟′ ∈ 𝑁 sao cho:

𝑎 = 𝑞′𝑛 + 𝑟′, 0 ≤ 𝑟 < 𝑛

Ta có thể giả sử 𝑟 ≤ 𝑟. Khi ấy: 𝑞𝑛 + 𝑟 = 𝑞′𝑛 + 𝑟′

Suy ra ( 𝑞 − 𝑞′) 𝑛 = 𝑟′ − 𝑟 ≥ 0

Rõ ràng 𝑟′ − 𝑟 < 𝑛 ≤ ( 𝑞 − 𝑞′) 𝑛 nếu 𝑞 − 𝑞′ ≥ 1

Cho trước số nguyên 𝑛 > 1, ta định nghĩa quan hệ: 𝑎𝑅𝑏 ⟺ 𝑎 − 𝑏 chia hết cho 𝑛 Quan hệ này được nói là quan hệ đồng dư modulo 𝑛. Nếu 𝑎𝑅𝑏 ta viết: 𝑎 ≡ 𝑏( 𝑚o𝑑 𝑛) Rõ ràng khi ấy 𝑎 và 𝑏 có cùng dư số khi chia cho 𝑛

Với 𝑛 = 7 ta có 9 ≡ 2( 𝑚o𝑑 7) và 3 ≡ 10( 𝑚o𝑑 7) nhưng 3 ≢ 6( 𝑚o𝑑 7).

Định nghĩa 3.1.2:

Cho trước các tập hợp 𝐴1, 𝐴2,…, 𝐴𝑛. Khi ấy ánh xạ chiếu lên thành phần thứ i là ánh xạ:

𝜋_i:  𝐴₁ × 𝐴₂ × …× 𝐴_𝑛   ⟼ 𝐴_i; ( 𝑎₁, 𝑎₂,…, 𝑎_𝑛)     ⟼ 𝑎_i

1. Ánh xạ chiếu 𝜋i rõ ràng là một toàn ánh

2. Đặc biệt các ánh xạ chiếu 𝜋_Æ, 𝜋_𝐵 từ 𝐴 × 𝐵 lên 𝐴 và 𝐵 tương ứng là các toàn ánh. Tuy nhiên nếu 𝑅 là tập hợp con của 𝐴 × 𝐵, nghĩa là một quan hệ giữa A và B thì 𝜋_Æ( 𝑅) và 𝜋_𝐵( 𝑅) có thể là tập hợp con thực sự của A và B tương ứng như các ví dụ sau cho thấy.

Ví dụ:

1. 𝐴 = 𝐵 = 𝑍, 𝑅 = {( 𝑥, 𝑦) / 𝑦 = |𝑥|}

Quan hệ 𝑅 được biểu diễn bởi sơ đồ

Ta có 𝜋_𝐴( 𝑅) = 𝑍

Tuy nhiên 𝜋_𝐵( 𝑅) = 𝑁  $\underset{Khác}{\subset }$ 𝐵 = 𝑍

2.   𝐴 = 𝐵 = 𝑅, 𝑅 = {( 𝑥, 𝑦) ∈ 𝐴 × 𝐵/ 𝑦 = 𝑥²}

Rõ ràng 𝜋_𝐴( 𝑅) = 𝐴 = 𝑅 trong khi 𝜋_𝐵( 𝑅) = [ 0, + ∞) = {𝑥 ∈ 𝑅/ 𝑥 ≥ 0} 𝑅

3.   𝐴 = 𝐵 = [ −1,1] = { 𝑥 ∈ 𝑅/ −1 ≤ 𝑥 ≤ 1} và 𝑅 = {( 𝑥, 𝑦) ∈ 𝐴 × 𝐵/ 𝑥² + 𝑦² ≤ 1}

Khi ấy 𝜋_Æ( 𝑅) = 𝜋_𝐵( 𝑅) = 𝐴 = 𝐵 mặc dù 𝑅$\underset{\mathrm{khác}}{\subset }$𝐴 × 𝐵

Định nghĩa 3.1.3

Một quan hệ trên các tập hợp 𝐴₁ × 𝐴₂ × …× 𝐴_𝑛 là một tập hợp con của

$\underset{i=1}{\overset{n}{G}}$ 𝐴_i = 𝐴₁ × 𝐴₂ × …× 𝐴_𝑛

Chú ý:

1. Giả sử 𝑅 là một quan hệ trên 𝐴₁, 𝐴₂,…, 𝐴_𝑛. Khi ấy các phần tử của 𝑅 là những bộ 𝑛 ( 𝑎₁, 𝑎₂,…𝑎_𝑛)

2. Xét 𝑚 số nguyên 1 ≤ i₁ < i₂ < ⋯ < i_𝑚 ≤ 𝑛. Khi ấy ta cũng có thể định nghĩa một ánh xạ chiếu

𝜋_i1,_i2,…,i𝑚:  𝐴₁ × 𝐴₂ × …× 𝐴_𝑛  ⟶ 𝐴_i1 × 𝐴_i2 × …× 𝐴_i𝑚

( 𝑎₁, 𝑎₂,…, 𝑎_𝑛)             ⟼       (𝑎_i1, 𝑎_i2 ,…, _𝑎i𝑚 )

Rõ ràng 𝜋_{i1,i2,…,i𝑚} cũng là một toàn ánh.

Định nghĩa 3.1.4

Nếu 𝑅 một quan hệ trên 𝐴₁, 𝐴₂,…, 𝐴_𝑛 thì 𝜋_{i1,i2,…,i𝑚} ( 𝑅) được gọi là quan hệ chiếu của 𝑅.

Chú ý:

1. Quan hệ chiếu 𝜋_{i1,i2,…,i𝑚} ( 𝑅) là một quan hệ trên 𝐴_i1 × 𝐴_i2 × …× 𝐴_i𝑚.

2. Trong Lý thuyết về cơ sở dữ liệu mô hình quan hệ, các tập hợp 𝐴₁, 𝐴₂,…, 𝐴_𝑛 được gọi là các thuộc tính. Như thế quan hệ chiếu 𝜋i ,i ,…,i𝑚 ( 𝑅) chính là quan hệ ban đầu nhưng các thuộc tính không thuộc các tập hợp 𝐴i1, 𝐴i2 ,…, 𝐴i𝑚   đã được bỏ qua như ví dụ sau cho thấy

Ví dụ: trong cơ sở dữ liệu Môn học ở Đại học Khoa học Tự nhiên, ta có các tập hợp thuộc tính sau:

𝐴1: các mã số môn học

𝐴2: các tên môn học

𝐴3: các Giảng viên

Quan hệ Môn học - Giảng viên được cho bởi bảng sau:

Quan hệ chiếu 𝜋_{1 2}  (Môn học-Giảng viên) là quan hệ Môn học được cho bởi bảng

Mặt khác quan hệ chiếu 𝜋₃ (Môn học – Giảng viên) chính là quan hệ Giảng viên: {Ông Bình, Ông An, Ông Minh, Cô Hà}.

QUAN HỆ TƯƠNG ĐƯƠNG

Định nghĩa 3.2.1

Một quan hệ 𝑅 trên tập hợp 𝐴 được nói là phản xạ nếu: ∀𝑥 ∈ 𝐴, 𝑥𝑅𝑥

Ví dụ:

1. Quan hệ “=” trên một tập hợp bất kỳ, quan hệ “≤” trên 𝑍, O, 𝑅, quan hệ đống dư trên Z là phản xạ

2. Quan hệ “// ” trên 𝑓 là phản xạ. Tuy nhiên quan hệ “⊥” (vuông góc) trên 𝑓 không phải là quan hệ phản xạ.

Chú ý: gọi ∆Ælà đường chéo chính của 𝐴 × 𝐴 : ∆_Æ= {( 𝑎, 𝑎) / 𝑎 ∈ 𝐴}. Khi ấy quan hệ 𝑅 trên 𝐴 là phản xạ khi và chỉ khi 𝑅 ⊃ ∆_Æ.

Định nghĩa 3.2.2

Quan hệ 𝑅 trên 𝐴 được nói là đối xứng nếu: ∀𝑥, 𝑦 ∈ 𝐴, 𝑥𝑅𝑦 ⟹ 𝑦𝑅𝑥

Ví dụ:

1. Các quan hệ “= , ≡, //, ⊥” là những quan hệ đối xứng

2. Quan hệ “≤” trên 𝑍, O, 𝑅 không phải là quan hệ đối xứng

3. Quan hệ 𝑅 = {( 1,2).( 2,1),( 1,3),( 3,1)} trên 𝐴 = { 1,2,3,4} là một quan hệ đối xứng nhưng không phản xạ:

Chú ý: trong hình vẽ trên ta thấy tập hợp 𝑅 tự đối xứng qua đường chéo ∆_Æ. Tổng quát hơn một quan hệ 𝑅 trên tập hợp 𝐴 bất kỳ là đối xứng khi và chỉ khi 𝑅 là tự đối xứng qua ∆𝐴

Định nghĩa 3.2.3

Một quan hệ 𝑅 trên 𝐴 được nói là bắc cầu nếu:

∀𝑥, 𝑦, 𝑧, ( 𝑥𝑅𝑦) 𝖠 ( 𝑦𝑅𝑧) ⟹ 𝑥𝑅𝑧

Ví dụ:

• Các quan hệ “= , ≡, //, ≤” là các quan hệ bắc cầu
• Quan hệ “⊥” trên 𝑓 không phải là quan hệ bắc cầu
• Quan hệ {(1,1),(2,3),(3,4),(2,4)} trên 𝐴 = { 1,2,3,4} là bắc cầu 

Định nghĩa 3.2.4

Một quan hệ 𝑅 trên tập 𝐴 được gọi là quan hệ tương đương nếu nó phản xạ, đối xứng, bắc cầu.

Ví dụ:

1. Các quan hệ “= , ≡, //” là các quan hệ tương đương

2. Quan hệ “≤, ⊥” không phải là một quan hệ tương đương

3. Quan hệ 𝑅 = {( 1,1),( 2,2),( 3,3),( 2,3),( 3,2)} trên 𝐴 = {1,2,3} là quan hệ tương đương

4. Quan hệ “tương đương logic” trên tập hợp các mệnh đề là một quan hệ tương đương.

5. Cho trước một ánh xạ ƒ: 𝐴 ⟶ 𝐵. Ta định nghĩa quan hệ 𝑅 trên 𝐴 như sau:

𝑥𝑅𝑦 ⟺ ƒ( 𝑥) = ƒ( 𝑦)

Khi đó 𝑅 là một quan hệ tương đương.

Định nghĩa 3.2.5

Giả sử 𝑅 là một quan hệ tương đương trên 𝐴 và 𝑥 ∈ 𝐴. Khi ấy lớp tương đương chứa 𝑥 là tập hợp con: { 𝑦 ∈ 𝐴/ 𝑦𝑅𝑥}

Chú ý: lớp tương đương chứa 𝑥 thường được ký hiệu bởi 𝑥̅ hay [ 𝑥]

Ví dụ: Quan hệ ≡ ( 𝑚o𝑑 3) có ba lớp tương đương:

$\overline{0}$ =  {,…, −6, −3,0,3,…}

$\overline{1}$ =  {,…, −5, −2,1,4,…}

$\overline{2}$ =  {,…, −4, −1,2,5,…}

Để ý rằng:

$$\begin{gathered} \overline{0}=\overline{3}=\overline{6}=... \\ \overline{1}=\overline{4}=\overline{7}=... \\ \overline{2}=\overline{5}=\overline{8}=... \end{gathered}$$

Như thế { $\overline{0}; \overline{1}; \overline{2}$}  là một phân hoạch của 𝑍, nghĩa là Z là hợp của 3 tập hợp đôi một  rời nhau { 0̅, 1̅, 2̅}. Tỗng quát hơn ta có: Định nghĩa 3.2.1

Giả sử 𝑅 là một quan hệ tương đương trên 𝐴. Khi ấy:

i. ∀𝑥 ∈ 𝐴, 𝑥 ∈ 𝑥̅

ii. ∀𝑥, 𝑦 ∈ 𝐴, 𝑥𝑅𝑦 ⟺

iii.  Hai lớp tương đương 𝑥̅  và 𝑦̅ sao cho 𝑥̅ ∩ 𝑦̅ ≠ ∅  thì trùng nhau

Chứng minh:

i. Do tính phản xạ, 𝑥𝑅𝑥. Nói cách khác 𝑥 ∈ 𝑥̅

ii.  Giả sử 𝑥𝑅𝑦. Gọi 𝑧 là một phần tử bất kỳ của 𝑥̅

Ta  có:  𝑧𝑅𝑥  và  𝑥𝑅𝑦  nên 𝑧𝑅𝑦  do  tính  bắt  cầu.Như  thế 𝑥̅  ⊂ 𝑦̅.  Mặt  khác  do  tính  đối xứng ta cũng có 𝑦𝑅𝑥. Do đó chứng minh tương tự như trên ta có 𝑦̅ ⊂ 𝑥̅.

Ngược lại giả sử 𝑥̅  =  𝑦̅, do 𝑥 ∈ 𝑥̅  nên 𝑥 ∈ 𝑦̅. Điều này có nghĩa là 𝑥𝑅𝑦

iii. Giả sử 𝑥̅ ∩ 𝑦̅ ≠ ∅. Khi ấy tồn tại 𝑧 ∈ 𝑥̅ ∩ 𝑦̅, nghĩa là 𝑧𝑅𝑥  và 𝑧𝑅𝑦. Do ii) ta có 𝑥̅  =  𝑧̅ =  𝑦̅

Ví dụ:

1.  Xét quan hệ 𝑅 trên 𝑍: 𝑚𝑅𝑛 ⟺ 𝑚2 = 𝑛2

Theo ví dụ 5 sau Định nghĩa 3.2.4, 𝑅 là quan hệ tương đương xác định bởi ánh xạ

𝑥 ⟼ 𝑥2 từ 𝑍 vào 𝑍. Các lớp tương đương là { 0},{ −1,1},{ −2,2},…,{ −𝑛, 𝑛},…

Ở đây 𝑍 được phân hoạch thành vô số tập hợp con hữu hạn.

Với 𝑛 ∈ 𝑍, quan hệ đồng dư (mod 𝑛) là một quan hệ tương đương với 𝑛 lớp tương đương 0̅, 1̅, …, 𝑛̅ ̅−̅ ̅1̅. Ta ký hiệu: 𝑍𝑛  =  { 0̅, 1̅, …, 𝑛̅ ̅−̅ ̅1̅}

Các phần tử của, được gọi là các số nguyên đồng dư mod 𝑛.

Với 𝑎̅, 𝑏̅ ∈ 𝑍𝑛,  chọn  tùy  ý 𝑥  ∈ 𝑎̅  và 𝑦 ∈ 𝑏̅.  Ta  có  thể  kiểm tra được ̅𝑥̅+̅ ̅𝑦̅  không  phụ    thuộc  vào 𝑥  và 𝑦 mà  chỉ phụ thuộc  vào 𝑎̅  và 𝑏̅. Do đó ta có thể dùng ̅𝑥̅+̅ ̅𝑦̅  để định  nghĩa

𝑎̅ +  𝑏̅. Đặc biệt ta có thể chọn 𝑥 =  𝑎 và 𝑦 =  𝑏: 𝑎̅ +  𝑏̅  =  ̅𝑎̅+̅ ̅𝑏̅

Tương tự ta có: $\overline{ab}=\overline{a}\overline{b}$

Bây giờ ta có thẻ kiểm được 2 phép toán ∙, + trên 𝑍𝑛 thỏa các tính chất tương tự như các phép toán ∙, + trên 𝑍:

• Tính giao hoán: ∀𝑥̅, 𝑦̅,

𝑥̅ +  𝑦̅  =  𝑦̅ +  𝑥̅ và   𝑥̅𝑦̅ =  𝑦̅𝑥̅

• Tính kết hợp: ∀𝑥̅, 𝑦̅, 𝑧,̅

=  ( 𝑥̅ +  𝑦̅) +  𝑧̅ và   𝑥̅( 𝑦̅𝑧   =  ( 𝑥̅𝑦̅) 𝑧

• Tính phân bố: ∀𝑥̅, 𝑦̅, 𝑧̅, 𝑥̅( 𝑦̅ +  𝑧̅)  =  𝑥̅𝑦̅ +  𝑥̅𝑧̅
• Phần tử trung hòa: ∀𝑥̅

𝑥̅ +  0̅  =  𝑥̅

𝑥̅1̅  =  𝑥̅

• Phần tử đối: ∀𝑥̅, 𝑥̅ +  (̅𝑛̅ ̅−̅ ̅𝑥̅)̅ =  0̅

Ta nói 𝑍𝑛 cũng như 𝑍 là những vành giao hoán có đơn vị

THỨ TỰ

Định nghĩa 3.3.1

Một quan hệ 𝑅 trên tập hợp 𝐴 được gọi là phản xứng nếu:

∀𝑥, 𝑦, ( 𝑥𝑅𝑦) 𝖠 ( 𝑦𝑅𝑥) ⟹ 𝑥 = 𝑦

Ví dụ:

Quan hệ “≤” trên 𝑍, O hay R là phản xứng Quan hệ “ ≡,/ / ” không phản xứng

Chú ý: trái với các quan hệ đối xứng, đối với một quan hệ phản xứng 𝑅, mọi bộ phận tự đối xứng của 𝑅 đều nằm trong đường chéo ∆_Æ

Định nghĩa 3.3.2

Một quan hệ trên tập hợp 𝐴 được nói là một thứ tự nếu nó phản xạ, phản xứng và bắc cầu. Khi ấy ta nói 𝐴 là một tập hợp sắp thứ tự (hay có thứ tự)

Chú ý:

1. Ta thường ký hiệu một thứ tự bởi ≺. Cặp ( 𝐴, ≺) là một tập hợp có thứ tự.

2. Giả sử 𝐵 là một tập hợp con của tập hợp có thứ tự ( 𝐴, ≺). Khi ấy ≺ cảm sinh một thứ tự trên 𝐵 một cách tự nhiên: với 𝑥, 𝑦 ∈ 𝐵, ta nói 𝑥 ≺ 𝑦 trong 𝐵 nếu 𝑥 ≺ 𝑦 trong 𝐴.

Ví dụ:

1. ( 𝑅, ≤) là một tập hợp có thứ tự. Thứ tự cảm sinh các thứ tự tự nhiên trên 𝑍, O.

2.  Nhắc lại tập hợp 𝑃( 𝐸) ta có quan hệ: 𝐴 ≺ 𝐵 ⟺ 𝐴 ⊂ 𝐵

Khi đó ≺ là một thứ tự trên 𝑃( 𝐸) gọi là thứ tự bao hàm. Ký hiêu 𝐴 ⊂ 𝐵 sẽ được dùng thay vì ≺

Trên tập hợp 𝑀 các dạng mệnh đề, ta định nghĩa 𝐸 ≺ 𝐹 khi và chỉ khi 𝐸 ⟹ 𝐹, nghĩa

𝐹 là một hệ quả logic của 𝐸. Rõ ràng quan hệ trên có tính phản xạ và bắc cầu.

Mặt khác nếu 𝐸 ⟹ 𝐹 và 𝐹 ⟹ 𝐸 thì 𝐸 𝑣à 𝐹 𝑡ươ𝑛𝑔 đươ𝑛𝑔 𝑙o𝑔i𝑐 . Do đó nếu ta đồng nhất các dạng mệnh đề tương đương logic thì quan hệ trên trở thành một thứ tự trên 𝑀.

Chính xác hơn, ta thấy quan hệ tương đương logic là một quan hệ tương đương trên 𝑀 . Ta có một quan hệ trên tập hợp các lớp tương đương như sau: [ 𝐸] ≺ [ 𝐹]  ⟺ 𝐹 là hệ quả logic của 𝐸

Khi ấy quan hệ trên vẫn còn là phản xạ và bắc cầu.

Giả sử [ 𝐸] ≺ [ 𝐹] và [ 𝐹] ≺ 𝐸. Khi ấy 𝐹 là hệ quả logic của 𝐸 và ngược lại, nghĩa là 𝐸 và 𝐹 tương đương logic. Suy ra [ 𝐸] = [ 𝐹]

Do đó ≺ là một thứ tự trên tập hợp các lớp tương đương của 𝑀.

Ví dụ: Gọi 𝑛 là một số nguyên dương. Đặt: ࣯𝑛 = { 𝑎 ∈ 𝑁/ 𝑎|𝑛}

Trong đó 𝑎|𝑛 có nghĩa 𝑎 là một ước của n hay n chia hết cho a. Trên ࣯𝑛 ta có thể định nghĩa một quan hệ: 𝑥 ≺ 𝑦 ⟺ 𝑥|𝑦

Khi ấy rõ ràng là phản xạ và bắc cầu Giả sử 𝑥 ≺ 𝑦 và 𝑦 ≺ 𝑥. Ta có: 𝑦 = 𝑎𝑥 và  𝑥 = 𝑏𝑦 với 𝑎, 𝑏 ∈ 𝑍+

Suy ra

𝑦 = 𝑎𝑏𝑦 ⟹ 𝑎𝑏 = 1 𝑣ì 𝑦 > 0

Do 𝑎, 𝑏 ∈ 𝑍+ ta phải có 𝑎 = 𝑏 = 1, nghĩa là 𝑥 = 𝑦 Quan hệ thứ tự trên vẫn được ký hiệu bởi 𝑥|𝑦 Với 𝑛 = 12 ta có ࣯12 = { 1,2,3,4,6,12}

Do đó ta có thể liệt kê các cặp thuộc quan hệ trên:

{( 1,1),( 1,2),( 1,3),( 1,4)( 1,6),( 1,12), ( 2,2),( 2,4),( 2,6),( 2,12),( 3,3),( 3,6),( 3,12),( 4,4),( 4,12),( 6,6),( 12,12)}

Tuy nhiên đối với các tập hợp hữu hạn có nhiều phần tử, ta không thể dùng phương pháp liệt kê như trên mà sẽ sử dụng biểu đồ Hasse

Định nghĩa 3.3.3

Xét một tập hợp có thứ tự ( 𝐴, ≺) và 𝑥, 𝑦 là hai phần tử bất kỳ của 𝐴

i. Nếu 𝑥 ≺ 𝑦 ta nói 𝑦 là trội của 𝑥 hay 𝑥 được trội bởi 𝑦

ii. 𝑦 là trội trực tiếp của 𝑥 nếu 𝑦 trội 𝑥 và không tồn tại một trội 𝑧 của 𝑥 sao cho: 𝑥 $\underset{khác}{\prec }$ 𝑧  $\underset{khác}{\prec }$𝑦

Định nghĩa 3.3.4

Biểu đồ Hasse của một tập hợp hữu hạn có thứ tự ( 𝐴, ≺) bao gồm:

i. Một tập hợp các điểm trong mặt phẳng tương ứng 1 – 1 với 𝐴, gọi là các đỉnh

ii. Một tập hợp các cung có hướng nối một số đỉnh: hai đỉnh 𝑥, 𝑦 được nói lại bởi một cung có hướng (từ 𝑥 tới 𝑦) nếu 𝑦 là trội trực tiếp của 𝑥.

Trên đây là biểu đồ Hasse của tập hợp sắp thứ tự { 𝑎₁, 𝑎₂, 𝑎₃, 𝑎₄, 𝑎₅, 𝑎₆} trong đó:

𝑎₁ ≺ 𝑎₂ < 𝑎₃ và 𝑎₄ ≺ 𝑎₅ ≺ 𝑎₃

𝑎₆ không so sánh được với các p hần tử khác, nghĩa là với 1 ≤ i ≤ 5 thì 𝑎₆ ⊀ 𝑎_i và 𝑎_i ⊀ 𝑎₆.

Ở đây ta quy ước các cung là không chéo nhau. Do đó một cách để hình dùng dễ dàng là xem như Biểu đồ Hasse của 𝑃( 𝐸) gồm các đỉnh và cạnh của một hình lập phương 3 chiều.

4. Biểu đồ Hasse của { 1,2,3,4,5} với thứ tự thông thường có dạng một dây chuyền:

Ta có thể duyệt hết các đỉnh một lần bằng cách đi theo các cung mà không quay trở lại

Cũng thế trong vô hạn, ta cũng có thể quy ước biểu diễn thứ tự trên bởi biểu đồ                                              

Biểu đồ Hasse trên vẫn còn là một dây chuyền vô hạn

Định nghĩa 3.3.5

Một thứ tự trên 𝐴 được nói là toàn phần nếu hai phần tử bất kỳ đều so sánh được, nghĩa là mệnh đề sau là đúng:

∀𝑥, 𝑦 ∈ 𝐴, ( 𝑥 ≺ 𝑦) 𝗏 ( 𝑦 ≺ 𝑥)

Ví dụ:

1. 𝑁, 𝑍, O, 𝑅 với thứ tự ≤ thông thường là những tập hợp sắp thứ tự toàn phần

2.Xét một tập hợp hữu hạn không rỗng 𝘗 mà ta gọi là bộ mẫu tự. Giả sử trên 𝘗 có một thứ tự toàn phần ≺ (ví dụ như thứ tự thông thường nếu 𝘗 là bộ chữ cái: 𝑎 ≺ 𝑏 ≺ 𝑐 ≺ ⋯ ≺ 𝑧, hay thứ tự xác định bởi mã ASCII nếu 𝘗 là bộ chữ cái được mở rộng thêm các ký tự là các số từ 0 đến 9, các dấu+,-,…)

Gọi 𝑆 là tập hợp các chuỗi ký tự có dạng 𝑠 = 𝑎1𝑎2 …𝑎𝑚 và 𝑎1𝑎2 …𝑎𝑚 ∈ 𝘗 với 𝑚 là số nguyên tự nhiên tùy ý. Với 𝑚 = 0 , ta được chuỗi rỗng ∅ không có ký tự nào cả. ta sẽ định nghĩa một quan hệ ≺ trên 𝑆 như sau:

• ∅ ≺ 𝑠, ∀𝑠 ∈ 𝑆
• Nếu 𝑠 = 𝑎1𝑎2 …𝑎𝑚 và 𝑡 = 𝑏1𝑏2 …𝑏𝑛 là hai chuỗi khác ∅, ta định nghĩa 𝑠 ≺ 𝑡 khi và chỉ khi một trong hai điều kiện sau được thỏa:

i. Tồn tại một chỉ số i, 1 ≤ i ≤ 𝑚 sao cho: 𝑎₁ = _𝑏1,…, 𝑎_i−1 = 𝑏_i−1 và  𝑎i $\underset{khác}{\prec }$𝑏i

ii. 𝑚 ≤ 𝑛 và 𝑎₁ = 𝑏₁,…, 𝑎_𝑚 = 𝑏_𝑚

Ta chứng minh được rằng ≺ là một thứ tự trên 𝑆 gọi là thứ tự tự điển. Hơn nữa với thứ tự tự điển, 𝑆 là một tập sắp thứ tự toàn phần (Bài tập)

Bây giờ với Định nghĩa 3.3.5, nhận xét trên đây về biểu đồ Hasse có thẻ được phát biểu dưới dạng một kết quả tổng quát hơn mà chứng minh là hiển nhiên.

Mệnh đề 3.3.1:

Biểu đồ Hasse của ( 𝐴, ≺) là một dây chuyền khi và chỉ khi ≺ là một thứ tự toàn phần trên 𝐴.

Do Mệnh đề 3.3.1, biểu đồ Hasse của một tập hợp sắp thứ tự toàn phần hữu hạn là một dây chuyền  xuất phát từ một phần tử 𝑎 và chấm dứt bởi 1 phần tử 𝑏. Rõ ràng 𝑎 là phần tử bé nhất và 𝑏 là phần tử lớn nhất theo nghĩa: ∀𝑥 ∈ 𝐴, 𝑎 ≺ 𝑥 ≺ 𝑏

Mặt khác, Ví dụ 1 cho thấy phần tử bé nhất và lớn nhất không nhất thiết tồn tại, ngay cả trong 1 tập hợp sắp thứ tự hữu hạn. Tuy nhiên các phần tử 𝑎3, 𝑎6 là những phần tử tối đại và 𝑎1, 𝑎4, 𝑎6 là những phần tử tối tiểu theo nghĩa sau:

Định nghĩa 3.3.6:

Trong tập hợp sắp thứ tự ( 𝐴, ≺) , một phần tử 𝑚 được nói là tối đại (tương ứng tối tiểu ) nếu 𝑚 không có trội thực sự (tương ứng không là trội thực sự của phần tử nào cả). Nói cách khác mệnh đề sau là đúng:

∀𝑥 ∈ 𝐴, ( 𝑚 ≺ 𝑥) ⟹ ( 𝑚 = 𝑥) (tương ứng ∀𝑥 ∈ 𝐴, ( 𝑥 ≺ 𝑚) ⟹ ( 𝑥 = 𝑚))

Định lý 3.3.2

Trong một tập hợp sắp thứ tự 𝐴, phần tử lớn nhất 𝑚, nếu tồn tại, là phần tử tố đại duy nhất. Suy ra 𝑚 cũng là phần tử lớn nhất duy nhất. Kết luận tương tự cho phần tử bé nhất và phần tử tối tiểu.

Chứng minh: Giả sử 𝑚 là phần tử lớn nhất và tồn tại 𝑥 sao cho 𝑚 ≺ 𝑥. Do 𝑚 lớn nhất, ta cũng có 𝑥 ≺ 𝑚. Do tính phản xứng, ta có 𝑥 = 𝑚. Suy ra 𝑚 là một phần tử tối đại.

Mặt khác nếu gọi 𝑏 là một phần tử tối đại tùy ý, do 𝑚 lớn nhất ta có 𝑏 ≺ 𝑚. Nhưng 𝑏 là tối đại, ta phải có 𝑏 = 𝑚. Như thế 𝑚 là phần tử tối đại duy nhất và dĩ nhiên cũng là phần tử lớn nhất duy nhất. Kết luận cho phần tử bé nhất và các phần tử tối tiểu được chứng minh tương tự bằng cách đổi chiều các thứ tự (bất đẳng thức).

Sự tồn tại của phần tử tối đại đối với các tập hợp sắp thứ tự hữu hạn được cho bởi:

Định lý 3.3.3 

Trong một tập hợp sắp thứ tự hữu hạn thì:

i. Mọi phần tử được trội bởi (tương ứng trội) một phần tử tối đại (tương ứng tối tiểu)

ii. Nếu 𝑚 là phần tử tối đại (tương ứng tối tiểu) duy nhất của 𝐴 thì 𝑚 là phần tử lớn nhất (tương ứng phần tử bé nhất)

Chứng minh:

1. Xét một phần tử 𝑥 ∈ 𝐴. Nếu 𝑥 không tối đại sẽ có 𝑥₁ ∈ 𝐴 sao: 𝑥  $\underset{khác}{\prec }\circ$: x  x₁

Nếu 𝑥₁ tối đại thì đó là phần tử phải tìm.

Nếu không sẽ có 𝑥₂ ∈ 𝐴 sao cho: 𝑥₁$\underset{khác}{\prec }$𝑥₂

Nếu 𝑥₂ tối đại thì đó là phần tử phải tìm vì 𝑥₂ rõ ràng trội 𝑥. Nếu không ta tiết tiếp tục tìm được một trội thực sự của 𝑥₂ …

Do 𝐴 hữu hạn và các phần tử 𝑥, 𝑥₁, 𝑥₂,… đôi một khác nhau, quá trình trên sẽ dừng sau tối đa 𝑛 − 1 bước, trong đó 𝑛 = |𝐴|. Phần tử cuối cùng tìm được chính là phần tử tối đại trội 𝑥.

2. Giả sử 𝑚 là phần tử tối đại duy nhất của 𝐴, và 𝑥 là một phần tử tùy ý của 𝐴. Do i) tồn tại một phần tử tối đại 𝑦 sao cho: 𝑥 ≺ 𝑦.

Do 𝑚 duy nhất ta có: 𝑦 = 𝑚

Suy ra 𝑥 ≺ 𝑚, ∀𝑥 ∈ 𝐴

Nói cách khác 𝑚 là phần tử lớn nhất.

Chứng minh cho kết luận về phần tử tối tiểu và phần tử bé nhất hoàn toàn tương tự.

Chú ý: Nếu 𝐴 không hữu hạn, Định lý không đúng theo cả khi kết luận:

1. 𝐴 không có phần tử tối đa; ví dụ như 𝐴 = 𝑍 với thứ tự thông thường.

2. 𝐴 có thể có phần tử tối đại duy nhất 𝑚 nhưng không có phần tử lớn nhất như ví dụ sau cho thấy:

DÀN

Giả sử 𝐵 là một tập hợp con hữu hạn của tập hợp sắp thứ tự toàn phần 𝐴, khi ấy phần tử lớn nhất của 𝐵 tồn tại và được ký hiệu bởi max 𝐵. Tương tự, phần tử bé nhất của 𝐵 tồn tại, và được ký hiệu bởi min 𝐵.

Đối với các tập hợp sắp thứ tự không toàn phần , khái niệm max, min có thể được giảm nhẹ thành khái niệm sup và inf như sau:

Định nghĩa 3.4.1

Giả sử 𝐵 là một tập hợp con của tập hợp sắp thứ tự ( 𝐴, ≺). Khi ấy

1.  Một phần tử 𝑐 ∈ 𝐴 được nói là chặn trên (tương ứng chặn dưới ) chung của 𝐵 nếu: ∀𝑏 ∈ 𝐵, 𝑏 ≺ 𝑐 (tương ứng ∀𝑏 ∈ 𝐵, 𝑐 ≺ 𝑏)

2. Phần tử bé nhất (tương ứng lớn nhất) của tập hợp

{ 𝑐 ∈ 𝐴/ 𝑐 là chặn trên chung của 𝐵 } (tương ứng { 𝑐 ∈ 𝐴/ 𝑐 là chặn dưới chung của 𝐵 } ) được ký hiệu bởi sup 𝐵 (tương ứng inf 𝐵)

Ví dụ:

1. Trong một tập hợp sắp thứ tự toàn phần 𝐴, rõ ràng max 𝐵 của một tập hợp con hữu hạn 𝐵 chính là sup 𝐵. Tương tự min 𝐵 chính là inf 𝐵.

2. Giả sử 𝐵 = { 𝐵1, 𝐵2,…, 𝐵𝑛} là một tâp hợp con hữu hạn của 𝑃( 𝐸).

Khi ấy  $\underset{i=1}{\overset{n}{\cup }}$𝐵_i  chính là sup 𝐵  𝑣à $\underset{i=1}{\overset{n}{ሩ}}$ 𝐵_i  chính là inf 𝐵

Trên tập hợp 𝑀 các dạng mệnh đề với thứ tự ⟹, xét một tập hợp con hữu hạn ℰ = { 𝐸₁, 𝐸₂,…, 𝐸_𝑛}. Khi ấy 𝐸₁ 𝗏 𝐸₂ 𝗏 …𝗏 𝐸_𝑛 và 𝐸₁ 𝖠 𝐸₂ 𝖠 …𝖠 𝐸_𝑛 chính là sup ℰ và inf ℰ (Bài tập).

Định nghĩa 3.4.2 

Một tập hợp sắp thứ tự ( 𝐴, ≺) được nói là một dàn nếu với hai phần tử bất kỳ 𝑥, 𝑦 ∈ 𝐴, thì sup { 𝑥, 𝑦} và inf { 𝑥, 𝑦} luôn luôn tồn tại.

Ký hiệu: trong một dàn, ta sẽ ký hiệu sup { 𝑥, 𝑦} và inf { 𝑥, 𝑦} bởi 𝑥 𝗏 𝑦 và 𝑥 𝖠 𝑦.

Ví dụ:

1. Một tập hợp sắp thứ tự toàn phần là một dàn

2. 𝑃( 𝐸) với thứ tự bao hàm là một dàn. Ta có:

𝐵1 𝗏 𝐵2     =     𝐵1 𝖴 𝐵2

𝐵1 𝖠 𝐵2     =     𝐵1 ∩ 𝐵2

3. 𝑀 với thứ tự ⟹ là một dàn: với 𝐸, 𝐹  là hai dạng mệnh đề, các ký hiệu mới 𝗏,  𝖠 dành cho sup{ 𝐸, 𝐹} và inf{ 𝐸, 𝐹} trùng với các ký hiệu quen thuộc của phép nối rời và phép nối liền: 𝐸 𝗏 𝐹 và 𝐸 𝖠 𝐹.

4. Tập hợp 𝐴 = { 𝑎, 𝑏, 𝑐, 𝑑, e, ƒ} với biểu đồ Hasse dưới đây không phải là một dàn vì { 𝑏, 𝑐} không có sup. Thật vậy các trội chung của { 𝑏, 𝑐} là { 𝑑, e, ƒ} và tập hợp này không có phần tử bé.

Tương tự ta cũng thấy { 𝑑, e} không có inf.

Định lý 3.4.1

Trong một dàn ( 𝐴, ≺) các phép toán 𝗏 và 𝖠 thỏa các tính chất giao hoán và kết hợp:

i. 𝑥 𝗏 𝑦 = 𝑦 𝗏 𝑥 𝑣à 𝑥 𝖠 𝑦 = 𝑦 𝖠 𝑥 ∀𝑥, 𝑦 ∈ 𝐴

ii. 𝑥 𝗏 ( 𝑦 𝗏 𝑧) = ( 𝑥 𝗏 𝑦) 𝗏 𝑧 𝑣à 𝑥 𝖠 ( 𝑦 𝖠 𝑧) = ( 𝑥 𝖠 𝑦) 𝖠 𝑧 ∀𝑥, 𝑦 ∈ 𝐴

Chứng minh:

i) Hiển nhiên nên ta chỉ cần chứng minh ii). Xét 3 phần tử bất kỳ 𝑥, 𝑦, 𝑧 ∈ 𝐴. Khi ấy 𝑎 = 𝑥 𝗏 ( 𝑦 𝗏 𝑧) là một trội chung của 𝑥 và 𝑦 𝗏 𝑧 nên nó cũng là một trội chung của 𝑥, 𝑦 và 𝑧 thì 𝑦 𝗏 𝑥 ≺ 𝑐 vì 𝑦 𝗏 𝑧 là trội chung bé nhất của { 𝑦, 𝑧} . Như thế 𝑐  là trội chung của { 𝑥, 𝑦 𝗏 𝑧}. Suy ra 𝑎 = 𝑥 𝗏 ( 𝑦 𝗏 𝑧) ≺ 𝑐.

Như thế 𝑎 chính là trội chung bé nhất của { 𝑥, 𝑦, 𝑧}. Tương tự ta cũng thấy ( 𝑥 𝗏 𝑦) 𝗏 𝑧 cũng là trội chung bé nhất của { 𝑥, 𝑦, 𝑧}. Do phần tử bé nhất là duy nhất, ta có:

𝑥 𝗏 ( 𝑦 𝗏 𝑧) = ( 𝑥 𝗏 𝑦) 𝗏 𝑧

Chứng minh của 𝑥 𝖠 ( 𝑦 𝖠 𝑧) = ( 𝑥 𝖠 𝑦) 𝖠 𝑧 hoàn toàn tương tự.

Chú ý: Do tính kết hợp, nếu 𝐵 = {𝑥₁, 𝑥₂, …, 𝑥_𝑛} là một tập hợp con hữu hạn của dàn 𝐴 thì 𝑥₁ 𝗏 𝑥₂ 𝗏 …𝗏 𝑥_𝑛 không phụ thuộc vào cách đặt các dấu “( )”. Hơn nữa, chứng minh tương tự như trong Định lý 3.4.1 ta thấy 𝑥₁ 𝗏 𝑥₂ 𝗏 …𝗏 𝑥_𝑛  chính  là sup 𝐵. Tương tự 𝑥₁ 𝖠 𝑥₂ 𝖠 …𝖠 𝑥_𝑛  = inf 𝐵. Đặc biệt nếu 𝐴 hữu hạn ta có:

Mệnh đề 3.4.2 

Trong dàn hữu hạn 𝐴 = { 𝑎₁, 𝑎_2,…, 𝑎_𝑛} thì 𝑎₁ 𝗏 𝑎₂ 𝗏 …𝗏 𝑎_𝑛 và 𝑎₁ 𝖠 𝑎₂ 𝖠 …𝖠𝑎_𝑛 chính là phần tử lớn nhất và phần tử bé nhất của 𝐴.

Chú ý: Nếu dàn 𝐴 không hữu hạn thì phần tử lớn nhất và bé nhất không nhất thiết tồn tại như ví dụ của 𝑍 cho thấy.

Định nghĩa 3.4.3

Một dàn 𝐴 được nói là phân bố nếu với mọi 𝑥, 𝑦, 𝑧 trong 𝐴 ta có:

𝑥 𝖠 ( 𝑦 𝗏 𝑧) = ( 𝑥 𝖠 𝑦) 𝗏 ( 𝑥 𝖠 𝑧)

𝑣à     𝑥 𝗏 ( 𝑦 𝖠 𝑧) = ( 𝑥 𝗏 𝑦) 𝖠 ( 𝑥 𝗏 𝑧)

Ví dụ:

1. Mọi tập hợp sắp thứ tự toàn phần là một dàn phân bố (Bài tập)

2. Do tính phân bố của các phép tính tập hợp, dàn 𝑃( 𝐸) là một dàn phân bố.

3. Do quy luật phân bố, dàn 𝑀 các dạng mệnh đề là một dàn phân bố

4. Xét tập hợp sắp thứ tự 𝐴 = { 𝑎, 𝑏, 𝑐, 𝑑, e} với biểu đồ Hasse như sau:

Ta có thể kiểm tra dễ dàng 𝐴 là một dàn. Tuy nhiên 𝐴 không phân bố vì:

𝑑 𝖠 ( 𝑏 𝗏 𝑐) = 𝑑 𝖠 e = 𝑑

Trong khi ( 𝑑 𝖠 𝑏) 𝗏 ( 𝑑 𝖠 𝑐) = 𝑎 𝗏 𝑎 = 𝑎 ≠ 𝑑

Định nghĩa 3.4.4

Giả sử 𝐴 là một dàn với phần tử lớn nhất mà bé nhất mà ta ký hiêu là 1 và 0. Khi ấy một phần tử 𝑥̅ ∈ 𝐴 được nói là phần bù của phần tử 𝑥 ∈ 𝐴 nếu:

𝑥 𝗏 𝑥̅ = 1

𝑣à    𝑥 𝖠 𝑥̅ = 0

Ta nói 𝐴 là một dàn bù nếu mọi phần tử của 𝐴 đều có phần bù.

Chú ý: Nếu 𝑥̅ là phần bù của 𝑥 thì rõ ràng 𝑥 là phần bù của 𝑥̅

Ví dụ:

1. Các dàn 𝑃( 𝐸) và 𝑀 là dàn bù. Phần bù của 𝐴 ∈ 𝑃( 𝐸) chính là phần bù của tập hợp 𝐴 trong 𝐸, còn phần bù của dạng mệnh đề 𝐸 chính là phủ định của 𝐸.

2. Dàn 𝐴 = { 𝑎, 𝑏, 𝑐, 𝑑, e} với biểu đồ Hasse như dưới đây là một dàn bù

DÀN 2𝐸

Cho trước hai tập hợp 𝐸, 𝐵, nhắc lại rằng 𝐵𝐸 ký hiệu tập hợp các ánh xạ từ 𝐸 vào 𝐵.

Giả sử ≺𝐵 là một thứ tự trên 𝐵. Khi ấy với ƒ, 𝑔 ∈ 𝐵𝐸, ta định nghĩa:

ƒ ≺ 𝑔 ⟺ ∀𝑥 ∈ 𝐸, ƒ( 𝑥) ≺𝐵 𝑔( 𝑥)

Có thể kiểm tra rằng ≺ là một thự tự trên 𝐵𝐸, và hơn nữa ( 𝐵𝐸, ≺) là một dàn nếu ( 𝐵, ≺𝐵) là một dàn (Bài tập)

Gọi ƒ, 𝑔 là hai phần tử bất kỳ của 𝐵^𝐸, ƒ 𝗏 𝑔 và ƒ 𝖠 𝑔 là ánh xạ sao cho với mọi 𝑥 ∈ 𝐸:

( ƒ 𝗏 𝑔) ( 𝑥) = ƒ( 𝑥) 𝗏_𝐵 𝑔( 𝑥)

𝑣à  ( ƒ 𝖠 𝑔) ( 𝑥) =  ƒ( 𝑥) 𝖠_𝐵 𝑔( 𝑥)

Trong đó 𝗏_𝐵 và 𝖠_𝐵 chỉ sup và inf của hai phần tử trong 𝐵 đối với thứ tự ≺𝐵

Đặc biệt với 𝐵 = { 0,1} , ta được dàn {0,1}^𝐸 mà ta ký hiệu là 2^𝐸 . Với ƒ ∈ 2^𝐸 , đặt 𝐴 =  ƒ⁻¹( 1). Khi ấy ta có:

$f\left(x\right) = \left\{\begin{array}{l}1 nếu x\in A\\ 0 nếu x không thuộc A\end{array}\right.$

Ta nói ƒ là hàm đặc trưng của 𝐴

Hàm đặc trưng của 𝐴 được ký hiệu bởi 3Æ. Ta có:

Định lý 3.5.1

Tương ứng 𝜑: 𝐴 ⟼ 3_Æ là một song ánh giữa 𝑃( 𝐸) và 2^𝐸. Hơn nữa với 𝐴₁, 𝐴₂ là hai tập hợp con tùy ý của 𝐸 ta có: 𝐴₁ ⊂ 𝐴₂ ⟺ 3_Æ1  ≺ 3_Æ2  ( 3.5.1)                                                   

Chứng minh: Trên đây ta đã thấy 𝜑 là toàn ánh. Hơn nữa nếu 3_Æ1 = 3_Æ2 thì :

$A_1=\underset{A{E}_1}{3^{-1}\left(1\right)} = \underset{A{E}_2}{3^{-1}\left(2\right)} = A_2$

Như thế 𝜑 là một song ánh,

Mặt khác, với 𝐴₁, 𝐴₂ là hai tập hợp con tùy ý của 𝐸, ta có:

𝐴₁ ⊂ 𝐴₂ ⟺  (∀𝑥 ∈ 𝐸, 3_Æ1 ( 𝑥) = 1 ⟹ 3_Æ2( 𝑥) = 1);  3Æ1 ≺ 3Æ2

Ta có thể viết lại (3.5.1) như sau: 𝐴1 ⊂ 𝐴2 ⟺ 𝜑( 𝐴1) ≺ 𝜑( 𝐴2)

𝜑 là đẳng cấu giữa hai tập hợp con có thứ tự 𝑃( 𝐸) và 2𝐸 theo nghĩa sau:

Định nghĩa 3.5.1

Môt đẳng cấu giữa hai tập hợp có thứ tự ( 𝐴, ≺Æ) , ( 𝐵, ≺𝐵) là một song ánh 𝜑: 𝐴 ⟷ 𝐵 sao cho:

∀𝑥, 𝑦, ( 𝑥 ≺Æ 𝑦) ⟺ 𝜑( 𝑥) ≺𝐵 𝜑(y)           (3.5.2)                                                             

Định lý 3.5.2 : Giả sử 𝜑 là một đẳng cấu giữa hai tập hợp có thứ tự ( 𝐴, ≺Æ) và ( 𝐵, ≺𝐵)

i. Nếu ( 𝐴, ≺Æ) và ( 𝐵, ≺𝐵) là hai dàn, thì với 𝑥, 𝑦 ∈ 𝐴 tùy ý ta có:

𝜑( 𝑥 𝗏 𝑦) = 𝜑( 𝑥) 𝗏 𝜑(y)     ( 3.5.3)

và   𝜑( 𝑥 𝖠 𝑦) = 𝜑( 𝑥) 𝖠 𝜑(y)       (3.5.4)

ii. Nếu 𝐴 là dàn phân bố thì 𝐵 cũng là dàn phân bố

iii. Giả sử 𝐴 có 0 là phần tử bé nhất và 1 là phần tử lớn nhất. Khi ấy 𝜑( 0) và 𝜑( 1) là phần tử bé nhất và lớn nhất của 𝐵.

iv.  Nếu 𝐴 là dàn bù thì 𝐵 cũng là dàn bù. Hơn nữa nếu 𝑥̅ là phần bù của phần tử 𝑥 ∈ 𝐴, thì 𝜑( 𝑥̅) là phần bù của 𝜑( 𝑥) . Nói cách khác 𝜑( 𝑥̅) = ̅𝜑̅(̅𝑥̅)̅.

Chứng minh:

i. Với 𝑥, 𝑦 ∈ 𝐴 tùy ý, do (3.5.2) rõ ràng 𝜑( 𝑥 𝗏 𝑦) là chặn trên chung của 𝜑( 𝑥) và 𝜑( 𝑦) . Suy ra:

𝜑( 𝑥) 𝗏 𝜑( 𝑦) ≺ 𝜑( 𝑥 𝗏y)        (3.5.5)                                           

Mặt khác, cũng do (3.5.2) 𝜑−1(𝜑( 𝑥) 𝗏 𝜑( 𝑦)) và chặn trên chung của 𝑥 và 𝑦 nên:

𝑥 𝗏 𝑦 ≺ 𝜑−1(𝜑( 𝑥) 𝗏 𝜑( 𝑦) )

Do đó 

𝜑( 𝑥 𝗏 𝑦) ≺ 𝜑( 𝑥) 𝗏 𝜑(y)          (3.5.6)                             

Từ (3.5.5) và (3.5.6) ta suy ra (3.5.3) Chứng minh của (3.5.4) hoàn toàn tương tự.

ii) , iii), iv) được suy ra dễ dàng từ định nghĩa

Hệ quả: nếu 𝐴, 𝐵 là hai tập hợp con tùy ý của 𝐸 thì

3_Æ𝖴𝐵  =  3_Æ 𝗏 3_𝐵  𝑣à  3_Æ∩𝐵  =   3_Æ3^𝐵

trong đó 3_Æ3_𝐵 = 3_Æ 𝖠 3_𝐵 là tích của hai hàm theo nghĩa tự nhiên.

DÀN ट𝑛

Ước số chung lớn nhất và bội số chung lớn nhất

Giả sử 𝑎, 𝑏 là hai số nguyên dương, khi ấy số nguyên dương 𝑐 được nói là ước số chung của 𝑎 và 𝑏 nếu 𝑐 là ước số của 𝑎 và 𝑐 là ước số của 𝑏. Khi ấy 0 ≤ 𝑐 ≤ min( 𝑎, 𝑏) . Do đó tập hợp của các ước số chung của 𝑎 và 𝑏 là một tập hợp hữu hạn và tồn tại một phần tử lớn nhất 𝑑 gọi là ước số chung lớn nhất của 𝑎 và 𝑏. Ta viết: 𝑑 = 𝑈𝑆𝐶𝐿𝑁( 𝑎, 𝑏)

Để tìm ước số chung lớn nhất của 2 số nguyên dương 𝑎, 𝑏 ta sử dụng thuật toán sau:

Thuật chia Euclide: nếu 𝑏 là ước của 𝑎, đặt 𝑟0 = 𝑏. Nếu không ta thực hiên lần lượt các phép chia có dư số:

Do 𝑏 > 𝑟₁ > 𝑟₂ > ⋯ > 𝑟_k > ⋯ ≥ 0, thuật chia sẽ ngưng sau một số hữu hạn bước.

Gọi 𝑟_𝑛+1 là dư số đầu tiên bằng 0. Ta có:

𝑟_𝑛−2 = 𝑟_𝑛−1𝑞_𝑛 + 𝑟_𝑛, 0 ≤ 𝑟𝑛 < 𝑟𝑛−1

𝑟_𝑛−1 = 𝑟_𝑛 𝑞_𝑛+1 + 0

Định lý 3.6.1

𝑟_𝑛 là ước số chung lớn nhất của 𝑎 và 𝑏. Hơn nữa mọi ước số chung của 𝑎 và 𝑏 là ước số của 𝑟𝑛

Chứng minh: Nếu 𝑏 là ước của 𝑎 thì ước số chung lớn nhất của 𝑎 và 𝑏 chính là 𝑏 = 𝑟₀. Nếu không 𝑟₁ > 0. Giả sử 𝑐  là ước số chung của 𝑎 và 𝑏. Do 𝑟₁ =  𝑎 − 𝑏𝑞₁  nên 𝑐  cũng là ước số của 𝑟_i với 1 ≤ i ≤ 𝑛. Thật vậy, giả sử 1 ≤ 𝑘 < 𝑛 và 𝑐 là ước của 𝑟_i với 1 ≤ i ≤ 𝑘. Khi ấy do 𝑟_k+1 = 𝑟_k−1 − 𝑟_k𝑞_k+i  nên 𝑐  cũng là ước của 𝑟_k+1. Như thế theo nguyên lý qui nạp, 𝑐  là ước của 𝑟_𝑛. Đặc biệt nếu gọi 𝑑 là ước số chung lớn nhất của 𝑎 và 𝑏 thì 𝑑 cũng là ước của 𝑟_𝑛.

Suy ra 𝑑 ≤ 𝑟𝑛

Ngược lại, do 𝑟_𝑛−1 = 𝑟_𝑛𝑞_𝑛+1 nên 𝑟_𝑛 là ước của 𝑟_𝑛−1. Tương tự như trên, dùng nguyên lý qui nạp , ta thấy 𝑟𝑛 là ước của 𝑟i với 1 ≤ i ≤ 𝑛. Nhưng 𝑏 = 𝑟₁𝑞₂ + 𝑟₂ nên 𝑟_𝑛 cũng là ước của 𝑏. Cuối cùng do 𝑎 = 𝑏𝑞₁ + 𝑟₁, cũng là ước của 𝑎. Như thế 𝑟_𝑛 là ước số chung của 𝑎 và 𝑏.

Suy ra 𝑟_𝑛 ≤ 𝑑

Tóm lại 𝑑 = 𝑟𝑛

Định lý 3.6.2

Giả sử 𝑑 là ước số chung lớn nhất của 𝑎 và 𝑏. Khi ấy tồn tại 𝑚, 𝑛 ∈ 𝑍 sao cho: 𝑑 = 𝑚𝑎 + 𝑛𝑏

Chứng minh: với ký hiệu như trong Định lý 3.6.1, ta có 𝑑 = 𝑟𝑛. Như thế:

𝑑 = 𝑟_𝑛−2 − 𝑞_𝑛 𝑟_𝑛−1 = 𝑚₁𝑟_𝑛−2 + 𝑚₂ 𝑟_𝑛−1

Nhưng

 𝑟_𝑛−1 = 𝑟_𝑛−3 − 𝑞_𝑛−1𝑟_𝑛−2

Do đó

𝑑 = 𝑚₂𝑟_𝑛−3 + ( 𝑚₁ − 𝑚₂𝑞_𝑛−1) 𝑟_𝑛−2

= 𝑚₂ 𝑟_𝑛−3+𝑚₃ 𝑟_𝑛−2

Bằng Nguyên lý qui nạp tương tự như trên ta cũng chứng minh được tồn tại 𝑚₁, 𝑚₂,…, 𝑚_𝑛−1 ∈ 𝑍 sao cho:

𝑑 = 𝑚_𝑛−2𝑟₁ + 𝑚_𝑛−1𝑟2

𝑑  = 𝑚_𝑛−1𝑏 + ( 𝑚_𝑛−2 − 𝑚_𝑛−1𝑞₂) 𝑟₁

Sử dụng 𝑟₂ = 𝑏 − 𝑞₂𝑟₁ ta được:

= 𝑚_𝑛−1𝑏 + 𝑚𝑟₁

= 𝑚𝑎 + ( 𝑚_𝑛−1𝑚𝑞₁) 𝑏

= 𝑚𝑎 + 𝑛𝑏

Chú ý: Một số nguyên 𝑝 > 1 được nói là số nguyên tố nếu 𝑝 không có ước nào ngoài 1 và chinh nó. Nếu 𝑝 là số nguyện tố và 𝑝 không phải là ước của 𝑎 thì 𝑝 và 𝑎 nguyên tố cùng nhau.

Mệnh đề 3.6.3:

Giả sử 𝑎, 𝑏, 𝑐 ∈ 𝑍+ sao cho 𝑎 là ước của 𝑏𝑐 và ( 𝑎, 𝑏) = 1. Khi ấy 𝑎 là ước của 𝑐.

Chứng minh: Do Định lý 3.6.2, tồn tại 𝑚, 𝑛 ∈ 𝑍 sao cho:

1 = 𝑚𝑎 + 𝑛𝑏

𝐷o đó   

𝑐 = 𝑚𝑎𝑐 + 𝑛𝑏𝑐

Vì 𝑎 là ước của 𝑏𝑐 nên 𝑎 cũng là ước của 𝑐 (ĐPCM)

Mệnh đề 3.6.4

Giả sử 𝑎, 𝑏, 𝑐 ∈ 𝑍+ sao cho ( 𝑎, 𝑏) = 1 và ( 𝑎, 𝑐) = 1. Khi ấy ( 𝑎, 𝑏𝑐) = 1

Chứng minh: Giả sử ước số chung lớ nhất của 𝑎 và 𝑏𝑐 là 𝑑 > 1. Khi ấy ( 𝑑, 𝑏) = 1 vì nếu không, gọi e là ước số chung lớn nhất của 𝑑 và 𝑏 ta có e > 1. Rõ ràng e cũng là ước chung của 𝑎 và 𝑏. Điều này mâu thuẫn với giả thiết ( 𝑎, 𝑏) = 1. Vậy ( 𝑑, 𝑏) = 1. Do đó theo Mệnh đề 3.6.3   𝑑 là ước số của 𝑐. Điều này mâu thuẫn với giả thiết ( 𝑎, 𝑐) = 1. Do đó 𝑑 = 1, nghĩa là( 𝑎, 𝑏𝑐) = 1  (ĐPCM)

Một số nguyên 𝑐 được nói là bội số chung của hai số nguyên 𝑎, 𝑏 nếu 𝑐 đồng thời là bội số của 𝑎 và 𝑏.

Bổ đề 3.6.5

Cho 𝐴, 𝐵, 𝐶 ∈ 𝑍+. Giả sử 𝑐 là bội số chung của 𝑎, 𝑏 và ( 𝑎, 𝑏) = 1. Khi ấy 𝑐 là bội số chung của 𝑎𝑏.

Chứng minh: Do 𝑐 là bội số của 𝑏, ta có thể viết 𝑐 = 𝑘𝑏 với 𝑘 là số nguyên. Do Mệnh đề 3.6.3, 𝑎 là ước số của 𝑘: 𝑘 = 𝑘′𝑎, 𝑘′ ∈ 𝑍+. Suy ra 𝑐 = 𝑘′𝑎𝑏 (ĐPCM)

Định lý 3.6 .6:

Giả sử 𝑎, 𝑏 ∈ 𝑍+. Gọi 𝑑 là ước số chung lớn nhất của 𝑎, 𝑏. Khi ấy $\frac{ab}{d}$ là bội số chung của 𝑎, 𝑏. Hơn nữa mọi bội số chung của 𝑎, 𝑏 đều chia hết cho $\frac{ab}{d}$. Suy ra $\frac{ab}{d}$ là bội số chung lớn nhất của 𝑎 và 𝑏.

Chứng minh:  Ta có thể viết $\frac{ab}{d}=a\frac{b}{d}=\frac{a}{d}b$ với 𝑎, 𝑏

Mặt khác để ý rằng $\frac{a}{b}$ và $\frac{b}{a}$ nguyên tố cùng nhau. Thật vậy gọi e là ước số chung lớn nhất của chúng thì 𝑑e cũng là ước số chung của 𝑎 và 𝑏. Suy ra e = 1.

Gọi 𝑚 là bội số chung của 𝑎 và 𝑏. Áp dụng Bổ đề 3.6.5 cho $\frac{m}{d}; \frac{b}{d} ;\frac{a}{d}$ ta thấy $\frac{m}{d}$ là bội số chung của $\frac{ab}{d^2}$ nên 𝑚 là bội số chung của $\frac{ab}{d}$ (ĐPCM)

Chú ý: ta ký hiệu bội số chung nhỉ nhất của 𝑎, 𝑏 bởi 𝐵𝑆𝐶𝑁𝑁 ( 𝑎, 𝑏)

Giả sử 𝑎 ∈ 𝑁, 𝑎 > 1. Khi ấy nếu gọi 𝑞 là ước bé nhất của 𝑎 sao cho 𝑞 > 1 thì rõ ràng 𝑞 là một số nguyên tố. Lại tiếp tục xét 𝑎 ta chứng minh được bằng qui nạp rằng 𝑎 là tích của một số hữu hạn số nguyên tố. Gộp các thừa số giống nhau lại ta có thể phân tích 𝑎 thành thừa số nguyên tố:

𝑎 = 𝑝^𝑟1 𝑝^𝑟2 …𝑝𝑟^𝑛    ( 3.6.1)                         

Mệnh đề 3.6.7: Biểu diễn (3.6.1) là duy nhất

Chứng minh: xét một phân tích ra thừa số nguyên tố khác của 𝑎:

$a =\underset{1}{q^{s1}} \underset{2}{q^{s2}...} \underset{m}{q^{sm}}$  (3.6.2)

Nếu 𝑝₁ ∉ { 𝑞₁, 𝑞₂,…, 𝑞_𝑚} thì áp dụng thì áp dụng Mệnh đề 3.6.4 nhiều lần ta đi đến kết luận 𝑝₁ và 𝑎 số nguyên tố cùng nhau. Điều mâu thuẫn này chứng tỏ 𝑝₁ ∈ {𝑞₁, 𝑞₂,…, 𝑞_𝑚}. Lập luận tương tự cho 𝑝₂,…, 𝑝_𝑛, 𝑞₁,…, 𝑞_𝑚 ta được:

{ 𝑝₁, 𝑝₂,…, 𝑝_𝑛} = { 𝑞₁, 𝑞₂,…, 𝑞_𝑚}

Đặc biệt 𝑛 = 𝑚 . Sắp xếp thứ tự lại 𝑞₁, 𝑞₂,…, 𝑞_𝑚 ta có thể giả sử 𝑝₁ = 𝑞₁, 𝑝₂ = 𝑞₂,…, 𝑝_𝑛 = 𝑞_𝑛. Ta sẽ chứng minh 𝑟₁ = 𝑠₁, 𝑟₂ = 𝑠₂,…, 𝑟_𝑛 = 𝑠_𝑛 bằng qui nạp trên 𝑛

•  Nếu 𝑛 = 1 thì 𝑎 = 𝑝^𝑟1 = 𝑝^𝑠1. Suy ra 𝑟₁ = 𝑠₁

•  Giả sử 𝑛 > 1. Nếu 𝑟1 < 𝑠1 thì r1  = 𝑝 2 …𝑝 𝑛 rõ ràng nguyên tố cùng nhau 

Do 𝑠₁ − 𝑟₁ > 0, 𝑝₁ là ước của. Điều mâu thuẫn này chứng tỏ 𝑟₁ ≥ 𝑠₁. Do 𝑟₁ và 𝑠₁ đóng vai trò đối xứng ta cũng có 𝑟1 ≤ 𝑠1, nghĩa là 𝑟1 = 𝑠1. Khi ấy ta được 2 biểu điễn của 𝑎 thành thừa số nguyên tố:

Áp dụng giả thiết qui nạp ta được 𝑟₂ = 𝑠₂, 𝑟₃ = _𝑠3,…, 𝑟_𝑛 = 𝑠_𝑛

Trước tiên nhận xét rằng nếu 𝑎 và 𝑏 có phân tích

𝑎 = 𝑝^𝑟1𝑝^𝑟2 …𝑝^𝑟𝑛    (3.6.3)  

𝑏 = 𝑞^𝑠1𝑞^𝑠2 …𝑞^𝑠𝑛      (3.6.4) 

Thì 𝑎 là ước của 𝑏 khi và chỉ khi 2 điều kiện dưới đây được thỏa:

•  { 𝑝₁, 𝑝₂,…, 𝑝_𝑛} ⊂ { 𝑞₁, 𝑞₂,…, 𝑞_𝑚}. Đặc biệt 𝑛 ≤ 𝑚
•  Ta sắp xếp thứ tự 𝑞₁, 𝑞₂,…, 𝑞_𝑛 lại sao cho 𝑝₁ = 𝑞₁, 𝑝₂ = 𝑞_2, 𝑝_𝑛 = 𝑞_𝑛. Khi ấy các số mũ thỏa: 𝑟₁ ≤ 𝑠₁, 𝑟₂ ≤ 𝑠₂,…, 𝑟_𝑛 ≤ 𝑠_𝑛.

Chứng minh của khẳng định trên dựa trên cùng ý tưởng với chứng minh Mệnh đề 3.6.7 nêu được dành cho đọc giả.

Bây giờ giả sử 𝑎 và 𝑏 có phân tích như trong (3.6.3) và (3.6.4) với các số mũ nguyên dương. Bằng cách bổ sung thêm vào 𝑎 các thừa số là lũy thừa 0 của những số nguyên tố trong (3.6.3) và ngược lại, ta có thể giả sử 𝑎, 𝑏 có dạng:

𝑎 = 𝑝^𝑟1𝑝^𝑟2 …𝑝^𝑟𝑛

𝑏 = 𝑝^𝑠1𝑝^𝑠2 …𝑝^𝑠𝑛

Với các số mũ lấy giá trị nguyên dương hay 0. Khi ấy do nhân xét trên ta có:

Mệnh đề 3.6.8

𝑈𝑆𝐶𝐿𝑁( 𝑎, 𝑏) =  𝑝^𝑢1𝑝^𝑢2 …𝑝^𝑢𝑛

và 𝐵𝑆𝐶𝑁𝑁( 𝑎, 𝑏) = 𝑝^𝑣1𝑝^𝑣2 …𝑝^𝑣𝑛

với 𝑢_i =  min( 𝑟_i, 𝑠_i) và 𝑣i = max( 𝑟i, 𝑠i)

Dàn ट𝑛 

Nhắc lại rằng tập hợp gồm các ước số dương của 𝑛 được sắp thứ tự bởi quan hệ:

𝑎 ≺ 𝑏 ⟺ 𝑎|𝑏 (𝑎 là ước số của 𝑏)

Giả sử 𝑎, 𝑏 ∈. Khi ấy 𝑑 = 𝑈𝑆𝐶𝐿𝑁( 𝑎, 𝑏) ∈ ࣯𝑛

Rõ ràng 𝑑 ≺ 𝑎 và 𝑑 ≺ 𝑏. Hơn nữa nếu 𝑐 ∈ ࣯𝑛 sao cho 𝑐 ≺ 𝑎 và 𝑐 ≺ 𝑏 thì 𝑐 là ước số chung của 𝑎, 𝑏 nên theo Định lý 3.6.1 𝑐 cũng là ước số của 𝑑, nghĩa là 𝑐 ≺ 𝑑.

Nói tóm lại 𝑑 chính là inf( 𝑎, 𝑏) . Tương tự 𝐵𝑆𝐶𝑁𝑁( 𝑎, 𝑏) là sup( 𝑎, 𝑏) . Với ký hiệu 𝖠,𝗏 cho inf và sup ta có:

𝑎 𝖠 𝑏 = 𝑈𝑆𝐶𝐿𝑁( 𝑎, 𝑏)

𝑎 𝗏 𝑏 = 𝐵𝑆𝐶𝑁𝑁( 𝑎, 𝑏)

Như thế ࣯𝑛 là một dàn phần tử bé nhất là 1, phần tử lớn nhất là 𝑛.

Hơn nữa nếu gọi 𝑝1, 𝑝2,…, 𝑝𝑚 là các ước số nguyên tố của 𝑛 thì ta có thể biểu diễn 1 phần tử bất kỳ của ࣯𝑛 dưới dạng (3.6.1) với số mũ thuộc 𝑁. Xét ba phần tử tùy ý 𝑎, 𝑏, 𝑐 ∈ ࣯𝑛 với biểu diễn như trên:

𝑎 = 𝑝^𝑟1𝑝^𝑟2 …𝑝^𝑟𝑚

𝑏 = 𝑝^𝑠1𝑝^𝑠2 …𝑝^𝑠𝑚

𝑐 = 𝑝^𝑡1𝑝^𝑡2 …𝑝^𝑡𝑚

Khi ấy do Mệnh đề 3.6.8 số mũ của 𝑝i trong 𝑎 𝖠 ( 𝑏 𝗏 𝑐) là:

min( 𝑟_i, max(, 𝑡_i) ) = max( min( 𝑟_i , 𝑠_i) , min( 𝑟_i , 𝑡_i))

Như thế 𝑎 𝖠 ( 𝑏 𝗏 𝑐) = ( 𝑎 𝖠 𝑏) 𝗏 ( 𝑎 𝖠 𝑐) Tương tự 𝑎 𝗏 ( 𝑏 𝖠 𝑐) = ( 𝑎 𝗏 𝑏) 𝖠 ( 𝑎 𝗏 𝑐) Tóm lại ta đã chứng minh.

Định lý 3.6.9  ࣯

𝑛 là một dàn phân bố.

Một số nguyên dương 𝑛 được nói là không có thừa số chính phương nếu 𝑛 không chia hết cho bình phương của bất kỳ số nguyên >1 nào.

Định lý 3.6.10: ࣯

𝑛 là dàn bù khi và chỉ khi 𝑛 không có thừa số phương.

Chứng minh: Giả sử 𝑛 không có thừa số chính phương và 𝑎 là một phần tử tùy ý của ࣯𝑛. Khi ấy 𝑎 và 𝑎 nguyên tố cùng nhau vì nếu không, bất kỳ ước số chung 𝑛 > 1 của chúng 𝑛 cũng đều có bình phương là ước của 𝑛.

Như thế

𝑎 𝖠 $\underset{a}{n}$ = 1

Ngoài ra 

𝑎 𝗏 $\underset{a}{n}$ = 𝐵𝑆𝐶𝑁𝑁 (𝑎, $\underset{a}{n}$) = 𝑎 $\underset{a}{n}$ = 𝑛

Vậy 𝑛 chính là phần bù của 𝑎 và do đó $\underset{\infty }{o}$là một dàn bù.

𝑎 𝖠 𝑎̅  =  1

𝑎 𝗏 𝑎̅ =  𝑛

Mà

𝑎 𝗏 𝑎̅ =  $\frac{a\overline{a}}{aA\overline{a}} = \overline{a}a$