Đại số của tập hợp
Nguyễn Phạm Duy Bảo - Thành viên Chuyên san EXP
- Đại sô tập hợp định nghĩa tính chất và luật của những tập hợp, những phép toán thuộc lý thuyết tập hợp về phép hợp, phép giao và phép lấy phần bù cũng như những quan hệ của đẳng thức tập hợp và bao hàm thức tập hợp. Nó cũng cung cấp những phương pháp có hệ thống để đánh giá các biểu thức, thực hiện các tính toán liên quan đến các quan hệ và phép toán trên tập hợp.
Mọi tập hợp của tập hợp đóng trong các phép toán tập hợp hình thành nên đại số Boolean với phép toán hợp trở thành phép hợp, phép toán giao trở thành phép giao và phép lấy phần bù trở thành phép lấy bù tập hợp.
Nguyên tắc cơ bản:
- Đại số tập hợp là một lý thuyết tập hợp tương tự như đại số các con số. Giống như tính chất số học của phép cộng và phép nhân là tính kết hợp và giao hoán, thì với phép hợp và giao của tập hợp. Còn với quan hệ số học “nhỏ hơn hoặc bằng” là phản xạ, phản đối xứng và bắc cầu, thì chúng ta cũng có tương tự ở những quan hệ của tập con.
- Tính đại số của lý thuyết tập hợp là về các phép toán là về phép hợp, phép giao và lấy phần bù và những quan hệ của đẳng thức và bao hàm thức. Về những giới thiệu cơ bản của tập hợp, xem bài viết về các tập hợp; về những giải thích cụ thể và đầy đủ hơn, xem lý thuyế tập hợp ngây thơ; và về những nghiên cứu về tiên đề chính xác hơn, xem lý thuyết tập hợp tiên đề.
Những nguyên tắc cở bản về các luật của đại số tập hợp:
- Những phép toán hai ngôi về hợp, giao của tập hợp thỏa mãn nhiều đồng nhất thức. Nhiều đồng nhất thức hay “luật” ấy được đặt cho những cái tên khá ổn.
- Luật giao hoán:
$$A\mathop{\cup }^{}B=B\mathop{\cup }^{}A$$
$$A\mathop{\cap }^{}B=B\mathop{\cap }^{}A$$
- Luật kết hợp:
$$\left( A\mathop{\cup }^{}B \right)\mathop{\cup }^{}C=A\mathop{\cup }^{}\left( B\mathop{\cup }^{}C \right)$$
$$\left( A\mathop{\cap }^{}B \right)\mathop{\cap }^{}C=A\mathop{\cap }^{}\left( B\mathop{\cap }^{}C \right)$$
- Luật phân phối:
$$A\mathop{\cup }^{}\left( B\mathop{\cap }^{}C \right)=\left( A\mathop{\cup }^{}B \right)\mathop{\cap }^{}\left( A\mathop{\cup }^{}C \right)A\mathop{\cap }^{}\left( B\mathop{\cup }^{}C \right)=\left( A\mathop{\cap }^{}B \right)\mathop{\cup }^{}\left( A\mathop{\cap }^{}C \right)$$
- Giữa phép hợp và giao của tập hợp với phép cộng và nhân của số có mối tương quan chặt chẽ với nhau. Giống như phép cọng và nhân, phép toán trên hợp và giao cũng có giao hoán và kết hợp, và phép giao phân phối với phép hợp. Tuy nhiên, không gióng như phép cộng và phép nhân, phép hợp cũng phân phối với nhau.
- Hai cặp luật được thêm vào có liên quan đến hai tập hợp đặc biệt được gọi là tập rỗng $\varnothing ~$và tập vũ trụ U; cùng với phép lấy phần bù. Tập rỗng là tập không chứa phần tử nào, tập vũ trụ là tập chứa tất cả các phần tử có thể (trong trường hợp đặc biệt).
- Luật đồng nhất:
$$A\mathop{\cup }^{}\varnothing =A$$
$$A\mathop{\cap }^{}U=A$$
- Luật lấy bù:
$$A\mathop{\cup }^{}{A}'=U$$
$$A\mathop{\cap }^{}{A}'=\varnothing $$
- Luật đồng nhất ( cùng với luật giao hoán) nói rằng, cũng giống như số 0 và 1 trong phép cộng và nhân, $\varnothing $ và U là những phần tử đơn vị của phép hợp và phép giao.
- Không giống như phép cộng và nhân, phép hợp và giao không có những phần tử nghịch đảo. Tuy nhiên những luật lấy phần bù cho chúng ta các tính chất cơ bản có đôi nét giống với nghịch đảo, đó là phép toán một ngôi của phép lấy bù tập hợp.
- Năm tính chất ghép cặp có trước của các luật – tính giao hoán, kết hợp, phân phối, đồng nhất và luật lấy bù – hoàn thiện tất cả về đại số tập hợp, có nghĩa là mọi mệnh đề có hiệu lực trong đại số tập hợp đều có thể được suy ra từ các luật trên.
- Chú ý rằng nếu luật bù bị suy yếu với với quy định ${{\left( {{A}'} \right)}^{'}}=A$, thì đây chính là đại số tuyến tính của logic mệnh đề.
Nguyên lí đối ngẫu:
- Một trong những đồng nhất thức được phát biểu ở trên là một trong những cặp đồng nhất mà có thể được chuyển đổi thành cái khác bởi sự tráo đổi $\mathop{\cup }^{}$ và $\mathop{\cap }^{}$, $\varnothing $ và U cũng vậy.
- Đây là những ví dụ trong nguyên lý đối ngẫu của tập hợp – một tính chất cực kỳ quan trọng và mạnh của đại số tập hợp. Nguyên lý này khẳng định mọi phát biểu đúng về tập hợp, phát biểu hình thành bằng cách tráo đổi hợp và giao, hay U và $\varnothing $ và ngược lại cũng đúng. Một phát biểu được gọi là tự đối ngẫu nếu nó cũng giống như phát biểu đối ngẫu của nó.
Một số luật bổ sung cho phép hợp và giao của tập hợp:
- Những mệnh đề theo sau đây phát biểu sáu luật quan trọng của đại số tập hợp, kéo theo phép hợp và giao.
MỆNH ĐỀ 3: cho tập con bất kỳ A và B của tập vũ trụ U, những đẳng thức sau đây hàm chứa:
Luật lũy đẳng (giá trị không thay đổi khi nó tự nhân lên):
$$A\mathop{\cup }^{}A=A$
$$A\mathop{\cap }^{}A=A$$
- Luật làm trội:
$$A\mathop{\cup }^{}U=U$$
$$A\mathop{\cap }^{}\varnothing =\varnothing $$
- Luật thu hút:
$$A\mathop{\cup }^{}\left( A\mathop{\cap }^{}B \right)=A$$
$$A\mathop{\cap }^{}\left( A\mathop{\cup }^{}B \right)=A$$
- Cũng như ghi chú trên, mỗi luật được phát biểu ở mệnh đề 3 có thể được suy ra từ năm luật ghép cặp cơ bản được phát biểu ở mệnh đề 1 và 2. Ví dụ như cách chứng minh bên dưới của luật lũy đẳng được minh họa bằng phép hợp.
$A\mathop{\cup }^{}A=\left( A\mathop{\cup }^{}A \right)\mathop{\cap }^{}U$ (luật đồng nhất của phép giao)
$=\left( A\mathop{\cup }^{}A \right)\mathop{\cap }^{}\left( A\mathop{\cup }^{}{A}' \right)~$(luật lấy bù của phép hợp).\[\]$=A\mathop{\cup }^{}\left( A\mathop{\cap }^{}{A}' \right)$ (luật phân phối của phép hợp với phép giao).
$=A\mathop{\cup }^{}\varnothing $ (luật bù của phép giao)
$=A$ (luật đồng nhất của phép hợp)
- Chứng minh sau đây minh họa sự đối ngẫu của phép chứng minh trên là phép chứng minh đối ngẫu của luật lũy đẳng với phép hợp, gọi là luật lũy đẳng của phép giao.
$A\mathop{\cap }^{}A=\left( A\mathop{\cap }^{}A \right)\mathop{\cap }^{}\varnothing $ luật đồng nhất của phép hợp
$=\left( A\mathop{\cap }^{}A \right)\mathop{\cup }^{}\left( A\mathop{\cap }^{}{A}' \right)~$luật lấy bù của phép giao
$=A\mathop{\cap }^{}\left( A\mathop{\cup }^{}{A}' \right)$ luật phân phối của phép giao với phép hợp
$=A\mathop{\cup }^{}U$ luật bù của phép hợp
$=A$luật đồng nhất của phép giao
- Phép giao có thể được biểu thị một cách khác dưới dạng thuật ngữ của tập hợp:
$$A\mathop{\cap }^{}B=A\backslash \left( A\backslash B \right)$$
Một vài luật bổ sung của phép lấy bù:
- Những mệnh đề sau đây phát biểu năm luật quan trọng hơn của đại số tập hợp, bao gồm phép lấy bù.
MỆNH ĐỀ 4: Cho A và B là hai tập con của tập vũ trụ U, khi đó:
- Luật De Morgan:
$${{\left( A\mathop{\cup }^{}B \right)}^{'}}={A}'\mathop{\cap }^{}{B}'{{\left( A\mathop{\cap }^{}B \right)}^{'}}={A}'\mathop{\cup }^{}{B}'$$
- Bù kép hay luật đối hợp:
$${{\left( {{A}'} \right)}^{'}}=A$$
- Luật bù cho tập vũ trụ và tập rỗng:
$${\varnothing }'=U$$
$${U}'=\varnothing$$
- Để ý rằng luật bù kép chính là tự đối ngẫu.
- Mênh đề tiếp theo, cũng là mệnh đề tự đối ngẫu, nói rằng phần bù của một tập hợp là một tập duy nhất thỏa mãn luật bù. Nói cách khác, phần bù là một đặc điểm của luật lấy bù.
MỆNH ĐỀ 5: cho A và B là hai tập con của tập vũ trụ U, khi đó:
- Tính duy nhất của phần bù:
- Nếu $A\mathop{\cup }^{}B=U,~v\grave{a}~A\mathop{\cap }^{}B=\varnothing ,~$ khi đó $~B={A}'$
Tính đại số của phép lồng (nhúng chìm):
- Những mệnh đề sau đây nói rằng phép lồng là một sắp thứ tự không hoàn toàn.
MỆNH ĐỀ 6: nếu A,B, C là những tập hợp thì sau đây ta có các ý:
- Phản xạ:
$$A\subseteq A$$
- Phản đối xứng:
$$A\subseteq B \, \text{và} \, B\subseteq A~ \, \text{khi và chỉ khi} \, A=B$$
- Bắc cầu:
$$\text{Nếu} \, A\subseteq B \, \text{và} \, B\subseteq C, \, \text{thì khi đó}\, A\subseteq C$$
- Mệnh đề sau đây nói rằng cho bất kỳ tập S, tập lũy thừa của S, được sắp xếp bởi phép lồng, là một lưới bị chặn, và do đó cùng với luật phân phối và luật bù bên trên, chúng biểu hiện thành đại số Boolean.
MỆNH ĐỀ 7: nếu A, B, và C là ba tập con của một tập S, khi đó có các ý sau:
- Tồn tại mọt phần tử nhỏ nhất và lớn nhất:
$$\varnothing \subseteq A\subseteq S$$
- Tồn tại sự tham gia:
$$A\subseteq A\mathop{\cup }^{}B$$
- Nếu $A\subseteq C~$ và $\grave{a}~B\subseteq C$, khi đó $A\subseteq C$
- Tồn tại sự giao nhau:
$$A\mathop{\cap }^{}B\subseteq A$$
- Nếu $C\subseteq A~$ và $\grave{a}~C\subseteq B$, khi đó $C\subseteq A\mathop{\cap }^{}B$
- Mệnh đề sau đây nói rằng phát biểu $A\subseteq B$ là tương đương với nhiều phát biểu khác nhau về phép hợp, giao và lấy bù.
MỆNH ĐỀ 8: cho hai tập bất kỳ là A và B, những mệnh đề sau đây là tương đương:
$$A\subseteq B$$
$$A\mathop{\cap }^{}B=A$$
$$A\mathop{\cup }^{}B=B$$
$$A\backslash B=\varnothing $$
$${B}'\subseteq {A}'$$
- Mệnh đề trên chỉ ra rằng quan hệ của những phép lồng tập hợp có thể được đặc trưng bởi mộ trong các thuật toán hợp và giao, có nghĩa là các khái niệm về phép lồng tập hợp là không cần thiết.
Tính đại số của tương quan phần bù:
- Sau đây là một danh sách nhiều đẳng thức khác nhau đáng quan tâm về quan hệ phần bù và hiệu trong lý thuyết tập hợp.
MỆNH ĐỀ 9: cho tập vũ trụ U bất kỳ với tập con A, B và C của U, nhưng đẳng thức sau đây bao gồm:
$$C\backslash \left( A\mathop{\cap }^{}B \right)=\left( C\backslash A \right)\mathop{\cup }^{}\left( C\backslash B \right)$$
$$C\backslash \left( A\mathop{\cup }^{}B \right)=\left( C\backslash A \right)\mathop{\cup }^{}\left( C\backslash B \right)$$
$$C\backslash \left( B\backslash A \right)=\left( A\mathop{\cap }^{}C \right)\mathop{\cup }^{}\left( C\backslash B \right)$$
$$\left( B\backslash A \right)\mathop{\cap }^{}C=\left( B\mathop{\cap }^{}C \right)\backslash A=B\mathop{\cap }^{}\left( C\backslash A \right)$$
$$\left( B\backslash A \right)\mathop{\cup }^{}C=\left( B\mathop{\cup }^{}C \right)\backslash \left( A\backslash C \right)$$
$$A\backslash A=\varnothing $$
$$\varnothing \backslash A=\varnothing $$
$$A\backslash \varnothing =A$$
$$B\backslash A={A}'\mathop{\cap }^{}B$$
$${{\left( B\backslash A \right)}^{'}}=A\mathop{\cup }^{}{B}'$$
$$U\backslash A={A}'$$
$$A\backslash U=\varnothing $$
Đây là một trong các sản phẩm của nhóm chuyên san EXP, trực thuộc CLB học thuật, khoa Toán - Tin học, Đại học Khoa học Tự nhiên, Tp. Hồ Chí Minh. Trong hơn 3 năm qua nhóm chúng tôi đã thực hiện các dự án quy mô nhỏ nhằm cải thiện tình trạng giáo dục Việt Nam, hút lại chất xám từ nước ngoài trở về, và hiện đại hóa các công cụ Toán học trong nước.
Bài viết này được dịch từ http://en.wikipedia....Algebra_of_sets
Bài viết đã được chỉnh sửa nội dung bởi hoangtrong2305: 14-11-2014 - 23:37
