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.