Giáo trình cơ sở lý thuyết tập hợp và logic Toán

93 trang huongle 7540

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình cơ sở lý thuyết tập hợp và logic Toán", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_co_so_ly_thuyet_tap_hop_va_logic_toan.pdf

Nội dung text: Giáo trình cơ sở lý thuyết tập hợp và logic Toán

NGUYỄN TIẾN TRUNG GIÁO TRÌNH Cơ Sở Lý Thuyết Tập Hợp Và Logic Toán Ebook.moet.gov.vn, 2008
Chịu trách nhiệm xuất bản: Chủ tịch HĐQT kiêm Tổng Giám đốc NGÔ TRẦN ÁI Giám đốc ĐINH NGỌC BẢO Phó Tổng Giám đốc kiêm Tổng biên tập NGUYỄN QUÝ THAO Tổng biên tập LÊ A Biên tập nội dung: NGUYỄN TIẾN TRUNG Thiết kế sách và Biên tập mĩ thuật: VIỆT QUANG Trình bày bìa: PHẠM VIỆT QUANG LỜI NÓI ĐẦU Để góp phần đổi mới công tác đào tạo và bồi dưỡng giáo viên tiểu học, Dự án phát triển giáo viên tiểu học đã tổ chức biên soạn các môđun đào tạo và bồi dửỡng giáo viên theo chửơng trình Cao đẳng Sử phạm và chửơng trình liên thông từ Trung học Sử phạm lên Cao đẳng Sử phạm. Việc biên soạn các môđun nhằm nâng cao năng lực chuyên môn, nghiệp vụ, cập nhật những đổi mới về nội dung, phửơng pháp dạy học và kiểm tra, đánh giá kết quả giáo dục tiểu học theo chửơng trình, SGK tiểu học mới Điểm mới của tài liệu viết theo môđun là việc thiết kế các hoạt động, nhằm tích cực hoá các hoạt động của ngửời học, kích thích óc sáng tạo và khả năng giải quyết vấn đề, tự giám sát và đánh giá kết quả học tập của ngửời học; chú trọng sử dụng nhiều phửơng tiện truyền đạt khác nhau (tài liệu in, băng hình, ) giúp cho ngửời học dễ học, dễ hiểu và gây đửợc hứng thú học tập. Môđun Cơ sở lí thuyết tập hợp và lôgic toán do nhóm tác giả trửờng Đại học Sử phạm Hà Nội biên soạn. Môđun Cơ sở lí thuyết tập hợp và lôgic toán có thời lửợng bằng 2 đơn vị học trình, bao gồm 2 chủ đề: Chủ đề 1: Cơ sở của lí thuyết tập hợp Chủ đề 2: Cơ sở của lôgic toán Lần đầu tiên, tài liệu đửợc biên soạn theo chửơng trình và phửơng pháp mới, chắc chắn không tránh khỏi những thiếu sót nhất định. Ban điều phối Dự án rất mong nhận đửợc những ý kiến đóng góp chân thành của bạn đọc,
đặc biệt là đội ngũ giảng viên, sinh viên các trửờng Sử phạm, giáo viên tiểu học trong cả nửớc. Xin trân trọng cảm ơn! DỰ ÁN PHÁT TRIỂN GIÁO VIÊN TIỂU HỌC
CHỦ ĐỀ 1 Cơ sở lí thuyết tập hợp I.Mục tiêu Kiến thức : Người học − Hiểu các khái niệm về tập hợp, quan hệ, ánh xạ và biết xây dựng các ví dụ minh hoạ cho mỗi khái niệm đó. − Nắm được định nghĩa của các phép toán trên tập hợp và ánh xạ. Phát biểu và chứng minh các tính chất của chúng Kỹ năng : Hình thành và rèn cho người học các kĩ năng − Thiết lập các phép toán trên tập hợp và ánh xạ − Vận dụng các kiến thức về tập hợp và ánh xạ trong toán học − Các quan hệ tương đương và thứ tự Thái độ: − Chủ động tìm tòi, phát hiện và khám phá các ứng dụng của lí tập hợp toán dạy và học toán II. Giới thiệu chủ đề : STT Tên tiểu chủ đề Trang 1 Tập hợp 2 Các phép toán trên tập hợp 3 Quan hệ 4 Quan hệ tương đương 5 Quan hệ thứ tự 6 Ánh xạ 7 Đơn ánh, toàn ánh, song ánh và ánh xạ ngược 8 ảnh và tạo ảnh qua một ánh xạ III. Điều kiện cần thiết để thực hiện môđun Kiến thức:
Nắm được kiến thức toán học trong chương trình toán PTTH Đồ dùng dạy học: Một số thiết bị sử dụng trong khi tổ chức các hoạt động dạy học: máy chiếu projector, máy chiếu đa năng, bảng phoóc mi ca Tài liệu tham khảo: Các tài liệu trong thư mục của giáo trình IV. Nội dung (Xem các tiểu chủ đề 1.1 – 1.8) Formatted: Heading02 Tài liệu tham khảo Formatted: Heading01 [1] Phan Hữu Chân – Nguyễn Tiến Tài: Số học và lôgíc toán – NXB Giáo dục – 1996. [2]Trần Diên Hiển : Các bài toán về suy luận lôgíc – NXB Giáo dục – 2001. [3] Trần Diên Hiển : Lôgíc giải trí – NXB Khoa học và kĩ thuật – 1993. [4] Đỗ Đình Hoan và tập thể tác giả : Toán 1 – NXB giáo dục – 2004. [5] Đỗ Đình Hoan và tập thể tác giả : Toán 2 – NXB Giáo dục – 2004. [6] Đỗ Đình Hoan và tập thể tác giả : Toán 3 – NXB Giáo dục – 2004 [7] Đỗ Đình Hoan và tập thể tác giả : Toán 4 – NXB Giáo dục – 2005. [8] Đỗ Đình Hoan và tập thể tác giả : Toán 5 – NXB Giáo dục – 2004. [9] Xavier Roegiers : Guide Mathématique de base Pari – 1993.
TIỂU CHỦ ĐỀ 1.1. TẬP HỢP Thông tin cơ bản 1. Khái niệm tập hợp − Tập con − các tập hợp bằng nhau 1.1. Khái niệm tập hợp Tập hợp là một trong các khái niệm cơ bản của Toán học. Khái niệm tập hợp không được định nghĩa mà chỉ được mô tả qua các ví dụ: Tập hợp các học sinh của một lớp học, tập hợp các cầu thủ của một đội bóng, tập hợp các cuốn sách trên một giá sách, tập hợp các số tự nhiên, Mụn toán học nghiên cứu các tính chất chung của tập hợp, không phụ thuộc vào tính chất của các đối tượng cấu thành nên tập hợp được xem là cơ sở của Toán học hiện đại, và được gọi là lí thuyết tập hợp. Khác với nhiều ngành Toán học khác mà sự phát triển là kết quả có được từ những cố gắng không mệt mỏi của nhiều tài năng toán học, cuộc đấu tranh với “vô cực” và tiếp theo đó, sự sáng tạo nên lí thuyết tập hợp là công trình của chỉ một người: Gioócgiơ − Căngtơ (Georg Cantor 1845 − 1918), nhà toán học Đức gốc Do Thái. Các đối tượng cấu thành một tập hợp được gọi là các phần tử của tập hợp đó. Người ta thường kí hiệu các tập hợp bởi các chữ A, B, C, X, Y, Z, và các phần tử của tập hợp bởi các chữ a, b, c, x, y, z, Nếu a là một phần tử của tập hợp A thì ta viết a A (đọc là a thuộc tập hợp A). Nếu a không phải là một phần tử của tập hợp A thì ta viết a A (đọc là a không thuộc tập hợp A). Có hai cách xác định một tập hợp: z Cách thứ nhất là liệt kê tất cả các phần tử của tập hợp. Tập hợp A gồm bốn số tự nhiên 1, 3, 5, 7 được viết là: A = {1, 3, 5, 7}. Tập hợp B gồm ba phần tử là các chữ a, b, c được viết là: B = {a, b, c}. z Cách thứ hai là nêu lên một tính chất chung của các phần tử của tập hợp, nhờ đó có thể nhận biết được các phần tử của tập hợp và các đối tượng không phải là những phần tử của nó. Chẳng hạn, Ví dụ 1.1 : Cho tập hợp C các ước số của 8. Khi đó, các số 1, 2, 4, 8 là những phần tử của C, còn các số 3, 5, 6, 13 không phải là những phần tử của C. Người ta thường viết: C = {x : x là ước số của 8},
đọc là C là tập hợp các phần tử x sao cho x là ước số của 8 : x biểu thị mỗi phần tử của tập hợp C. Ví dụ 1.2 : Nếu D là tập hợp các nước thuộc châu á thì Việt Nam, Trung Quốc, Lào là những phần tử của tập hợp D, còn Pháp, Angiêri, Canađa không phải là những phần tử của D. Ta viết: D = {x : x là nước thuộc châu á} Người ta thường biểu thị tập hợp A bởi một đường cong kín gọi là lược đồ ven (Venn). Hình 1 Nếu chẳng hạn tập hợp Acó 4 phần tử a, b, c, d thì trên lược đồ đó mỗi phần tử đã được biểu diễn bởi một điểm nằm trong đường cong kín. Các điểm e và f biểu diễn những đối tượng không phải là phần tử của tập hợp A. Các tập hợp trong các ví dụ đã nêu chỉ có một số hữu hạn phần tử. Ta gọi chúng là những tập hợp hữu hạn. Tập hợp có vô số phần tử được gọi là tập hợp vô hạn. Chẳng hạn, tập hợp các hình chữ nhật có các kích thước tuỳ ý là một tập hợp vô hạn, vì ta không thể liệt kê tất cả các phần tử của nó. Tương tự, tập hợp A các số tự nhiên bội của 3 cũng là một tập hợp vô hạn. Tập hợp A được biểu diễn bởi lược đồ Ven trong Hình 2. Vì không thể biểu diễn tất cả các phần tử của A, ta chỉ đưa vào hình một số điểm có tên và một số điểm khác không có tên. Ngoài ra còn ghi chú thêm rằng sự biểu diễn tập hợp là không đầy đủ. Người ta cũng viết: A = {0, 3, 6, 9, 12, 15, }
Hình 2 Hiển nhiên mỗi phần tử tiếp sau được xác định một cách dễ dàng. Tập hợp không có phần tử nào được gọi là tập hợp rỗng, kí hiệu là φ. Chẳng hạn, tập hợp các nghiệm thực của phương trình x2 + 2 = 0 là tập hợp rỗng. Ta viết: {x ∈ R : x2 + 2 = 0} = φ. (R là tập hợp các số thực). Tập hợp các số (tự nhiên) chẵn là ước số của 15 là tập hợp rỗng: {x ∈ N: x là ước số chẵn của 15} = φ. Tập hợp chỉ có một phần tử gọi là tập một phần tử. Chẳng hạn, tập hợp các thủ đô của một nước là tập một phần tử. Tập hợp chỉ có một phần tử a được kí hiệu là {a}. Như vậy tập hợp E các nghiệm thực của phương trình 3x − 21 = 0 là tập một phần tử: E = {7}. Tập hợp T các tỉ số của độ dài mỗi đường tròn và đường kính của nó là tập một phần tử: T = {π}. 1.2. Tập con của một tập hợp Các tập hợp bằng nhau Formatted: Heading04 Formatted: Font: Times New a) Tập hợp A được gọi là một tập con của tập hợp X nếu mọi phần tử của A Roman đều là những phần tử của X.
Hình 3 Ví dụ 1.3 : Tập hợp A = {a, b, c, d} là tập hợp con của tập hợp X = {a, b, c, d, e, f}. Khi đó ta viết: (1) A ⊂ X (đọc là A chứa trong X), hoặc (2) X ⊃ A (đọc là X chứa A). Ký hiệu ⊂ được gọi là dấu bao hàm. Hệ thức (1) hoặc (2) gọi là một bao hàm thức. Ví dụ 1.4 : Tập hợp C các hình chữ nhật là một tập con của tập hợp B các hình bình hành vì mỗi hình chữ nhật là một hình bình hành: C ⊂ B (C chứa trong B). Hình 4 Ví dụ 1.5 ; Tập hợp N các số tự nhiên là một tập con của tập hợp Z các số nguyên: N ⊂ Z. Tập hợp Q các số hữu tỉ là một tập con của tập hợp R các số thực (vì mỗi số hữu tỉ là một số thực): Q ⊂ R. Hiển nhiên tập hợp X là một tập hợp con của X. Nếu A là một tập con của X và A ≠ X thì A gọi là một tập con thực sự của X. Trong ví dụ 3, A là một tập con thực sự của X. Trong Ví dụ 4, C là một tập thực sự của B. Tập hợp A không phải là một tập hợp con của tập hợp X nếu có ít nhất một phần tử của A không thuộc X.
Khi đó, ta viết: A ⊄ X (hoặc X ⊃ A) và biểu thị quan hệ này bằng lược đồ trong Hình 5. Hình 5 Ví dụ 1.6 : Nếu A = {a, b, c, d, e} và X = {a, b, c, f, g} thì A ⊄ X. Hình 6 Ví dụ 1.7 : Tập hợp C các hình chữ nhật không phải là một tập con của tập hợp T các hình thoi: C ⊄ T. Thật vậy, hình chữ nhật có chiều dài khác chiều rộng không phải là một hình thoi. b) Hai tập hợp A và B được gọi là bằng nhau nếu mỗi phần tử của A là một phần tử của B và mỗi phần tử của B là một phần tử của A. Khi đó ta viết A = B. Ví dụ 1.8 : Tập hợp các nghiệm thực của phương trình x2 - 1 = 0 bằng tập hợp gồm hai số -1 và 1: {x ∈ R : x2 − 1 = 0} = {−1, 1}.
Ví dụ 1.9 : Nếu A là tập hợp các số nguyên chia hết cho 2 và 3 và B là tập hợp các số nguyên chia hết cho 6 thì A = B. Thật vậy, một số nguyên chia hết đồng thời cho 2 và 3 khi và chỉ khi nó chia hết cho 6. Như vậy một số nguyên là một phần tử của A khi và chỉ khi nó là một phần tử của B. Do đó A và B có cùng các phần tử. Từ định nghĩa tập con và các tập hợp bằng nhau dễ dàng suy ra: c) Với các tập hợp bất kì A, B, C, ta có: (i) φ ⊂ A, (ii) A ⊂ A, (iii) Nếu A ⊂ B và B ⊂ C thì A ⊂ C, (iv) Nếu A ⊂ B và B ⊂ A thì A = B, (v) Nếu A ≠ B thì A ⊄ B hoặc B A. (ii) gọi là tính phản xạ, (iii) gọi là tính bắc cầu, (iv) gọi là tính phản ð?i xứng). Chứng minh. Ta sẽ chứng minh (iv) và (v). (iv) Giả sử A ⊂ B và B ⊂ A. Khi đó mỗi phần tử của A là một phần tử của B và mỗi phần tử của B là một phần tử của A. Theo định nghĩa của hai tập hợp bằng nhau, từ đó suy ra A = B. (v) Ta chứng minh (v) suy ra từ (iv) bằng phản chứng. Thật vậy, nếu A ⊂ B và B ⊂ A thì A = B. Điều này trái với giả thiết. 1.3. Tập hợp những tập hợp Formatted: Heading04 Ta xem một đội bóng của một câu lạc bộ bóng đá Anh, kí hiệu bởi A, là một tập hợp cầu thủ. Các phần tử của tập hợp này là những cầu thủ: A = {a1, a2, , am}. Ta cũng có thể xét tập hợp E các đội bóng của các câu lạc bộ bóng đá Anh. Các phần tử của tập hợp này là những đội bóng: Acxơnan (Arsenal), Manchétxtơ − Iunaitiđơ (Manchester−United), Trenxi (Chelsea), , Niu − Cátxơn (New − Castle), Livơpunlơ (Liverpool). E = {A, M, T, , N, L}
Hình 7 Tập hợp E vừa nêu là một tập hợp những tập hợp vì các phần của của E là những tập hợp. Ta có: a1 ∈ A : a1 là một cầu thủ của đội bóng A, A ∈ E : đội bóng A thuộc tập hợp các đội bóng của các câu lạc bộ bóng đá Anh. Không thể viết a1 ∈ E vì mỗi phần tử của E là một đội bóng chứ không phải là một cầu thủ. Ta xét một ví dụ khác: Trường trung học phổ thông Nguyễn Trãi có 5 lớp 10: 10A, 10B, 10C, 10D và 10E. Ta xem lớp 10A, kí hiệu bởi A, là một tập hợp học sinh. Các phần tử của tập hợp này là những học sinh. Ta viết: A = {a1, a2, , am}. Ta cũng có thể nói đến tập hợp E các lớp khối 10 của trường. Các phần tử của tập hợp này là các lớp khối 10 của trường. E = {A, B, C, D, E}. Tập hợp các lớp khối 10 của trường là một tập hợp những tập hợp. 1.4. Số tập con của một tập hợp hữu hạn Formatted: Heading04 Một câu hỏi tự nhiên được đặt ra là: Nếu A là một tập hợp có n phần tử từ A có cả thảy bao nhiêu tập con? Ta chỉ xét trường hợp: n = 0, 1, 2, 3, 4. a) Với n = 0, ta có A = φ. Hiển nhiên φ chỉ có một tập con; đó là chính nó, tập hợp φ. Vậy tập hợp không có phần tử nào có một tập con. b) n = 1.
Giả sử A là tập hợp một phần tử: A = {a} (a là phần tử duy nhất của A). Khi đó, các tập hợp φ và {a} là tất cả các tập con của A. Vậy A có cả thảy 2 tập con. Nếu kí hiệu P(A) là tập hợp tất cả các tập con của tập hợp A thì ta có: P(φ) = {φ} và P ({a}) = {φ, {a}}. c) n = 2. Giả sử tập hợp A có 2 phần tử a và b: A = {a, b}. Khi đó A có các tập con sau: φ, {a{, {b} và {a, b}. Đó là tất cả các tập con của A: P ({a, b}) = {, {a}, {b}, {a, b}}. Vậy A có cả thảy 4 tập con. d) n = 3. Để dễ hình dung, ta xét bài toán sau: Giả sử có ba người a, b và c của một tập hợp A được mời dự khai mạc một cuộc triển lãm (ba người được mời độc lập với nhau). Hỏi có thể có bao nhiêu sự kết hợp khác nhau về sự có mặt của mỗi người trong ngày khai mạc triển lãm? Ta hãy xét mọi khả năng (a đến hoặc không, b đến hoặc không, c đến hoặc không) và biểu diễn chúng trên một cây chẽ đôi, tức là một cây mà mọi sự phân cành đều có được từ cặp “đến, không”. Hình 8
Trên Hình 8, ta thấy có cả thảy 8 khả năng, mỗi khả năng tương ứng với một tập con của A = {a, b, c}, kể cả tập con là φ. Tập hợp tất cả các tập con của A là: P ({a, b, c}) = {{a, b, c}; {a, b}; {a, c}; {b, c}; {a}; {b}; {c}; φ}. Vậy tập hợp A = {a, b, c} có cả thảy 8 tập con. e) n = 4. Giả sử tập hợp B có bốn phần tử a, b, c, d : B = {a, b, c, d{. Có thể nghĩ đến một người thứ tư, d, cũng được mời đến dự khai mạc triển lãm. Khi đó, từ mỗi trường hợp trong 8 trường hợp vừa nêu trong d), sẽ có hai khả năng, tuỳ thuộc vào việc d đến hay không đến dự khai mạc. Do đó tập hợp tất cả các tập con của tập hợp B là: P (B) = P ({a, b, c, d}) = {{a, b, c}; {a, b}; {a, c}; {b; c}; {a}; {b}; {c}; φ; {a, b, c, d}; {a, b, d}; {a, c, d}; {b, c, d}; {a, d}; {b, d}; {c, d}; {d}}. Vậy tập hợp B = {a, b, c, d} có cả thảy 16 tập con. Đó là 8 tập con của tập hợp A = {a, b, c} và 8 tập hợp mới, nhận được bằng cách thêm d vào mỗi tập hợp con của A. Như vậy, Tập hợp φ có cả thảy 1 = 20 tập con. Tập hợp có 1 phần tử có cả thảy 2 = 21 tập con. Tập hợp có 2 phần tử có cả thảy 4 = 22 tập con. Tập hợp có 3 phần tử có cả thảy 8 = 23 tập con. Tập hợp có 4 phần tử có cả thảy 16 = 24 tập hợp con, Bằng phương pháp quy nạp, có thể chứng minh được rằng tập hợp có n phần tử có cả thảy 2n tập hợp con. Hoạt động 1.1. tìm hiểu các khái niệm cơ bản của tập hợp Sinh viiên tự đọc thông tin nguồn để thực hiện các nhiệm vụ dưới đây: Nhiệm vụ Nhiệm vụ 1: Tìm hiểu về:
− Khái niệm tập hợp, các phần tử của một tập hợp. − Hai cách xác định một tập hợp: • Liệt kê các phần tử của tập hợp. • Nêu lên được một tính chất đặc trưng của các phần tử của tập hợp. − Tập hợp φ (cho các ví dụ về tập hợp φ). − Cách biểu diễn một tập hợp (hữu hạn và vô hạn) bằng lược đồ Ven. Nhiệm vụ 2 Thảo luận để có thể giải thích được các nội dung sau: − Định nghĩa tập con của một tập hợp và các tập hợp bằng nhau. (Phân biệt được các phần tử và các tập con của một tập hợp cho trước). − Cách biểu diễn tập con của một tập hợp bằng lược đồ Ven. − Một vài tính chất của quan hệ bao hàm. (Nêu và chứng minh được các tính chất đó). Nhiệm vụ 3: − Hiểu được thế nào là tập hợp của một số tập hợp. (Hãy cho một vài ví dụ về tập hợp những tập hợp). − Liệt kê được tất cả các tập con của một tập hợp có n phần tử với n = 1, 2, 3, 4, 5. − Biết cách tính số các tập hợp con của một tập hợp hữu hạn. Đánh giá hoạt động 1.1 1. Hãy liệt kê các phần tử của các tập hợp sau: a) A là tập hợp các bội tự nhiên của 3 lớn hơn 20 và nhỏ hơn 40; b) B là tập hợp các số nguyên tố lớn hơn 30 và nhỏ hơn 50; c) C là tập hợp các ước tự nhiên của 36. 2. Hãy liệt kê các phần tử của các tập hợp sau: a) A = {x ∈ N : 2x2 − 15x + 13 < 0}; b) B = {x ∈⏐R: 2x3 + 5x2 + 3x = 0}; c) C = {x ∈ Z : 6x2 + x − 1 = 0}. 3. Cho các tập hợp A = {3, 7, 11, 15, 19, 23, 27};
B = {17, 19, 23, 29, 31, 37, 41, 43, 47}; 64 2 4 8 16 32 − − − , , , , , 1 1 1 1 1 C = {1, 1 } Hãy nêu một tính chất đặc trưng của các phần tử của mỗi tập hợp đã cho (tức là tính chất, nhờ đó nhận biết được một đối tượng là phần tử hay không phải là phần tử của tập hợp đã cho). 4. Cho các tập hợp A = {x ∈ N : x4 − 4 0}. Chứng minh rằng: A ⊂ B và C ⊂ D. 5. Cho A là tập hợp các ước tự nhiên của 30 và B = {x ∈ N : 4x2 − 4x > 3}. Đúng ghi Đ, sai ghi S vào ô trống: ± A ⊂ B ; ± B ⊂ A; ± A ⊄ B; ± B ⊂ A 6. Gọi C là tập hợp các tam giác cân, D là tập hợp các tam giác đều và V là tập hợp các tam giác vuông. Đúng ghi Đ, sai ghi S vào ô trống. ± V ⊂ C; ± C ⊂ V; ± V ⊄ C; ± C ⊂ V ± D ⊂ C; ± C ⊂ D; ± D ⊄ V; ± V ⊂ D 7. Gọi A là tập hợp các chữ số 135x sao cho số tự nhiên chia hết cho 4 và B là tập hợp các chữ số 137y sao cho số tự nhiên chia hết cho 2. Chứng minh rằng: A = B 8. Cho tập hợp A = {a, b, c}. Đúng ghi Đ, sai ghi S vào ô trống: ± a ∈ A ± {a} ∈ A ± {a} ∈ A ± {a, b} ∈ A ± {a, b} ⊂ A ± b ⊂ {b, c} ± {b} ⊂ {b, c} ± {b} ⊂ {b, c} 9. Cho tập hợp A = {a1, a2, a3}. Gọi P (A) là tập hợp tất cả các tập hợp con của tập hợp A. a) Hãy liệt kê tất cả các phần tử của P(A). b) P(A) có bao nhiêu phần tử ? 10. Cho tập hợp B = {a1, a2, a3, a4}. Gọi P(B) là tập hợp tất cả các tập hợp con của tập hợp Aa) Hãy liệt kê tất cả các phần tử của P(B).
b) P(B) có bao nhiêu phần tử? 11. Cho các tập hợp A = {a, b, c}, B = {a, b, c, d}. Trong hai cách viết sau đây, cái nào đúng, cái nào sai? a) P(A) ∈ P(B) ; b) P(A) ∈ P(B). 12. Bằng phương pháp quy nạp, hãy chứng minh rằng nếu tập hợp A có n phần tử thì nó có cả thảy 2n tập con. Formatted: Heading01
TIỂU CHỦ ĐỀ 1.2. CÁC PHÉP TOÁN TRÊN CÁC TẬP HỢP Thông tin cơ bản 2.1. Giao của các tập hợp Formatted: Heading03 a) Giao của hai tập hợp A và B là tập hợp tạo nên bởi các phần tử chung của hai tập hợp đó, kí hiệu là: A ∩ B (đọc là A giao B) Từ định nghĩa của A ∩ B suy ra rằng x ∈ A ∩ B khi và chỉ khi x ∈ A và x ∈ B. Ta viết: x ∈ A ∩ B ⇔ x ∈ A và x ∈ B. Ví dụ 2.1 : Nếu A là tập hợp các bội tự nhiên của 4 và B là tập hợp các bội tự nhiên của 6: A = {0, 4, 8, 12, 16, 20, }; B = {0, 6, 12, 18, 24, 30 } thì A ∩ B là tập hợp các bội tự nhiên của 12: A ∩ B = {0, 12, 24, 36 } Hình 9 Ví dụ 2.2 : Cho tập hợp A = {x ∈ ⏐R : 2x − 1 < 0}. Tìm A ∩ N (N là tập hợp các số tự nhiên). Ta có: A = {x ∈ ⏐R : x < } Do đó: A ∩ N = {0}.
Hình 10 Hai tập hợp A và B gọi là không giao nhau hoặc rời nhau nếu A ∩ B = φ. Ví dụ 2.3 : Nếu D là tập hợp các tam giác đều và V là tập hợp các tam giác vuông thì D và V là hai tập hợp rời nhau. Thật vậy, một tam giác không thể vừa đều vừa vuông. Do đó: D ∩ V = φ Phần có các đường gạch chéo trong Hình 11 biểu thị tập hợp φ. Hình 11 Từ định nghĩa giao của hai tập hợp suy ra rằng: x ∉ A B x ∉ A hoặc x ∉ B. b) Đối với hai tập hợp A và B bất kì, ta có lược đồ Ven dưới đây. Lược đồ chỉ ra bốn miền được đánh số I, II, III, IV. Các miền này được làm rõ bởi một cây chẽ đôi.
Hình 12 Người ta cũng biểu diễn bốn miền nay trong một bảng của hai tập hợp A, B. Bảng này được gọi là lược đồ Carôlơ (Caroll). Hình 13 Ví dụ 2.4 : Gọi A là tập hợp các ước tự nhiên của 6 và B là tập hợp các ước tự nhiên của 8. Các miền I, II, III, IV được cho trong lược đồ Ven là lược đồ Carôlơ trong Hình 13. Một số tính chất của phép lấy giao các tập hợp Từ định nghĩa giao của hai tập hợp, dễ dàng chứng minh được các đẳng thức sau: c) Với các tập hợp bất kì A, B, C, ta có: (i) A ∩ B = B ∩ A, (ii) (A ∩ B) ∩ C = A ∩ (B ∩ C),
(iii) φ ∩ A = φ, (iv) A ∩ A = A Đẳng thức (ii) cho phép, khi lấy giao của một số hữu hạn tập hợp, bỏ các dấu ngoặc hoặc chỉ thứ tự phép lấy giao. Quan hệ giữa bao hàm thức và giao của các tập hợp được cho trong định lí sau: d) Với các tập hợp bất kì A, B, C, D, ta có: (i) A ∩ B ⊂ A, A ∩ B ⊂ B, (ii) Nếu A ⊂ B và A ⊂ C thì A ⊂ B ∩ C, (iii) Nếu A ∩ B và C ∩ D thì A ∩ C ⊂ B ∩ D, (iv) A ⊂ B ⇔ A ∩ B = A. Chứng minh: (ii) giả sử A ⊂ B, A ⊂ C và x là một phần tử bất kì của A. Khi đó, x ∈ B và x ∈ C; do đó x ∈ B ∩ C. (iv) (⇒) Giả sử A ⊂ B. Khi đó, nếu x ∈ A thì x ∈ B, do đó x ∈ A ∩ B . Từ đó ta có A ⊂ A ∩ B. Mặt khác, theo (i), A ∩ B ⊂ A. Từ hai bao hàm thức trên suy ra A ∩ B = A. (⇐) giả sử A ∩ B = A. Khi đó, nếu x ∈ A thì x ∈ A ∩ B ; do đó x ∈ B. Vậy A ⊂ B . e) Các mảnh lôgic Điênétxơ (Diénès) Đó là một bộ gồm 48 mảnh gỗ, đôi một được phân biệt bởi ít nhất là một thuộc tính (tiêu chuẩn) và nhiều nhất là bốn thuộc tính. Mỗi mảnh gỗ được xác định bởi bốn thuộc tính:
Có 24 mảnh cùng độ dày. Mỗi mảnh được xác định bởi bốn chữ tượng trưng cho bốn thuộc tính, nhờ đó phân biệt được nó với các mảnh khác. Bốn thuộc tính được nhắc đến theo thứ tự sau: Hình dạng − Độ lớn − Màu sắc − Độ dày. Hình 14
Hình 14 Chẳng hạn, VLĐD hay CBXM Hình vuông lớn đỏ dày Hình chữ nhật bé xanh mỏng. Tập hợp tất cả các mảnh lôgic Điênétxơ được kí hiệu là L0 Các tập con những mảnh lôgic được kí hiệu bởi một, hai hoặc ba chữ. Chẳng hạn, V là tập hợp các mảnh hình vuông và XM là tập hợp các mảnh xanh mỏng. Lược đồ Ven của hai tập hợp này được cho trong Hình 15. Dễ thấy. V ∩ XM = {x : x là một mảnh vuông xanh mỏng} = {VBXM, VLXM}
Hình 15 2.2. Hợp của các tập hợp Formatted: Heading03 a) Hợp của hai tập hợp A và B là tập hợp tạo nên bởi các phần tử thuộc ít nhất một trong hai tập hợp đó, kí hiệu là A ∪ B (đọc là A hợp B). Từ định nghĩa của A ∪ B suy ra rằng: x ∈ A ∪ B ⇔ x ∈ A hoặc x ∈ B. Ví dụ 2.5 : Nếu A = {a, b, c, d, e}; B = {b, e, f, g} thì A ∪ B = {a, b, c, d, e, f, g} Ví dụ 2.6 : Hợp của tập hợp các số hữu tỉ và tập hợp các số vô tỉ là tập hợp các số thực. Hợp của tập hợp Z các số nguyên và tạp hợp Q các số hữu tỉ là tập hợp Q: Z ∪ Q = Q. Từ định nghĩa hợp của hai tập hợp suy ra rằng: x ∉ A ∪ B ⇔ x ∉ A và x ∉ B. Ví dụ 2.7 : Xét tập hợp T các mảnh tam giác và tập hợp X các mảnh có màu xanh trong bộ các mảnh Lôgic Điênétxơ. Khi đó T ∪ X là tập hợp các phần tử thuộc T hoặc thuộc X. Đó là tập hợp các mảnh hình tam giác hoặc có màu xanh.
Hình 16 TUX là tập hợp các mảnh tam giác hoặc xanh. Một số tính chất của phép lấy hợp các tập hợp Từ định nghĩa của hợp các tập hợp dễ dàng suy ra: b) Với các tập hợp bất kì A, B, C, (i) A ∪ B = B ∪ A, (ii) (A ∪ B) ∪ C = A ∪ (B ∪ C), (iii) φ ∪ A = A, (iv) A ∪ A = A. Đẳng thứ (ii) cho phép, khi lấy hợp của một số hữu hạn tập hợp, bỏ các dấu ngoặc chỉ thứ tự các phép lấy hợp. Quan hệ giữa bao hàm thức và phép lấy hợp được cho trong định lí sau: c) Với các tập hợp bất kì A, B, C, D, (i) A ⊂ A ∪ B, B ⊂ A ∪ B, (ii) Nếu A ⊂ C và B ⊂ C thì A ∪ B ⊂ C, (iii) Nếu A ⊂ C và B ⊂ D thì A B ⊂ C ∪ D, (iv) A ⊂ B ⇔ A ∪ B = B. Chứng minh (ii) giả sử A ⊂ C và B ⊂ C. Khi đó, nếu x ∈ A ⊂ B thì x ∈ A hoặc x ∈ B. Do đó x ∈ C. Vậy A ∪ B ⊂ C.
(iv) (⇒) Giả sử A ⊂ B. Khi đó, nếu x ∈ A ∪ B thì x B hoặc x A B, do đó x B. Vậy A B B. Mặt khác, theo (i), ta có B A B. Từ hai bao hàm thức vừa nêu suy ra A ∪ B = B. (⇐) Giả sử A ∪ B = B. Khi đó, theo (i), ta có: A ⊂ A ∪ B = B. Định lí sau nêu lên quan hệ giữa hai phép lấy hợp và giao của các tập hợp. d) Với các tập hợp bất kì A, B, C, (i) A ∩ (A ∪ B) = A, (ii) (A ∩ B) ∪ B = B, (iii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), (iv) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Chứng minh (i) Vì A ⊂ A ∪ B nên A ∩ (A ∪ B) = A (theo (iv) trong 1.d)). (ii) Vì A ∩ B ⊂ B nên (A ∩ B) ∪ B = B (theo (iv) trong c) (iii) Giả sử x ∈ A ∩ (B ∪ C). Khi đó x ∈ A và x ∈ B ∪ C. Do đó x ∈ A và x ∈ B hoặc x ∈ C. Nếu x ∈ A và x ∈ B thì x ∈ A ∩ B. Do đó x ∈ (A ∩ B) ∪ (A ∩ C). Tương tự, nếu x A và x C thì x ∪ A ∩ C. DO đó x ∈ (A ∩ B) ∪ (A ∩ C). Vậy: A ∩ (B ∪ C) ⊂ (A ∩ B) ∪ (A ∩ C) (1) Đảo lại, nếu x ∈ (A ∩ B) ∪ (A ∩ C) thì x ∈ A ∩ B hoặc x ∈ A ∩ C. Nếu x ∈ A ∩ B thì x ∈ A và x ∈ B ⊂ B ∪ C; do đó x ∈ A ∩ (B ∪ C). Nếu x ∈ A ∩ C thì, chứng minh tương tự, ta cũng được x ∈ A ∩ (B ∪ C). Vậy: (A ∩ B) ∪ (A ∩ C) ⊂ A ∩ (B ∪ C) (2) Từ hai bao hàm thức (1) và (2) suy ra đẳng thức trong (iii) cần chứng minh: (iv) được chứng minh tương tự Công thức (iii) cho thấy phép hợp có tính phân phối đối với phép giao; công thức (iv) cho thấy phép giao có tính phân phối đối với phép hợp. 2.3. Hiệu của hai tập hợp Formatted: Heading03 a) Hiệu của hai tập hợp A và B là tập hợp các phần tử thuộc A nhưng không thuộc B, kí hiệu là A \ B (đọc là A trừ B). Từ định nghĩa của A \ B suy ra: x ∈ A \ B ⇔ x ∈ A và x ∉ B.
Ví dụ 2.8 : Cho hai tập hợp: A = {a, b, c, d, e, f}, B = (c, e, g, h, k}. Khi đó: A \ B = {a, b, d, f} Ví dụ 2.9 : Gọi C là tập hợp các hình chữ nhật, T là tập hợp các hình thoi. Khi đó, C \ T là tập hợp các hình chữ nhật mà không phải là hình thoi (Hình 18). Hình 17 Hình 18 Đó cũng chính là tập hợp các hình chữ nhật mà không phải là hình vuông. Ví dụ 2.10 : Hiệu của tập hợp các số thực và tập hợp các số hữu tỉ là tập hợp các số vô tỉ. Hiệu của tập hợp N các số tự nhiên và tập hợp Z là tập hợp rỗng: N \ Z = φ. Từ định nghĩa hiệu hai tập hợp suy ra rằng: x ∉ A \ B ⇔ x ∉ A hoặc x ∈ B. Một số tính chất của phép trừ Quan hệ giữa bao hàm thức và phép lấy hiệu hai tập hợp được cho trong định lí sau: b) Với các tập hợp bất kì A, B, C, D, ta có: (i) A \ B ⊂ A, (ii) Nếu A ⊂ B và C ⊂ D thì A \ D ⊂ B \ C, (iii) Nếu C ⊂ D thì A \ D A \ C, (iv) A ⊂ B ⇔ A \ B = φ.
Chứng minh: (ii) Nếu x ∈ A \ D thì x ∈ A và x ∉ D. Vì A ⊂ B và x ∈ A nên x ∈ B. Vì C ⊂ D và x ∉ D nên x ∉ C. Như vậy, ta có x ∈ B và x ∉ C; do đó x ∈ B \ C. Vậy A \ D ⊂ B \ C. (iii) Vì A ⊂ A nên trong (ii), thay B bởi A, ta được (iii). (iv) suy ra từ định nghĩa hiệu của hai tập hợp. Quan hệ giữa phép trừ với hai phép hợp và giao các tập hợp được nêu trong định lí sau: c) Với các tập hợp bất kì A, B, C, ta có: (i) A \ (B ∪ C) = (A \ B) ∩ (A \ C), (ii) A \ (B ∩ C) = (A \ B) ∪ (A \ C). ((i) và (ii) được gọi là cac công thức Moocgăng (Morgan)). Chứng minh: (i) x ∈ A \ (B ∪ C) ⇔ x ∈ A và x ∉ B ∪ C. x ∉ B ∪ C ⇔ x ∉ B và x ∉ C. Do đó: x ∈ A \ (B ∪ C) ⇔ x ∈ A và x ∉ B và x ∉ C ⇔ x ∈ A \ B và x ∈ A \ C. ⇔ x ∈ (A \ B) ∩ (A \ C). Từ đó ta có đẳng thức (i). (ii) được chứng minh tương tự. 2.4. Không gian. Phần bù của một tập hợp Formatted: Heading03 a) Trong các ứng dụng của lí thuyết tập hợp, các tập hợp được xét thường là các tập con của một tập hợp X cho trước. Tập hợp X được gọi là không gian. Chẳng hạn, trong số học, người ta chỉ xét các tập con của tập hợp N các số tự nhiên. Khi đó, ta có không gian N. Trong giải tích, tập hợp ⏐R các số thực được xem là không gian và trong hình học, tập hợp các điểm của không gian Ơclit được xem là không gian. Khi nghiên cứu các tập con của một không gian X, người ta thường đồng nhất một tập hợp con A của X với một tính chất đặc trưng T của các phần tử của A: Chỉ các phần tử của A có tính chất T, các phần tử khác của X không có tính chất đó. Khi đó, thay cho x ∈ A, ta nói x có tính chất T. Chẳng hạn, tập hợp P các số nguyên tố là một tập hợp con của không gian N các số tự nhiên. Thay cho x P, ta nói rằng x là một số nguyên tố. Tương
tự, tập hợp N các nghiệm thực của phương trình (x2 − 2) (x2 + x − 6) = 0 là một tập hợp con của không gian ⏐R các số thực. Thay cho x ∈ N, là nói rằng x là một nghiệm thực của phương trình vừa xét. b) Giả sử X là một không gian và A là một tập con của X. Tập hợp X \ A được gọi là phần bù của A và được kí hiệu là CA. Hình 19 Chú ý rằng phần bù của một tập hợp phụ thuộc vào không gian chứa nó. Chẳng hạn, tập hợp A = {0, 1, 2, 3, 4} có phần bù trong không gian N các số tự nhiên là tập hợp các số tự nhiên lớn hơn 4, nhưng trong không gian Z các số nguyên, phần bù của A là tập hợp gồm các số nguyên âm và các số nguyên lớn hơn 4. Từ định nghĩa phần bù của một tập hợp suy ra rằng: Nếu X là một không gian và A ⊂ X thì với mọi x ∈ X, x ∈ CA ⇔ x ∉ A. Một số tính chất của phần bù của tập hợp Từ định nghĩa của phần bù một tập hợp, dễ dàng chứng minh được rằng: c) Với các tập con bất kì A, B của không gian X, ta có: (i) X ∩ A = A, (ii) X ∪ A = X, (iii) CX = φ, (iv) Cφ = X, (v) CCA = A,
(vi) A ⊂ B ⇔ CB ⊂ CA. Chứng minh (v) Nếu x ∈ C(CA) thì x ∉ CA; do đó x ∈ A. Vậy CCA ⊂ A. Đảo lại, nếu x ∈ A thì x ∉ CA, do đó x ∈ C(CA). Vậy A ⊂ CCA. Từ hai bao hàm thức vừa nêu suy ra đẳng thức cần chứng minh. Quan hệ giữa một tập hợp bất kì với phần bù của nó trong không gian. d) Với mọi tập con A của không gian X, ta có: (i) A ∪ CA = X, (ii) A ∩ CA = φ. Chứng minh (i) Nếu x ∈ X thì x ∈ A hoặc x ∉ A, do đó x thuộc ít nhất một trong hai tập hợp A và CA, tức là x ∈ A ∪ CA. Đảo lại, nếu x ∈ A ∪ CA thì x thuộc ít nhất một trong hai tập hợp A và CA. Vì cả hai tập hợp này đều là những tập hợp con của X nên x ∈ X. Từ đó ta có đẳng thức (i). (ii) Nếu x ∈ A ∩ CA thì x ∈ A và x ∈ CA, tức là x ∈ A và x ∉ A, điều này là vô lí. Vậy tập hợp A ∩ CA không có phần tử nào, tức là A ∩ CA = φ. Từ định lí 3 c) và định nghĩa phần bù của tập hợp suy ra rằng: e) Với hai tập hợp con bất kì A, B của không gian X, ta có: (i) C(A ∪ B) = (CA ∩ CB, (ii) C(A ∩ B) = CA ∪ CB. Như vậy, phần bù của tập hợp hai tập hợp bằng giao các phần bù của chúng và phần bù của giao hai tập hợp bằng hợp các phần bù của chúng. (i) và (ii) gọi là các công thức Moócgăng. Quan hệ giữa hiệu của hai tập hợp con bất kì của một không gian với các phép lấy phần bù, hợp và giao được nêu trong định lí sau: f) Với hai tập hợp con bất kì A, B của không gian X, ta có: (i) A \ B = A ∩ [B, (ii) A \ B = C(CA ∪ B). Chứng minh (i) x ∈ A \ B ⇔ x ∈ A và x ∉ B ⇔ x ∈ A và x ∈ [B ⇔ x ∈ A ∩ [B. Do đó ta có đẳng thức trong (i).
(ii) Theo (v) trong c), ta có: A \ B = CC(A \ B). Từ (i) và (ii) trong e) suy ra: [(A \ B) = [(A ∩ [B) = [A ∪ [[B = [A ∪ B Do đó: A \ B = C(CA ∪ B) Định lí sau thường được sử dụng trong thực hành: g) Với hai tập hợp con bất kì A, B của không gian X, (i) A ⊂ B ⇔ A ∩ [B = φ, (ii) A ⊂ B ⇔ [A ∪ B = X. Chứng minh (i) Ta biết rằng A ⊂ B khi và chỉ khi A \ B = φ. Mặt khac,ta co A \ B = A ∩ [B (xem (i) trong f)). Từ đó suy ra đẳng thức cần chứng minh: (ii) Theo (i), chỉ cần chứng minh A ∩ {B = φ ⇔ [A ∪ B = X. Thật vậy, các điều kiện sau là tương đương: A ∩ CB = φ, C(A ∩ CB) = X, CA ∪ CCB = X (suy ra từ công thức Đờ−Mooc−găng) CA ∪ B = X b. hoạt động. Sinh viên tự đọc thông tin cơ bản, sau đó thảo luận theo nhóm 2, 3 người để thực hiện các nhiệm vụ dưới đây. Mỗi nhóm cử đại diện trình bày để giáo viên tổng kết: Nhiệm vụ Nhiệm vụ 1: Formatted: Heading03 − Nắm vững định nghĩa giao của hai tập hợp và có kĩ năng thành thạo trong việc tìm giao của hai tập hợp cho trước. − Lập được lược đồ Ven và lược đồ Carôlơ đối với hai tập hợp A và B cho trước. − Nắm vững các tính chất của phép lấy giao các tập hợp. Nhiệm vụ 2: Formatted: Heading03
− Nắm vững định nghĩa hợp của hai tập hợp và có kĩ năng thành thạo trong việc tìm hợp của hai tập hợp cho trước. − Lập được lược đồ Ven của hợp hai tập hợp. − Nắm vững các tính chất của phép lấy hợp các tập hợp. − Nắm vững quan hệ giữa phép lấy hợp và lấy giao các tập hợp. Nhiệm vụ 3: Formatted: Heading03 − Nắm vững định nghĩa hiệu của hai tập hợp và có kĩ năng thành thạo trong việc tìm hiệu của hai tập hợp cho trước. − Lập được lược đồ Ven của hiệu của hai tập hợp. − Nắm vững các tính chất của phép trừ tập hợp: z Quan hệ giữa phép trừ và bao hàm thức. z Quan hệ giữa phép trừ và phép lấy hợp và giao các tập hợp. Nhiệm vụ 4: Formatted: Heading03 − Nắm vững khái niệm không gian và định nghĩa phần bù của một tập hợp và có kí năng thành thạo trong việc tìm phần bù của một tập hợp cho trước. − Nắm vững một số tính chất của phần bù của tập hợp: z Quan hệ giữa một tập hợp con của một không gian với phần bù của nó. z Phép lấy phần bù của hợp và giao của hai tập hợp (các công thức Moócgăng). z Quan hệ giữa phần bù của tập hợp và bao hàm thức. z Quan hệ giữa phần bù của tập hợp với phép trừ các tập hợp. Đánh giá hoạt động 1. 2 Formatted: Heading02 1. Gọi A là tập hợp các số lẻ giữa 10 và 40 (lớn hơn 10 và nhỏ hơn 40) và B là tập hợp các số nguyên tố giữa 10 và 40. a) Tìm các tập hợp A ∪ B, A ∩ B, A \ B và B \ A. b) Lập lược đồ Ven đối với hai tập hợp A và B. 2. Gọi A là tập hợp các số tự nhiên chia hết cho 2 và B là tập hợp các số tự nhiên chia hết cho 5. a) Tìm các tập hợp A ∪ B, A ∩ B, A \ B và B \ A. b) Lập sơ đồ Ven đối với A và B. 3. Gọi V là tập hợp các tam giác vuông và C là tập hợp các tam giác cân. a) Tìm các tập hợp V ∩ C, V ∪ C, V \ C và C \ V. b) Lập lược đồ Ven đối với hai tập hợp V và C.
4. Cho hai tập hợp A = {x ∈ ⏐R : |x| ≥ 5} và B = {x ∈ ⏐R : −6 ≤ x < 0} Tìm các tập hợp A B, A B, A \ B và B \ A. 5. Tìm hai tập hợp E và F những mảnh lôgic Điênétxơ (E, F ∈ L0) trong mỗi lược đồ dưới đây biết rằng mỗi tập hợp được xác định bởi hai thuộc tính và giao E ∩ F là tập một điểm: Hình 20 6. Trong tập hợp L0 các mảnh lôgic Điênétxơ, gọi N là tập hợp các mảnh nâu, BN là tập hợp các mảnh bé nâu và V là tập hợp các hình vuông. a) Xác định các miền II, IV và V bằng cách nêu một tính chất đặc trưng của các phần tử của mỗi miền. b) Tính số phần tử của mỗi miền.
Hình 21 7. Chứng minh rằng với các tập hợp bất kì A, B, ta có: a) A \ B = A \ (A ∩ B) ; b) A = (A ∩ B) ∪ (A \ B); c) A \ (A \ B) = A ∩ B. 8. Chứng minh rằng với ba tập hợp A, B, C bất kì, ta có: a) A \ (B ∪ C) = (A \ B) \ C; b) A ∩ (B \ C) = (A ∩ B) \ C; c) (A ∪ B) \ C) = (A \ C) ∪ (B \ C); d) A \ (B \ C) = (A \ B) ∪ (A ∩ C). 9. Chứng minh rằng với hai tập hợp con bất kì A, B của không gian X, nếu [A ∪ [B = [A và B ⊂ A thì A = B. 10. Chứng minh rằng với hai tập hợp con A và B bất kì của không gian X, A ⊂ B ⇔ [A ∩ [B = [B. 11. Hiệu đối xứng của hai tập hợp A và B, kí hiệu là A ∆ B, là tập hợp các phần tử thuộc A hoặc thuộc B nhưng không thuộc đồng thời cả hai tập hợp đó: A ∆ B = (A \ B) ∪ (B \ A). Chứng minh rằng: a) A ∆ B = φ ⇔ A = B, b) A ∆ B = B ∆ A, c) (A ∆ B) ∆ C = A ∆ (B ∆ C), d) A ∩ (B ∆ C) = (A ∩ B) ∆ (A ∩ C), e) A ∪ B = A ∆ B ∆ (A ∩ B), f) A \ B = A ∆ (A ∩ B). 12. Chứng minh rằng với ba tập hợp A, B, C bất kì, A ∆ B = C ⇒ B = A ∆ C. 13. Với hai tập hợp con bất kì A, B của không gian X, ta định nghĩa hợp và giao của hai tập hợp đó dựa vào quan hệ bao hàm như sau: A B là tập con nhỏ nhất của X chứa A và B, A B là tập con lớn nhất của X chứa trong A và trong B. a) Chứng minh các định nghĩa này tương đương với các định nghĩa đã biết.
b) áp dụng các định nghĩa vừa nêu, hãy chứng minh các khẳng định sau: (i) A ⊂ B ⇔ A ∪ B = B, (ii) (A ∩ B) ∩ C = A ∩ (B ∩ C), (iii) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C), A, B, C là những tập con bất kì của không gian X. 14. Cho không gian (tập hợp X). Tập hợp các tập con A1, A2, , Am gọi là một phép phân hoạch của X nếu các điều kiện sau được thoả mãn. (i) Ai ≠ φ với i = 1, 2, , m, (ii) Ai ∩ Aj = φ với i ≠ j (tức là các tập hợp A1, A2, , Am đôi một rời nhau), (iii) A1 A2 Am = X. Chứng minh rằng mỗi tập các tập con sau đây của L0 là một phép phân hoạch của L0: a) {Đ, X, N}; b) {C, V, T, H}; c) {LM, BM, LD, BD}; d) BĐ, LX, BX, LĐ, N}. 15. Gọi A là tập hợp các bội tự nhiên của 3, B là tập hợp các số tự nhiên n sao cho n − 1 là một bội tự nhiên của 3 và C là tập hợp các số tự nhiên n sao cho n − 2 là một bội tự nhiên của 3. Chứng minh rằng: {A, B, C} là một phép phân hoạch của không gian N. 16. Với một tập hợp hữu hạn A bất kì, kí hiệu N (A) chỉ số phần tử của A. Chứng minh rằng với hai tập hợp hữu hạn A, B bất kì, ta có: N (A ∪ B) = N (A) + N (B) − N (A ∩ B). 17. Cho ba tập hợp hữu hạn A, B, C. Chứng minh rằng: N (A ∪ B ∪ C) = N (A) + N (B) + N (C) + N (A ∩ B ∩ C) − N (A ∩ B) − N (A ∩ C) − N (B ∩ C). 18. Trong một lớp học ngoại ngữ, tập hợp A các học viên nữ có 4 phần tử, tập hợp B các học viên từ 20 tuổi trở lên có 5 phần tử. Có 3 học viên nữ từ 20 tuổi trở lên. Tìm số phần tử của tập hợp A ∪ B. 19. Trên một bãi để xe, có 42 xe gồm taxi và xe buýt. Có 14 xe màu vàng và 37 xe buýt hoặc xe không có màu vàng. Hỏi trên bãi để xe có bao nhiêu xe buýt vàng?
20. Một lớp học có 40 học sinh, trong đó có 15 em học khá môn Toán, 16 em học khá môn Văn và 17 em học khá môn Tiếng Anh. Có 5 em học khá cả hai môn Văn và Toán, 8 em học khá cả hai môn Toán và Anh, 6 em học khá cả hai môn Văn và Anh, và 2 em học khá cả ba môn. Hỏi có bao nhiêu học sinh chỉ học khá môn Toán? Chỉ học khá môn Văn? Chỉ học khá môn Anh? Không học khá môn nào? Formatted: Heading01
TIỂU CHỦ ĐỀ 1.3. QUAN HỆ Thông tin cơ bản 3.1. Quan hệ hai ngôi Formatted: Heading03 3.1.1. Tích Đềcác của các tập hợp Formatted: Heading04 a) Cặp thứ tự Ta biết rằng tập hợp gồm hai phần tử a và b được kí hiệu là {a, b}. Kí hiệu {b, a} cũng chỉ tập hợp đó, tức là {a, b} = {b, a}. Tuy nhiên trong nhiều trường hợp người ta quan tâm đến thứ tự của hai phần tử: a đứng trước, b đứng sau hay b đứng trước, a đứng sau. Khi đó người ta được hai dãy được sắp theo thứ tự khác nhau: Dãy a, b và dãy b, a. Đó là hai dãy khác nhau, trừ phi a = b. Mỗi dãy được gọi là một cặp thứ tự của hai phần tử. Như vậy, Dãy gồm hai đối tượng a và b, được sắp theo thứ tự a đứng trước, b đứng sau gọi là một cặp thứ tự, kí hiệu là (a, b); a gọi là phần tử đứng trước, b là phần tử đứng sau. Nếu a ạ b thì (a, b) và (b, a) là hai cặp thứ tự khác nhau. Hai cặp thứ tự (a, b) và (c, d) là bằng nhau khi và chỉ khi a = b và c = d. Cặp thứ tự (a, b) được biểu diễn bởi một mũi tên đi từ phần tử đứng trước a đến phần tử đứng sau b. Hình 1 Nếu a = b thì mũi tên trở thành một vòng. Ví dụ 3.1 : Kết quả của một trận bóng đá là: (3; 1), (1; 3); (2; 0). Cặp thứ tự (3; 1) được hiểu là trên sân nhà, đội chủ nhà đã thắng đội khách: Đội chủ nhà đã ghi được 3 bàn còn đội khách chỉ ghi được 1 bàn. Cặp thứ tự (1; 3) cho biết đội chủ nhà đã thua đội khách: Trong trận đấu, đội chủ nhà chỉ ghi được 1 bàn, trong khi đội khách ghi được 3 bàn. Ví dụ 3.2 : Diện tích của các nước trên thế giới (tính trên một ngàn km2) cũng được ghi bằng các cặp thứ tự, chẳng hạn: (Tây Ban Nha; 500), (Italia; 300), (Việt Nam, 330)
Ví dụ 3.3 : Mỗi số phức là một cặp thứ tự (a, b) của hai số thực. Ta biết rằng hai số thực a và b khác nhau thì (a, b) và (b, a) là hai số phức khác nhau; Hai số phức (a, b) và (c, d) bằng nhau khi và chỉ khi chúng có phần thực bằng nhau và phần ảo bằng nhau, tức là a = c và b = d. b) Tích Đêcác của hai tập hợp. Cho hai tập hợp X và Y. Tập hợp tất cả các cặp thứ tự (x, y) trong đó x ∈ X, y ∈ Y gọi là tích Đêcác của hai tập hợp X, Y và được kí hiệu là X x Y. Như vậy, X x Y = {(x, y) : x ∈ X, y ∈ Y}. Ví dụ 3.4: Cho hai tập hợp X = {x1, x2} và Y = {y1, y2, y3}. Khi đó X x Y = {(x1, y1), (x1, y2), (x1, y3), (x2, y1), (x2, y2), (x2, y3)} Hình 2 Trong Hình 2 a), mỗi phần tử của X x Y được biểu diễn bởi một mũi tên đi từ tập hợp X vào tập hợp Y. Người ta gọi đó là lược đồ hình tên. Trong hình 2 b), các phần tử của X x Y được biểu diễn bởi các điểm của một lưới xác định bởi hai tập hợp X và Y. Người ta gọi đó là lược đồ Đêcác. Trong trường hợp tập hợp X hoặc tập hợp Y có vô số phần tử, ta chỉ có thể sử dụng lược đồ Đêcác.
Ví dụ 3.5 : Tích Đêcác của tập hợp N các số tự nhiên và tập hợp ⏐R các số thực là tập hợp. N x ⏐R = {(x, y) : x N, y ⏐R}. Trong mặt phẳng toạ độ, N x ⏐R được biểu diễn bởi tập hợp các điểm của các đường thẳng x = 0, x = 1, x = 2, Hình 3 Điểm (2; ) nằm trên đường thẳng x = 2, các điểm (3; ) và (4; −2,2), theo thứ tự, nằm trên các đường thẳng x = 3 và x = 4. Nếu Y = X thì tập hợp X x X còn được kí hiệu là X2. Như vậy, X2 = {(x, y) : x ∈ X, y ∈ X}. Ví dụ 3.6 : Cho tập hợp X = {a, b}. Tìm tập hợp X2. Ta có: X2 = {(a, a), (a, b), (b, a), (b, b)}. Ví dụ 3.7 : Cho tập hợp X = [1,5; 4] = {x ∈ ⏐R = 1,5 ≤ x ≤ 4}. Tìm X2. Ta có:
X2 = [1,5; 4] x (1,5; 4] = {(x, y) : 1,5 x 4; 1,5 ≤ y ≤ 4}. Hình 4 Trong mặt phẳng toạ độ, tập hợp X2 được biểu diễn bởi tập hợp các điểm của hình vuông giới hạn bởi các đường thẳng x = 1,5, x = 4, y = 1,5 và y = 4 (Hình 4). c) Ta mở rộng định nghĩa tích Đêcác cho một số hữu hạn tập hợp. Cho m tập hợp X1, X2, , Xm. Tập hợp các dãy m phần tử (x1, x2, , xm), trong đó x1 ∈ X1, x2 ∈ X2, , xn ∈ Xm gọi là tích Đêcác của m tập hợp X1, X2, , Xm và được kí hiệu là X1 x X2 x x Xm. X1 x X2 x x Xm = {(x1, x2, , xm) : x1 ∈ X1, xm ∈ Xm}. Nếu X1 = X2 = = Xm thì tập hợp X1 x X2 x x Xm được kí hiệu là Xm. Như vậy X là tập hợp các dãy m phần tử (x1, x2, , xm), trong đó x1, , xm ∈ X. Ví dụ 3.8 : Tích Đêcác R3, trong đó R là tập hợp các số thực là không gian Ơclit ba chiều, tích Đêcác Rm là không gian Ơclit m chiều. Ví dụ 3.9 : Tìm các ước số của 4312. Ta có: 4312 = 22 x 72 x 11. Mọi ước số của 4312 có dạng 2a x 7b x 11c, với a = 0, 1, 2 hoặc 3, b = 0, 1 hoặc 2, c = 0 hoặc 1. Đặt X = {20, 21, 22, 23}, Y = {70, 71, 72}, C = {110, 111}. Khi đó, với mọi (x, y, z) ∈ X x Y x Z, tích xyz là một ước của 4312.
3.2. Định nghĩa quan hệ hai ngôi Formatted: Heading04 Ta đã biết có thể đồng nhất một tập hợp con A của một không gian X với mọt tính chất T nào đó của các phần tử của không gian X: Chỉ các phần tử của A có tính chất T, các phần tử của X không thuộc A không có tính chất đó. Nói một cách khác, x có tính chất T ⇔ x ∈ A (xem mục 4, hoạt động 2, chủ đề 1). Trong toán học người ta thường quan tâm đến các tính chất của các cặp thứ tự, tức là các tính chất của các phần tử của tích Đêcác. Các tính chất đó được gọi là những quan hệ hai ngôi, gọi tắt là quan hệ. Theo nhận xét vừa nêu ở trên, có thể xem các quan hệ hai ngôi là các tập hợp con của các tích Đêcác. Điều này sẽ được làm sáng tỏ qua các ví dụ. Ví dụ 3.10 : Ta kí hiệu P = P (⏐R) là tập hợp tất cả các tập con của tập hợp số thực ⏐R. Giữa số thực và tập hợp số thực {1, , 5} có quan hệ “phần tử thuộc tập hợp”, tức là quan hệ ∈ {1, , 5}. Một cách tổng quát, có quan hệ này giữa một số thực x và một tập con A của ⏐R khi và chỉ khi x ∈ A. Quan hệ vừa nêu là một tính chất của các cặp thứ tự (x, A), trong đó x ∈⏐R, A P. Cặp thứ tự (x, A) trong đó x ∈⏐R, A ∈ P có tính chất này khi và chỉ khi x ∈ A. Vì vậy có thể xem quan hệ được xét là một tập con của tích Đêcác ⏐R x P; tập con này được tạo nên bởi các cặp thứ tự (x, A), trong đó x ∈ A. Ví dụ 3.11: Ta nói rằng giữa các số nguyên dương 2 và 8, hoặc 3 và 15, hoặc 7 và 14 có quan hệ chia hết : 2 chia hết 8, 3 chia hết 15 và 7 chia hết 14. Một cách tổng quát, có quan hệ chia hết giữa hai số nguyên dương x và y khi và chỉ khi x chia hết y. Quan hệ chia hết là một tính chất của các cặp thứ tự (x, y), trong đó x ∈ N*, y ∈ N*. Cặp thứ tự (x, y), trong đó x ∈ N*, y ∈ N* có tính chất này khi và chỉ khi x chia hết y. Vì vậy, có thể xem quan hệ chia hết là một tập con của tích Đêcác N* x N* = (N*)2. Tập con này được tạo nên bởi các cặp thứ tự (x, y), trong đó x và y là hai số nguyên dương sao cho x chia hết y. Một cách tổng quát, ta có: Định nghĩa:
Cho hai tập hợp X và Y. Tập con R của tích Đêcác X x Y gọi là một quan hệ hai ngôi trên X x Y. Nếu R là một tập con của tích Đêcác X x X thì ta nói rằng R là một quan hệ hai ngôi trên X (thay cho “R là một quan hệ hai ngôi trên X x X”.). Nếu R là một quan hệ hai ngôi trên X x Y và (x, y) ∈ ℜ thì ta viết x ℜ y và đọc là x có quan hệ R với y. Nếu (x, y) R thì ta viết x R y và đọc là x không có quan hệ R với y). Quan hệ hai ngôi thường được gọi tắt là quan hệ. Ví dụ 3.12 : Cho X = {1, 2, 3, 4, 5, 6}, A = {1, 2}, B = {1, 4} và Y = {A, B}. Gọi R là quan hệ “phần tử thuộc tập hợp” trên X x Y. Theo định nghĩa quan hệ hai ngôi, ta có: R = {(1, A), (1, B), (2, A), (4, B)}. Các phần tử của R, tức là các cặp thứ tự, được biểu diễn trong hai lược đồ sau: Hình 5 Ví dụ 3.13 : Cho tập hợp X = {2, 3, 5, 8, 15}. Hãy tìm quan hệ chia hết R trên X. Ta hiểu R là quan hệ hai ngôi trên X x X. Theo định nghĩa quan hệ hai ngôi, ta có: R = {(2, 2), (2, 8), (3, 3), (3, 15), (5, 5), (5, 15), (8, 8), (15, 15)}. Các phần tử của R được biểu diễn trong hai lược đồ sau:
Hình 6 Giả sử R là một quan hệ hai ngôi trên X x Y. Tập hợp các phần tử đứng trước của các cặp thứ tự (x, y) thuộc quan hệ R gọi là tập xác định của quan hệ R, kí hiệu là D (R). Như vậy, phần tử x ∈ X thuộc D (R) khi và chỉ khi tồn tại một phần tử y ∈ Y sao cho x R y: x ∈ D (R) ⇔ tồn tại y ∈ Y sao cho x R y. hay D (R) = {x ∈ X: Tồn tại y ∈ Y sao cho x R y}. Tập hợp các phần tử đứng sau của các cặp thứ tự (x, y) thuộc quan hệ R gọi là tập ảnh (gọi tắt là ảnh) của quan hệ R, kí hiệu là D* (R). Như vậy, phần tử y ∈ Y thuộc D* (R) khi và chỉ khi tồn tại một phần tử x ∈ X sao cho x R y: y ∈ D* (R) ⇔ tồn tại x ∈ X sao cho x R y, hay D* (R) = {y ∈ Y: Tồn tại x ∈ X sao cho x R y}. Chẳng hạn, với quan hệ hai ngôi R trong ví dụ 12, ta có: D* (R) = {1, 2, 4} , D* (R) = {A, B} = Y. Ví dụ 3.14 : Cho tập hợp X = {2, 3, 5} và Y = N. Gọi R là quan hệ chia hết trên X x N, tức là x R y khi và chỉ khi x là ước số của y. Khi đó. D* (R) = X = {2, 3, 5}, và D* (R) tập hợp tất cả các số tự nhiên chia hết cho 2, 3 hoặc 5: D* (R) = {2m : m ∈ N} ∪ {3n : n ∈ N} ∪ {5k : k ∈ N}. Có thể biểu diễn quan hệ hai ngôi R trên tập hợp Rcác số thực bởi lược đồ Đêcác. Quan hệ R được biểu diễn bởi một tập con của mặt phẳng toạ độ Oxy. Tập xác định D (R) của quan hệ R được biểu diễn bởi hình chiếu của
R trên trục hoành Ox; tập ảnh D* (R) của quan hệ ℜ được biểu diễn bởi hình chiếu của R trên trục tung Oy (Hình 7). Hình 7 Hình 8 Trong Hình 8, ta có lược đồ biểu diễn quan hệ hai ngôi R trên ⏐R (R = ⏐R2) xác định như sau: Với mọi (x, y) ⏐R2, x R y khi và chỉ khi x2 = y. Dễ dàng thấy rằng: D (R) = ⏐R và D*(R = [0, + ∞) = x : x ≥ 0 3.3. Một số tính chất thường gặp của quan hệ hai ngôi Formatted: Heading04 a) Quan hệ hai ngôi R trên tập hợp X gọi là phản xạ nếu với mọi x ∈ X, ta đều có x R x. Ví dụ 3.15 : Quan hệ chia hết trên tập hợp số nguyên dương N* là phản xạ vì với mọi số nguyên dương x, x chia hết x. • Quan hệ ≤ (nhỏ hơn hoặc bằng) trên tập hợp các số thực ⏐R là phản xạ vì với mọi x ∈ ⏐R, x ≤ x. • Giả sử A là một tập hợp các mảnh lôgíc (A ⊂ L0). Quan hệ RA “có cùng màu với” (mảnh x có cùng màu với mảnh y) hiển nhiên là phản xạ (Hình 9).
Hình 9 Hình 10 Nếu R là một quan hệ phản xạ trên A thì lược đồ hình tên của nó có một vòng tại mỗi điểm của A (Hình 9). • Quan hệ “là bình phương của” trên N không phải là một quan hệ phản xạ vì chỉ có hệ số 0 và 1 là bình phương của chính nó (Hình 10). Nếu quan hệ hai ngôi R trên X không phải là phản xạ thì lược đồ hình tên của nó có ít nhất một điểm tại đó không có vòng. Quan hệ hai ngôi R trên tập hợp X gọi là đối phản xạ nếu với mọi x ∈ X, x đều không có quan hệ R với x, tức là không xảy ra x R x. Nói một cách khác, R là đối phản xạ nếu (x, x) ∉ R với mọi x ∈ X. Ví dụ 3.16 : Quan hệ “<” trên ⏐R là đối phản xạ vì với mọi x ∈ ⏐R, đều không có x < x. Nếu quan hệ hai ngôi R trên tập hợp X là đối phản xạ thì lược đồ tên của nó không có một vòng nào (Hình 11). Hình 11 Hình 12 • Quan hệ “vuông góc với” trên tập hợp các đường thẳng của một mặt phẳng là đối phản xạ vì mọi đường thẳng đều không vuông góc với chính nó. • Quan hệ “là bố của” trên một tập hợp người cho trước là đối phản xạ. b) Quan hệ hai ngôi ℜ trên tập hợp X gọi là đối xứng nếu với mọi x, y ∈ X, x R y ⇒ y R x. Ví dụ 3.17 : Giả sử X là một tập hợp khác . Tập hợp: R = {(x, x) : x ∈ X} ⊂ X2 gọi là quan hệ đồng nhất trên X.
Như vậy, với mọi x, y ∈ X, x R y ⇔ x = y. Dễ thấy quan hệ đồng nhất trên X là đối xứng. • Quan hệ “vuông góc với” trên tập hợp các đường thẳng của một mặt phẳng là đối xứng. • Quan hệ “là anh hoặc em trai của” trên một tập hợp trẻ em là đối xứng (Hình 12). Nếu quan hệ hai ngôi R trên tập hợp X là đối xứng thì trong lược đồ hình tên của nó, hễ có một mũi tên đi từ x đến y, ắt có một mũi tên đi từ y đến x. Chú ý rằng giữa hai điểm x và y có thể không có mũi tên nào, nhưng nếu đã có thì tất phải có hai mũi tên đi ngược hướng nhau. • Cho tập hợp A = {1, 2, 3, 4}. Quan hệ “nhỏ hơn hoặc bằng” (≤) trên A không phải là một quan hệ đối xứng (Hình 13). Hình 13 Hình 14 Nếu quan hệ hai ngôi R trên tập hợp X không phải là một quan hệ đối xứng thì trên lược đồ tên của R có ít nhất một mũi tên đi từ x đến y mà không có mũi tên ngược từ y đến x. Quan hệ hai ngôi R trên tập hợp X gọi là phi đối xứng nếu với mọi x, y ∈ X, x R y ⇒ y R x. Nói một cách khác, R là phi đối xứng nếu với mọi x, y ∈ X (x, y) ∈ R ⇒ (y, x) ∉ R. Ví dụ 3.18 : • Quan hệ hai ngôi “<” (nhỏ hơn) trên tập hợp các số thực ⏐R là phi đối xứng vì với hai số thực bất kì x, y, các điều kiện x < y và y < x loại trừ nhau. • Gọi R là quan hệ hai ngôi xác định trên tập hợp các số nguyên dương N* xác định bởi: x R y khi và chỉ khi x = 2y R là một quan hệ phi đối xứng vì với mọi x, y ∈ N* không thể đồng thời xảy ra x = 2y và y = 2a (Hình 14).
Nếu R là một quan hệ phi đối xứng trên tập hợp X thì trên lược đồ hình tên của R, giữa hai điểm khác nhau x, y ∈ X, hoặc không có mũi tên nào, hoặc chỉ có một mũi tên (không có mũi tên ngược) (Hình 14). Quan hệ hai ngôi R trên tập hợp X gọi là phản đối xứng nếu với mọi x, y ∈ X, x R y và y R x ⇒ x = y. Ví dụ 3.19 : • Quan hệ hai ngôi “” trên tập hợp ⏐R là phản đối xứng vì với hai số thực bất kì x, y, hai điều kiện x y và y x kéo theo x = y. • Quan hệ hai ngôi “vuông góc với” trên tập hợp các đường thẳng của một mặt phẳng không phải là một quan hệ phản đối xứng. c) Quan hệ hai ngôi ℜ trên tập hợp X gọi là bắc cầu nếu với mọi x, y, z ∈ X, x R y và y R z ⇒ x R z. Hình 15 Trên lược đồ hình tên của quan hệ bắc cầu R, nếu có một mũi tên đi từ x đến y và một mũi tên đi từ y đến z thì có một mũi tên đi từ x đến z. (Hình 15). Ví dụ 3.20 : • Quan hệ hai ngôi “chia hết” trên tập hợp các số tự nhiên là bắc cầu vì với mọi x, y, z N, nếu x là một ước số của y và y là một ước số của z thì x là một ước số của z. • Quan hệ hai ngôi “<” trên tập hợp ⏐R là bắc cầu. • Quan hệ hai ngôi “vuông góc với” trên tập hợp các đường thẳng của một mặt phẳng không phải là một quan hệ bắc cầu. 3.4. Quan hệ ngược – Hợp của hai quan hệ Formatted: Heading04 a) Quan hệ ngược của một quan hệ cho trước
Cho hai tập hợp X, Y và quan hệ hai ngôi R trên X x Y. Quan hệ ngược của quan hệ R, kí hiệu là R−1, là quan hệ hai ngôi trên Y x X xác định như sau: Với mọi y ∈ Y, x ∈ X, y R−1 x x R y. (tức là (y, x) R−1 ⇔ (x, y) ∈ R). Ví dụ 3.21: Gọi X là tập hợp năm thành phố X = {Hà Nội, Cần Thơ, Bắc Kinh, Viên Chăn, Nam Kinh} = {h, c, b, v, n}, Y là tập hợp hai nước. Y = {Việt Nam, Trung Quốc} = {V, T}, và R là quan hệ “là một Thành phố của” R là quan hệ hai ngôi trên X x Y: R = {(h, V), (c, V), (b, T), (n, T)}. Hình 16 Quan hệ ngược R−1 của R là quan hệ hai ngôi trên Y x X. R−1 = {(V, h), (V, c), (T, b), (T, n)}. Hình 17
Các điểm biểu diễn các cặp thứ tự của R−1 đối xứng với các điểm biểu diễn các cặp thứ tự của R qua đường phân giác thứ nhất. Ví dụ3.22 : Cho tập hợp X = {0, 1, 2, 3, 4, 5, 7, 9} và quan hệ hai ngôi R “là bình phương của” trên X: R = {(0, 0), (1, ), (4, 2), (9, 3)}. Quan hệ ngược của R là quan hệ R−1 “là căn bậc hai của” trên X: R−1 = {(0, 0), (1, 1), (2, 4), (3, 9)}. Hình 18 b) Hợp của hai quan hệ Cho ba tập hợp X, Y, Z, quan hệ R1 trên X x Y và quan hệ R2 trên Y x Z. Quan hệ R trên X x Z gồm các cặp thứ tự (x, z) ∈ X x Z thoả mãn điều kiện sau: Tồn tại một phần tử y ∈ Y sao cho x R1 y và y R2 z gọi là hợp của hai quan hệ R1 và R2, kí hiệu là R2 ° R1 . Như vậy, R = R2 ° R1 = {(x, z) X x Z: Tồn tại y ∈ Y sao cho x R1 y và y R2 z}. Ví dụ 3.23 : Cho ba tập hợp Tập hợp các bà X = {Mai, Tuyết} (thế hệ thứ nhất), tập hợp các anh chị Y = {Dungx, Loan, Cường} (thế hệ thứ hai), tập hợp các cháu Z = {Khôi, Nga, Hùng, Vân} (thế hệ thứ ba), và hai quan hệ:
Quan hệ R1 “là mẹ của” trên X x Y: R1 = {(Mai, Dũng), (Tuyết, Loan), (Tuyết, Cường)}, quan hệ R2 “là bố của” trên Y x Z: R2 = {(Dũng, Khôi), (Dũng, Nga), (Cường, Vân)}. Hình 18 Quan hệ hợp R2 ° R1 của hai quan hệ R1 và R2 là quan hệ “là bà nội của” trên X x Z; R2 ° R1 = {(Mai, Khôi), (Mai, Nga), (Tuyết, Vân)}. (Bà Mai là mẹ của anh Dũng và anh Dũng là bố của cháu Khôi nên Bà Mai là bà nội của cháu Khôi). Nói chung quan hệ R2 ° R1 và quan hệ R1 ° R2 là khác nhau. Trong ví dụ vừa xét, ta có: Hình 19 Ví dụ 3.24 : Cho quan hệ R1 “là một nửa của” trên tập hợp N* các số nguyên dương và quan hệ R2 “gấp bốn lần” trên N*. Tìm R2 ° R1 Ta có: R1 = {(1; 2), (2; 4), (3, 6), (4, 8), (5, 10), } R2 = {(4; 1), (8; 2), (12, 3), (16, 4), (20, 5), }
Hình 20 R2 ° R1 là một quan hệ trên N*: R2 ° R1 = {(2, 1), (4, 2), (6, 3), (8, 4), }. R2 ° R1 là quan hệ “gấp đôi” trên N*. Có thể biểu diễn tập hợp N* chỉ bởi một đường cong kín. Khi đó, để khỏi lẫn, phải phân biệt các mũi tên biểu diễn các cặp thứ tự của R1, R2 và R1 ° R2. Hình 21 Trong hình các cặp thứ tự của các quan hệ R1 ° R2 và R2 ° R1, theo thứ tự, được biểu diễn bởi các mũi tên xanh, mũi tên có nét gạch và mũi tên đỏ. B. Hoạt động. tìm hiểu khái niệm tính đề các và quan hệ hai ngôi. Nhi•m v•:
Nhiệm vụ 1: Formatted: Heading04 − Nắm vững định nghĩa tich Đêcác của hai tập hợp và của một số hữu hạn tập hợp. − Biết biểu diễn tích Đêcác của hai tập hợp bằng lược đồ hình tên và lược đồ Đêcác. Nhiệm vụ 2: Formatted: Heading04 − Nắm vững định nghĩa quan hệ hai ngôi trên X x Y và trên X. − Có kĩ năng thành thạo trong việc xác định các cặp thứ tự của một quan hệ hai ngôi trong các tình huống khác nhau. − Biểu diễn được quan hệ hai ngôi bằng lược đồ hình tên và lược đồ Đêcác. Nhiệm vụ 3 Formatted: Heading04 − Nắm vững các tính chất phản xạ, đối xứng và bắc cầu của quan hệ hai ngôi. − Có kĩ năng nhận biết một quan hệ hai ngôi cho trước có các tính chất đó hay không? − Có kĩ năng biểu diễn các quan hệ hai ngôi có các tính chất đã nêu bằng lược đồ hình tên. Nhiệm vụ 4: Formatted: Heading04 − Nắm vững các định nghĩa của quan hệ ngược của một quan hệ hai ngôi cho trước và quan hệ hợp của hai quan hệ hai ngôi cho trước. − Có kĩ năng thành thạo trong việc xác định quan hệ ngược và quan hệ hợp. − Biểu diễn thành thạo các cặp thứ tự của quan hệ ngược và quan hệ hợp bằng lược đồ hình tên. Đánh giá hoạt động 3.1 Formatted: Heading02 1. Cho ba tập hợp X, Y, Z. Chứng minh các đẳng thức sau: a) A x (B ∪ C) = (A x B) ∪ ( A x C), b) (B ∪ C) x A = (B x A) ∪ (C x A), c) A x (B ∩ C) = (A x B) ∩ (A x C), d) (B ∩ C) x A = (B x A) ∩ (C x A), e) A x (B \ C) = (A x B) \ (A x C), f) (B \ C) x A = (B x A) \ (C x A). 2. Cho ba tập hợp A, B và C ≠ φ. Chứng minh rằng: a) A ⊂ B ⇔ A x C ⊂ B x C, b) A ⊂ B ⇔ C x A ⊂ C x B.
3. Giả sử tập hợp X có m phần tử và tập hợp Y có n phần tử. Chứng minh rằng tập hợp X x Y có mn phần tử. 4. Giả sử tập hợp Xk có nk phần tử, k = 1, 2, m. Chứng minh rằng tập hợp X1 x X2 x x Xm có n1 n2 nm phần tử. 5. Cho hai tập hợp A = {2, 4, 7, 9} và B = {1, 3, 4, 5, 12, 14}. Tìm quan hệ “chia hết” R trên A x B và biểu diễn quan hệ R bằng lược đồ hình tên. 6. Cho tập hợp X = {1, 2, 7, 8}. Tìm quan hệ “chia hết” R trên X và biểu hiện quan hệ R bằng lược đồ hình tên. 7. Cho tập hợp X = {1, 2, 6, 7, 8}. Tìm quan hệ “chia hết cho” R trên X và biểu diễn R bằng lược đồ hình tên. 8. Tìm quan hệ “chia hết cho” R trên tập hợp các số nguyên dương N* và biểu hiện R bằng lược đồ hình tên. 9. Cho các tập hợp X = {1, 2, 3, 4, 5, 7}, A = {1, 2, 9}, B = {4, 9}, C = {6, 7, 8} và Y = {A, B, C}. Tìm quan hệ R “phần tử thuộc tập hợp” trên X x Y. Biểu diễn quan hệ này bằng lược đồ hình tên. 10. Cho các tập hợp A = {1, 2}, B = {1, 5, 7}, C = {1, 2, 5, 7, 8} và X = {A, B, C}. Tìm quan hệ bao hàm “chứa trong” R trên X. (Quan hệ bao hàm “chứa trong” ℜ được cho bởi A ℜ B khi và chỉ khi A B). 11. Cho tập hợp X = {1, 2, 3, 5, 7}. Tìm quan hệ “nhỏ hơn” (<) trên X (quan hệ “nhỏ hơn” được hiểu theo nghĩa thông thường). 12. Gọi R1 là quan hệ “<” trên ⏐R và R2 là quan hệ “≠” trên ⏐R. Hãy biểu diễn R1 và R2 bằng lược đồ Đêcác. 13. Chứng minh rằng nếu tập hợp X có m phần tử và tập hợp Y có n phần tử thì có 2mn quan hệ hai ngôi trên X x Y. 14. Quan hệ “song song hoặc trùng nhau với” trên tập hợp tất cả các đường thẳng của một mặt phẳng có phải là một quan hệ phản xạ, đối xứng, bắc cầu hay không? 15. Trong một mặt phẳng cho một điểm O cố định. Gọi X là tập hợp các điểm của mặt phẳng và là quan hệ hai ngôi trên X xác định bởi: x R y khi và chỉ khi x là điểm đối xứng của điểm y qua điểm O. Hãy nêu các tính chất (phản xạ, đối xứng, bắc cầu) của R. 16. Nêu các tính chất (phản xạ, đối xứng, bắc cầu) của quan hệ “chia hết cho” trên tập hợp N* các số nguyên dương.
17. Quan hệ R1 trên tập hợp X, quan hệ R2 trên tập hợp Y và quan hệ R3 trên tập hợp Z được biểu diễn bởi các lược đồ hình tên sau đây: Hình 22 Trong ba quan hệ đó, quan hệ nào là phản xạ. 18. Quan hệ R1 trên tập hợp A, quan hệ R2 trên tập hợp B là quan hệ R3 trên tập hợp C được biểu diễn bởi các lược đồ hình tên sau đây: Hình 23 Quan hệ nào trong ba quan hệ đó là đối xứng? bắc cầu? 19. Chứng minh rằng nếu quan hệ hai ngôi R trên tập hợp X là đối phản xạ và bắc cầu thì nó là phi đối xứng. 20. Gọi R là quan hệ hai ngôi “gấp 7 lần” trên tập hợp N* các số nguyên dương: Với mọi x, y N*, x R y ⇔ x = 7y. Tìm quan hệ ngược R−1 của R. 21. Chứng minh rằng nếu quan hệ hai ngôi R trên tập hợp X là phản xạ, đối xứng, bắc cầu thì quan hệ ngược R−1 của nó cũng là phản xạ, đối xứng, bắc cầu. 22. Cho hai quan hệ hai ngôi R1 R2 trên tập hợp N* xác định bởi: x R1 y ⇔ x = 3y, x R2 y ⇔ y = x + 5. Tìm các quan hệ hợp R2 . R1 và R1 . R2 . Formatted: Heading01, Left, Space Before: 0 pt, After: 0 pt
TIỂU CHỦ ĐỀ 1.4. QUAN HỆ TƯƠNG ĐƯƠNG Thông tin cơ bản 4.1. Định nghĩa: Quan hệ hai ngôi R trên tập hợp X gọi là quan hệ tương đương trên X nếu nó là phản xạ, đối xứng và bắc cầu, tức là: a) Với mọi x ∈ X, x R x, b) Với mọi x, y ∈ X, x R y ⇒ y R x, c) Với mọi x, y, z ∈ X, x R y và y R z ⇒ x R z. Quan hệ tương đương thường được kí hiệu là ~. Khi đó x R y được kí hiệu là x ~ y đọc là x tương đương với y. Ví dụ 4.1 : Gọi ~ là quan hệ hai ngôi trên ⏐R xác định bởi x ~ y x − y Z. Trong đó Z là tập hợp các số nguyên. Quan hệ ~ là quan hệ tương đương ⏐R. Thật vậy, với mọi x ∈⏐R, ta có x − x = 0 ∈ Z; do đó ~ là phản xạ. Với mọi x, y ∈⏐R, nếu x ~ y thì x − y ∈ Z; do đó y − x = −(x − y) ∈ Z; Vậy ~ là đối xứng. Cuối cùng, với mọi x, y, z ∈⏐R, nếu x ~ y và y ~ z, tức là x − y ∈ Z và y − z ∈ Z thì x − z = (x − y) + (y − z) Z; do đó ~ là bắc cầu. Ví dụ 4.2 : Gọi X là tập hợp các vectơ buộc trong mặt phẳng ⏐R2 (A, B là hai điểm của mặt phẳng). Nếu (xA, yA) và (xB, yB) là các toạ đội của hai điểm A và B thì các hiệu xB − xA và yB − yA gọi là các thành phần của vectơ . Gọi ~ là quan hệ hai ngôi trên X xác định bởi: ~ ⇔ xB − xA = xD − xC và yB − yA = yD − yC . Dễ dàng thấy rằng ~ là một quan hệ tương đương trên X. Ví dụ 4.3 : Giả sử Đ là tập hợp các đường thẳng trong mặt phẳng ⏐R2. Gọi ~ là quan hệ hai ngôi trên Đ xác định như sau: Với mọi a, b ∈ Đ, a ~ b ⇔ a // b hoặc a trùng với b. Dễ thấy ~ là một quan hệ tương đương trên Đ. Ví dụ 4.4 : Chia một số tự nhiên bất kì cho 3, số dư của phép chia là 0 hoặc 1 hoặc 2. Quan hệ “có cùng số dư với trong phép chia cho 3” trên N hiển nhiên là
phản xạ, đối xứng và bắc cầu. Do đó nó là một quan hệ tương đương trên N. 4.2. Các lớp tương đương và tập thương Formatted: Heading03 a) Giả sử X là một tập hợp khác φ và ~ là một quan hệ tương đương trên X. Với mỗi phần tử x ∈ X, ta kí hiệu là tập hợp các phần tử y ∈ X sao cho x ~ y: = {y ∈ X : x ~ y}. Tập hợp gọi là lớp tương đương của quan hệ ~ trên X cú đại diện là phần tử x. Tập hợp chia lớp tương đương của quan hệ trên X được gọi là tập thương, kí hiệu là X/~. Hình 24 Các tính chất cơ bản của các lớp tương đương của quan hệ ~ được cho trong định lí sau: b) Định lí: Giả sử ~ là một quan hệ tương đương trên tập hợp X ≠ φ. Khi đó: (i) Với mọi x ∈ X, x ∈ , (ii) Với mọi x1, x2 ∈ X, 1 = 2 ⇔ x1 ~ x2, (iii) Với mọi x1, x2 ∈ X, nếu 1 2 Thì 1 2 = φ. Chứng minh: (i) Vì quan hệ ~ là phản xạ nên với mọi x ∈ X, x ~ x. Do đó x ∈ . (ii) Giả sử 1 = 2. Theo (i), ta có x1 ∈ 1; do đó x1 ∈ 2. Vậy x1 ~ x2. Đảo lại, giả sử x1 ~ x2. Khi đó nếu x 1; thì x ~ x1, do đó x ~ x2 vì quan hệ ~ là bắc cầu. Vậy 1 ⊂ 2 . Tương tự, ta có 2 1. Từ hai bao hàm thức trên suy ra 1 = 2. (iii) Giả sử 1 ∩ 2 ≠ φ. Khi đó, tồn tại x ∈ X sao cho x ∈ 1 và x ∈ 2. Do đó x1 ~ x và x2 ~ x. Từ đó, ta có x1 ~ x và x ~ x2. Do đó x1 ~ x2. Theo (ii), từ đó suy ra 1 = 2.
Từ định lí trên suy ra định lí sau gọi là nguyên lí đồng nhất các phần tử tương đương. c) Định lí: Quan hệ tương đương ~ trên tập hợp X ≠ φ chia X thành các tập con khác đôi một rời nhau (các tập hợp con đó là các lớp tương đương của quan hệ ~) sao cho hai phần tử x, y của tập hợp X thuộc cùng một tập con khi và chỉ khi chúng tương đương với nhau. Tập thương X / ~ là một phép phân hoạch tập hợp X. (Xem bài tập 14 trong Hoạt động 2, Chủ đề 1). d) Ví dụ về tập thương. Ta trở lại bốn ví dụ đã nêu. • Trong Ví dụ 1, quan hệ tương đương ~ trên ⏐R chia tập hợp ⏐R thành các lớp tương đương. Dễ dàng nhận thấy rằng tất cả các số nguyên thuộc cùng một lớp tương đương và ngoài các số nguyên không có một số thực nào thuộc lớp tương đương đó. • Trong Ví dụ 2, quan hệ tương đương ~ trên X chia tập hợp các Vectơ buộc trong mặt phẳng ⏐R2 thành các lớp tương đương. Mỗi lớp tương đương được gọi là một véctơ tự do: Đó là tập hợp tất cả các vectơ buộc tương đương với một vectơ buộc cho trước. (Trong sách giáo khoa toán ở trường phổ thông hai vectơ tương đương được gọi là bằng nhau; đó là hai vectơ cùng hướng có độ dài bằng nhau, xem hình 25). Hình 25 • Trong ví dụ 3, quan hệ tương đương ~ trên D chia tập hợp các đường thẳng trong mặt phẳng ⏐R2 thành các lớp tương đương. Mỗi lớp tương đương được gọi là một phương. Đó là tập hợp tất cả các đường thẳng trong mặt phẳng ⏐R2 song song hoặc trùng với một đường thẳng cho trước trong mặt phẳng này
Hình 26 • Trong Ví dụ 4, quan hệ “có cùng số dư với trong phép chia cho 3” chia tập hợp N thành ba lớp tương đương: . Mọi số tự nhiên chia hết cho 3 đều thuộc lớp . Mọi số tự nhiên có số dư là 1 trong phép chia cho 3 đều thuộc lớp. Mọi số tự nhiên có số dư là 2 trong phép chia cho 3 đều thuộc lớp . Ta lấy thêm một ví dụ. Hình 27 Ví dụ 4.5 : Xét quan hệ hai ngôi “cùng màu với” trên tập hợp L0 các mảnh lôgic Điênétxơ. Dễ dàng thấy rằng đó là một quan hệ tương đương trên L0. Quan hệ này chia L0 thành ba lớp tương đương: Đ, X, N. Đ là tập hợp các mảnh màu đỏ, X là tập hợp các mảnh màu xanh và N là tập hợp các mảnh màu nâu. Mỗi lớp tương đương có 16 mảnh với hình dạng, độ lớn và độ dày khác nhau Hình 28 4.3. ứng dụng của nguyên lí đồng nhất các phần tử tương đương a) Xây dựng tập hợp các số nguyên Ta nhắc lại rằng kí hiệu N chỉ tập hợp các số tự nhiên và N2 = N x N chỉ tập hợp tất cả các cặp thứ tự (m, n), trong đó m và n là những số tự nhiên.
Gọi ~ là quan hệ hai ngôi trên N x N xác định bởi (m1, n1) ~ (m2, n2) khi và chỉ khi m1 + n2 = m2 + n1. Quan hệ ~ là một quan hệ tương đương trên N x N. Thật vậy, vì với mọi (m, n) ∈ N x N, ta có m + n = m + n, nên (m, n) ~ (m, n). Do đó quan hệ ~ là phản xạ. Dễ ràng thấy rằng quan hệ ~ là đối xứng. Cuối cùng nếu (m1, n1) ~ (m2, n2) và (m2, n2) ~ (m3, n3) thì m1 + n2 = m2 + n1 và m2 + n3 = m3 + n2. Do đó m1 + n2 + m2 + n3 = m2 + n1 + m3 + n2 ⇔ m1 + n3 = m3 + n1, tức là (m 1, n1) tương đương (m3, n3). Vậy quan hệ ~ là bắc cầu. Quan hệ tương đương ~ trên N x N chia tập hợp N x N thành các lớp tương đương đôi một rời nhau. Các lớp tương đương của quan hệ ~ trên tập hợp N x N được gọi là các số nguyên. Dễ dàng thấy rằng: • (0, 0) ~ (1, 1) ~ (2, 2) , (3, 3), Lớp tương đương (0, 0)~ có đại diện là phần tử (0, 0) gọi là số nguyên 0. • Các lớp tương đương (m, n)~ có đại diện là phần tử (m, n) trong đó m > n và m = n + k, k = 1, 2, xác định các số nguyên dương k = 1, 2, • Các lớp tương đương (m, n)~ có đại diện là phần tử (m, n) trong đó m < n và n = m + k, k = 1, 2, xác định các số nguyên âm −k = −1, −2, −3, Phép cộng và phép nhân trong tập hợp các số nguyên, tức là trong tập thương N x N / ~ được định nghĩa như sau: ~ ~ ~ (m1, n1) + (m2, n2) = (m1 + m2, n1 + n2) . (m1,n1) . (m2,n2) = (m1m2 + n1n2, m1n2 + n1m2) Người ta chứng minh được rằng các phép toán được xác định như trên không phụ thuộc vào việc chọn các phần tử đại diện của các lớp tương đương, các phép toán đó thoả mãn các quy tắc về số học đã biết trong tập hợp các số tự nhiên N; hơn nữa, trong tập hợp các số nguyên, có thể thực hiện phép trừ đối với hai số bất kì. b) Xây dựng tập hợp các số hữu tỉ Ta kí hiệu Z là tập hợp các số nguyên, Z* là tập hợp các số nguyên khác 0. Tích Đêcác Z x Z* là tập hợp các cặp thứ tự (m, n), trong đó m là một số nguyên và n là một số nguyên khác 0. Gọi ~ là quan hệ hai ngôi trên tập hợp Z x Z* xác định như sau: (m1, n1) ~ (m2, n2) khi và chỉ khi m1n2 = m2n1. (Chẳng hạn, ta có (2, 3) ~ (4, 6), (3, 5) ~ (18, 30),
(-3, 7) ~ (-12, 28), (-3, 7) ~ (6, − 14) Ta chứng minh ~ là một quan hệ tương đương trên Z x Z*. Thật vậy, dễ thấy quan hệ ~ là phản xạ và đối xứng. Nếu (m1, n1) ~ (m2, n2) và (m2, n2) ~ (m3, n3) thì m1n2 = m2n1 và m2n3 = m3n2 (1) Do đó: m1n2m2n3 = m2n1m3n2 ⇔ m1m2n3 = m2n1m3, vì n2 ≠ 0. Từ đó suy ra rằng nếu m2 khỏc 0 thì m1n3 = m3n1; do đó (m1, n1) ~ (m3, n3). Nếu m2 = 0 thì từ hai đẳng thức trong (1) suy ra m1 = 0 và m3 = 0. Do đó ta cũng có m1n3 = m3n1, tức là (m1, n1) ~ (m3, n3). Vậy quan hệ ~ là bắc cầu. Quan hệ tương đương ~ trên Z x Z* chia tập hợp Z x Z* thành các lớp tương đương đôi một rời nhau. Các lớp tương đương của quan hệ tương đương ~ trên Z x Z* gọi là các số hữu tỉ. Lớp tương đương (m, n)~ có đại diện là phần tử (m, n) xác định số hữu tỉ, kí hiệm là . Hai cặp thứ tự (m1, n1) và (m2, n2) thuộc cùng một lớp tương đương, tức là m1n2 = m2n1, xác định cùng một số hữu tỉ. Như vậy, hai số hữu tỉ là bằng nhau. Phép cộng và phép nhân trong tậphợp các số hữu tỉ, tức là trong tập thương Z x Z*/~ được định nghĩa như sau: ~ ~ ~ (m1, n1) + (m2, n2) = (m1n2 + n1m2, n1n2) , ~ ~ ~ (m1, n1) . (m2, n2) = (m1m2, n1n2) Người ta chứng minh được rằng hai phép toán được xác định như trên không phụ thuộc vào việc chọn các phần tử đại diện của các lớp tương đương, các phép toán đó thoả mãn các quy tắc về số học trong tập hợp các số nguyên; hơn nữa, trong tập hợp các số hữu tỉ phép chia cho một số khác không bao giờ cũng thực hiện được. Hoạt động 4.1. Tìm hiểu về quan hệ tương đương Nhiệm vụ: Nhi•m v• 1: Đọc các thông tin cơ bản để có được các kiến thức về: − Định nghĩa quan hệ tương đương. − Định nghĩa lớp tương đương, tập thương.
− Một số ví dụ về quan hệ tương đương, tập thương. Nhiệm vụ 2: Trình bày và thấy được tầm quan trọng của nguyên lí đồng nhất các phần tử tương đương: − Quan hệ tương đương trên một tập hợp chia tập hợp đó thành các lớp tương đương đội một rời nhau. − Biết vận dụng một cách sinh động nguyên lí này trong các ví dụ và ứng dụng khác nhau. Đánh giá hoạt động 4.1 1. Gọi ~1, ~2 và ~3, theo thứ tự, là quan hệ hai ngôi “có cùng hình dạng với”, “có cùng độ lớn với” và “có cùng độ dày với” trên tập hợp L0 các mảnh lôgic. a) Chứng minh rằng chúng là những quan hệ tương đương trên L0. b) Mỗi quan hệ đó chia tập hợp L0 thành mấy lớp tương đương? 2. Gọi R là quan hệ hai ngôi “có cùng số dư với trong phép chia cho 4” trên tập hợp N. a) Chứng minh rằng R là một quan hệ tương đương trên tập hợp N. b) Quan hệ tương đương R trên N chia tập hợp N thành mấy lớp tương đương? Hãy vẽ sơ đồ Ven biểu diễn các lớp tương đương của quan hệ R. 3. Cho tập hợp X = {1, 2, 3, 4, 5} và P = P(X) là tập hợp các tập con của X. Gọi ~ là quan hệ hai ngôi trên P xác định bởi: A ~ B khi và chỉ khi N (A) = N (B) Trong đó N (C) là số phần tử của tập hợp C ⊂ X. a) Chứng minh rằng ~ là một quan hệ tương đương trên P. b) Tìm lớp tương đương của quan hệ ~ trên P, có đại diện là phần tử {1, 3} của P. 4. Gọi X = ⏐R2 là tập hợp các điểm của mặt phẳng và ~ là quan hệ hai ngôi trên tập hợp ⏐R2 xác định bởi: (x , y ) ~ (x , y ) khi và chỉ khi 1 1 2 2 . a) Chứng minh rằng ~ là một quan hệ tương đương trên ⏐R2. b) Tìm tập thương ⏐R2/ ~. 5. Cho một tập hợp X ≠ φ. Chứng minh rằng quan hệ đồng nhất R trên X là một quan hệ tương đương trên X và tìm tập thương X/R. 6. Gọi D là tập hợp các đường thẳng trong một mặt phẳng và a là một đường thẳng cho trước trong mặt phẳng đó. Gọi R là quan hệ hai ngôi trên
D xác định như sau: Với mọi x, y ∈ D, x R y khi và chỉ khi x ∩ a ≠ φ và y ∩ a ≠ φ. R có phải là một quan hệ tương đương trên D hay không? 7. Cho các tập con của ⏐R2: A = {x ∈⏐R : 1 ≤ x 0. a) Chứng minh rằng R là một quan hệ tương đương trên ⊄*. b) Minh hoạ hình học các lớp tương đương của quan hệ R. Tiểu chủ đề 1.5. Quan hệ thứ tự Thông tin cơ bản Formatted: Heading03, Space Before: 0 pt 5.1. Định nghĩa: Formatted: Heading04 Quan hệ hai ngôi R trên tập hợp X được gọi là quan hệ thứ tự nếu nó là phản xạ, bắc cầu và phản đối xứng, tức là nếu R thoả mãn các điều kiện sau: a) Với mọi x ∈ X, x R x, b) Với mọi x, y, z ∈ X, (x R y và y R z) ⇒ x R z, c) Với mọi x, y ∈ X, (x R y và y R x) ⇒ x = y. Người ta thường kí hiệu quan hệ thứ tự là “≤”. Như vậy x R y được viết là x ≤ y, đọc là x nhỏ hơn hoặc bằng y, hay y lớn hơn hoặc bằng x.
Nếu ≤ là một quan hệ thứ tự trên tập hợp X thì cặp (X, ≤) gọi là một tập hợp sắp thứ tự. Người ta cũng gọi X là một tập hợp sắp thứ tự khi chỉ nói tới một quan hệ thứ tự nào đó trên X. Ví dụ 5.1: Quan hệ hai ngôi “chia hết” trên tập hợp N* là một quan hệ thứ tự trên N* vì: Với mọi số nguyên dương n, ta có n / n (n chia hết n), Với mọi m, n, k N*, (m / n và n / k) m / k, Với mọi m, n N*, (m / n và n / m) m = n, Ví dụ 5.2: Cho tập hợp X ≠ φ và tập hợp Q những tập con của X (Q ⊂ P(X)), Q ≠ φ. Quan hệ hai ngôi “chứa trong” trên Q là một quan hệ thứ tự vì: Với mọi A ∈ Q, A ⊂ A, Với mọi A, B, C ∈ Q, (A ⊂ B và B ⊂ C) ⇒ A ⊂ C, Với mọi A, B ∈ Q, (A ⊂ B và B ⊂ A) ⇒ A = B. Ví dụ 5.3: Nếu X là một tập con khác φ của tập hợp các số thực thì quan hệ hai ngôi “≤” trên X là một quan hệ thứ tự vì với mọi x, y, z ∈ X, ta có: x ≤ x, (x ≤ y và y ≤ z) ⇒ x ≤ z, (x ≤ y và y ≤ x) ⇒ x = y. Để phân biệt quan hệ thứ tự ≤ trên một tập hợp X tuỳ ý với quan hệ ≤ trên R, ta gọi quan hệ sau là quan hệ thứ tự thông thường trên R. Ví dụ 5.4: Xét các quan hệ hai ngôi trên các tập hợp X, Y, Z được biểu diễn bởi các lược đồ hình tên trong hình 29 Hình 29
Trong lược đồ hình tên 29 a), quan hệ hai ngôi R trên tập hợp X = {a, b} được xác định bởi: a R a, b R b, a R b. Dễ dàng thấy rằng R là một quan hệ thứ tự trên X. • Quan hệ hai ngôi R trên tập hợp Y = {a, b, c} được biểu diễn bởi lược đồ hình tên 29 b) không phải là một quan hệ thứ tự trên tập hợp Y vì nó không phải là quan hệ phản đối xứng : a R b, b R a và a ≠ b. Quan hệ hai ngôi R trên tập hợp Z = {a, b, c, d} được biểu diễn bởi lược đồ hình tên 29 c) không phải là một quan hệ thứ tự trên Z vì nó không phải là quan hệ bắc cầu: a R b và b R c nhưng không có a R c. 5.2. Quan hệ thứ tự nghiêm ngặt Formatted: Heading04 a) Định nghĩa: Quan hệ hai ngôi ℜ trên tập hợp X gọi là quan hệ thứ tự nghiêm ngặt nếu nó là đối phản xạ và bắc cầu, tức là nếu R thoả mãn các điều kiện sau: a) Với mọi x ∈ X, không có x R x, tức là (x, x) ∉ R, b) Với mọi x, y, z X, (x R y và y R z) x R z. Quan hệ thứ tự nghiêm ngặt R thường được kí hiệu là “ ) trên tập hợp R là một quan hệ thứ tự nghiêm ngặt. Quan hệ hai ngôi “đắt hơn” trên một tập hợp các mặt hàng cũng là một quan hệ thứ tự nghiêm ngặt. Chú ý rằng quan hệ thứ tự nghiêm ngặt không phải là một quan hệ thứ tự. Mối liên hệ giữa quan hệ thứ tự và quan hệ thứ tự nghiêm ngặt được cho trong hai định lí sau. b) Định lí Nếu là một quan hệ thứ tự trên tập hợp X thì quan hệ hai ngôi < trên X xác định bởi x < y khi và chỉ khi x ≤ y và x ≠ y, là một quan hệ thứ tự nghiêm ngặt trên X. Chứng minh : Từ định nghĩa của quan hệ < suy ra rằng < không phải là một quan hệ đối phản xạ. Ta chứng minh < là bắc cầu. Thật vậy, giả sử x < y và y < z. Khi đó, x ≤ y, y ≤ z, x ≤ y và y ≠ z. Vì là một quan hệ bắc cầu nên từ đó suy ra x ≤ z. Nếu x = z thì ta có z ≤ y và y ≤ z. Do đó y = z (suy ra từ tính phản đối xứng của quan hệ ≤); điều này mâu thuẫn với y ≤ z. Vậy x ≤ z. Như vậy, ta có x ≤ z và x ≠ z, tức là x < z.
Đảo lại, ta có: c) Định lí Nếu < là một quan hệ thứ tự nghiêm ngặt trên tập hợp X thì quan hệ hai ngôi ≤ trên X xác định bởi: x ≤ y khi và chỉ khi x < y hoặc x = y, là một quan hệ thứ tự trên X. Chứng minh : Từ định nghĩa của quan hệ ≤ suy ra rằng ≤ là một quan hệ phản xạ. Ta chứng minh ≤ là quan hệ bắc cầu. Thật vậy, giả sử x ≤ y và y ≤ z. Khi đó, x < y hoặc x = y và y < z hoặc y = z. Nếu x < y và y < z thì x < z; do đó x z. Nếu x < y và y = z thì x < z; do đó x ≤ z. Nếu x = y và y < z thì x < z; do đó x ≤ z. Cuối cùng nếu x = y và y = z thì x = z, do đó x ≤ z. ≤ là quan hệ phản đối xứng. Thật vậy, giả sử x ≤ y và y ≤ x. Khi đó, x < y hoặc x = y và y < x hoặc y = x. Hai điều kiện x < y và y < x loại trừ nhau vì nếu xảy ra đồng thời hai điều kiện này thì ta có x < x điều này không thể vì < là quan hệ đối phản xạ. Hai điều kiện x < y và y = x loại trừ lẫn nhau. Hai điều kiện x = y và y < x cũng loại trừ nhau. Do đó chỉ có thể xảy ra một trường hợp x = y và y = x. Như vậy các điều kiện x ≤ y và y ≤ x kéo theo x = y. Giả sử là một quan hệ thứ tự trên tập hợp X và x, y là hai phần tử của X. Ta nói rằng x đứng trước y nếu x ≤ y và x ≠ y. Khi đó, ta viết x < y (< là quan hệ thứ tự nghiêm ngặt trên X nói trong Định lí b). 5.3. Quan hệ thứ tự toàn phần và quan hệ thứ tự bộ phận. Formatted: Heading04 Quan hệ thứ tự ≤ trên tập hợp X gọi là toàn phần nếu với hai phần tử bất kì x, y của X, ta có x ≤ y hoặc y ≤ x. Trong lược đồ hình tên của quan hệ thứ tự toàn phần trên tập hợp X, các phần tử của X đôi một được nối với nhau bởi ít nhất một mũi tên. Nếu tồn tại ít nhất hai phần tử x, y của X sao cho cả hai điều kiện x ≤ y và y ≤ x đều không xảy ra thì ≤ gọi là quan hệ thứ tự bộ phận. Ví dụ 5.6: Quan hệ thứ tự “≤” (theo nghĩa thông thường) trên tập hợp R là toàn phần. Quan hệ “chia hết” trên tập hợp N* là quan hệ thứ tự bộ phận vì chẳng hạn số nguyên 3 và 7 là không so sánh được”. Ta không có 3 / 7, cũng không có 7 / 3. Quan hệ thứ tự nghiêm ngặt < trên tập hợp X được gọi là toàn phần nếu với hai phần tử khác nhau bất kì x, y của X, ta có x < y hoặc y < x.
Nếu tồn tại ít nhất hai phần tử khác nhau x, y của X sao cho cả hai điều kiện x < y và y < x đều không xảy ra thì quan hệ < được gọi là bộ phận. Ví dụ 5.7 : Xét các quan hệ thứ tự và quan hệ thứ tự nghiêm ngặt biểu diễn bởi các lược đồ hình tên trong hình 29 dưới đây. Hình 30 Quan hệ thứ tự trên tập hợp A được biểu diễn bởi lược đồ hình tên 30 a) là toàn phần. Quan hệ thứ tự trên tập hợp B trong Hình 30 b) là bộ phận. Quan hệ thứ tự nghiêm ngặt trên tập hợp C trong Hình 30 c) là toàn phần. Lược đồ hình tên trong Hình 30 c) biểu diễn quan hệ thứ tự nghiêm ngặt bộ phận trên tập hợp D. 5.4. Các phần tử tối đại, tối tiểu Formatted: Heading04 a) Giả sử (X, ≤) là một tập hợp sắp thứ tự. Phần tử x0 ∈ X được gọi là tối đại nếu nó không đứng trước bất kì một phần tử nào của X, tức là không tồn tại x ∈ X sao cho x0 < x. Nói một cách khác, x0 ∈ X là phần tử tối đại nếu không tồn tại x ∈ X sao cho x0 ∈ x và x0 ≠ x. Điều kiện này tương đương với điều kiện sau: Với mọi x ∈ X, nếu x0 ∈ x thì x = x0. Ví dụ 5.8: Cho tập hợp X ≠ φ. Gọi P = P(X) là tập tất cả các tập con của X. Ta biết rằng quan hệ hai ngôi “⊂” trên P là một quan hệ thứ tự. Do đó (P, ⊂) là một tập hợp sắp thứ tự. Ta chứng minh X là phần tử tối đại của P.
Thật vậy, giả sử A P và X A. Khi đó, ta có A X và X A. Do đó A = X. Vậy X là phần tử tối đại. Mọi tập hợp A ∈ P khác X đều không phải là phần tử tối đại vì A ⊂ X. Như vậy X là phần tử tối đại duy nhất. Ví dụ 5.9 : Gọi X là tập hợp các số nguyên lớn hơn 1 và là quan hệ trên X xác định như sau: Với mọi m, n ∈ X, m ≤ n khi và chỉ khi m chia hết cho n. Dễ dàng thấy rằng là một quan hệ thứ tự trên X. Ta chứng minh rằng mỗi số nguyên tố đều là một phần tử tối đại. Thật vậy, nếu p là một số nguyên tố và n ∈ X, p ≤ n thì n = p. Do đó p là một phần tử tối đại. Như vậy tập hợp sắp thứ tự X có vô số phần tử tối đại. Ví dụ 5.10 : Kí hiệu ≤ là quan hệ “chia hết” trên tập hợp N*: Với m, n nguyên dương, m ≤ n khi và chỉ khi m : n. Tập hợp sắp thứ tự N* không có phần tử tối đại vì với mọi n ≤ N*, ta có n : 2n và 2n ≠ n, tức là n ≤ 2n và 2n ≠ n. Các ví dụ trên cho thấy một tập hợp sắp thứ tự có thể có một hoặc nhiều phần tử tối đại, cũng có thể không có phần tử tối đại nào. Trong lược đồ hình tên biểu diễn quan hệ thứ tự trên một tập hợp, phần tử tối đại được biểu diễn bởi một điểm mà từ đó không có một mũi tên nào đi đến các điểm khác. Trong hình 31, c và d là hai phần tử tối đại của tập hợp sắp thứ tự X. Hình 31 b) Giả sử (X, ≤) là một tập hợp sắp thứ tự. Phần tử x0 ∈ X gọi là tối tiểu nếu không có một phần tử nào của X đứng trước nó, tức là không tồn tại x ∈ X, x ≠ x0 sao cho x ≤ x0.
Trong lược đồ hình tên biểu diễn quan hệ thứ tự trên một tập hợp, phần tử tối tiểu được biểu diễn bởi một điểm mà không có bất kì một mũi tên nào đi từ các điểm khác đến điểm đó. Trong Hình 30, a và d và hai điểm tối tiểu của tập hợp sắp thứ tự X. Chú ý rằng d cũng là điểm tối dại của X. Ví dụ 5.11 : Giả sử P là tập hợp tất cả các tập con của tập hợp X ≠ φ. Khi đó, tập hợp sắp thứ tự (P, ⊂) có một phần tử tối tiểu duy nhất, đó là tập hợp φ. Thật vậy, với mọi A ∈ P mà A ⊂ φ, ta có A = φ. Do đó là phần tử tối tiểu. Ngoài ra, với mọi A ∈ P mà A ≠ φ, ta có φ ⊂ A. Do đó A không phải là phần tử tối tiểu. Ví dụ 5.12 : Giả sử X là tập hợp các số nguyên lớn hơn 1. Ta biét rằng (X, :) là một tập hợp sắp thứ tự (kí hiệu : chỉ quan hệ “chia hết” trên X). Nếu p là một số nguyên tố thì với mọi n ∈ X, mà n : p, ta có n = p. Do đó p là một phần tử tối tiểu của tập hợp sắp thứ tự X. Như vậy, X có vô số phần tử tối tiểu, đó là tất cả các số nguyên tố. Ví dụ 5.13 : Gọi X là tập hợp các số nguyên lớn hơn 1 và ≤ là quan hệ “chia hết cho” trên X (Xem ví dụ 9). Tập hợp sắp thứ tự (X, ≤) không có phần tử tối tiểu vì với mọi n ∈ X, ta có 2n chia hết cho n và 2n ≠ n, tức là 2n ≤ n và 2n ≠ n. Các ví dụ trên cho thấy một tập hợp sắp thứ tự có thể có một hoặc nhiều phần tử tối tiểu và cũng có thể không có phần tử tối tiểu nào. 5.5. Các phần tử lớn nhất, nhỏ nhất Formatted: Heading04 a) Giả sử (X, ≤) là một tập hợp sắp thứ tự. Phần tử x0 ∈ X gọi là lớn nhất nếu: x ∈ x0 với mọi x ∈ X. b) Định lí: Tập hợp sắp thứ tự (X, ≤) có nhiều nhất là một phần tử lớn nhất. Phần tử lớn nhất là tối đại. Chứng minh Giả sử x0 và x1 là những phần tử lớn nhất trong tập hợp sắp thứ tự X. Khi đó: x ≤ x0 với mọi x ∈ X và x ≤ x1 với mọi x ∈ X. Do đó x1 ≤ x0 và x0 ≤ x1. Vì quan hệ ≤ là phản đối xứng nên từ đó suy ra x1 = x0. Vậy phần tử lớn nhất, nếu có, là duy nhất.
Giả sử x0 là phần tử lớn nhất trong (X, ≤). Khi đó, với mọi x ∈ X, nếu x0 ≤ x thì vì ta cũng có x ≤ x0 (suy ra từ định nghĩa của x0) nên x = x0. Vậy x0 là phần tử tối đại Trong lược đồ hình tên biểu diễn quan hệ thứ tự trên một tập hợp, phần tử lớn nhất được biểu diễn bởi một điểm mà tại mỗi điểm của tập hợp đều có một mũi tên đi từ đó đến điểm đã nêu. Hình 32 Trong Hình 32, d là phần lớn nhất của tập hợp sắp thứ tự A. Ví dụ 5.14 : Trong tập hợp sắp thứ tự (P, ⊂) (P = P (X) là tập hợp tất cả các tập con của hợp X ≠ φ), tập hợp X là phần tử lớn nhất. • Tập hợp sắp thứ tự (N*, :) không có phần tử tối đại. Do đó, theo Định lí b), tập hợp N* không có phần tử lớn nhất. • Xét tập hợp sắp thứ tự (X, ≤), trong đó X là tập hợp các số nguyên lớn hơn 1 và ≤ là quan hệ “chia hết cho” trên X. Trong tập hợp này không có phần tử lớn nhất vì với mỗi n ∈ X, số n + 1 không chia hết cho n. Để ý rằng trong (X, ≤) có vô số phần tử tối đại (xem Ví dụ 9). c) Giả sử (X, ≤) là một tập hợp sắp thứ tự. Phần tử x0 ∈ X gọi là nhỏ nhất nếu x0 ≤ x với mọi x ∈ X. Tương tự như trong Định lí b), dễ dàng chứng minh được rằng. d) Tập hợp sắp thứ tự (X, ≤) có nhiều nhất là một phần tử nhỏ nhất. Phần tử nhỏ nhất là tối tiểu. Trong lược đồ hình tên biểu diễn quan hệ thứ tự trên một tập hợp, phần tử nhỏ nhất được biểu diễn bởi một điểm mà từ đó có các mũi tên đi đến mọi điểm Hình 33 khác của tập hợp.
Hình 33 Hình 33, a là phần tử nhỏ nhất của tập hợp sắp thứ tự A. Ví dụ 5.15: • Trong tập hợp sắp thứ tự (P, ⊂), trong đó P là tập hợp tất cả các tập con của tập hợp X ≠ φ, φ là phần tử nhỏ nhất duy nhất. • Xét tập hợp sắp thứ tự (X, ≤), trong đó x là tập hợp các số nguyên lớn hơn 1 và ≤ là quan hệ “chia hết cho” trên X. Trong Ví dụ 13, ta biết rằng trong X không có phần tử tối tiểu. Do đó, theo Định lí d), tập hợp sắp thứ tự X không có phần tử nhỏ nhất. • Tập hợp sắp thứ tự (X, :), trong đó X là tập hợp các số nguyên lớn hơn 1 và : là quan hệ “chia hết” trên X, không có phần tử nhỏ nhất vì với mọi n ∈ X, n không chia hết n + 1. Để ý rằng tập hợp sắp thứ tự này có vô số phần tử tối tiểu (xem Ví dụ 12). 5.6. Các tập con của một tập sắp thứ tự. Bổ đề Doóc−nơ (Zorn). Formatted: Heading04 a) Giả sử (X, ≤) là một tập hợp sắp thứ tự và A là một tập con của X. Gọi A là quan hệ hai ngôi xác định trên tập hợp A như sau: Với mọi x, y ∈ A, x ≤A y khi và chỉ khi x ≤ y. Dễ dàng thấy rằng ≤A là một quan hệ thứ tự trên A. Tập hợp sắp thứ tự (A, ≤A) gọi là tập con sắp thứ tự của tập hợp sắp thứ tự (X, ≤). Thay cho (A, ≤A) người ta viết (A, ≤). Khi nói A là một tập con của tập hợp sắp thứ tự (X, ≤) mà không giải thích gì thêm thì ta hiểu A là tập hợp sắp thứ tự (A, ≤). b) Giả sử (X, ≤) là một tập hợp sắp thứ tự. Tập con A của X gọi là dây xích nếu với mọi x, y ∈ X, x ≤ y hoặc y ≤ x. Nói một cách khác, A là một dãy sích nếu quan hệ thứ tự ≤A trên A là toàn phần. Ví dụ 5.16 :
• Tập con A = {5, 15, 60} là một dây xích trong tập hợp sắp thứ tự (N*, :). • Tập con B = {3, 6, 12, 18} không phải là một dõy xích trong tập hợp sắp thứ tự (N*, ≤), trong đó ≤ là quan hệ “chia hết cho” trên N vì 18 không chia hết cho 12. c) Phần tử chặn trên, chặn dưới Giả sử (X, ≤) là một tập hợp sắp thứ tự và A là một tập hợp con của X. (i) x0 ∈ X gọi là phần tử chặn trên của A nếu x ≤ x0 với mọi x ∈ A. (ii) x0 ∈ X gọi là phần tử chặn dưới của A nếu x0 ≤ x với mọi x ∈ A. Ví dụ 5.17 : Xét tập hợp sắp thứ tự (N*, :) và tập con A = {10, 15, 20}. Dễ dàng thấy rằng các số 60, 120, 180, là những phần tử chặn trên của A và các số 1, 5 là các phần tử chặn dưới của A. Ví dụ 5.18 : Xét hai tập con Z (là tập các số nguyên) và X = {x ∈ R : −1 ≤ x < 3} của tập hợp sắp thứ tự (R, ≤) (≤ là quan hệ thứ tự thông thường trên R). Dễ dàng thấy rằng trong R không có phần tử chặn trên cũng không có phần tử chặn dưới của Z, mỗi số thực lớn hơn hoặc bằng 3 đều là một phần tử chặn trên của A và mỗi số thực nhỏ hơn hoặc bằng −1 là một phần tử chặn dưới của A. Như vậy, một tập con của một tập hợp sắp thứ tự có thể có một hoặc nhiều, cũng có thể không có phần tử chặn trên, chặn dưới. Bổ đề mà ta thừa nhận sau đây là một định lí quan trọng được áp dụng ð? chứng minh nhiều định lí. d) Bổ đề Zooc−nơ. Giả sử (X, ≤) là một tập hợp sắp thứ tự. Nếu trong X mỗi dây xích đều có một phần tử chặn trên thì trong X có phần tử tối đại. Hoạt động. Tìm hiểu về quan hệ thứ tự Formatted: Heading02 Nhiệm vụ: Deleted: Formatted: Heading03, Space Sinh viên đọc thông tin cơ bản để thực hiện các nhiệm vụ sau Before: 0 pt Nhiệm vụ 1 Formatted: Heading04 Trình bày các khái niệm quan hệ thứ tự và quan hệ thứ tự nghiêm ngặt, quan hệ thứ tự toàn phần và bộ phận.
Lí giải một số quan hệ thứ tự thường gặp như quan hệ “chia hết”, quan hệ “chia hết cho” trên tập hợp N*, quan hệ “bao hàm” trên một tập hợp những tập hợp ,quan hệ (nhỏ hơn hoặc bằng theo nghĩa thông thường) trên tập hợp R. Nhận biết một quan hệ cho trước trên một tập hợp có phải là một quan hệ thứ tự hay không, biết cho các ví dụ về quan hệ thứ tự. − Biểu diễn một số quan hệ thứ tự và quan hệ thứ tự nghiêm ngặt bằng lược đồ hình tên. Nhiệm vụ 2 Formatted: Heading04 Trình bày các khái niệm phần tử tối đại, tối tiểu, phần tử lớn nhất, nhỏ nhất, phần tử chặn trên, chặn dưới, dây xích trong một tập hợp sắp thứ tự. Tìm các phần tử đó nêu trong một tập hợp sắp thứ tự cho trước. − Biểu diễn được các phần tử này trong một số quan hệ thứ tự bằng lược đồ hình tên. Đánh giá hoạt động 5.1 Formatted: Heading02 1. Cho tập hợp X = {1, 3, 9, 18, 36}. Gọi ≤ là quan hệ “chia hết” trên X. a) Chứng minh ≤ là một quan hệ thứ tự trên X. b) Quan hệ thứ tự ≤ trên X có phải là toàn phần không? 2. Cho tập hợp A = {3, 6, 12, 36, 48}. Quan hệ “chia hết cho” trên A có phải là một quan hệ thứ tự không? Nếu có, nó có phải là một quan hệ toàn phần không? 3. Cho R là quan hệ hai ngôi trên tập hợp C các số phức xác định như sau: Với mọi a + bi, c + di ∈ C, (a + bi) ℜ (c + di) khi và chỉ khi a ≤ c và b ≤ d. a) Chứng minh rằng ℜ là một quan hệ thứ tự trên C. b) R có phải là toàn phần không? 4. Cho tập hợp X = {1, 2, 3, 4, 5, 6, 7} và quan hệ hai ngôi R xác định trên X như sau: Với mọi x, y ∈ X, x R y khi và chỉ khi x ≤ y và 2 : (x − y). a) Chứng minh rằng R là một quan hệ thứ tự trên X. b) R có phải là toàn phần không? c) Biểu diễn quan hệ R bằng lược đồ hình tên. 5. Giả sử X là tập hợp tất cả các dãy số thực và R là quan hệ hai ngôi trên X xác định như sau: Với mọi dãy số thực (xn) và (yn), (xn) R (yn) khi và chỉ khi tồn tại một số nguyên dương m sao cho xn ≤ yn với mọi n > m. a) Chứng minh quan hệ R là phản xạ và bắc cầu. b) R có phải là quan hệ thứ tự hay không?
6. Có thể xác định được bao nhiêu quan hệ thứ tự. Trên một tập hợp có hai phần tử? 7. Cho tập hợp sắp thứ tự (X, ), trong đó X = {2, 5, 8, 10, 20, 40} và ≤ là quan hệ “chia hết” trên X. a) Tìm các phần tử tối đại và tối tiểu của X. b) Tìm phần tử lớn nhất và nhỏ nhất (nếu có) của X. 8. Cho tập hợp sắp thứ tự (X, ≤) với X = {35, 36, 37, 38, 39} và là quan hệ “chia hết cho” trên X. Tìm giá trị lớn nhất và giá trị nhỏ nhất của X. 9. Các lược đồ hình tên trong Hình 34 dưới đây biểu diễn các quan hệ hai ngôi RA, RB, RC, theo thứ tự, trên các tập hợp A, B, C. Quan hệ nào trong ba quan hệ đó là quan hệ thứ tự? Hình 34 10. Hai lược đồ hình tên trong Hình 35 dưới đây biểu diễn quan hệ hai ngôi R và ϕ, theo thứ tự, trên tập hợp X và Y. a) Chứng minh rằng R là quan hệ thứ tự trên X và Y là quan hệ thứ tự trên Y. b) Tìm các phần tử tối đại, tối tiểu và phần tử lớn nhất, nhỏ nhất của mỗi tập hợp X và Y.
Hình 35 11. Cho ví dụ về một tập hợp sắp thứ tự có m phần tử vừa là tối đại vừa là tối tiểu. Hướng dẫn. Xem lược đồ trong Hình 35a) 12. Cho ví dụ về một tập hợp sắp thứ tự có a) m + 1 phần tử, trong đó có k phần tối đại và một phần tử tối tiểu, b) m + 1 phần tử, trong đó có k phần tử tối tiểu và một phần tử tối đại. 13. Trong mặt phẳng toạ độ Oxy cho bốn hình tròn D1, D2, D3, D4 : D1 và D2 đều có tâm là điểm gốc (0, 0) và có bán kính theo thứ tự, là 1 và 2, D3 có tâm là điểm (2, 0) và bán kính là 1, D4 có tâm là điểm (−2, 0) và bán kính là 4. Gọi X là tập hợp 4 hình tròn đã cho : X = {D1, D2, D3, D4} và ⊂ là quan hệ “chứa trong” trên X. a) Hãy biểu diễn quan hệ ⊂ bằng lược đồ hình tên. b) Tìm các phần tử tối đại, tối tiểu và phần tử lớn nhất, nhỏ nhất (nếu có) của tập hợp sắp thứ tự X. 14. Cho hai tập con A = {9, 18, 36, 72, 216} và B = {7, 14, 28, 56, 84} của tập hợp N*. A và B có phải là dây xích trong tập hợp sắp thứ tự N* với quan hệ “chia hết” hay không? 15. Tìm các phần tử chặn trên và chặn dưới (nếu có) của mỗi tập con A = {7, 11} và B = {2, 4, 6, , 2n, } trong tập hợp sắp thứ tự {N*, ≤}, trong đó ≤ là quan hệ “chia hết” trên tập hợp N*. 16. Tìm các phần tử chặn trên và chặn dưới (nếu có) của mỗi tập con A = {6, 9, 15} và B = {35, 36, 37, } trong tập hợp sắp thứ tự {N*, ≤}, trong đó ≤ là quan hệ “chia hết cho” trên tập hợp N*. 17. Giả sử {R, ≤} là tập hợp sắp thứ tự, trong đó ≤ là quan hệ “nhỏ hơn hoặc bằng” (thông thường) trên tập hợp các số thực ≤. a) Tìm các phần tử chặn trên và các phần tử chặn dưới của tập hợp A = [−7, 3) = {x ∈ R : −7 ≤ x < 3} trong R. b) Tìm các phần tử chặn trên và chặn dưới (nếu có) của tập hợp N các số tự nhiên. 18. Chứng minh rằng trong mỗi tập con hữu hạn khác rỗng A của tập hợp sắp thứ tự (X, ≤) luôn tồn tại phần tử tối đại và phần tử tối tiểu. Nếu ngoài ra, A là một dây xích thì tồn tại phần tử lớn nhất và phần tử nhỏ nhất của A.
Formatted: Heading01
TIỂU CHỦ ĐỀ 1.6. ÁNH XẠ Thông tin cơ bản ánh xạ và hàm số, một trường hợp đặc biệt của ánh xạ, là những khái niệm quen thuộc với chúng ta đã từ lâu. Đây là những khái niệm quan trọng, thường gặp không chỉ trong mọi bộ môn toán học mà cả trong vật lí, hoá học, cũng như trong các ngành khoa học, kĩ thuật khác. Chủ đề này dành riêng cho việc giới thiệu định nghĩa, các khái niệm cơ bản về ánh xạ và một số tính chất chung của ánh xạ. 6.1. Định nghĩa ánh xạ Formatted: Heading03 Ta xét một số ví dụ Ví dụ 6.1 : Giả sử X là tập hợp gồm 7 em học sinh của một trường trung học phổ thông, trong đó 5 em Cường, Luân, Thái, Mai, Hạnh là học sinh khối 10, hai em Nguyệt, Việt là học sinh khối 11: X = {c, l, t, m, h, n, v}, Y là tập hợp gồm 5 lớp 10A, 10B, 10C, 10D, 10E của trường Y = {A, B, C, D, E}, và R là quan hệ hai ngôi “là học sinh của lớp” trên X x Y, xác định bởi: R = {(c, A), (l, B), (t, B), (m, C), (h, D)}. ((<, A) ∈ R hay c R A được hiểu “Cường là học sinh lớp 10A”). Lược đồ hình tên biểu diễn quan hệ R được cho trong Hình 1 dưới đây. Ta thấy 5 phần tử c, l, t, m, h của tập hợp X có quan hệ R với những phần tử trong tập hợp Y, còn hai phần tử n, v không có quan hệ R với bất cứ một phần tử nào của Y. Như vậy, ta có D (R) ≠ X, D(R) là tập xác định của quan hệ R: D (R) = (c, l, t, m, h}. “là học sinh của lớp”
Hình 1 Trên lược đồ hình tên biểu diễn quan hệ R ta thấy từ mỗi điểm c, l, t, m, h có một mũi tên đi ra và không có mũi tên nào đi từ hai điểm n và v. Ví dụ 6.2 : Giả sử X là tập hợp gồm 5 ông: Hùng, Cung, San, Việt, Tuấn ở trong một nhà của khu tập thể: X = {h, s, c, v, t}, Y là tập hợp gồm 6 em: Dũng, Anh, Loan, Đào, Mạnh, Kiệt, ở nhà đó: Y = {d, a, l, đ, m, k}, và ϕ là quan hệ hai ngôi “là bố của” trên X x Y xác định bởi: ϕ = {(h, d), (s, a), (s, l), (c, đ), (v, m), (t, k)}. ((h, d) ∈ φ hay h ϕ d có nghĩa “Ông Hùng là bố của em Dũng”). Khác với Ví dụ 1, ở đây mỗi phần tử của tập hợp X đều có quan hệ ϕ với một phần tử nào đó của Y, tức là D (ϕ) = X. Trên lược đồ hình tên biểu diễn quan hệ ϕ (Hình 2), ta thấy từ mỗi điểm của tập hợp X đều có mũi tên đi ra. Ngoài ra, phần tử s của X có quan hệ ϕ với hai phần tử a và l của Y. Trên lược đồ hình tên, ta thấy có hai mũi tên từ điểm s đi ra.
Hình 2 Ví dụ 6.3 : Giả sử X là tập hợp gồm 7 học sinh: Dũng, Mai, Hạnh, Tuấn, Cường, Quỳnh, Việt: X = {d, m, h, t, c, q, v}, Y là tập hợp gồm một số họ: Nguyễn, Lê, Trần, Đặng, Huỳnh, Vũ: Y = {N, L, T, Đ, H, V}, và ρ là quan hệ “có họ là” trên X x Y xác định bởi ρ = {(d, N), (m, N), (h, L), (t, T), (c, T), (q, Đ), (v, H)}. ((d, N) ∈ ρ hay d ρ N có nghĩa “Dũng có họ là Nguyễn”). Trong ví dụ này, mỗi phần tử của tập hợp X đều có quan hệ với một phần tử nào đó của tập hợp Y, tức là D (ρ) = X. Ngoài ra, mỗi phần tử của X chỉ có quan hệ ρ với một phần tử duy nhất của Y. Hình 3
Trên lược đồ hình tên biểu diễn quan hệ ρ, ta thấy từ mỗi điểm của tập hợp X đều có một mũi tên đi ra. Hơn nữa, không có điểm nào của X mà từ đó có quá một mũi tên đi ra. Tóm lại, quan hệ hai ngôi ρ trên X x Y thoả mãn điều kiện sau: Với mỗi phần tử x của tập hợp X, tồn tại một phần tử duy nhất y của tập hợp Y sao cho x ρ y. Quan hệ ρ được gọi là một ánh xạ. Một cách tổng quát, ta có: Định nghĩa: Giả sử X và Y là hai tập hợp. Quan hệ hai ngôi f trên X x Y gọi là một ánh xạ từ X vào Y nếu với mỗi phần tử x ∈ X, tồn tại một phần tử duy nhất y ∈ Y sao cho x f y. ánh xạ f từ tập hợp X vào tập hợp Y được kí hiệu là: f : X → Y. Nếu x là một phần tử của tập hợp X thì phần tử y của tập hợp Y sao cho x f y được gọi là ảnh của x qua ánh xạ f và được kí hiệu là f (x). Hiển nhiên ánh xạ f được xác định nếu ảnh f (x) của mỗi phần tử x X đều được xác định. Vì vậy người ta còn dùng kí hiệu x → f (x), x ∈ X hoặc x y, x ∈ X để chỉ anh xạ f. Trong trường hợp X là một tập hợp hữu hạn, người ta thường cho ánh xạ dưới dạng một bảng gồm hai hàng. Các phần tử của tập hợp X được ghi ở hàng trên. ảnh tương ứng chúng (những phần tử của tập hợp Y) được ghi ở hàng dưới. Chẳng hạn, ánh xạ ρ : X → Y trong Ví dụ 3 được cho ở bảng sau: Trước kia ta nói “d có quan hệ ρ với N” và viết d ρ N. Bây giờ ta nói “N là ảnh của d qua ánh xạ ρ” và viết: N = ρ (d). Giả sử f : X → Y là một ánh xạ từ tập hợp X vào tập hợp Y. Khi đó, X được gọi là tập xác định của ánh xạ f. Tập hợp các ảnh f (x) của tất cả các phần tử x của tập hợp X được gọi là ảnh của ánh xạ f, kí hiệu là f (X). Như vậy, với mọi y ∈ Y, y ∈ f (X) khi và chỉ khi tồn tại x ∈ X sao cho y = f (x), tức là: f(X) = {y ∈ Y : tồn tại x ∈ X sao cho y = f(x)}.
Hiển nhiên f (X) là một tập con của Y. Tập hợp Y chứa ảnh của ánh xạ f được gọi là tập đến (hoặc tập đích) của f. Trở lại các ví dụ đã xét, ta thấy quan hệ ℜ trong Ví dụ 1 là quan hệ ρ trong Ví dụ 2 không phải là những ánh xạ. Hiển nhiên quan hệ ρ trong Ví dụ 3 là một ánh xạ như đã nêu. Tập xác định của ánh xạ ρ là X. ρ (d) = N, ρ (m) = N, ρ (h) = L, , ρ (v) = H. ảnh của ánh xạ là: ρ (X) = {N, L, T, Đ, H} ⊂ Y. Không có phần tử nào của tập hợp X có quan hệ ℜ với phần tử V ∈ Y, tức là V không phải là ảnh của bất kì một phần tử nào của X. Như vậy ρ(X) là một tập con thực sự của Y, tức là ρ(X) ⊂ Y và ρ(X) ≠ Y. Ví dụ 6.4 : Cho tập hợp X = {a, b, c} và ánh xạ f: X → N xác định bởi bảng sau: a) Biểu diễn ánh xạ f bằng lược đồ hình tên. b) Tìm ảnh của f. a) Lược đồ hình tên của ánh xạ f được cho trong Hình 4 dưới đây: Hình 4 b) ảnh của ánh xạ f là : f (X) = {1, 3, 5}. f (X) là một tập con thực sự của N.
ánh xạ mà tập xác định và tập đến đều là những tập hợp số (như N, Z, Q, ⏐R, C hoặc các tập con của chúng) thường được cho bởi một công thức. Chẳng hạn, khi cho hàm số : f : ⏐R* → ⏐R xác định bởi công thức : x → f(x) = , ta hiểu rằng mỗi số thực x ≠ 0 nhận một phần tử duy nhất y = ∈⏐R làm ảnh của nó qua ánh xạ f. (Kí hiệu ⏐R* chỉ tập hợp các số thực khác không :⏐R* = ⏐R\{0}). Ví dụ 6.5 : ánh xạ f : ⏐R →⏐R xác định bởi công thức x f(x) = sin x là một ánh xạ từ tập hợp các số thực ⏐R vào ⏐R. Tập xác định của hàm số f là ⏐R. Tập đến của f cũng là ⏐R. ảnh của ánh xạ là tập hợp: f (⏐R) = {y ∈⏐R : −1 ≤ y ≤ 1}, vì với mọi số thực y, y f (⏐R) khi và chỉ khi y = f (x) = sin x Điểu này xảy ra khi và chỉ khi −1 ≤ y ≤ 1 Ví dụ 6.6 : ánh xạ f : ⏐R → ⏐R xác định bởi công thức x → f(x) = x2 + 1 là một ánh xạ từ tập hợp các số thực ⏐R vào ⏐R. Tập xác định của ánh xạ này là ⏐R. Tập đến của f cũng là ⏐R. ảnh của ánh xạ: f (⏐R) = {y ∈ ⏐R : y ≥ 1}, vì với mọi số thực y, y ∈ f (⏐R) khi và chỉ khi y = f (x) = x2 + 1. Điều này xảy ra khi và chỉ khi y ≥ 1. Ví dụ 6.7 : Giả sử X là một tập hợp cho trước tuỳ ý. ánh xạ I: X → X xác định bởi x → I (x) = x là một ánh xạ từ X vào X. Tập xác định của ánh xạ I là X. Tập đến của I cũng là X. Hiển nhiên ảnh của ánh xạ I là I (X) = X. I được gọi là ánh xạ đồng nhất trên tập hợp X. Khi có nhiều tập hợp X, Y, được đồng thời đề cập đến, để phân biệt, người ta dùng các kí hiệu IX, IY, để chỉ các ánh xạ đồng nhất trên các tập hợp X, Y, Ví dụ 6.8 : Phép cộng trên tập hợp các số thực ⏐R là một ánh xạ từ tập hợp ⏐R2 = ⏐R x ⏐R vào tập hợp ⏐R:
ánh xạ f: ⏐R x ⏐R → ⏐R xác định bởi: (x, y) → f (x, y) = x + y là một ánh xạ từ tập hợp ⏐R x ⏐R vào tập hợp ⏐R. (ảnh của phần tử (x, y) ∈ ⏐R x ⏐R qua ánh xạ f được kí hiệu là f (x, y) thay cho f ((x, y))). Tập xác định của ánh xạ f là ⏐R x⏐R. Tập đến của f là ⏐R. Dễ dàng thấy rằng ảnh của f là f (⏐R x ⏐R) = ⏐R. Tương tự, phép trừ và phép nhân trên tập hợp ⏐R cũng là những ánh xạ từ tập hợp ⏐R x ⏐R vào tập hợp ⏐R. Ví dụ 6.9 : Ký hiệu ⏐R* chỉ tập hợp các số thực khác 0: ⏐R* = ⏐R \ {0}. Phép chia trên ⏐R la f một ánh xạ từ tập hợp ⏐R x ⏐R* vào tập hợp ⏐R: ánh xạ f : ⏐R x ⏐R* → ⏐R xác định bởi (x, y) → f (x, y) = là một ánh xạ từ tập hợp ⏐R x ⏐R* vào tập hợp ⏐R. Tập xác định của f là ⏐R x ⏐R*. Tập đến của f là ⏐R. Dễ dàng thấy rằng ảnh của f là tập hợp f (⏐R x ⏐R*) = ⏐R. 6.2. ánh xạ bằng nhau Formatted: Heading03 Giả sử X và Y là hai tập hợp, f và g là hai ánh xạ từ X vào Y. Ta nói rằng hai ánh xạ f và g là bằng nhau, và viết f = g, nếu f (x) = g (x) với mọi x X. Chẳng hạn, ánh xạ f : ⏐R → ⏐R x → f (x) = x3 − 1 và ánh xạ g: ⏐R → ⏐R x → g (x) = (x − 1) (x2 + x + 1) là hai ánh xạ bằng nhau. 6.3. Thu hẹp và thác triển ánh xạ Formatted: Heading03 a) Giả sử f : X → Y là một ánh xạ từ tập hợp X vào tập hợp Y và A là một tập con của X. ánh xạ g : A → Y xác định bởi g (x) = f (x) với mọi x ∈ A, Gọi là ánh xạ thu hẹp (gọi tắt là thu hẹp) của ánh xạ f trên tập hợp A và được kí hiệu là f/A. Như vậy, f/A : A → Y là ánh xạ xác định bởi: x f/A (x) = f(x). Ví dụ 6.10 : Giả sử f: ⏐R → ⏐R là ánh xạ xác định bởi:
A và B là hai tập con của ⏐R với : A = {x ∈⏐R : x ≥ 0} và B = {x ∈⏐R : x < 0}. Khi đó, ánh xạ thu hẹp của f trên A là: f/A: A →⏐R x → f/A (x) = , và ánh xạ thu hẹp của f trên B là: f/B: B → ⏐R x → f/B(x) = . b) Giả sử X, Y là hai tập hợp, A là một tập con của X, f: A → Y và F: X → Y là những ánh xạ. Nếu F/A = f, tức là F (x) = f (x) với mọi x ∈ A thì ánh xạ F được gọi là ánh xạ thác triển (gọi tắt là thác triển) của ánh xạ f lên tập hợp X. Ví dụ 6.11 : Giả sử f : Q → {0, 1} là ánh xạ từ tập hợp các số hữu tỉ Q vào tập hợp {0, 1} xác định bởi: f (x) = 1, với mọi x ∈ Q, và D : ⏐R → {0, 1} là ánh xạ xác định bởi: Khi đó, ánh xạ D là thác triển của ánh xạ f (từ tập con Q của ⏐R) lên tập hợp ⏐R. ánh xạ D được gọi là hàm số Điritslê (Diritchlet). (Điritslê Pitơ Guxtao Lơgiơn (Diritchlet Peter Gustav Lejeune, 1805 − 1859) là nhà toán học Đức). 6.4. Hợp của các ánh xạ Formatted: Heading03 a) Cho hai ánh xạ f : X → Y và g : Y → Z. ánh xạ h : X → Z xác định bởi x → h(x) = g [f(x)] gọi là ánh xạ hợp của hai ánh xạ f và g, kí hiệu là gof.
Như vậy, gof: X → Z là ánh xạ xác định bởi: (gof) (x) = g[f(x)], x ∈ X. (Trong kí hiệu ánh xạ hợp “gof” của ánh xạ f và g, hãy chú ý đến thứ tự của hai ánh xạ: g được viết trước f). Lược đồ sau giúp ta nhớ định nghĩa ánh xạ hợp dễ hơn. Hình 5 Ví dụ 6.12 : (i) cho hai ánh xạ. f: ⏐R → ⏐R x → f (x) = 2 x − và g : ⏐R → ⏐R x → f (x) = sin x. Khi đó, ánh xạ hợp của f và g là: gof : ⏐R → ⏐R x → (gof) (x) = sin (2x − ). (ii) cho hai ánh xạ f : ⏐R+ ⏐R x → f (x) = (Ký hiệu ⏐R+ chỉ tập hợp các số thực không âm), và g: R → ⏐R x → g (x) = cos x. Khi đó, ảnh xạ hợp của f và g là: gof: ⏐R → ⏐R