T.7 · Set images, equivalence relations and logical negation

Chuẩn bị GRE đại học. Mục tiêu cục bộ nằm trong phạm vi ETS đã xem xét; đây là giảng dạy nguyên bản, không phải bài thi chính thức hoặc dự đoán điểm số.

Kiến thức nền: Các phép toán tập hợp, lượng từ, hàm số và chứng minh cơ bản.

• Chứng minh các đẳng thức tập ảnh và phân biệt inclusion (tập con) với equality (bằng nhau)
• Kiểm tra tính phản xạ, đối xứng và bắc cầu với các trường hợp cụ thể
• Phủ định các suy luận và mệnh đề chứa lượng từ mà không thay đổi phạm vi của chúng

preimage: Tập hợp các giá trị đầu vào mà các giá trị đầu ra của chúng nằm trong một tập đích đã chỉ định.

quan hệ tương đương: Một quan hệ thỏa mãn tính phản xạ, đối xứng và bắc cầu.

Với f:X→Y và A⊆X, ảnh f(A) bao gồm tất cả các giá trị f(a) với a thuộc A. Một điểm nằm trong f(A∪B) khi và chỉ khi nó đến từ A hoặc B, do đó f(A∪B)=f(A)∪f(B). Nếu A⊆B, thì f(A)⊆f(B). Chỉ có f(A∩B)⊆f(A)∩f(B) là luôn đúng: cùng một giá trị có thể xuất phát từ các đầu vào khác nhau. Sử dụng f(x)=x², A={−1}, B={1}; ảnh bên trái là tập rỗng trong khi giao của ảnh bên phải là {1}.

Ảnh ngược hoạt động theo cách khác. Với C⊆Y, ký hiệu f⁻¹(C) ở đây chỉ tập hợp tất cả các đầu vào được ánh xạ vào C, ngay cả khi f không có hàm nghịch đảo. Thuộc về hai ảnh ngược nghĩa là cùng một đầu vào ánh xạ vào cả hai tập đích. Do đó, ảnh ngược bảo toàn hợp, giao và phần bù so với miền/mã miền đã cho. Đừng áp dụng định lý về ảnh ngược sang ảnh trực tiếp. Nếu f là đơn ánh, giao của các ảnh sẽ trở nên bằng nhau, vì các giá trị bằng nhau khi đó buộc phải có chung một đầu vào.

Một quan hệ R trên X là phản xạ khi xRx với mọi x, đối xứng khi xRy suy ra yRx, và bắc cầu khi xRy và yRz suy ra xRz. Cả ba tính chất này tạo thành một quan hệ tương đương; các lớp tương đương phân hoạch X. Trên số nguyên, xRy khi x và y có cùng dư khi chia cho 4 tạo ra bốn lớp. Quan hệ |x−y|≤1 là phản xạ và đối xứng nhưng không bắc cầu: 0R1 và 1R2 trong khi 0 không liên quan đến 2. Chỉ kiểm tra sơ đồ hoặc hai tính chất là chưa đủ.

Kém implication P⇒Q chỉ sai khi P đúng và Q sai. Do đó phủ định của P⇒(Q∧R) là P∧(¬Q∨¬R), chứ không phải ¬P⇒(¬Q∧¬R). Phủ định “mọi x đều có tính chất A” cho “tồn tại x không có A”; phủ định “tồn tại x” cho “mọi x đều không”. Một ví dụ phản chứng có thể bác bỏ một khẳng định phổ quát, trong khi các ví dụ không thể chứng minh nó. Các lượng từ giữ nguyên thứ tự khi bị phủ định từng cái: ¬(∀x∃y S(x,y)) là ∃x∀y ¬S(x,y).

Giả sử f ánh xạ cả a và b đến nhãn L. Với A={a}, B={b}, ta có f(A∩B)=∅ nhưng f(A)∩f(B)={L}. Đối với xRy được định nghĩa bởi x=y hoặc x=−y trên R, tính phản xạ và đối xứng suy ra trực tiếp, và hai lần đổi dấu vẫn cho z=±x, chứng minh tính bắc cầu. Các lớp là {x,−x}, với {0} là một tập đơn. Một phát biểu sai "mọi file lưu trữ đều có hash" có nghĩa là ít nhất một file lưu trữ không có hash; nó không có nghĩa là tất cả các file đều thiếu hash.

f⁻¹(C) có thể chỉ tập tiền ảnh mà không cần hàm ngược. Một quan hệ phản xạ, đối xứng vẫn có thể không thỏa mãn tính bắc cầu. Hãy phủ định toàn bộ phát biểu trước rồi mới rút gọn các phần bên trong.

Chứng minh $f(A\cap B)\subseteq f(A)\cap f(B)$. Đưa ra một ví dụ về inclusion chặt chẽ. Dưới giả thiết bổ sung nào về f thì dấu bằng xảy ra với mọi A và B?

Giải mẫu

Nếu $y=f(x)$ với $x\in A\cap B$, thì x thuộc mỗi tập, do đó y thuộc mỗi ảnh. Để chứng minh tính chặt chẽ, ánh xạ a, b phân biệt khác nhau thành cùng một c và lấy $A=\{a\}$, $B=\{b\}$. Ảnh bên trái là tập rỗng và giao của ảnh bên phải là $\{c\}$. Nếu f là đơn ánh và $y=f(a)=f(b)$ với $a\in A,b\in B$, tính đơn ánh cho a=b trong giao, chứng minh sự bao hàm ngược. Ngược lại, ví dụ tập một phần tử cho thấy dấu bằng với mọi cặp buộc f phải là đơn ánh.

Trên số nguyên, định nghĩa $aRb$ khi $a-b$ chia hết cho 4. Chứng minh đây là quan hệ tương đương và mô tả mỗi lớp. Phủ định: “Với mỗi số nguyên n, tồn tại số nguyên m lớn hơn n có tính chất P.”

Kiểm tra sau khi đã làm

Tính phản xạ sử dụng $a-a=0$; tính đối xứng sử dụng bội âm của 4; tính bắc cầu sử dụng tổng của hai bội như vậy. Các lớp là bốn dư số modulo 4; lớp của a là $a+4\mathbb Z$. Phủ định là: tồn tại số nguyên n sao cho mọi số nguyên m lớn hơn n đều không có P. Tương đương $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. Nó không khẳng định P sai với mọi số nguyên, cũng không khẳng định m ≤ n với mọi m.