The question is stated as: Determine if the relation $R$ is an equivalence relation on $A$ and If it is, describe the equivalence classes.
- $A$ is the set of all subsets of the set of integers
- $R = \{(x,y) : x \in A \land y \in A \land (x-y) \cup (y-x)$ is a finite set$\}$
- Hint: $xRy$ if and only if $x$ and $y$ differ by only a finite number of elements
My problem is when trying to show the transitive property of $R$ and to understand the equivalence classes. Let me know if a did it correct and if the equivalence classes well described.
Showing that $R$ is an equivalence relation:
- $R$ is reflexive
For any set we have by definition that the difference to itself is $\emptyset$, thus $(\forall x)(x \in A \Rightarrow (x-x) \cup (x-x) = \emptyset)$, as empty set is a finite set we have that $(\forall x)(x \in A \Rightarrow xRx)$ and therefore $R$ is reflexive.
- $R$ is symmetric
By assumption if $xRy$, we have that $(x-y) \cup (y-x)$ is a finite set, but as union is just a specific case of arbitrary union we have that: $$\bigcup_{A \in\{(x-y), (y-x)\}}A = (x-y) \cup (y-x) = (y-x) \cup (x-y)$$ thus if $(x-y) \cup (y-x)$ is a finite set then $(y-x) \cup (x-y)$ is too because they are the same set, from this we have.
$(\forall x)(\forall y)(xRy \Rightarrow yRx)$ and then R is symmetric.
- $R$ is transitive
- First assume that $xRy \land yRz$ then we should show that $xRz$ holds true
The first observation i did in this part is that $xRy$ is true for any pair of finite sets from A, and the second is that if two sets from $A$ are disjoint then these need to be finite to be in $R$. Both observation come from the Hint on question. from now on we have $(xRy \land yRz \Rightarrow xRz)$ holds true for any finite $x,y,z$ in $A$
Now lets assume $x$ is a set from $A$ with infinite number of elements and as $xRy$ is true by assumption we have that $x-y$ is a finite set, as $x$ and $y$ differ by a finite number of elements they need to have infinite elements in common, then $y$ need to be a set with infinite number of elements to $xRy$ hold true.
But if $y$ have infinite number of elements and we have $yRz$ by assumption, we have that $z$ need to have infinite number of elements too, thus in our assumption of $xRy \land yRz$ we have that if $x$ is a set with infinite number of elements then $y$ and $z$ are too.
From $xRy \land yRz$ we have that $(x-y), (y-x), (y-z), (z-y)$ are all finite sets.
Let $x_f = x-y$ then $x \subseteq x_f \cup y$
Lets define the set $(x_f \cup y) - z$:
$$ p \in (x_f \cup y) - z \Leftrightarrow (p \in x_f \lor p \in y) \land p \notin z$$ $$ p \in (x_f \cup y) - z \Leftrightarrow (p \in x_f \land p \notin z) \lor (p \in y \land p \notin z)$$ $$ p \in (x_f \cup y) - z \Leftrightarrow (p \in (z_f - z) \lor p \in (y-z))$$ $$ p \in (x_f \cup y) - z \Leftrightarrow (p \in (z_f - z) \cup (y-z))$$ $$(x_f \cup y) - z \Leftrightarrow (z_f - z) \cup (y-z)$$ As $z_f$ is a finite set $(z_f - z)$ still finite, and $(y-z)$ is finite by our assumption, thus, we have that $(x_f \cup y) - z$ is a finite set because is equal to a union of two finite sets, and as we have $x \subseteq (x_f \cup y)$ we have also: $$x - z \subseteq (x_f \cup y) - z$$ then as $x-z$ is a finite set because it a subset of a finite set.
If we let $z_f = z-y$ then its possible to follow the same process to conclude that $z-x$ is a finite set too, and if $(x-z)$ and $(z-x)$ are finite sets we have that $(x-z) \cup (z-x)$ is a finite set and therefore we have:
$(\forall x)(\forall y)(\forall z)(xRy \land yRz \Rightarrow xRz)$.
so R is transitive, and it is a equivalence relation.
The equivalence classes consists on:
$[x] = \{z : z \in A \land x-z \cup z-x $ is a finite set$\}$
If the given set $x$ is a finite set then the equivalence class consist in the set of all finite sets in $A$, but if the given $x$ is a set with infinite number of elements the equivalence class consist of all the infinite sets in $A$ that differ by a finite number of elements from the given set.