Quan hệ tương đương và phân chia tập hợp

2

M. M. Shukhol

Sự tương đương bị hiểu sai
và phân vùng của tập hợp

Hãy thử tưởng tượng tất cả các mối quan hệ ngữ nghĩa đa dạng của từ “giai cấp”: “giai cấp công nhân”, “học sinh lớp 10”, “kαιota lớp 1”, “lớp động vật có vú”… Cho dù những mối quan hệ này có vẻ khác nhau như thế nào, thì từ “giai cấp” trong mọi trường hợp đều có cùng một nguồn gốc - nó luôn gắn liền với việc phân loại hoặc phân chia bất kỳ tập hợp nào thành các lớp rời rạc. Khái niệm “giai cấp” và nhiều phân khu của nó (họ, loại, chủng loại, loài, giống, chi, chủng loại, v.v.) được sử dụng rộng rãi trong mọi lĩnh vực hoạt động của con người. Ví dụ, khi chúng ta cần nghiên cứu các đối tượng của một tập hợp liên quan đến một số thuộc tính của chúng, chúng ta cố gắng chia tập hợp này thành các lớp sao cho tất cả các phần tử của một lớp hoạt động theo cùng một cách đối với các thuộc tính có liên quan với nhau, và sau đó có thể nghiên cứu toàn bộ lớp đối tượng dựa trên một trong các đại diện của nó.

Do đó, sinh học không nghiên cứu từng loài thực vật mà chia tất cả các loài thực vật thành các lớp, họ, chi và loài, để khi nghiên cứu, chẳng hạn như họ logic, một bông hoa được xây dựng như một đại diện của cả một họ (hoặc loài). Khi nghiên cứu một lớp thông qua đại diện của nó, người ta thường cố gắng chọn lớp đơn giản nhất theo quan điểm của các thuộc tính khác (hiện tại chúng tôi không quan tâm). Mỗi người trong chúng ta đã nhiều lần sử dụng cơ hội này, chẳng hạn như với các phương trình lời giải, thay thế phương trình này bằng phương trình khác, đơn giản hơn nhưng có cùng gốc, nghĩa là nằm trong lớp phương trình tương đương với phương trình đã cho.

Để phân chia một tập hợp, nghĩa là phân chia các phần tử của nó thành các lớp sao cho mỗi phần tử thuộc một và chỉ một lớp, người ta thường sử dụng các đặc điểm khác nhau vốn có trong các phần tử của một tập hợp nhất định. Ví dụ: các đối tượng được hiển thị trong Hình 1.

4

có các quan hệ bằng nhau (về số, hình, hàm số), quan hệ “nhiều hơn” và “nhỏ hơn” đối với các số, quan hệ chia hết cho số nguyên, quan hệ song song và vuông góc đối với đường thẳng và đa giác. Trong cuộc sống đời thường, các mối quan hệ giữa con người với nhau rất phổ biến: quan hệ thâm niên, họ hàng, láng giềng, quan hệ cộng sự, cùng một dân tộc, cùng nghề nghiệp.

Bây giờ hãy xem xét kỹ hơn một mối quan hệ, ví dụ, mối quan hệ bằng nhau. Các đẳng thức số là đúng (đúng) và không chính xác (sai). Ví dụ: đẳng thức 5 = 5 là đúng nhưng 5 = 2 là sai. Nếu $x_1$ và $x_2$ là các số chưa biết thì đẳng thức $x_1 = x_2$ (câu “$x_1$ bằng $x_2$”) không có ý nghĩa cụ thể: nó phụ thuộc vào “ẩn số” $x_1, x_2$, là hàm của chúng: đối với mỗi giá trị số cụ thể $x_1, x_2$ nó sẽ đúng hoặc sai.

