Lý Thuyết Tập Hợp Và Logic Toán - Tài Liệu Text - 123doc

Tải bản đầy đủ (.pdf) (129 trang)

1. Trang chủ
>>
2. Giáo án - Bài giảng
>>
3. Cao đẳng - Đại học

Lý thuyết tập hợp và logic toán

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (631.71 KB, 129 trang )

2BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC TÂY BẮCNGUYỄN TRIỆU SƠN - NGUYỄN ĐÌNH YÊNLÝ THUYẾT TẬP HỢP VÀ LOGIC TOÁNSơn La, 2015Lời nói đầuLý thuyết tập hợp và lôgic toán là cơ sở nền tảng của toán học nói chungvà của các môn học toán học trong chương trình đào tạo đại học nói riêng.Lôgic toán mà chủ yếu là các quy luật cơ bản của lôgic hình thức xuất hiệnvà phát triển từ rất sớm, khoảng 300 năm trước công nguyên, thời Aristote(384-322 trước công nguyên).Tuy nhiên trong quá trình phát triển, khi mà toán học chuyển từ phạm vi"bất biến, hữu hạn" sang phạm vi "vận động, vô hạn và liên tục" thì các cơsở lý luận - lôgic hình thức ban đầu ấy tỏ ra không đủ đáp ứng được nữa.Để khắc phục những khó khăn về cơ sở lý luận - lôgic hính thức, vào cuốithế kỷ thứ 19 Cantor đã xây dựng lý thuyết tập hợp với tư tưởng chính là thừanhận tập hợp theo nghĩa "Một sự hợp lại trong một toàn thể các đối tượng bấtkỳ mà nhận thức hay tư duy của chúng ta có thể hình dung ra" và với nhữngtập hợp như vậy, vô hạn cũng như hữu hạn, ta có thể vận dụng các quy luậtcủa lôgic hình thức "cổ điển" không phân biệt và không hạn chế. Tuy rằngtrong quá trình phát triển của toán học, lý thuyết tập hợp của Cantor còn vấpphải nhiều nghịch lý không thể lý giải, nhưng có thể nói rằng lý thuyết tậphợp mà Cantor xây dựng về căn bản đã cung cấp một nền tảng thống nhấtcho việc xây dựng và phát triển hầu như toàn bộ các ngành toán học.Đồng thời với việc khắc phục, loại bỏ các nghịch lý trong lý thuyết tập hợp23mà Cantor xây dựng bằng cách hạn chế ngoại diên của của khái niệm tập hợp,quy định những điều làm được và những điều không thể làm được đối với cácđối tượng và quan hệ cơ bản của lý thuyết tập hợp, người ta cũng đề nghị tiênđề hóa lý thuyết cơ sở về lôgic nhằm xây dựng một nền tảng vững chắc chotoán học.Tập giáo trình này bao gồm 4 chương, được viết chi tiết theo chương trìnhmôn lý thuyết tập hợp và lôgic toán, của Khoa Toán-Lý-Tin Trường Đại họcTây Bắc nhằm phục vụ trực tiếp cho công tác giảng dạy và học tập trong khoa.Chương 1. Tập hợp quan hệ và ánh xạ: Trình bày các khái niệm cơ bản vềtập hợp, phần tử của tập hợp, quan hệ thuộc, các phép toán về tập hợp, ...theo quan điểm của Cantor. Ngoài ra các khái niệm quan hệ tương đương,quan hệ thứ tự, ánh xạ cùng các tính chất của của chúng cũng được trình bàychi tiết nhằm phục vụ cho việc nghiên cứu vấn đề bản số của tập hợp, tạo cơsở cho việc xây dựng các tập số sau này.Chương 2. Đại số mệnh đề: Trình bày các khái niệm mệnh đề, các phép toánmệnh đề, công thức và các luật của lôgic mệnh đề,...Chương 3. Đại số vị từ: Trình bày các vấn đề cơ bản về Đại số vị từ, nhưlà một mở rộng tất yếu của Đại số mệnh đề. Nội dung của chương bao gồm:Khái niệm hàm mệnh đề (vị từ) một biến và nhiều biến, các phép toán về hàmmệnh đề, lượng từ, công thức vị từ, vấn đề về tính giải được. Ngoài ra còntrình bày một số ứng dụng của Đại số mệnh đề và Đại số vị từ vào vấn đề suyluận và chứng minh.Chương 4. Sơ lược về hệ toán mệnh đề và hệ toán vị từ: Trình bày các hệtiên đề của lôgic toán mà chúng ta gọi chúng tương ứng là "Hệ toán mệnh đề"và "Hệ toán vị từ". Đồng thời cũng chỉ ra tính phi mâu thuẫn, tính đầy đủ vàđộc lập của các hệ tiên đề đó.4Hệ thống kiến thức cơ bản được chọn lựa một cách tối thiểu, các mệnh đề,định lý được chứng minh tỉ mỉ, chi tiết cùng hệ thống ví dụ minh họa trựcquan và bài tập phong phú, đặc biệt các bài tập được đặt sau mỗi bài lý thuyếttạo điều kiện thuận lợi cho sinh viên tự học môn học này ở năm thứ nhất. Hyvọng rằng với cách trình bày như vậy giáo trình sẽ góp phần nâng cao hiệuquả học tập của sinh viên.Chúng tôi chân thành cám ơn các đồng nghiệp trong khoa Toán - Lý - TinTrường Đại học Tây bắc đã đóng góp nhiều ý kiến bổ ích trong quá trình biênsoạn giáo trình này. Đặc biệt chúng tôi xin trân trọng cảm ơn Ban giám hiệu,Phòng đào tạo sau đại học, Khoa Toán - Lý - Tin đã tạo điều kiện thuận lợiđể chúng tôi hoàn thành tập giáo trình này.Cuối cùng, có thể việc biên soạn của các tác giả vẫn còn thiếu sót, chúngtôi mong muốn tiếp tục nhận được các ý kiến đóng góp phê bình của các bạnđồng nghiệp.Các tác giảMục lụcLời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51 Tập hợp, Quan hệ, Ánh xạ1.11.210Tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.1.1Khái niệm tập hợp . . . . . . . . . . . . . . . . . . . . . 101.1.2Cách xác định tập hợp . . . . . . . . . . . . . . . . . . . 111.1.3Quan hệ giữa các tập hợp . . . . . . . . . . . . . . . . . 121.1.4Phép toán trên các tập hợp . . . . . . . . . . . . . . . . 131.1.5Tích đề các của các tập hợp . . . . . . . . . . . . . . . . 171.1.6Sự phân hoạch của một tập hợp . . . . . . . . . . . . . . 181.1.7Tập hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . 18Quan hệ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.2.1Quan hệ hai ngôi . . . . . . . . . . . . . . . . . . . . . . 241.2.2Một số tính chất thường gặp của quan hệ hai ngôi . . . . 241.2.3Quan hệ tương đương . . . . . . . . . . . . . . . . . . . . 251.2.4Lớp tương đương và tập thương . . . . . . . . . . . . . . 261.2.5Quan hệ thứ tự . . . . . . . . . . . . . . . . . . . . . . . 2756MỤC LỤC1.2.6Quan hệ thứ tự toàn phần và bộ phận . . . . . . . . . . 281.2.7Cận trên, cận dưới, phần tử lớn nhất, nhỏ nhất . . . . . 281.2.8Tập sắp thứ tự tốt . . . . . . . . . . . . . . . . . . . . . 301.2.9Tiên đề chọn và các mệnh đề tương đương . . . . . . . . 301.3 Ánh xạ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341.3.1Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . . . . 341.3.2Ánh xạ bằng nhau . . . . . . . . . . . . . . . . . . . . . 361.3.3Thu hẹp và mở rộng ánh xạ . . . . . . . . . . . . . . . . 361.3.4Ảnh và tạo ảnh . . . . . . . . . . . . . . . . . . . . . . . 371.3.5Đơn ánh; Toàn ánh; Song ánh . . . . . . . . . . . . . . . 371.3.6Tích ánh xạ . . . . . . . . . . . . . . . . . . . . . . . . . 381.3.7Ánh xạ ngược . . . . . . . . . . . . . . . . . . . . . . . . 401.4 Bản số của tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . 411.4.1Khái niệm bản số . . . . . . . . . . . . . . . . . . . . . . 411.4.2Tập đếm được . . . . . . . . . . . . . . . . . . . . . . . . 431.4.3Tập continum . . . . . . . . . . . . . . . . . . . . . . . . 461.4.4So sánh các bản số . . . . . . . . . . . . . . . . . . . . . 472 Đại số mệnh đề532.1 Mệnh đề và các phép toán mệnh đề . . . . . . . . . . . . . . . . 532.1.1Khái niệm mệnh đề . . . . . . . . . . . . . . . . . . . . . 532.1.2Phép toán trên các mệnh đề . . . . . . . . . . . . . . . . 542.2 Công thức lôgic mệnh đề . . . . . . . . . . . . . . . . . . . . . . 592.2.1Khái niệm công thức . . . . . . . . . . . . . . . . . . . . 59MỤC LỤC2.372.2.2Giá trị của công thức . . . . . . . . . . . . . . . . . . . . 602.2.3Công thức tương đương . . . . . . . . . . . . . . . . . . 612.2.4Các đẳng thức cơ bản . . . . . . . . . . . . . . . . . . . 622.2.5Luật của lôgic mệnh đề . . . . . . . . . . . . . . . . . . . 642.2.6Mệnh đề liên kết, điều kiện cần, điều kiện đủ . . . . . . . 652.2.7Dạng chuẩn tắc của công thức . . . . . . . . . . . . . . . 652.2.8Phép đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . . 69Hàm đại số lôgic . . . . . . . . . . . . . . . . . . . . . . . . . . 733 Đại số vị từ3.13.23.376Khái niệm hàm mệnh đề . . . . . . . . . . . . . . . . . . . . . . 773.1.1Hàm mệnh đề một biến. . . . . . . . . . . . . . . . . . 773.1.2Hàm mệnh đề nhiều biến . . . . . . . . . . . . . . . . . . 783.1.3Hàm mệnh đề hằng đúng . . . . . . . . . . . . . . . . . . 80Phép toán trên các hàm mệnh đề . . . . . . . . . . . . . . . . . 813.2.1Phép phủ định. . . . . . . . . . . . . . . . . . . . . . . . 813.2.2Phép hội . . . . . . . . . . . . . . . . . . . . . . . . . . . 823.2.3Phép tuyển . . . . . . . . . . . . . . . . . . . . . . . . . 833.2.4Phép kéo theo . . . . . . . . . . . . . . . . . . . . . . . . 843.2.5Phép tương đương . . . . . . . . . . . . . . . . . . . . . 84Các lượng từ. . . . . . . . . . . . . . . . . . . . . . . . . . . . 863.3.1Khái niệm lượng từ . . . . . . . . . . . . . . . . . . . . . 863.3.2Lượng từ với các hàm mệnh đề nhiều biến . . . . . . . . 873.3.3Liên hệ giữa các lượng từ phổ dụng và tồn tại . . . . . . 888MỤC LỤC3.4 Công thức lôgic vị từ . . . . . . . . . . . . . . . . . . . . . . . . 923.4.1Khái niệm công thức vị từ . . . . . . . . . . . . . . . . . 923.4.2Công thức bằng nhau và công thức hằng đúng . . . . . . 943.4.3Một số luật thường gặp của lôgic vị từ . . . . . . . . . . 953.4.4Dạng chuẩn của công thức . . . . . . . . . . . . . . . . . 963.4.5Vấn đề về tính giải được . . . . . . . . . . . . . . . . . . 983.5 Suy luận và chứng minh . . . . . . . . . . . . . . . . . . . . . . 1023.5.1Quy tắc suy luận . . . . . . . . . . . . . . . . . . . . . . 1023.5.2Hai kiểu suy luận . . . . . . . . . . . . . . . . . . . . . . 1043.5.3Chứng minh . . . . . . . . . . . . . . . . . . . . . . . . . 1054 Sơ lược về hệ toán mệnh đề và hệ toán vị từ1114.1 Hệ toán mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . . 1124.1.1Các ký hiệu của hệ toán mệnh đề . . . . . . . . . . . . . 1124.1.2Định nghĩa công thức của hệ toán mệnh đề . . . . . . . . 1134.1.3Các tiên đề của hệ toán mệnh đề . . . . . . . . . . . . . 1134.1.4Quy tắc suy diễn . . . . . . . . . . . . . . . . . . . . . . 1144.2 Suy diễn trong hệ toán mệnh đề . . . . . . . . . . . . . . . . . . 1144.3 Tính phi mâu thuẫn, tính đầy đủ, tính độc lập . . . . . . . . . . 1174.3.1Tính phi mâu thuẫn . . . . . . . . . . . . . . . . . . . . 1174.3.2Tính đầy đủ của hệ toán mệnh đề . . . . . . . . . . . . . 1184.3.3Tính độc lập của hệ toán mệnh đề . . . . . . . . . . . . 1204.4 Hệ toán vị từ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1244.4.1Ký hiệu của hệ toán vị từ . . . . . . . . . . . . . . . . . 124MỤC LỤC4.594.4.2Các tiên đề của hệ toán vị từ . . . . . . . . . . . . . . . 1244.4.3Các quy tắc suy diễn . . . . . . . . . . . . . . . . . . . . 124Tính phi mâu thuẫn và tính đầy đủ . . . . . . . . . . . . . . . . 1264.5.1Tính phi mâu thuẫn của hệ toán vị từ . . . . . . . . . . 1264.5.2Tính đầy đủ của hệ toán vị từ . . . . . . . . . . . . . . . 127Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 128Chương 1Tập hợp, Quan hệ, Ánh xạLý thuyết tập hợp được khởi xướng xây dựng bởi Cantor vào khoảng cuốithế kỷ 19 nhằm thống nhất một thứ ngôn ngữ chung diễn đạt cho hầu hết cáctư tưởng toán học, nhằm tạo nên một cơ sở vững chắc cho sự phát triển củahầu hết các ngành, từ số học, đại số đến hình học, tôpô, giải tích, ...Tư tưởng chính của lý thuyết tập hợp mà Cantor xây dựng là thừa nhậnkhái niệm tập hợp theo nghĩa "Một sự hợp lại trong một toàn thể các đốitượng bất kỳ mà nhận thức hay tư duy của chúng ta có thể hình dung ra" vàvới những tập hợp như vậy, vô hạn cũng như hữu hạn, ta có thể vận dụng cácquy luật của lôgic hình thức cổ điển không phân biệt và không hạn chế.Trong chương này chúng ta sẽ trình bày các khái niệm cơ bản về tập hợp,phần tử của tập hợp, quan hệ thuộc, các phép toán về tập hợp, ... theo quanđiểm của Cantor. Ngoài ra các khái niệm quan hệ tương đương, quan hệ thứtự, ánh xạ cùng các tính chất của chúng cũng được trình bày chi tiết nhằmphục vụ cho việc nghiên cứu vấn đề bản số của tập hợp, tạo cơ sở cho việc xâydựng các tập số sau này.1.11.1.1Tập hợpKhái niệm tập hợpKhái niệm tập hợp là khái niệm cơ bản của toán học, được hiểu một cáchtrực giác, không định nghĩa. Chúng ta quan niệm tập hợp là một sự tụ tậpcác vật hay các đối tượng có một hay nhiều tính chất chung nào đó. Các đốitượng đó gọi là các phần tử của tập hợp.Tập hợp đôi khi được gọi tắt là tập, và ký hiệu bằng các chữ cái La tinh10111.1 Tập hợpA, B, C, ..., X, Y, Z hoặc các chữ cái Hy lạp cổ như Γ, Ω, ... Các phần tử củatập hợp ký hiệu bởi các chữ cái in thường a, b, c, ..., x, y, zMột phần tử a của tập A được ký hiệu là a ∈ A đọc là a thuộc A. Ngượclại thì ta viết a ∈/ A và đọc là a không thuộc A.Ví dụ 1.1. Tập các số tự nhiên N; Tập các số nguyên Z; Tập các số hữu tỷQ; Tập các số thực R; Tập các số phức C1.1.2Cách xác định tập hợpMột tập hợp được gọi là xác định khi ta chỉ ra được cách nhận biết cácphần tử của nó. Có hai phương pháp chính xác định tập hợp sau đây:1. Phương pháp liệt kêMột tập hợp có thể xác định bằng cách liệt kê đầy đủ tất cả các phầntử của nó hoặc liệt kê một số phần tử đại diện của nó và để trong haidấu móc {...} đủ để ta xác định một phần tử tùy ý có thuộc tập hợp đóhay không.Ví dụ 1.2. A = {1, 2, 3} là tập hợp gồm ba phần tử là các số 1, 2, 3B = {1, 4, 9, 16, ...} là tập tất cả các số chính phương.2. Phương pháp chỉ ra dấu hiệu đặc trưng các phần tửMột tập hợp có thể xác định bằng cách chỉ ra dấu hiệu đặc trưng củacác phần tử của nó, mà dựa vào dấu hiệu đó ta nhận biết được một phầntử tùy ý là thuộc hay không thuộc tập hợp đó.Nếu A là tập hợp gồm các phần tử x có tính chất P (x) thì ta viếtA = {x | P (x)}Các phần tử x có tính chất P (x) thiết lập nên tập A thường được chọntừ một tập X đã biết nào đó, khi đó ta viếtA = {x ∈ X | P (x)}Ví dụ 1.3.A = {x ∈ R | x2 − 3x + 2 = 0}là tập các nghiệm thực của phương trình x2 − 3x + 2 = 0B = {n ∈ Z | 10 < n < 23}C = {n ∈ N | n chia hết 15}12Tập hợp, Quan hệ, Ánh xạ3. Tập rỗngTập hợp không chứa phần tử nào được gọi là tập rỗng, ký hiệu ∅. Chẳnghạn tập các nghiệm thực của phương trình x2 + 1 = 0 là ∅.1.1.3Quan hệ giữa các tập hợpĐịnh nghĩa 1.1. Cho hai tập hợp A và B. Nếu mọi phần tử của A đều thuộcB thì ta gọi A là tập con của tập B ký hiệu A ⊆ B hoặc B ⊇ A. Ngoài cáchgọi A là tập con của tập B ta còn gọi A là bộ phận của tập B; A chứa trongB; A bao hàm trong B; B chứa A. Nếu A không là tập con của tập B thì taviết A ⊆ B hoặc B ⊇ A.Nếu A ⊆ B và A = B thì A được gọi là tập con thực sự của B ký hiệuA ⊂ B và ta cũng gọi A ⊂ B là bao hàm thức thực sự.Hai tập A và B gọi là bằng nhau nếu A ⊆ B và B ⊆ A, ký hiệu A = B.Quy ước: Tập ∅ là tập con của mọi tập hợp.Ví dụ 1.4. N ⊂ Z ⊂ Q ⊂ R ⊂ C.A = {n ∈ N | n là ước của 10} và B = {1, 2, 5, 10} thì A = B.Nhận xét:1. Từ định nghĩa suy ra tập ∅ là duy nhất.2. Cách viết tập hợp theo phương pháp liệt kê không phụ thuộc vào thứtự sắp xếp các phần tử cũng như số lần các phần tử xuất hiện trong haidấu móc. Chẳng hạn như:{a, b, c} = {a, a, b, c} = {b, a, b, c, c}.3. Viết tập hợp thông qua dấu hiệu đặc trưng của các phần tử, nghĩa là cácphần tử của tập hợp được cho dưới dạng ẩn, mà đôi khi việc xác địnhcụ thể chúng là vô cùng khó khăn. Chẳng hạn, xét tập hợp:A = {n ∈ N | xn + y n = z n có nghiệm nguyên x, y, z = 0}.Định lý lớn Fecma đã khẳng định rằng tập A chỉ gồm hai phần tử là 1với 2 và phải trải qua hàng trăm năm với biết bao công sức của các nhàtoán học mới chứng minh được định lý này.131.1 Tập hợp1.1.4Phép toán trên các tập hợpTrong mục này chúng ta sử dụng một số ký hiệu lôgic, với cách hiểu nhưđã biết ở phổ thông: ∀; ∃; ⇒; ⇔; ∨; ∧ đọc tương ứng là: Với mọi; tồn tại; kéotheo; tương đương; hoặc; và. Nội dung của các ký hiệu đó sẽ được trình bàychi tiết và đầy đủ ở các chương sau.1. Phép hợpĐịnh nghĩa 1.2. Hợp của hai tập hợp X và Y là một tập hợp được kýhiệu và xác định bởiX ∪ Y = {x | x ∈ X ∨ x ∈ Y }.Ký hiệu X ∪ Y đọc là X hợp Y .Nhận xét: Từ định nghĩa ta có:(a) x ∈ X ∪ Y ⇔ (x ∈ X) ∨ (x ∈ Y ) ⇔(b) x ∈/ X ∪ Y ⇔ (x ∈/ X) ∧ (x ∈/ Y)⇔x∈Xx∈Yx∈/Xx∈/Y2. Phép giaoĐịnh nghĩa 1.3. Giao của hai tập hợp X và Y là một tập hợp được kýhiệu và xác định bởiX ∩ Y = {x | x ∈ X ∧ x ∈ Y }.Ký hiệu X ∩ Y đọc là X giao Y .Nhận xét: Từ định nghĩa ta có:(a) x ∈ X ∩ Y ⇔ (x ∈ X) ∧ (x ∈ Y ) ⇔(b) x ∈/ X ∩ Y ⇔ (x ∈/ X) ∨ (x ∈/ Y)⇔x∈Xx∈Yx∈/Xx∈/Y14Tập hợp, Quan hệ, Ánh xạ3. Phép trừĐịnh nghĩa 1.4. Hiệu của hai tập hợp X và Y là một tập hợp ký hiệuvà xác định bởi:X \ Y = {x | x ∈ X ∧ x ∈/ Y }.Ký hiệu X \ Y đọc là X trừ Y . Nếu Y ⊆ X thì X \ Y gọi là phần bù củaY trong X và ký hiệu là CX Y.Nhận xét: Từ định nghĩa ta có:(a) x ∈ X \ Y ⇔ (x ∈ X) ∧ (x ∈/ Y)⇔(b) x ∈/ X \ Y ⇔ (x ∈/ X) ∨ (x ∈ Y ) ⇔x∈Xx∈/Yx∈/Xx∈Y4. Hiệu đối xứngĐịnh nghĩa 1.5. Hiệu đối xứng của hai tập hợp X và Y là một tập hợpký hiệu và xác đinh bởiX △ Y = (X \ Y ) ∪ (Y \ X) .Ký hiệu X △ Y đọc là X trừ đối xứng Y .Nhận xét: Từ định nghĩa ta có:(a) x ∈ X △ Y ⇔(b) x ∈/ X △Y ⇔x∈X \Yx∈Y \Xx∈/ X \Yx∈/ Y \XChú ý: Người ta thường minh họa mỗi tập hợp như một phần mặtphẳng giới hạn bởi một đường cong khép kín, phần mặt phẳng đó đượctô màu hoặc đánh dấu để nhận biết được và gọi là biểu đồ ven. Chẳnghạn:151.1 Tập hợpA∩BAA\BA△BA∪BĐịnh lý 1.1. Với các tập hợp tùy ý A, B và C ta luôn có:1. Tính chất giao hoán: A ∪ B = B ∪ A; A ∩ B = B ∩ A.2. Tính chất kết hợp:(A ∪ B) ∪ C = A ∪ (B ∪ C)(A ∩ B) ∩ C = A ∩ (B ∩ C)3. Tính chất phân phối:A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)4. Luật De Morgan:A \ (B ∪ C) = (A \ B) ∩ (A \ C)A \ (B ∩ C) = (A \ B) ∪ (A \ C)5. Luật hấp thu: Nếu A ⊆ B thì A ∪ B = B; A ∩ B = AChứng minh. Các đẳng thức (1), (2), (5) được suy trực tiếp từ địnhnghĩa. Các đẳng thức còn lại được chứng minh tương tự nhau, chúng tachứng minh chẳng hạn:Ta có:A \ (B ∪ C) = (A \ B) ∩ (A \ C)x ∈ A \ (B ∪ C) ⇔⇔x∈Ax∈A/B⇔ x∈x∈/ B∪Cx∈/Cx∈A\Bx∈A\C⇔ x ∈ (A \ B) ∩ (A \ C)16Tập hợp, Quan hệ, Ánh xạVậy A \ (B ∪ C) = (A \ B) ∩ (A \ C)Nhận xét: Theo luật hấp thu thì từ ∅ ⊆ A và A ⊆ A suy raA ∪ ∅ = A; A ∩ ∅ = AA ∪ A = A; A ∩ A = A5. Mở rộng các phép toán trên các tập hợpTừ tính chất (2) của Định lý 1 ta có thể định nghĩa hợp, giao của n tậphợp bằng quy nạp như sau:• A1 ∪ A2 ∪ A3 = (A1 ∪ A2 ) ∪ A3ni=1Ai = (A1 ∪ A2 ∪ ... ∪ An−1 ) ∪ An• A1 ∩ A2 ∩ A3 = (A1 ∩ A2 ) ∩ A3ni=1Ai = (A1 ∩ A2 ∩ ... ∩ An−1 ) ∩ AnTừ đó các tính chất (3) và (4) của Định lý 1 được mở rộng thành:n3′ . B ∩n(B ∩ Ai ); B ∪i=1i=1nn′4.B\nAi =Ai =i=1(B \ Ai ); B \i=1n(B ∪ Ai )Ai =i=1i=1nnAi =i=1i=1(B \ Ai )6. Tập các bộ phận của một tập hợpCho tập hợp X. Nếu coi mỗi một bộ phận của X là một phần tử thì tacó tập hợp các bộ phận của X℘(X) = {A | A ⊆ X}mà mỗi phần tử của ℘(X) là một bộ phận của X.Ví dụ 1.5.• X = {a, b} thì ℘(X) = {∅, {a}, {b}, X}• X = ∅ thì ℘(∅) = {∅}; ℘(℘(∅)) = {∅, {∅}}.Nhận xét: Nếu tập X có n phần tử thì ℘(X) có 2n phần tử.171.1 Tập hợp1.1.5Tích đề các của các tập hợpCho các tập hợp A1 , ..., An , với ai ; bi ∈ Ai , i = 1, ..., n. Khi đó (a1 , ..., an ) =(b1 , ..., bn ) khi và chỉ khi a1 = b1 , a2 = b2 , ..., an = bn .Định nghĩa 1.6. Cho các tập hợp A1 , ..., An . Một tập hợp C được xác địnhnhư sau:(i)(ii)C = ∅ nếu một trong các tập A1 , A2 , ..., An là ∅.C = A1 nếu n = 1(iii) C = {(a1 , a2 , ..., an ) | a1 ∈ A1 , a2 ∈ A2 , ..., an ∈ An } nếu n > 1 và cácAi = ∅.Được gọi là tích Descartes (tích Đề-các) của n tập A1 , A2 , ..., An . Ký hiệunC = A1 × A2 × ... × An =Ai .i=1Trường hợp đặc biệt khi A1 = A2 = ... = An = A thì viết C = An .Ví dụ 1.6. Xét các tập hợp:1. A = {a, b, c} và B = {x, y} thìA × B = {(a, x), (a, y), (b, x), (b, y), (c, x), (c, y)} .B × A = {(x, a), (y, a), (x, b), (y, b), (x, c), (y, c)} .2. Cho A = [a, b]; B = [c, d] là các đoạn thẳng, khi đó tích A × B là tập cácphần tử được biểu thị bởi các điểm của hình chữ nhật trong mặt phẳngtọa độ Oxy (Hình 1.a)3. Cho A là tập điểm của hình tròn thuộc mặt phẳng Oxy, B là tập điểmcủa đoạn [0, h] trên trục Oz trong hệ trục tọa độ Oxyz thì A × B là tậphợp các phần tử biểu thị các điểm của khối trụ có chiều cao h đáy làhình tròn A (Hình 1.b)zyhabOxxOcdHinh 1.ayHinh 1.b18Tập hợp, Quan hệ, Ánh xạNhận xét: Khi hai tập A, B khác nhau và khác ∅ thì A × B = B × A điều nàynói lên rằng tích Descartes của hai tập hợp nói chung không có tính chất giaohoán.1.1.6Sự phân hoạch của một tập hợpTa nói rằng tập hợp X được phân chia (phân hoạch) thành các bộ phậnA, B, C, ... nếu A, B, C, ... đều khác rỗng và rời nhau từng đôi một sao cho mọiphần tử của X đều thuộc một trong các bộ phận đó. Chính xác hơn ta có địnhnghĩa sau:Định nghĩa 1.7. Cho X là một tập hợp, ℘(X) là tập các bộ phận của X. Bộphận khác rỗng P ⊆ ℘(X) được gọi là một phân hoạch của tập X nếu và chỉnếu các điều kiện sau được thỏa mãn(i) ∀A ∈ P; A = ∅(ii) ∀A, B ∈ P; A = B ⇒ A ∩ B = ∅.(iii) ∀x ∈ X, ∃A ∈ P : x ∈ A.1.1.7Tập hữu hạn1. Bản số của tập hữu hạnTa gọi một tập là hữu hạn nếu nó là tập rỗng hoặc là liệt kê được tấtcả các phần tử của nó. Nói cách khác một tập A gọi là tập hữu hạn nếunhư:(i) A = ∅ hoặc(ii) A = {a1 , a2 , ..., an }Trong trường hợp thứ nhất ta nói A có bản số 0, trong trường hợp thứhai ta nói A có bản số n. Bản số của A ký hiệu là cardA hoặc |A|.Nhận xét:• Bản số của tập hữu hạn chính là số phần tử của tập đó, vì vậy haitập hợp hữu hạn có cùng bản số khi và chỉ khi chúng có cùng sốphần tử.• Tập số tự nhiên N là tập các bản số của các tập hữu hạn.2. Một số tính chất của bản số hữu hạnĐịnh lý 1.2. (Nguyên lý cộng) Nếu A và B là các tập hữu hạn rời nhau,nghĩa là A ∩ B = ∅ thì |A ∪ B| = |A| + |B|.191.1 Tập hợpChứng minh. Giả sử |A| = m và |B| = n vàA = {a1 , a2 , ..., am } ; B = {b1 , b2 , ..., bn } .Do A ∩ B = ∅ nên ta có:A ∪ B = {a1 , a2 , ..., am , b1 , b2 , ..., bn } .Vậy|A ∪ B| = m + n = |A| + |B|.Hệ quả 1.1. Cho A và B là các tập hữu hạn tùy ý, ta luôn có:|A \ B| = |A| − |A ∩ B|Chứng minh. Từ các đẳng thức sau:A = (A \ B) ∪ (A ∩ B) và (A \ B) ∩ (A ∩ B) = ∅.Suy ra |A| = |A \ B| + |A ∩ B|. Vậy |A \ B| = |A| − |A ∩ B|.Bằng quy nạp ta dễ dàng nhận được kết quả tổng quát hơn sau đây:Định lý 1.3. Nếu A1 , ..., An là các tập hữu hạn đôi một rời nhau, tứclà Ai ∩ Aj = ∅ nếu i = j, thì|A1 ∪ A2 ∪ ... ∪ An | = |A1 | + |A2 | + ... + |An |.Định lý 1.4. (Nguyên lý nhân) Cho A và B là các tập hữu hạn. Khi đóta có |A × B| = |A||B|.Chứng minh. Giả sử A = {a1 , a2 , ..., an }; B = {b1 , b2 , ..., bm }. Với mọiai ; i = 1, ..., n ta có{ai } × B = {(ai , b1 ), (ai , b2 ), ..., (ai , bm )}.Suy ra |{ai } × B| = m. Mặt khác A × B =n({ai } × B) và các tậpi=1{a1 } × B, {a2 } × B, ..., {an } × B đôi một rời nhau. Theo nguyên lý cộngta có |A × B| = |{a1 } × B| + ... + |{an } × B| = n.m = |A||B|.Bằng quy nạp ta cũng nhận được kết quả tổng quát hơn sau đây:20Tập hợp, Quan hệ, Ánh xạĐịnh lý 1.5. Cho A1 , ..., An là các tập hữu hạn tùy ý. Khi đó:|A1 × A2 × ... × An | = |A1 ||A2 |...|An |.Định lý 1.6. (Nguyên lý bù trừ) Cho A và B là các tập hữu hạn. Khiđó ta có:|A ∪ B| = |A| + |B| − |A ∩ B|.Chứng minh. Ta có:A =(A ∩ B) ∪ (A \ (A ∩ B))B =(A ∩ B) ∪ (B \ (A ∩ B))A ∪ B =(A ∩ B) ∪ (A \ (A ∩ B)) ∪ (B \ (A ∩ B)).Các vế phải ở ba đẳng thức trên là hợp của các tập đôi một rời nhau. Vìvậy theo nguyên lý cộng ta có:|A| =|A ∩ B| ∪ |A \ (A ∩ B)||B| =|A ∩ B| ∪ |B \ (A ∩ B)||A ∪ B| =|A ∩ B| ∪ |A \ (A ∩ B)| ∪ |B \ (A ∩ B)|.Theo Hệ quả 1.1 ta có: |A ∪ B| = |A| + |B| − |A ∩ B|.Cũng bằng quy nạp ta nhận được kết quả tổng quát hơn sau đây:Định lý 1.7. Giả sử A1 , A2 , ..., An là các tập hữu hạn tùy ý. Khi đó:|A1 ∪ A2 ∪ ... ∪ An | =|Ai1 | −|Ai1 ∩ Ai2 | + . . . +1≤i1 ≤n(−1)k+11≤i1