Consider a powerset $P(X)$ of a set $X$. On $P(X)$, we define two equivalence relations. The first is defined as "$S+T$ is a finite set". (where $S$ and $T$ are subsets of $X$, and $+$ denotes symmetric difference). The second is defined as "there exist finite sets $F$ and $G$ such that $(S \cup F) - G = T$". How does one prove that these are the same relation?
Asked
Active
Viewed 35 times
0
-
You have to prove that each equivalence relation implies the other. – Chaotic Good Jan 30 '21 at 20:32
1 Answers
3
HINT: If $S+T$ is finite, let $F=T\setminus S$ and $G=S\setminus T$; then
$$(S\cup F)\setminus G=(S\cup T)\setminus(S\setminus T)=T\,,$$
and you need only verify that $F$ and $G$ are finite. Conversely, if there are finite $F$ and $G$ such that $(S\cup F)\setminus G=T$, show that $S+T\subseteq F\cup G$; use the fact that if $x\in S+T$, then either $x\in S\setminus T$, or $x\in T\setminus S$.
Brian M. Scott
- 616,228