Trong trường hợp tổng quát, chúng ta sẽ gọi mối quan hệ nhị phân (hoặc nhị phân *) trên tập hợp $M$ là một câu lệnh về các phần tử của tập hợp $M$, phụ thuộc vào hai biến và chuyển thành câu lệnh đúng hoặc sai khi thay thế các biến của bất kỳ phần tử cụ thể nào từ $M$ vào đó. Nói chung, mối quan hệ được viết là $x_1\Theta x_2$ ($x_1 = x_2, x_1 < x_2, x_1 \parallel x_2, x_1 \perp x_2$, v.v.). Thường thì “thái độ $x_1\Theta x_2$” được gọi đơn giản là “thái độ $\Theta$”. Ví dụ: cùng với “quan hệ $x_1 = x_2$” chúng ta nói là “quan hệ bình đẳng”. Các thuật ngữ “quan hệ trật tự”, “quan hệ lân cận”… cũng có ý nghĩa tương tự. Nếu mối quan hệ $a\Theta b$ là đúng thì người ta cũng nói rằng $a$ và $b$ có liên quan với nhau bởi mối quan hệ $\Theta$ hoặc nằm trong mối quan hệ $\Theta$. Nếu mối quan hệ $\Theta$ có tính chất là tính đúng của $a\Theta b$ luôn bao hàm tính đúng của $b\Theta a$ thì nó được gọi là “đối xứng”. (Trong phần tiếp theo, đôi khi chúng ta sẽ gọi một cách đối xứng là “thuộc tính 1.”) Ví dụ, quan hệ song song và vuông góc của các đường thẳng là đối xứng, nhưng quan hệ < trên tập hợp số thực là không đối xứng (5 < 8 là đúng và 8 < 5 là sai).

Mối quan hệ $\Theta$ trên tập $M$ được gọi là reflexin (“thuộc tính 2”). nếu $a\Theta a$ đúng với bất kỳ phần tử $a$ nào của $M$ và chuyển tiếp (“thuộc tính 3”) nếu chân lý của $a\Theta b$ và $b\Theta c$ kéo theo chân lý của $a\Theta c$. Ví dụ, quan hệ đẳng thức của các số là phản xạ và bắc cầu, quan hệ vuông góc của các đường thẳng không phản xạ và không bắc cầu, và quan hệ “nhỏ hơn” đối với các số là bắc cầu, nhưng không phản xạ.

Vấn đề. Tìm ra tính chất nào trong số các tính chất 1-3 có quan hệ chia hết cho các số nguyên, quan hệ “giao nhau” (nghĩa là sẽ có một điểm chung) cho các đường thẳng và quan hệ lân cận đối với con người.

Bệnh tương đương

Bây giờ chúng ta hãy quay lại câu hỏi mà chúng ta quan tâm: những mối quan hệ nào, được xác định trên một tập hợp nhất định $M$, tạo ra phân vùng tập hợp này thành các lớp? Nói cách khác, các mối quan hệ $\Theta$ phải có những thuộc tính nào, theo đó tập hợp $M$ có ​​thể được chia thành các lớp rời rạc sao cho

1. bất kỳ hai phần tử nào (khác hoặc giống nhau) từ cùng một lớp đều nằm trong mối quan hệ $\Theta$,
2. không có hai phần tử nào từ các lớp khác nhau có trong mối quan hệ $\Theta$?

Đối với câu hỏi này đáp số theo dõi

Định lý. Mối quan hệ $\Theta$ trên tập hợp $M$ có thể và chỉ có thể tạo ra một phân vùng của tập hợp $M$ khi nó phản xạ, đối xứng và bắc cầu.

5

Bằng chứng. Cho quan hệ $\Theta$ tạo ra một phân vùng của tập hợp $M$, nghĩa là các tập hợp $M$ có ​​thể được phân chia thành các lớp thỏa mãn điều kiện 1) và 2). Dù chúng ta lấy phần tử nào $a$, nó đều thuộc về một lớp nào đó trong phân vùng của chúng ta. Theo 1), $a$ liên hệ với $\Theta$ với chính nó: $a\Theta a$ là đúng, vì vậy $\Theta$ là phản xạ. Ngoài ra, nếu $a\Theta b$ đúng thì như sau từ 1)–2), các phần tử $a$ và $b$ thuộc cùng một lớp phân vùng. Khi đó từ 1) suy ra $b\Theta a$ cũng đúng. Điều này có nghĩa là với bất kỳ $a, b \in M^*$) nào từ $a\Theta b$ đều theo sau $b\Theta a$, tức là mối quan hệ $\Theta$ là đối xứng.

Không đọc dữ liệu cho đến khi bạn chắc chắn rằng mối quan hệ $\Theta$ là bắc cầu!

Do đó, nếu mối quan hệ $\Theta$ tạo ra một phân vùng của tập hợp $M$ thì $\Theta$ là phản xạ, đối xứng và bắc cầu: các thuộc tính 1–3 là cần thiết để $\Theta$ tạo ra một phân vùng của tập hợp $M$.

