Given a non-empty set A, and define a power set of A as $S=P(A)$.
Proving R={$(A_1,A_2)\in S^2| (A_1\setminus A_2 )\cup (A_2\setminus A_1 ) $ is finite } is a equivalence relation. I know how to prove reflexive and symmetric, need more lights on transitivity. Following is my attempt, and I realised it is wrong.

suppose $(A_i,A_j) \in R$ and $(A_j,A_k) \in R$, $(A_i \cup A_j) \setminus (A_i \cap A_j) $ is finite and $(A_j \cup A_k) \setminus (A_j \cap A_k) $ is finite. Then $(A_i \cup A_j\cup A_j \cup A_k) \setminus (A_i \cap A_j \cap A_j \cap A_k) $is finite. Obviously $(A_i \cup A_k) \leqslant (A_i \cup A_j\cup A_j \cup A_k)$ and $(A_i \cap A_k) \leqslant (A_i \cap A_j \cap A_j \cap A_k)$. Then I conclude the transitivity which is inappropriate. I should not ensure the bigger set minus smaller set $(A_i \cup A_j\cup A_j \cup A_k) \setminus (A_i \cap A_j \cap A_j \cap A_k) $ will be finite as well.

My gut is looking for a specific way involving cardinal and inequality to prove the transitivity. Anyone enlighten me, please.

"Already known the finite set is the union of each finite set and combined with complement approach"

  • $\begingroup$ Why $i,j,k$ instead of $1,2,3$? $\le$ is not the same as $\subseteq$ (\subseteq in LaTeX\MathJax). $\endgroup$ – Henno Brandsma Aug 25 at 9:08
  • 1
    $\begingroup$ The "inclusion" $(A_i \cap A_k) \subseteq (A_i \cap A_j \cap A_j \cap A_k)$ is wrong, it is the other way around. $\endgroup$ – Henno Brandsma Aug 25 at 9:09
  • $\begingroup$ @HennoBrandsma I thought $ i, j ,k $ just notation, same as 1,2,3. isn't it? $\endgroup$ – Lawrence Guo Aug 25 at 9:54
  • $\begingroup$ $i$ suggests that there are infinitely many $A_i$. We're just working with three variables here, whcih you can call $A,B,C$ or $A_1,A_2,A_3$. It's simpler. $\endgroup$ – Henno Brandsma Aug 25 at 9:58

We have a pre-order $\subseteq_\ast$ on $P(S)$ defined by $A \subseteq_\ast B$ iff $A\setminus B$ is finite (almost all elements of $A$ are in $B$).

This is clearly reflexive (as $\emptyset$ is finite) and transitive: $A \subseteq_\ast B \subseteq_\ast C$ implies $$C\setminus A = ((C \setminus A) \cap B) \cup ((C \setminus A) \cap B^\complement) \subseteq (B \setminus A) \cup (C \setminus B)$$

so $C\setminus A$ is also finite and so $A \subseteq_\ast C$. (You won't escape the fact that somewhere in the proof you'll use that the union of two finite sets is finite.).

It follows by standard facts that $A \sim B$ defined by $$A \sim B \iff (A \subseteq_\ast B) \land (B \subseteq_\ast A)$$ is an equivalence relation, as the "symmetrification" of a pre-order. And this is exactly your $R$.

  • $\begingroup$ what if there are no such premise $A\subset B \subset C$ $\endgroup$ – Lawrence Guo Aug 25 at 9:56
  • $\begingroup$ @LawrenceGuo That doesn't matter for the proof of transitivity. $\endgroup$ – Henno Brandsma Aug 25 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.