Collections of Sets, Problem 3

Solution part (c)

Reflexive

Let X be a subset of the integers. Then \(X \oplus X = \emptyset\), which is finite. So \(X \sim X \).

Symmetric

Let A and B be subsets of the integers. Suppose that \(A \sim B \). Then Then \(A \oplus B\) is finite. But \(A \oplus B = (A - B) \cup (B - A) = (B - A) \cup (A - B) = B \oplus A \). So \(B \oplus A \) is also finite. So \(B \sim A \).

Transitive

Let A, B, and C be sets. Suppose that \(A \sim B \) and \(B \sim C \). Then \(A \oplus B\) and \(B \oplus C\) are finite. This means that \((A - B) \cup (B - A)\) and \((B - C) \cup (C - B)\) are finite. So (A-B), (B-A), (B-C) and (C-B) are all finite.

Since (A-B), (B-A), (B-C) and (C-B) are all finite, \((A-B) \cup (B - C)\) and \((B-A) \cup (C - B)\) are both finite.

From part (b), we know that \((A - C) \subseteq (A-B) \cup (B - C)\) and \((C - A) \subseteq (B-A) \cup (C - B)\). So (A-C) and (C-A) must be finite So \(A \oplus C = (A - C) \cup (C - A)\) must be finite. This means that \(A \sim C\), which is what we needed to show.