Bây giờ đã rõ tại sao chúng ta không thể chia một người thành các nhóm người tôn trọng lẫn nhau và tại sao mối quan hệ vuông góc không gây ra sự phân chia các mặt phẳng thẳng. Mối quan hệ giữa “sự phản xạ” và độ vuông góc không mang tính bắc cầu (và không phản xạ).

Bây giờ chúng ta hãy chứng minh đủ tính chất 1–3. Giả sử $\Theta$ có các thuộc tính 1–3 và $a$ là phần tử tùy ý của tập hợp $M$. Chúng ta hãy biểu thị bằng $M_a$ lớp (tập hợp) của tất cả các phần tử như vậy $x$ từ $M$ trong đó $a\Theta x$ là đúng:

$$M_a = \{x \mid a\Theta x \text{ — истинно}\}.$$

Bằng cách này, chúng ta sẽ có được một tập hợp các lớp nhất định. Vì theo thuộc tính 1 $a\Theta a$ là đúng, nên $a \in M_a$ (theo định nghĩa của lớp $M_a$) và do đó, mỗi phần tử của tập hợp $M$ thuộc về ít nhất một trong các lớp kết quả. Hãy chứng minh rằng hai lớp bất kỳ $M_a, M_b$ trùng nhau hoặc không cắt nhau. Thật vậy, nếu $M_a$ và $M_b$ có ít nhất một phần tử chung $c$, thì $a\Theta c$ và $b\Theta c^*$. Theo thuộc tính 2, từ $b\Theta c$ nó theo sau $c\Theta b$, và từ $a\Theta c$ và $c\Theta b$, theo thuộc tính 3, chúng ta thu được $a\Theta b$. Vậy $a\Theta b$ là đúng. Bây giờ chúng ta lấy một phần tử tùy ý $d$ từ lớp $M_b$. Theo định nghĩa của lớp $M_b$ đúng $b\Theta d$ và theo thuộc tính 3 từ $a\Theta b$ và $b\Theta d$ thì nó tuân theo $a\Theta d$; có nghĩa là $d \in M_a$. Vì vậy, nếu $d \in M_b$, thì $d \in M_a$. Người ta chứng minh tương tự rằng từ $d \in M_a$ nó dẫn đến $d \in M_b$ (bạn hãy tự suy luận tương ứng). Điều này chứng tỏ rằng $M_a = M_b$, tức là các lớp có ít nhất một phần tử chung, trùng khớp. Do đó, mỗi phần tử của tập hợp $M$ được chứa trong một số lớp và các lớp khác nhau không giao nhau. Điều này có nghĩa là chúng ta có một phân vùng của tập hợp $M$. Hãy chứng minh rằng phân vùng này là thực và dẫn đến hệ thức $\Theta$, tức là các điều kiện 1)—2) được thỏa mãn. Đặt các phần tử $a$ và $b$ trong cùng một lớp. Vì $a \in M_a$, điều này có nghĩa là $b \in M_a$ (ở dạng trước cả hai được cam kết đều bằng nhau!), tức là $a\Theta b$. Vì vậy, bất kỳ hai phần tử nào trong cùng một lớp đều có quan hệ $\Theta$: điều kiện 1) đều được thỏa mãn. Bây giờ, hãy đặt $a$ và $b$ là hai phần tử tùy ý từ các lớp khác nhau, sao cho $M_a \neq M_b$. Nếu có $a\Theta b$, thì điều này có nghĩa là $b \in M_a$, tức là các lớp $M_a$ và $M_b$ có ít nhất một phần tử $b$. Nhưng sau đó, theo những gì đã được chứng minh ở trên, nó sẽ là $M_a = M_b$, mâu thuẫn với các điều kiện. Điều này có nghĩa là $a\Theta b$ là sai, nghĩa là các phần tử từ các lớp khác nhau không nằm trong mối quan hệ $\Theta$ (thỏa mãn điều kiện 2). Định lý đã được chứng minh.

Khi sửa tập hợp $M$, các phần tử chứa trong một lớp thường được gọi là quan hệ tương đương và các lớp của phân vùng kết quả được gọi là lớp tương đương.

*) Dấu ∈ được đọc là “thuộc về”: $u \in M$ có nghĩa là $a$ là một phần tử của tập hợp $M$.

6

Bây giờ định lý được chứng minh ở trên có thể được phát biểu ngắn gọn hơn: quan hệ $\Theta$ trên tập $M$ có thể và chỉ có thể tạo ra một phân hoạch của tập hợp $M$ khi nó là một quan hệ tương đương.

Vì vậy, nếu chúng ta muốn tìm hiểu xem liệu quan hệ $\Theta$ có tạo ra sự phân chia của tập hợp $M$ nào đó hay không, thì chúng ta cần kiểm tra xem quan hệ $\Theta$ có ​​phải là quan hệ tương đương trên $M$ hay không.

Ví dụ, tập hợp tất cả các đường tròn của một mặt phẳng rơi vào lớp đường tròn đồng tâm, vì mối quan hệ đồng tâm của các đường tròn là phản xạ, đối xứng và bắc cầu. (Đồng thời, chúng tôi tự nhiên tin rằng

Cơm. 3.

mọi đường tròn đều đồng tâm với chính nó.) Người ta cũng xác minh rất đơn giản rằng mối quan hệ đồng dạng của các tam giác là phản xạ, đối xứng và bắc cầu. Do đó, tập hợp tất cả các tam giác được chia thành các lớp tam giác đồng dạng.

Hãy lấy một ví dụ ít rõ ràng hơn. Đặt $Q$ là tập hợp tất cả các phân số có dạng $\frac{a}{b}$, trong đó $a, b$ là số nguyên và $b \neq 0$. Đối với mỗi phân số $\frac{a}{b}$, chúng tôi xác định lớp $Q_{a,b}$, gán phân số $\frac{c}{d}$ cho lớp này khi và chỉ khi $ad = bc$. Kết quả có phải là sự chia tất cả các phân số thành các lớp rời rạc không?

Chúng ta đã xác định một số quan hệ $\Theta$ trên tập $Q$:

$$\frac{a}{b} \Theta \frac{c}{d}$$ nếu và chỉ khi $ad = bc.$

Chúng ta hãy tìm hiểu xem $\Theta$ có phải là quan hệ tương đương hay không.

1. Phản ánh. Đối với mọi phân số $\frac{a}{b} \frac{a}{b} \Theta \frac{a}{b}$, vì $ab = ba$.

2. Sự đối xứng. Nếu $\frac{a}{b} \Theta \frac{c}{d}$ thì $ad = bc$ hoặc $cb = da$. Đẳng thức cuối cùng có nghĩa là $\frac{c}{d} \Theta \frac{a}{b}$.

3. Tính chuyển tiếp. Đặt $\frac{a}{b} \Theta \frac{c}{d}$ và $\frac{c}{d} \Theta \frac{e}{f}$, tức là $ad = bc$ và $cf = de$. Nhân đẳng thức cuối cùng với $f$ và $b$, chúng ta nhận được:

$$adf = bcf, \ bcf = bde.$$

Do đó, chúng ta có $adf = bde$ và $af = be$ (có thể rút ngắn thành $d$, vì $d \neq 0$!). Nhưng $af = be$ chỉ có nghĩa là $\frac{a}{f} \Theta \frac{e}{f}$.

Do đó, $\Theta$ là một quan hệ tương đương và do đó tập hợp tất cả các phân số rơi vào các lớp rời rạc của các phân số tương đương (hoặc, như người ta nói ở trường, có độ lớn bằng nhau). Vì vậy, khi có quan hệ tương đương trên một tập hợp nhất định, chúng ta có thể chia tập hợp này thành các lớp. Nhưng bạn cũng có thể làm ngược lại: đầu tiên chia tập hợp thành các lớp, sau đó xác định mối quan hệ tương đương, xem xét theo định nghĩa hai phần tử là tương đương khi và chỉ khi chúng thuộc cùng một lớp của phân vùng được đề cập.

Ví dụ, đây là cách thể hiện thái độ “là bạn cùng lớp”: đầu tiên, trẻ mới đến trường được chia (gần như tùy tiện) thành các lớp, sau đó những trẻ học cùng lớp được gọi là bạn cùng lớp.

Có thể tiết kiệm tiền không?

Nếu chúng ta thường xuyên phải kiểm tra xem một quan hệ đã cho có tính phản xạ, đối xứng và bắc cầu hay không thì đương nhiên

8

một tập hợp các phi hành gia trên tàu vũ trụ Voskhod và Voskhod-2, một tập hợp “các phần của thế giới” (không có Nam Cực!), v.v. Từ danh sách nhỏ này, rõ ràng là một lớp bao gồm các tập hợp có bản chất rất khác nhau và điểm chung duy nhất cho tất cả chúng là chúng đều có sức mạnh ngang nhau, nghĩa là, bất kỳ lớp nào trong số chúng đều có thể được ánh xạ duy nhất lên bất kỳ lớp nào khác. Bây giờ chúng ta sẽ hình thành định nghĩa về số tự nhiên: bằng số tự nhiên, chúng ta gọi bất kỳ lớp nào gồm các tập hữu hạn mạnh như nhau.

Lúc đầu, một định nghĩa như vậy có thể khá đáng ngạc nhiên: một thứ có vẻ đơn giản như số tự nhiên lại được định nghĩa thông qua một cái gì đó cồng kềnh và khó nhìn thấy - thông qua toàn bộ lớp các tập hợp! Tuy nhiên, nếu bạn thực sự suy nghĩ về định nghĩa này và làm quen với nó, bạn sẽ đồng ý rằng nó thực sự phản ánh “bản chất định lượng” của khái niệm số tự nhiên. Định nghĩa này bộc lộ cái gọi là sự trừu tượng của việc nhận dạng: đầu tiên chúng ta chia tất cả các tập hợp hữu hạn thành các lớp gồm các tập hợp bằng nhau, sau đó chúng ta “xác định” tất cả các tập hợp thuộc một lớp và coi kết quả của việc nhận dạng này là một số tự nhiên nhất định.

Vì mỗi loại tập hợp đẳng thức được xác định hoàn toàn bởi bất kỳ đại diện nào của nó, nên chúng ta có thể nói về một số tự nhiên được xác định bởi bất kỳ tập hợp nào của một lớp cho trước. Số được xác định bởi tập hợp $M$ được ký hiệu là $|M|$ và được gọi là thứ tự hoặc số lượng của tập hợp $M$. Đối với các số tự nhiên, bạn có thể giới thiệu một hệ thống ký hiệu không liên quan đến các bộ cụ thể. Tất nhiên, điều này có thể được thực hiện theo những cách khác nhau. Trong lịch sử, trường hợp này là như vậy: các dân tộc khác nhau có hệ thống ký hiệu và đặt tên số tự nhiên khác nhau. (Điều này được thảo luận chi tiết hơn trong bài viết “Hệ thống số” của I.M. Yaglom, xem «Kvant», số 6, 1970). Tuân thủ hệ thống ký hiệu và đặt tên được chấp nhận rộng rãi hiện nay, chúng ta có thể nói rằng số 1 (một) là lớp của một tập hợp bằng tập hợp thủ đô của Liên Xô, số 2 (hai) là lớp của một tập hợp bằng với bộ mắt người, v.v. Bằng cách thêm một phần tử nữa vào bất kỳ tập hợp hữu hạn nào, chúng ta sẽ có được một tập hợp mới không bằng tập hợp ban đầu. Thực hiện quá trình này, chúng ta sẽ thu được một dãy vô hạn các tập hợp không bằng nhau và các số tự nhiên được xác định bởi nó:

1, 2, 3, …

Rashchina nói rằng số hữu tỉ là một phân số có dạng $\frac{a}{b}$, trong đó $a, b$ là số nguyên và $b \neq 0$. Tuy nhiên, định nghĩa như vậy không đầy đủ, vì nó không dẫn đến ngay lập tức liệu các số $1/2$ và $3/6$ có bằng nhau hay không, chẳng hạn. Do đó, cần phải cộng ngay: các số hữu tỷ $\frac{a}{b}$ và $\frac{c}{d}$ bằng nhau khi và chỉ khi $ad = bc$. Kết quả là, một số hữu tỷ không chỉ là một phân số, mà là cả một lớp phân số. Vì vậy, khái niệm số hữu tỉ được giới thiệu kỹ hơn như sau.

Xem xét tập hợp $Q$ của tất cả các phân số và xác định trên $Q$ mối quan hệ $\Theta$ bằng cách đặt $\frac{a}{b} \Theta \frac{c}{d}$ khi và chỉ khi $ad = bc$. Ở trên chúng ta đã chỉ ra rằng $\Theta$ là một quan hệ tương đương và do đó, tập hợp $Q$ sẽ phát triển thành các lớp rời rạc. Chúng tôi sẽ gọi hai phân số bất kỳ của cùng một lớp của phân vùng được chỉ định là tích lũy. Bây giờ chúng ta có thể xây dựng một định nghĩa: số hữu tỉ là bất kỳ lớp phân số tương đương nào. Sau mọi điều đã nói ở trên về định nghĩa số tự nhiên, chúng ta định nghĩa số hữu tỉ là một lớp phân số một cách rất đơn giản.